Pemangkatan metode divide and conquer

Oleh : Alham Fikri Aji

diberikan A dan B, bilangan integer, berapa hasil dari A pangkat B modulus 10000??Apakah algoritma yang tepat untuk menyelesaikan permasalahan tersebut?

cara naifnya adalah mengalikan A sebanyak B, yang kompleksitasnya O(B). dengan metode divide and conquer, kompleksitasnya ialah O( log B). jauh lebih cepat. sebagai perbandingan, cara divide & conquer bisa menghitung 2 pangkat 1 triliyun kurang dari 100

proses.

ide algoritma ini kira2 seperti ini:

A pangkat B = A jika B = 1
A pangkat B = A*A pangkat B/2 jika B genap
A pangkat B = A * (A pangkat B-1) jika B ganjil

untuk lebih jelasnya kita hitung 2 pangkat 10
2 pangkat 10
= 4 pangkat 5
= 4* (4 pangkat 4)
= 4* (16 pangkat 2)
= 4* (256 pangkat 1)
= 4* 256
= 1024
(selesai kurang dari 10 proses, dimana cara naif butuh 10 kali proses untuk menghitungnya)

fungsi di C++, untuk menghitung a pangkat b

int pangkat(int a,int b){
int res=1;
     while (b != 0){
		  if (b%2 == 1){
		  	 	   b--;
		  	 	   res=(res*a)%10000;
		 		}
		  else {
		  	   b/=2;
		  	   a=(a*a)%10000;
			}
		  }
	return res;
}

Selamat Mencoba

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s