Analisis Pengaruh Nilai Batas Base Case pada Algoritma Karatsuba terhadap Tingkat Efisiensi Waktu Eksekusi

Felix Felix, Syanti Irviantina

Abstract


Algoritma Karatsuba adalah algoritma perkalian yang masih banyak diteliti oleh peneliti Ilmu Komputer dan Matematika meskipun telah berusia lebih dari setengah abad. Algoritma ini merupakan algoritma yang menerapkan konsep Divide & Conquer. Oleh karena itu terdapat nilai base case (BC) yang dapat diganti. Hipotesisnya adalah nilai BC ketika ditingkatkan akan mengurangi waktu eksekusi sampai mencapai suatu nilai x. Setelah melewati nilai x, waktu eksekusi akan bertambah. Pada penelitian ini dilakukan dengan 36 percobaan dengan kombinasi dari 3 pilihan digit, 3 kasus, dan 4 BC. Pilihan digitnya adalah 2000, 4000, dan 6000 digit. Kasus yang digunakan adalah angka acak yang dikalikan dengan angka acak itu sendiri. BC yang digunakan adalah 1010^n dengan nilai n = {0, 1, 2, 3}.Penelitian ini menghasilkan fakta yang berlawanan dengan hipotesis. Semakin besar BC membutuhkan waktu eksekusi yang lebih singkat. Hal ini diduga karena di dalam Python sendiri sudah menerapkan algoritma Karatsuba secara implisit.

Keywords


base case; Karatsuba; waktu eksekusi

Full Text: PDF

Refbacks

  • There are currently no refbacks.


Lembaga Penelitian & Pengabdian pada Masyarakat (LPPM)
Universitas Mikroskil
Jl. Thamrin No. 124 Medan - 20212
Gedung A. 07.L2
Telp. 061-4573767
Email: publication@mikroskil.ac.id

Creative Commons License
The JSM site and its metadata are licensed under CC BY-NC-ND