Czy ktos potrafi podac algorytm potegowania modularnego w c/c++??
[email protected]
0
0
Tak
0
johny_brawo to jak potrafisz to podaj!
0
jaki wujek?
0
Wujek, wujek google, wcisnij ten tekst podswietlony jako link (takie cos wykorzystywane czasem na stronach www), to Cie przeniesie do strony wyszukiwania google'a z odpowiedzia na Twoje pytanie... [glowa]
0
Już przy mnożeniu pojawia się problem, gdy korzystamy z 64 bitowych liczb.
Pośrednie obliczenia mają 128 bitów, mam tu ciekawą sztuczkę:
//float64 to zmienny przecinek z 64 bitową mantysą, long double
uint64 mul_mod(uint64 a, uint64 b, uint64 m) {
uint64 y = (uint64)((float64)a*(float64)b/m+(float64)1/2); // floor(a*b/m)
y = y * m; // m*floor(a*b/m) mod z
uint64 x = a * b; // a*b mod z
uint64 r = x - y; // a*b mod z - m*floor(a*b/m) mod z
if ( (int64)r < 0 ) { // normalization needed ?
r = r + m;
y = y - 1; // (a*b)/m quotient, omit line if not needed
}
return r; // (a*b)%m remnant
}