Analisis Waktu Eksekusi Algoritma Perkalian Karatsuba Dan Nikhilam

Abstract

Sebagian perkalian dalam Ilmu Komputer melibatkan bilangan dengan jumlah digit yang banyak. Beberapa cabang ilmu yang banyak melibatkan perkalian bilangan dengan jumlah digit yang banyak adalah Kriptografi dan Kriptanalisis. Untuk melakukan perkalian tersebut, cara biasa yang dipelajari di tingkat SD sudah tidak memadai karena selain waktu komputasinya sangat lama, beberapa kalkulator pun tidak sanggup memberikan nilai yang akurat. Keakurasian tersebut merupakan hal pokok dalam Kriptografi dan Kriptanalisis. Oleh karena itu muncul algoritma perkalian Karatsuba pada tahun 1963 yang memiliki waktu komputasi yang lebih singkat. Algoritma ini selain menerapkan metode Divide and Conquer, juga menerapkan algoritma yang bersifat rekursif. Hal ini memang mampu menurunkan waktu eksekusi secara drastis, namun masih ada potensi untuk menurunkan waktu eksekusinya dengan menggabungkan algoritma Nikhilam ke dalam algoritma Karatsuba. Setelah penulis menggabungkan kedua algoritma tersebut, dihasilkan algoritma gabungan yang hanya membutuhkan kurang dari setengah kali waktu eksekusi algoritma Karatsuba Klasik.