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

Во-первых, глупейший вопрос: если я для хранения больших чисел использую, к примеру,


то наименьшему или наибольшему элементу массива логичнее хранить младшую часть числа?

Обычно младшая часть в начальных ячейках, а старшая - в ячейках с бОльшим адресом.
Был бы ты сишник, а не паскалист - "послал" бы тебя по разным источникам. Например, http://algolist.manual.ru/maths/longnum.php

a^b mod c = ?



для "Монтгомери" нужно сначала произвести деление...

Можно поконкретнее описать, что нужно? И большая ли степень b? TDigit - целое число? Модуль c имеет какие-то особенности, например c=2^N или c=2^N+1?

Добавлено ([mergetime]1271183161[/mergetime]):
С Монтгомери плохо знаком.

Так вот я описал что нужно найти. Куда это вставляется сам точно не знаю. TDigit объявлен в первом посте, все три числа произвольные.

Всё равно не очень понятно.

Вариант: тупо умножать x="a" на "a" b-1 раз, а потом вычислить остаток от деления на "c".

В том-то и дело, что это не вариант степень - число до 2048 бит, аргумент - тоже. Даже если бы они были по 32 бит, никакой памяти бы не хватило на хранение результата возведения в степень, да и сколько времени это бы длилось...

А вот статьи, в которых не понял смысла некоторых выражений и обозначений (похоже на опечатки, но кто знает):

Деление: http://naukoved.ru/content/view/1300/45/

Монтгомери: http://dic.academic.ru/dic.nsf/ruwiki/1277680
http://naukoved.ru/content/view/1301/45/

Есть вариант для такого случая: после каждого умножения находить остаток от деления на "c" и потом умножать уже на него.

не, количество итераций умножения / деления все равно будет слишком большим.

Есть алгоритмы, оптимизирующие количество умножений при возведении в степень.
Например: x^16 - 15 умножений?
A = x*x = x^2; B = A*A = x^4; C = B*B = x^8; D = C*C = x^16. То есть 4 умножения. Для x^31 придётся выполнить, кажется, 7 умножений. В среднем 2*log₂b умножений.
После каждого умножения находим остаток и потом используем его.

насколько я понял, это алгоритм компьютерного деления.

еще вариант:
( a * b ) mod c = ( ( a mod c ) * ( b mod c ) ) mod c
в твоем варианте:
( a ^ b ) mod c = ( ( a mod c ) ^ b ) mod c

Пришлось использовать для хранения чисел string, причем в читабельной десятичной форме. Сел сегодня, что-то сваял, для размера основания, степени и делителя по ~2048 бит программа работала 85 секунд. Если ~512 бит, то 1.5 секунд. Монтгомери ниасилил, поэтому сделал по-тупому.
Всем еще раз спасибо за помощь.

возведение в целую степень. быстрый алгоритм.


Или вот, в общем случае:

а что такое х?

исправил.

x^a=П_i=0^∞(x^-ki)^a_i где
aєR
a_i=[a'_i]
a'₀=a
a'_i={a'_i-1}*k

Добавлено ([mergetime]1272979500[/mergetime]):
П_i=0^∞ - имеется ввиду произведение от 0 до бесконечности

не умничай ))

дык это способ.

Добавлено ([mergetime]1272987048[/mergetime]):
можно еще в ряд Тейлора раскладывать в окрестности 1

Как реализовать расширенный алгоритм Евклида
( http://www.cyberguru.ru/cpp-sources/algori...tm-evklida.html )

да так, чтобы Y получился гарантированно отрицательный, а X - положительный.

(точнее, оба они получились положительные в формуле ax - by = НОД)

а никак. поменять a и b местами. и алгоритмы там кривые.
GCD(a,b==0)?a:GCD(b,a mod .
bx+(a mod y=ay+b(x-[a/b]y)

Добавлено ([mergetime]1273488582[/mergetime]):
код на с++

В этом коде выходит что x не меняется...

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

меняется. это была проверка на внимательность и ты ее не прошел.

Добавлено ([mergetime]1273493270[/mergetime]):
а почему они не могут быть отрицательными?

Потому что можно это реализовать без геморной реализации отрицательных чисел

этот алгоритм - нельзя

Добавлено ([mergetime]1273495326[/mergetime]):
и она не геморная. давай исходники, я ее приделаю

и будет ли целесообразным такой результат?

ведь у уравнения 1 = xr - yn есть больше одного решения, почему-то в примере для одних и тех же чисел там указаны другие числа, которые подходят, но тем не менее, по знаку положительные. Только там не был дан алгоритм, только отсылка на расш.Евклида.

r = 1024 n = 789
x = 742 y = 963

по обычному алгоритму другие числа получаются (-47, -61)

оба верны

Добавлено ([mergetime]1273509342[/mergetime]):
789-742=47
1024-963=61
думаю, происхождение чисел очевидно.

Точно... надеюсь, это верно во всех случаях.

во всех, можешь не сомневаться