Как найти значение выражения

← →
Werewolf (2003-12-12 10:38) [0]

Нужно найти остаток от деления числа X в степени Y на Z

← →
Sandman25 (2003-12-12 10:43) [1]

power(x, y) mod z

← →
Werewolfru (2003-12-12 10:53) [2]

Ежу понятно, но у меня 474^343 mod 527

← →
Romkin (2003-12-12 10:59) [3]

Угу, а как насчет переполнения?
Ответ простой: перемножить модули и взять модуль результата.
Еще лучше - умножать постоянно на х и брать модуль, потом снова умножать... Пока не получится нужная степень.
Еще лучше минимизировать количество умножений %)
Стоит только покопаться, и находишь занятный алгоритм (мнемоника)
a^b mod n : ПУсть (b[k],b[k-1]..b[0]) - биты числа b, тогда
c := 0 d := 1 for i := k downto 0 do begin c := 2*c d := (d*d) mod n if b[i] = 1 then begin c := c + 1 d := (d * a) mod n end end Result := d
А вот как работать с битами и тд - к Зотову :)

← →
werewolfru (2003-12-12 11:08) [4]

Щас попробую разобраться...

← →
Romkin (2003-12-12 11:19) [5]

Здесь просто последовательное возведение в степень и взятие модуля от промежуточного результата. Только водведение идет оптимальным способом, например, в степень 5 быстрее всего возвести, взяв дважды квадрат и домножив результат на основание степени, в девятую - в третью (квадрат и умножить) и результат в третью :)

← →
Werewolfru (2003-12-12 11:22) [6]

А разве оно не вылазит за пределы обычного Integer?

← →
Romkin (2003-12-12 11:31) [7]

Дык модули перемножаются здесь :)
Кстати, запутался я. Возведение в степень 11: 10 = 1011b, идем слева направо по битам, 1 - третья степень, 0 - квадрат. Следовательно, квадрат * основание (3 степень), снова квадрат (5), квадрат * основание (8) , квадрат * основание (11). 7 умножений, ессно, умножаются модули, и от результата тоже модуль берется.
А вот проход по степени справа налево (так удобнее) см. Кнут т.2 4.6.3

← →
Werewolfru (2003-12-12 11:33) [8]

Дык это оттудова? тогда завтра его посмотрю. Спасибо!

← →
Romkin (2003-12-12 11:40) [9]

Не совсем :) Там просто возведение в степень, но если добавить воды: (uv) mod m == (u mod m)(v mod m) mod m, то все получается (если не ошибаюсь)

← →
Werewolfru (2003-12-12 11:57) [10]

По твоему алгоритму a^b mod n всегда равно a. В чем-то глюк...

Как найти значение выражения Найти похожие ветки