Форум: "Потрепаться";
Текущий архив: 2003.09.15;
Скачать: [xml.tar.bz2];
ВнизАрифметика по модулю. Найти похожие ветки
← →
MBo (2003-08-25 14:15) [0]Любопытная задачка оказалась (в чате вчера спросили):
Найти остаток по модулю С от A в степени B, т.е.
(A^B) mod C
A,B,C:DWord;
← →
Romkin (2003-08-25 14:26) [1]Если не ошибаюсь, остаток произведения по модулю равен произведению остатков по модулю :)
← →
MBo (2003-08-25 14:34) [2]ага, так сложность O(B) получится. А можно и лучше ;)
← →
nikkie (2003-08-25 14:52) [3]> сложность O(B) получится
ну не надо... сложность возведения в степень N - O(log(N))
тем более, что по модулю С достаточно возводить в степень не N, а в степень (N mod \phi(С)), где \phi - функция Эйлера.
можно еще дискретным логарифмом воспользоваться, но оценить его сложность я на вскидку не могу. вроде быстрее не получится (если стоит задача единоразовой операции).
← →
MBo (2003-08-25 15:13) [4]>nikkie ©
Угу, моя промашка - я сначала в степень простым циклом по одному возводил, вот и не воспринял сразу ;)
← →
MBo (2003-08-25 17:11) [5]C функцией Эйлера интересно - не знал про это. Действительно, для c=10 Phi=4, а степени чисел по модулю 10 имеют макс. периодичность именно 4. Правда, вычислять ее накладно, за исключением случаев многократных вычислений для одного С.
← →
MBo (2003-08-26 09:25) [6]Если кому-то интересно:
function APowerBModC(A,B,C:DWord):DWord;
asm
push ebx
push esi
push edi
mov ebx,eax //A
mov esi,ecx //C
mov ecx,edx //B
mov edi,1 //Temp
test ecx,ecx
jz @@Finish
@@LoopStart:
test ecx,1 //Odd
jz @@Reduce
mov eax,edi
call @@LModulus
mov edi,eax // Temp:=(Temp*A) mod C
@@Reduce:
shr ecx,1 // B div 2
jz @@Finish
mov eax,ebx
call @@LModulus
mov ebx,eax // A:=Sqr(A) mod C
jmp @@LoopStart
@@Finish:
mov eax, edi
pop edi
pop esi
pop ebx
ret
@@LModulus:
xor edx,edx
push ecx
push edx
push esi
mul ebx //edx:eax - InputEAX*A
call System.@_llmod
pop ecx
ret
end;
Страницы: 1 вся ветка
Форум: "Потрепаться";
Текущий архив: 2003.09.15;
Скачать: [xml.tar.bz2];
Память: 0.46 MB
Время: 0.011 c