2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 линейные диофантовы уравнения и алгоритм Евклида
Сообщение03.08.2009, 20:16 
Заблокирован
Аватара пользователя


03/08/09

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

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

 Профиль  
                  
 
 Re: читая Серпинского ``О решении уравнений в целых числах''...
Сообщение04.08.2009, 00:48 
Заслуженный участник
Аватара пользователя


22/11/06
1096
Одесса, ОНУ ИМЭМ
Garik2 в сообщении #232701 писал(а):
А есть ли у него полное решение линейного диофантова уравнения $ax-by=r$, где $(a>1,b>1) $ - взаимно простые числа ? Найти нужно $x$ и $y$.

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

 Профиль  
                  
 
 Re: читая Серпинского ``О решении уравнений в целых числах''...
Сообщение04.08.2009, 01:56 
Заблокирован
Аватара пользователя


03/08/09

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

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

 Профиль  
                  
 
 Re: читая Серпинского ``О решении уравнений в целых числах''...
Сообщение04.08.2009, 09:57 
Заблокирован
Аватара пользователя


03/08/09

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

 Профиль  
                  
 
 Re: читая Серпинского ``О решении уравнений в целых числах''...
Сообщение04.08.2009, 13:14 
Заслуженный участник
Аватара пользователя


18/12/07
762
Коровьев в сообщении #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 \\$

 Профиль  
                  
 
 Re: читая Серпинского ``О решении уравнений в целых числах''...
Сообщение04.08.2009, 15:41 
Заблокирован
Аватара пользователя


03/08/09

235
Эх, это я давно выяснил и именно так делал. Пришлось попотеть и доконать все-таки некомбинаторный подход. Такое удалось найти у математика Г.Александрова (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.

 Профиль  
                  
 
 Re: читая Серпинского ``О решении уравнений в целых числах''...
Сообщение05.08.2009, 04:29 
Модератор
Аватара пользователя


11/01/06
5660
Garik2 в сообщении #232701 писал(а):
А есть ли у него полное решение линейного диофантова уравнения $ax-by=r$, где $(a>1,b>1) $ - взаимно простые числа ? Найти нужно $x$ и $y$.

Неужели так трудно заглянуть в книжку? Линейным диофантовым уравнениям там посвящен параграф 2.
Garik2 в сообщении #232879 писал(а):
Данную процедуру можно было бы добавить во все пакеты математических программ.

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

 Профиль  
                  
 
 Re: читая Серпинского ``О решении уравнений в целых числах''...
Сообщение05.08.2009, 04:38 
Заблокирован
Аватара пользователя


03/08/09

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

 Профиль  
                  
 
 Re: читая Серпинского ``О решении уравнений в целых числах''...
Сообщение05.08.2009, 04:51 
Модератор
Аватара пользователя


11/01/06
5660
Garik2 в сообщении #232986 писал(а):
Так покажите мне этот более эффективный метод на моем конкретном примере, что я привел выше.

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

 Профиль  
                  
 
 Re: читая Серпинского ``О решении уравнений в целых числах''...
Сообщение05.08.2009, 05:44 
Заблокирован
Аватара пользователя


03/08/09

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

 Профиль  
                  
 
 Re: читая Серпинского ``О решении уравнений в целых числах''...
Сообщение05.08.2009, 16:42 
Заслуженный участник
Аватара пользователя


22/11/06
1096
Одесса, ОНУ ИМЭМ
Garik2 в сообщении #232988 писал(а):
Однако, все это - 19 век, если не эпоха Евклида.

А интегралы - 17-й и 18-й. Если не эпоха Архимеда. И что?
Garik2 в сообщении #232988 писал(а):
Свой пример решил по-своему и лучшего способа, к сожалению, нигде не нахожу.

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

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

 Профиль  
                  
 
 Re: читая Серпинского ``О решении уравнений в целых числах''...
Сообщение05.08.2009, 18:45 
Заблокирован
Аватара пользователя


03/08/09

235
Цитата:

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

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

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

 Профиль  
                  
 
 Re: читая Серпинского ``О решении уравнений в целых числах''...
Сообщение05.08.2009, 20:16 
Модератор
Аватара пользователя


11/01/06
5660
Garik2 в сообщении #233157 писал(а):
Как Вы понимаете, алгоритм Евклида ни в какие ворота не лезет, ибо заказчик сутками результата ждать не будет.

Алгоритм Евклида - это очень эффективный алгоритм, значение которого трудно переоценить. Он является фундаментальным кирпичиком многих более сложных теоретико-числовых алгоритмов (например, факторизации чисел).
Если для всего мира он работает, а для вас нет - вероятно, вы его неправильно "готовите".
Garik2 в сообщении #233157 писал(а):
P.S. Ваши рассуждения очень развеселили моего начальника. "Это все равно, что решать квадратное уравнение методом итераций Ньютона", - вот его резюме.

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

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

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

 Профиль  
                  
 
 Re: линейные диофантовы уравнения и алгоритм Евклида
Сообщение05.08.2009, 21:34 
Заслуженный участник
Аватара пользователя


22/11/06
1096
Одесса, ОНУ ИМЭМ
Garik2 в сообщении #233157 писал(а):
P.S. Ваши рассуждения очень развеселили моего начальника. "Это все равно, что решать квадратное уравнение методом итераций Ньютона", - вот его резюме.

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

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

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

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

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

 Профиль  
                  
 
 Re: линейные диофантовы уравнения и алгоритм Евклида
Сообщение05.08.2009, 22:23 
Заблокирован
Аватара пользователя


03/08/09

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 24 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group