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!

___________________

(atau bisa amati gambar)

Kode Program PythonINVALID_ENTRY = -9999def 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 Utamaif __name__ == '__main__':    while True:        basis = int(input(

Semoga dengan pertanyaan yang sudah terjawab oleh henriyulianto dapat membantu memudahkan mengerjakan soal, tugas dan PR sekolah kalian.

Apabila terdapat kesalahan dalam mengerjakan soal, silahkan koreksi jawaban dengan mengirimkan email ke yomemimo.com melalui halaman Contact

Last Update: Thu, 27 Oct 22