2014 dxdy logo

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

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



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


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

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

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

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

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



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


22/11/06
1096
Одесса, ОНУ ИМЭМ
Хм, давайте вы предоставите ваш файл данных и скажете, какого быстродействия вам удалось достичь. Можно попробовать придумать какие-нибудь специфические оптимизации под задачи вашего масштаба. Какие ограничения на объем памяти?

 Профиль  
                  
 
 Re: линейные диофантовы уравнения и алгоритм Евклида
Сообщение06.08.2009, 18:05 


23/01/07
3072
Новосибирск
Я не знаю каким образом Вам задаются параметры $a$ и $b$ и велики ли они?
В определенных случаях для четных $r$ можно попробовать найти сначала
$z$ такие, что $z^2\equiv \frac{r^2}{4}\pmod {ab} $,
затем определить
$xy=\dfrac{z^2-\frac{r^2}{4}}{ab} $,
а уж затем решить исходное уравнение.

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


03/08/09

235
Батороев в сообщении #233383 писал(а):
Я не знаю каким образом Вам задаются параметры $a$ и $b$ и велики ли они?

Параметр $a$ брали только из массива простых чисел - от 2 до 99991. Значение $b$ - любое натуральное, но большее, чем $a$. Как они были собраны в пары - это не моя задача, да и мне, как программисту, это неинтересно.

Зачем выдумывать новое решение уравнения? Я его решил, решение - единственное при любом заданном $r$. Весь вопрос - в быстроте счета. Мне нужно увеличить скорость счета хотя бы на порядок. Числовые функции Эйлера хранятся в виде одномерного массива, их вычислять не надо. Остается только ускорить процессы возведения в степень и выявления остатков (сравнения по модулю). Но как ускорить в 10 раз - ума не приложу.

Сегодня приобрели супермашину NEC SX-9. Скорость счета возросла в тысячи раз. Теперь все ок. Использование явных выражений в 4,5 раза эффективней (по скорости), чем алгоритм Евклида. Проверено на 18 триллионах значений $x$ и $y$. И запомните: явные формулы всегда эффективней "крутящихся". Всем спасибо!

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


03/08/09

235
Garik2 в сообщении #232879 писал(а):
Эх, это я давно выяснил и именно так делал. Пришлось попотеть и доконать все-таки некомбинаторный подход. Такое удалось найти у математика Г.Александрова (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: линейные диофантовы уравнения и алгоритм Евклида
Сообщение31.08.2009, 23:34 
Заслуженный участник
Аватара пользователя


22/11/06
1096
Одесса, ОНУ ИМЭМ
Garik2 в сообщении #233602 писал(а):
И запомните: явные формулы всегда эффективней "крутящихся".

Интересно, вы осознаете, что возведение в степень - "крутящаяся" операция?

Давайте устроим "соцсоревнование"? Я программирую алгоритм Евклида с некоторыми оптимизациями, вы - свою программу с явными формулами. И прогоняем энное количество итераций на случайных числах.

 Профиль  
                  
 
 Re: линейные диофантовы уравнения и алгоритм Евклида
Сообщение02.09.2009, 23:12 


28/08/09
35
Ну, тогда попробуйте целочисленное возведение в степень оптимизировать.
Допустим, нужно возвести $a^n$.
Разложим n в сумму степеней двойки (проще всего посмотреть номера единичных битов в двоичном представлении n).
Начнём их последовательно находить. (Например, пусть
$n = 13 = 8+4+1 = 2^3 + 2^2 + 2^0$
"наши" биты - 3, 2, 0).
Тогда $result = p_3\cdot p_2\cdot p_0$, где
$p_0 = a\\p_{i+1} = p_i * p_i$
Наш алгоритм сводится к такому
$p_0 = a$ - надо запомнить
$p_1 = p_0\cdot p_0$ - запоминать не надо, не участвует
$p_2 = p_1\cdot p_1$
$p_3 = p_2\cdot p_2$
$result = p_3\cdot p_2\cdot p_0$
Что-то вроде того. ИМХО будет работать быстрее обычного последовательного умножения a*a*a... но реализовать желательно на ассемблере. В итоге возведение в степень n, где n является m-битным числом, получим не более чем за 2*m-2 умножений - сложность O(\log_{2} n), при фиксированном числе бит - вообще константная.

 Профиль  
                  
 
 Re: линейные диофантовы уравнения и алгоритм Евклида
Сообщение12.08.2016, 18:05 
Модератор
Аватара пользователя


11/01/06
5137
mrbus
В Википедии подробно: Алгоритмы быстрого возведения в степень

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


16/07/14
813
Москва

(занудство)

mrbus в сообщении #239961 писал(а):
при фиксированном числе бит - вообще константная

При фиксированном числе бит в основании и показателе степени и прямое перемножение имеет константную сложность. И даже перебор всех чисел, извлечение из них корня, и сравнение - тоже.

 Профиль  
                  
 
 Re: линейные диофантовы уравнения и алгоритм Евклида
Сообщение12.08.2016, 18:27 
Заслуженный участник


16/02/13
2549
Владивосток

(Оффтоп)

maxal в сообщении #1143690 писал(а):
В Википедии подробно:
Так понимаю, после семи лет размышления вы пришли к озвученному выводу?

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

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



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

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


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

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