Деление с остатком Опции

[FBX]

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

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

Код

type
 TDigit = array[0..63] of dword;

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

[Etoprostoya]

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

[FBX]

var a,b,c: TDigit;

a^b mod c = ?



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

[Etoprostoya]

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

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

[FBX]

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

[Etoprostoya]

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

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

[FBX]

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

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

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

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

[Etoprostoya]

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

[FBX]

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

[Etoprostoya]

Есть алгоритмы, оптимизирующие количество умножений при возведении в степень.
Например: 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 умножений.
После каждого умножения находим остаток и потом используем его.

[gamecreator]

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

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

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

[FBX]

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

[hippocamus]

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

Код

function Power (A, B: Int64): Int64; {или LongInt?}
begin
  Result := 1;
  while (B > 0) do
     begin
         if (B and 1 = 1) then Result := Result * A;
         A := A + A;
         B := B shr 1;
     end;
end;

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

Код

function Power (A, B: Double): Double;
begin
 if (A < 0) then Result := -1 * Exp(B * Ln(Abs(A)))
 else if (A > 0) then Result := Exp(B * Ln(Abs(A)))
 else Result := 0;
 if (Round(B) mod 2 = 0) then Result :=Abs(Result);
 if (B = 0) then Result := 1;
end;

[gamecreator]

а что такое х?

[hippocamus]

исправил.

[gamecreator]

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 до бесконечности

[Дьяк]

не умничай ))

[gamecreator]

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

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

[FBX]

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

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

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

[gamecreator]

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

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

Код

int gcd(int a,int b,int &x,int &y)
{
   if(!b)
   {
       x=1;
       y=0;
       return a;
   }
   int res;
   res=gcd(b,a%b,y,x);
   y-=(a/b)*x;
   return res;
}