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

[Бодигрим]

Хм, давайте вы предоставите ваш файл данных и скажете, какого быстродействия вам удалось достичь. Можно попробовать придумать какие-нибудь специфические оптимизации под задачи вашего масштаба. Какие ограничения на объем памяти?

[Батороев]

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

[Garik2]

Батороев в сообщении #233383 писал(а):

Я не знаю каким образом Вам задаются параметры $a$ и $b$ и велики ли они?

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

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

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

[Garik2]

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.

[Бодигрим]

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

И запомните: явные формулы всегда эффективней "крутящихся".

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

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

[mrbus]

Ну, тогда попробуйте целочисленное возведение в степень оптимизировать.
Допустим, нужно возвести $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), при фиксированном числе бит - вообще константная.

[maxal]

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

[mihaild]

(занудство)

mrbus в сообщении #239961 писал(а):

при фиксированном числе бит - вообще константная

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

[iifat]

(Оффтоп)

maxal в сообщении #1143690 писал(а):

В Википедии подробно:

Так понимаю, после семи лет размышления вы пришли к озвученному выводу?