2014 dxdy logo

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

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




 
 возведение в степень больших чисел
Сообщение05.01.2009, 14:47 
Надо вычислить 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)

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

 
 
 
 
Сообщение05.01.2009, 15:03 
Аватара пользователя
см. http://algolist.manual.ru/maths/count_fast/fast_exp.php

 
 
 
 
Сообщение05.01.2009, 15:08 
maxal
Спасибо, но это Си, а надо Паскаль и быстро.

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

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

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

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

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

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

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

 
 
 
 
Сообщение06.01.2009, 13:44 
Андрей А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;
Спасибо за прочтение.

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

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

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

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

 
 
 
 
Сообщение13.01.2009, 18:05 
Усталый писал(а):
Нет. 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 - то тот пример подойдёт.

 
 
 
 
Сообщение14.01.2009, 01:43 
Упс, я оказывается «не в теме». Я просто про возведение в степень (т.е. без mod). А то сижу и удивляюсь:
Цитата:
Но раз надо всего лишь 32000 ^ 32000 - то тот пример подойдёт.
:D

 
 
 [ Сообщений: 12 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group