линейные диофантовы уравнения и алгоритм Евклида

[Garik2]

// Отделено от темы: читая Серпинского ``О решении уравнений в целых числах''...

Таким образом, задача упрощается: нужно полностью перевести с английского книгу Серпинского и добавить последние достижения в области теории чисел.
А есть ли у него полное решение линейного диофантова уравнения $ax-by=r$, где $(a>1,b>1) $ - взаимно простые числа ? Найти нужно $x$ и $y$.

[Бодигрим]

Garik2 в сообщении #232701 писал(а):

А есть ли у него полное решение линейного диофантова уравнения $ax-by=r$, где $(a>1,b>1) $ - взаимно простые числа ? Найти нужно $x$ и $y$.

Обобщенный алгоритм Евклида?

[Garik2]

Очень красиво решено! Не понял только, откуда взялась $t$ и чему она равна?

И еще. Покажите, пожалуйста, как найти решение для конкретного числового уравнения:
$13x-36y=2$
по возможности подробно, иначе я не пойму метод.

[Garik2]

Я жду помощи. Мне нужно срочно писать процедуру-функцию в проге. Пока что я комбинаторно нахожу неизвестные $x$ и $y$, но это, на мой взгляд, грязная работа.

[Коровьев]

Коровьев в сообщении #232744 писал(а):

пусть $ (a,b) = 1$
и $ ay + bx = A $
Все решения этого уравнения есть
$ x = Ab^{\varphi (a) - 1} + at $
$ y = A\frac{{ - b^{\varphi (a)} + 1}}{a} - bt $

Однако это формула для получения всех решений слишком неэффективна в реальных задачах и годится лишь, разве что, в доказательствах чего-либо.
Гораздо эффективнее найти одно из решений этого уравнения
$ ax_0 + by_0 =A$
тогда все решения будут иметь вид
$ x = x_0 - bt $
$ y = y_0 + at $
где $t$ - любое целое число.
*****
$13x-36y=2$

$ x = \frac{{36y + 2}}{{13}}$ - д.б. целым числом.
Подставляя
$ y = \pm 1, \pm 2,... \pm \frac{{13 - 1}}{2} = \pm 6$
мы обязательно его получим, и только одно. /Это из теории чисел/

$y_0 = 5,x_0 = 14 \\ x = 14 + 36t \\ y = 5 + 13t \\$

[Garik2]

Эх, это я давно выяснил и именно так делал. Пришлось попотеть и доконать все-таки некомбинаторный подход. Такое удалось найти у математика Г.Александрова (1972 г)...
Вот в явном виде результаты:

Решить диофантово уравнение: $ax-by=r$

$x=b-\frac{b}{a} \, \cdot \, [r[b(mod \,a) ]^{\varphi(a)-1} ](mod \,a )+ \frac {r}{a}$

$y=a- [r[b(mod \,a) ]^{\varphi(a)-1}](mod \,a )$

Все вычисляется однозначно.

Данную процедуру можно было бы добавить во все пакеты математических программ.

Подскажите, как вставить изображение в формате gif ? Я бы здесь привел пример решения в ППП. В других форумах есть опция Обзор и Добавить файл. Здесь же какое-то Img.

[maxal]

Garik2 в сообщении #232701 писал(а):

А есть ли у него полное решение линейного диофантова уравнения $ax-by=r$, где $(a>1,b>1) $ - взаимно простые числа ? Найти нужно $x$ и $y$.

Неужели так трудно заглянуть в книжку? Линейным диофантовым уравнениям там посвящен параграф 2.

Garik2 в сообщении #232879 писал(а):

Данную процедуру можно было бы добавить во все пакеты математических программ.

Через расширенный алгоритм Евклида эта задача решается гораздо эффективнее.

[Garik2]

Так покажите мне этот более эффективный метод на моем конкретном примере, что я привел выше. Способ, что изложил Коровьев, в 5 раз медленней работает в проге, чем явные формулы. Мне важна скорость счета, так как будут решаться миллионы диофантовых уравнений.

[maxal]

Garik2 в сообщении #232986 писал(а):

Так покажите мне этот более эффективный метод на моем конкретном примере, что я привел выше.

Это вы уж сами свои примеры решайте. У Серпинского все разжевано.

[Garik2]

Прочитал я хваленого Серпинского... В Википедии даже лучше и полнее освещен интересующий меня вопрос. Однако, все это - 19 век, если не эпоха Евклида.
Свой пример решил по-своему и лучшего способа, к сожалению, нигде не нахожу.

[Бодигрим]

Garik2 в сообщении #232988 писал(а):

Однако, все это - 19 век, если не эпоха Евклида.

А интегралы - 17-й и 18-й. Если не эпоха Архимеда. И что?

Garik2 в сообщении #232988 писал(а):

Свой пример решил по-своему и лучшего способа, к сожалению, нигде не нахожу.

Решение вашего уравнения через алгоритм Евклида, как это предлагали выше я и maxal, выполняется за $O(\log(\min(a,b)))$ элементарных операций (умножения/сложения) и не требует реализации каких-либо специальных арифметических подпрограмм.

Предложенные вами формулы хотя и представляют решение в "замкнутой", "явной" форме, но вычисляются дольше итеративного процесса алгоритма Евклида. Наиболее сложный элемент здесь - вычисление функции Эйлера, для которой неизвестен (поправьте меня, если я ошибаюсь) алгоритм сложности $O(\log a)$.

[Garik2]

Цитата:

Предложенные вами формулы хотя и представляют решение в "замкнутой", "явной" форме, но вычисляются дольше итеративного процесса алгоритма Евклида.

Уважаемый коллега. Поправляю Вас. В моей проге значения числовой функции Эйлера вычислены заранее в требуемых для задачи пределах (до $a=100000$). Поэтому явная форма проходит молниеносно. Делал поверочные расчеты и соотношение скоростей (по сравнению с итеративным) приблизительно 1:5 в мою пользу. Надеялся найти еще более быстрый алгоритм, чтобы тестовая задача шла не 47 минут, как сейчас, а хотя бы на порядок быстрее. Как Вы понимаете, алгоритм Евклида ни в какие ворота не лезет, ибо заказчик сутками результата ждать не будет.

P.S. Ваши рассуждения очень развеселили моего начальника. "Это все равно, что решать квадратное уравнение методом итераций Ньютона", - вот его резюме.

[maxal]

Garik2 в сообщении #233157 писал(а):

Как Вы понимаете, алгоритм Евклида ни в какие ворота не лезет, ибо заказчик сутками результата ждать не будет.

Алгоритм Евклида - это очень эффективный алгоритм, значение которого трудно переоценить. Он является фундаментальным кирпичиком многих более сложных теоретико-числовых алгоритмов (например, факторизации чисел).
Если для всего мира он работает, а для вас нет - вероятно, вы его неправильно "готовите".

Garik2 в сообщении #233157 писал(а):

P.S. Ваши рассуждения очень развеселили моего начальника. "Это все равно, что решать квадратное уравнение методом итераций Ньютона", - вот его резюме.

Неуместное сравнение, и сарказм тоже.

-- Wed Aug 05, 2009 12:35:30 --

Garik2
Сравните свою реализацию с приведёнными здесь: http://algolist.manual.ru/maths/teornum/nod.php

[Бодигрим]

Garik2 в сообщении #233157 писал(а):

P.S. Ваши рассуждения очень развеселили моего начальника. "Это все равно, что решать квадратное уравнение методом итераций Ньютона", - вот его резюме.

Я счастлив, что вашего начальника радуют рассуждения о теоретической сложности алгоритмов. [Сарказм за сарказм:] Только не могу сообразить: это симптом или диагноз? Ибо такие сравнения говорят о том, что он очень и очень не в теме.

Теперь по сути вопроса:

1. Даже протабулировав значения $\varphi(n)$, вы за счет трудоемкости операции возведения в степень получаете те же $O(\log(a))$. Это не лучше алгоритма Евклида по порядку и по идее должно работать медленнее за счет больших накладных расходов. Возможно вы просто очень неэффективно организовываете алгоритм Евклида или эта неэффективность обусловлена спецификой языка программирования (кстати, на чем вы пишете?).

2. Более того, если вам не дано по условию, что уравнение при данных значениях коэффициентов обязательно имеет решение, то вам нужно до расчетов по вашим формулам проверить условие $\text{НОД}(a,b)\mid r$, разве не так? Вы проверяете его, не используя алгоритм Евклида?

3. Хе, а какой производительности можно достичь в алгоритме Евклида, используя некоторое количество табулированных значений!..

[Garik2]

Мне сейчас не до сарказмов и пустых обсуждений. У меня факты: малое быстродействие и того, и другого. На кону большие деньги и престиж фирмы. Я хочу только выяснить - есть ли еще более эффективные методы, чем мы рассмотрели? Если нет, то нам придется покупать суперкомп с быстродействием на порядки большим, чем у имеющихся в наличии.
Что касается алгоритма Евклида, то я им пользуюсь не один десяток лет и здесь уже ничего не выжмешь.
Пишу я на С++.
Что касается взаимной простоты параметров $a$ и $b$ , то они даны уже изначально, в виде файла данных. Поэтому проверки не требуется (поскольку константа $a$ выбирается из массива простых чисел). Переменным параметром задачи является только $r$.