Analisis Pengaruh 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 and 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

References


Baruchel, T. 2019. Flattening Karatsuba’s Recursion Tree into a Single Summation. SN Computer Science (2020) 1:48. Springer

Ramakrishna, S. 2019. Speeding up the Karatsuba algorithm. arXiv:1905.07455v3 [cs.DS] 23 Oct 2019.

Çalik, Ç. dkk. 2019. Searching for Best Karatsuba Recurrences. Springer: Analysis of Experimental Algorithms Special Event, SEA2 2019, Kalamata, Greece, June 24–29, 2019 Revised Selected Papers

Li, Y. dkk. 2019. On the Complexity of Hybrid n-Term Karatsuba Multiplier for Trinomials. IEEE Transactions on Circuits and Systems–I: Regular Papers. IEEE

Guo, S. dan Zorin-Kranich, P. 2020. Decoupling for moment manifolds associated to Arkhipov–Chubarikov–Karatsuba systems, Advances in Mathematics 360 (2020) 106889. Elsevier

Dwivedi, S. P. 2013. An efficient multiplication algorithm using Nikhilam method. Fifth International Conference on Advances in Recent Technologies in Communication and Computing (ARTCom), 20-21 Sept, Bangalore, IET, ISBN: 978-1-84919-842-4, 223-228.

Eyupoglu, C. 2015. Performance Analysis of Karatsuba Multiplication Algorithm for Different Bit Lengths. World Conference on Technology, Innovation and Entrepreneurship. Elsevier Procedia - Social and Behavioral Sciences Journal, Volume 195. pp 1860-1864.




DOI: https://doi.org/10.55601/jsm.v22i1.777

Refbacks

  • There are currently no refbacks.