Форум: "Основная";
Текущий архив: 2003.12.26;
Скачать: [xml.tar.bz2];
Вниз
Как найти значение выражения Найти похожие ветки
← →
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. В чем-то глюк...
Страницы: 1 вся ветка
Форум: "Основная";
Текущий архив: 2003.12.26;
Скачать: [xml.tar.bz2];
Память: 0.46 MB
Время: 0.109 c
