Witam,
Mam problem ze zrozumieniem szybkiego potęgowania modulo. Chcę pominąć szczegół implementacyjny tzn. na chwile obecną nie chcę używać operacji bitowych (z góry dziękuje za wyrozumiałość). Zajmę się tym później, bo chcę najpierw dobrze zrozumieć ideę. Moja liczba jest zapisana w tablicy znakowej i jest odwrócona (tzn. po odwróceniu tablicy otrzymam bity w odpowiedniej kolejności). Wiem, że użycie strlen jest nieotymalne, ale chodzi mi o samą ideę. Jest w sieci mnóstwo kodów, a ja chcę to zrozumieć.
a^k
a - liczba podnoszona do potęgi
k - szereg, czyli liczba naturalna rozbita na sumę potęg liczby 2, po zsumowaniu daje wykladnik w postaci liczby naturalnej
dzięki własnościom potęg mogę to zamienić a podniesione do szeregu na iloczyn liczb, który zwracając da mi liczbę której poszukuje (z własności potęg)
int potega_modulo(int liczba, int modulo, char* wykladnik)
{
int zwracana = 1, wykladnik, wynik_czesciowy;
int ilosc_iteracji = strlen(tablica);
liczba = liczba % modulo;
// tablica jest domyslne odwrocona
for(int j = 0; j <= ilosc_iteracji; ++j) {
if(tablica[j] == '1') {
wykladnik = pow(2, j);
wynik_czesciowy = pow(liczba, wykladnik);
zwracana = (zwracana * wynik_czesciowy) % modulo;
}
}
return zwracana;
}
To zwraca dobre wyniki, ale nie wykonuje tego tak jak trzeba, ponieważ obliczam na piechotę wykładnik oraz przemnażam po kolei wszystkie składniki.
- Jak wyeliminować użycie funkcji pow? Z jej użyciem raczej nie jest to szybkie potęgowanie, tylko przekombinowane potęgowanie zwykłe.