Saya sedang mencari algoritma untuk menghitung x^y mod z, dimana bilangan x, y, dan z semuanya besar. Saya ambil contoh bilangan yang kecil dulu ya:
123^456 mod 987 = …
Kalau kita hitung langsung, misalnya 123 dipangkatkan 456 dahulu, variabel integer sudah tidak cukup. Ini nampaknya harus diprogram dengan menggunakan big integer. Itu tidak masalah, tapi saya tetap membutuhkan algoritma yang membuatnya lebih efisien.
Sebenarnya saya sedang membaca fast exponentiation, tetapi siapa tahu ada yang punya cara lebih baik. Saya akan membuat kodenya dalam bahasa C, jika itu dibutuhkan.
Ada formula yang bisa membantu, pak. Saya pernah membacanya di salah satu buku.
(A*B*C) mod N == ((A mod N) * (B mod N) * (C mod N)) mod N
Dengan formula di atas kita bisa menyelesaikan x^y mod z dengan divide and conquer seperti berikut
long bigmod(long x, long y, long z) {
if (y == 0)
return 1;
else
if (y % 2 == 0)
return (bigmod(x, y/2, z) * bigmod(x, y/2, z)) % z;
else
return ((x % z) * bigmod(x, y-1, z)) % z;
}
yang dibuku buchmann #46 itu gak bisa dipake ya?
wah mantabbb
siippp
waduh masalah matematika ya…
mohon dukungannya ya di Stop Dreaming Start Action
Yth. Pak Budi,
Tampaknya modular exponentiation yang Bapak butuhkan itu mirip dengan modular exponentiation yang digunakan dalam RSA.
Saya pernah ikut merancang chip RSA. Dan algoritma yang digunakan waktu itu adalah left-to-right binary-method (http://en.wikipedia.org/wiki/Exponentiation_by_squaring) dengan operasi perkalian dilakukan dengan menggunakan Montgomery multiplication (http://en.wikipedia.org/wiki/Montgomery_reduction).
Jika Bapak menginginkan operasi yang lebih efisien, Chinese Remainder Theorem (http://en.wikipedia.org/wiki/Chinese_Remainder_Theorem) bisa digunakan.
Maaf saya tidak menuliskan detailnya di sini.
-albert-
Inspirasi di pagi hari…. Ternyata tdk cukup puas dgn fast exponentiation. Saya ketawa sendiri, Intuisi mengatakan lebih cepat lebih baik… lanjutkan! hahaha…
apa kota wolframalhpa ya ..
barusan nyoba. a=74347,b=2477,a^b=
http://www78.wolframalpha.com/input/?i=a%3D74347%2Cb%3D2477%2Ca^b%3D , klo dikasih angka makin tinggi gak kluar juga hasilnya.. algorithm apa yg mreka pake ya?
ini jawabannya
123^456 mod 987 = …
123^456(mod 987)=267
wah mantabs pak experimentnya, ditunggu jawabannya