TANPA MENGGUNAKAN FUNGSI pow(), buatlah fungsi dan program Python yang

Berikut ini adalah pertanyaan dari qed pada mata pelajaran TI untuk jenjang Sekolah Dasar

TANPA MENGGUNAKAN FUNGSI pow(), buatlah fungsi dan program Python yang dapat melakukan perhitungan a^b mod c, dengan nilai a^b yang besar.Contoh output yang diharapkan:
Bilangan basis = 9999 (input)
Eksponen = 9999 (input)
Modulus = 10 (input)
9999^9999 mod 10 = 9

Jangan lupa, ujilah fungsi yang sudah Anda buat dengan beberapa masukan lain.

Jawaban dan Penjelasan

Berikut ini adalah pilihan jawaban terbaik dari pertanyaan diatas.

Kode Program Python

INVALID_ENTRY = -9999

def powermod(basis, eksponen, modulus):
if basis < 1 or eksponen < 0 or modulus < 1:
return INVALID_ENTRY
if eksponen == 1:
return basis % modulus
hasil = powermod(basis, eksponen // 2, modulus)
hasil = hasil*hasil % modulus
if eksponen & 1 == 1:
hasil = hasil * basis % modulus
return hasil

# Program Utama
if __name__ == '__main__':
while True:
basis = int(input("Bilangan basis = "))
eksponen = int(input("Eksponsn = "))
modulus = int(input("Modulus = "))
print("========================")
print("⇒ {b:d}^{e:d} mod {m:d} = {h:d}\n"
.format(b = basis, e = eksponen, m = modulus,
h = powermod(basis, eksponen, modulus)))
cobalagi = input("Mau coba lagi? (y/t) ")
if cobalagi in "Yy":
# coba lagi
print()
continue
else:
if cobalagi in "Tt":
# selesai
print("OK deh. Selesai ya.\n")
else:
print("Ngawur kamu! Nggak jelas deh!\n")
break
### END OF PROGRAM ###
________________

Pembahasan

Sebenarnya Python sudah menyediakan fungsi $\texttt{pow(x, y[, z])}$ . Tanpa parameter z, $\texttt{pow(x, y)}$ mengembalikan nilai x^y. Dengan parameter z, $\texttt{pow(x, y, z)}$ mengembalikan nilai x^y mod z. Pembuat soal jelas tahu tentang hal ini, oleh karena itu, ada persyaratan "tanpa menggunakan fungsi pow()".

Dari aritmetika modular, kita tahu bahwa $ab\ \rm mod\ c = (a\ \rm mod\ c)(b\ \rm mod\ c)\ \rm mod\ c$ , dengan $a,b,c > 0$ . Berdasarkan hal itu, algoritma utama modulo ini dapat diimplementasikan baik secara iteratif maupun rekursif.

Pada program di atas, fungsi yang secara rekursif mengimlementasikan algoritma utama terdapat dalam fungsi $\texttt{powermod(...)}$ . Fungsi tersebut menerima 3 parameter, yaitu $\texttt{basis}$ , $\texttt{eksponen}$ , dan $\texttt{modulus}$ . Hasil akhir dari fungsi tersebut adalah nilai basis^eksponen mod modulus.

Contoh kasus dan hasil eksekusi program

Untuk pengujian program, kita gunakan 3 contoh kasus. Kita hitung hasilnya secara matematis terlebih dahulu.

Contoh 1 (seperti pada soal)

$\begin{aligned}&9999^{9999}\\&\equiv(-1)^{9999}&(\rm mod\ 10)\\&\equiv(-1)&(\rm mod\ 10)\\&\equiv\boxed{\bf9}&(\rm mod\ 10)\\\end{aligned}$

Jadi, $9999^{9999}\ \rm mod\ 10=\bf9$ .

Contoh 2

$\begin{aligned}&2022^{2021}\\&\equiv(-1)^{2021}&(\rm mod\ 2023)\\&\equiv(-1)&(\rm mod\ 2023)\\&\equiv\boxed{\bf2022}&(\rm mod\ 2023)\\\end{aligned}$

Jadi, $2022^{2021}\ \rm mod\ 10=\bf2022$ .

Contoh 3

$\begin{aligned}&17^{8}\\&{\equiv\ }17^{3\times2+2}&(\rm mod\ 1945)\\&{\equiv\ }\left(17^3\right)^2\times17^2&(\rm mod\ 1945)\\&{\equiv\ }4913^2\times289&(\rm mod\ 1945)\\&{\equiv\ }(1023+1945(2))^2\times17^2&(\rm mod\ 1945)\\&{\equiv\ }1023^2\times17^2&(\rm mod\ 1945)\\&{\equiv\ }(3\times11\times31\times17)^2&(\rm mod\ 1945)\\&{\equiv\ }(3\times5797)^2&(\rm mod\ 1945)\\&{\equiv\ }(3\times(1907+1945(2)))^2&(\rm mod\ 1945)\end{aligned}$
$\begin{aligned}&{\equiv\ }(3\times1907)^2&(\rm mod\ 1945)\\&{\equiv\ }(3\times(-38))^2&(\rm mod\ 1945)\\&{\equiv\ }(-114)^2&(\rm mod\ 1945)\\&{\equiv\ }114^2&(\rm mod\ 1945)\\&{\equiv\ }12996&(\rm mod\ 1945)\\&{\equiv\ }1326+1945(6)&(\rm mod\ 1945)\\&{\equiv\ }\boxed{\bf1326}&(\rm mod\ 1945)\end{aligned}$

Jadi, $17^{8}\ \rm mod\ 1945=\bf1326$ .

Berikutnya adalah hasil eksekusi program.

Bilangan basis = 9999
Eksponsn = 9999
Modulus = 10
========================
⇒ 9999^9999 mod 10 = 9

Mau coba lagi? (y/t) y

Bilangan basis = 2022
Eksponsn = 2021
Modulus = 2023
========================
⇒ 2022^2021 mod 2023 = 2022

Mau coba lagi? (y/t) y

Bilangan basis = 17
Eksponsn = 8
Modulus = 1945
========================
⇒ 17^8 mod 1945 = 1326

Mau coba lagi? (y/t) x
Ngawur kamu! Nggak jelas deh!