Скачать: CL | DM;

Арифметика по модулю.   Найти похожие ветки 

← →
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 вся ветка

Скачать: CL | DM;



Память: 0.46 MB
Время: 0.013 c