Pripreme za algoritme(7)

Potenciranje cijelog broja 

Danas ćemo proći potenciranje cijelih brojeva. Odlučio sam se sada kod prikazati u Pascalu, ali ako ima problema oko prevođenja u drugi programski jezik slobodno se javite.

Najjednostavniji algoritam je:

U:=1;

For I:=1 To P Do Begin

                          U:=U*Broj;

                     End;

U je konačni umnonžak, broj je broj koji potenciramo, P je eksponent. U slučaju ovog algoritma broj operacija množenja jednak je potenciji.

Algoritam koji umanjuje broj operacija množenja je:

U:=1;

While P>0 Do Begin

                          If Odd(P) Then U:=U*Broj;

                          Broj:=Broj*Broj;

                          P:=P div 2;

                        End;

U ovom slučaju najveći broj množenja imamo ako se radi o neparnoj potenciji (npr. 15) i to dva puta manje od broja potencije. Broj polaza kroz petlju jednak je broju znamenaka u binarnom prikazu potencije (za 15 to je 4 znamenke=4 prolaza = 8 operacija množenja umjesto 15). Za potpuno razumjevanje algoritma dobro je napraviti tablicu vrijednosti varijabla u svakom prolazu kroz petlju. Ovdje je pokazano za 2¹⁵.

Prolaz kroz petlju	u	broj	p
Prije petlje	1	2	15
1. prolaz	2	4	7
2. prolaz	8	16	3
3. prolaz	128	256	1
4. prolaz	128*256	256*256	0

Usporedni rezultati za 1^20000000 izvedeni u oba algoritma (testirano na Borland Pascalu).

Pokazano je na broju 1 radi konačnog rezultata. U prvom slučaju izvodi se 20 milijuna operacija i to traje više oko 7 sekundi (670 stotinki), mjereno na Pentiumu 4 na 2 Ghz. U drugom slučaju izvodi se najviše 64*2 operacije što osjećamo kao trenutne (0 stotinki).

program potencija;

uses crt;

var  broj,i,u:longword;

begin

        clrscr;

        readln(broj);

        u:=1;

        for i:=1 to 20000000 do begin

                                u:=u*broj;

                               end;

        writeln(u);

        readln

end.

program potencija;

uses crt;

var  broj,p,u:longword;

begin

        readln(broj);

        u:=1;

        p:=20000000;

        while p>0 do begin

                       if odd(p) then u:=u*broj;

                       broj:=broj*broj;

                       p:=p div 2;

                     end;

        writeln(u);

        readln

end.

Ubrzanje izvođenja programa je evidentno. Naravno kada se radi o malim potencijama možemo koristiti jednostavniji algoritam.

Algoritam koji koristi logaritmiranje

xy =exp(y*ln(x)) readln(x,y); z:=exp(y*ln(x));

z=x^y

ln(z)=ln(x^y )

ln(z)=y*ln(x)

e ^ln(z)=e ^y*ln(x)

x^y = e ^y*ln(x)