возведение в степень больших чисел

[Melania]

Надо вычислить a^d (mod m):
1. Число d представить в двоичной системе счисления: d = d0 * 2r + ... + dr - 1 * 2 + dr, где di - цифры в двоичном представлении, равные 0 или 1, d0 = 1
2. Положить a0 = a, затем для i = 1, ... , r вычислить ai = (ai - 1)^ 2 * a^di (mod m)
3. ar есть искомое число a^d (mod m)

Как это реализовать на Паскале?

[maxal]

см. http://algolist.manual.ru/maths/count_fast/fast_exp.php

[Melania]

maxal
Спасибо, но это Си, а надо Паскаль и быстро.

[maxal]

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

[Melania]

maxal
Си то я не знаю. Совсем не знаю. Мне правда очень надо и не лень переводить. Так случилось что надо быстро.

[Андрей АK]

В том примере вовсе не возведение больших чисел в степень (long-это совсем не большие числа).
То пример возведения маленьких чисел в большие степени (со взятием по модулю).
И там алгоритм всего-лишь минимизирует количество возведений в степень, за счёт двоичной оптимизации (При этом тупо переводит число в массив, называя это двоичным представлением, тогда как любое число и так всегда находится в двоичном представлении).

А возведение "больших" чисел в степени облегчается тем свойством, что не надо возводить в степень само число, а достаточно возвести в степень его остаток от деления (по модулю), взять результат снова по модулю и получим ответ.

А вот если и сам остаток от деления тоже большое число ... то тут уж ничего не поделаешь - надо его просто возвести в степень.

Но думаю ваша задача всё-же возведение небольших чисел в большие степени - так паскаль от си не сильно отличается - все языки близнецы-братья.

Заменить фигурные скобки на бегины-энды немного косметики и готово.

[Melania]

Андрей АK
Спасибо. За ночь научилась кое что узнавать в Си. Порядок моих чисел для возведения 32000^32000. А как быть с типом? Подскажите, пожалуйста. Можно на Си. Я понимаю, что серьезные люди на Паскале не пишут. Хоть идею.

Добавлено спустя 41 минуту 53 секунды:

maxal
Надо 32000^32000 (x^n).
Такая функция подойдет?
function step(x,n:longint):longint;
var otv:longint;
begin
otv:=1;
while n>0 do
begin
if n mod 2 =1 then otv:=otv*x;
x:=x*x;
n:= n div 2
end;
step:=otv
end;
Спасибо за прочтение.

[worm2]

Похоже на правду.
Только:
1) Вместо x := x*x нужно otv := otv*otv;
2) Вам ведь нужно по модулю m? Тогда сразу после умножения нужно добавлять mod m:

...otv := (otv * x) mod m;
...
otv := (otv * otv) mod m;

[Усталый]

Нет. longint в Pascal, по-моему, зависит от разрядности процессора. В любом случае, $ 32000 ^ {32000} $ -- это больно круто. Это примерно $ 2 ^ {\log_{2}{32000} \cdot 32000} = 2 ^ {478905} $
Так что всё, что больше 32-й (64-й) степени двойки -- «большое число».

[Melania]

worm2
Усталый
Спасибо за помощь. Учту. К сожалению больше нет времени искать ответ. Может хоть часть тестов пройдет.

Большое спасибо всем, кто откликнулся.

[Андрей АK]

Усталый писал(а):

Нет. longint в Pascal, по-моему, зависит от разрядности процессора. В любом случае, $ 32000 ^ {32000} $ -- это больно круто. Это примерно $ 2 ^ {\log_{2}{32000} \cdot 32000} = 2 ^ {478905} $
Так что всё, что больше 32-й (64-й) степени двойки -- «большое число».

Да нет, это как раз возведение небольшого числа в большую степень.
Двоичная оптимизация позволяет не умножать 32000 раз а обойтись всего log2(32000)=15-ю умножениями.

А свойство модуля (x^y mod m = (x mod m)^y) позволяет не искать само число, а только результат.

А большое число - это массив из нескольких long чисел - такие числа за одну операцию не перемножишь и надо писать специальные функции сложения/умножения таких больших чисел.

Эти большие числа используются в RSA шифровании - там используют простые числа длиной ... 1024 бита это 128 байт - т.е. массив из 32 long чисел!
В десятичном виде это будет строка из 200 цифр!

Но раз надо всего лишь 32000 ^ 32000 - то тот пример подойдёт.

[Усталый]

Упс, я оказывается «не в теме». Я просто про возведение в степень (т.е. без mod). А то сижу и удивляюсь:

Цитата:

Но раз надо всего лишь 32000 ^ 32000 - то тот пример подойдёт.