Potegowanie szybkie modulo

2011-10-08 21:16
Student
0

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.

  1. Jak wyeliminować użycie funkcji pow? Z jej użyciem raczej nie jest to szybkie potęgowanie, tylko przekombinowane potęgowanie zwykłe.

Pozostało 580 znaków

2011-10-08 21:49
0

W potęgowaniu binarnym chodzi o to, żeby zmniejszyć liczbę działań arytmetycznych potrzebnych do otrzymania wyniku. Robisz to, podnosząc do potęgi drugiej wyniki poprzedniego potęgowania do drugiej. Jeżeli masz obliczyć a^8, to zamiast wykonywać aaaaaaaa, wykonujesz ((a^2)^2)^2. Przy wykładnikach niebędących potęgami 2, musisz znaleźć sposób na potęgowanie liczb nieparzystych, ponieważ liczba ta w swoim rozkładzie będzie zawierać co najmniej 1 liczbę nieparzystą. Sposób jest prosty:
tworzysz 2 zmienne p (wykładnik parzysty) i n (nieparzysty). Jeżeli podstawa to a, a wykładnik w:
=> do p wpisujesz a, do n 1;
while (w==1)
{
jeżeli w parzyste => podnosisz p do kwadratu, zapisujesz w p i dzielisz wykładnik przez 2;
jeżeli wykładnik nieparzysty => mnożysz n
a, zapisujesz w n i odejmujesz 1 od w;
}
=> mnożysz p*n
=> masz wynik

przeanalizuj sobie te kroki dla np. 23, 1010.

Kod RAM, wykonujący szybkie potęgowanie i wypisujący 4 ostatnie cyfry (skracanie w trakcie wykonywania):

          read  1
          load  1
          div   =10000
          mult  =10000
          sub   1
          mult  =-1
          store 1
          load  =1
          store 2
          read  3
          load  3
petla:  jzero licz
          div   =2
          mult  =2
          sub   3
          jzero parzyste
          load  2
          mult  1
          store 2
          div   =10000
          mult  =10000
          sub   2
          mult  =-1
          store 2
parzyste: load  1
          mult  1
          store 1
          div   =10000
          mult  =10000
          sub   1
          mult  =-1
          store 1
          load  3
          div   =2
          store 3
          jump  petla
licz:     load  2
          div   =10000
          mult  =10000
          sub   2
          mult  =-1
          store 2
          write 2

edytowany 1x, ostatnio: merlinnot, 2011-10-08 21:52

Pozostało 580 znaków

2011-10-08 23:02
Student
0

Nauczyłem się to liczyć na papierze. Sprawa jest prosta. Dzięki.

Pozostało 580 znaków

Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0