Analisis Waktu Eksekusi Algoritma Perkalian Karatsuba dan Nikhilam

Abstract

Multiplication is a common thing which is done by everybody in daily routine. Even though, multiplication in Computer Science is not as simple as what is done by most people. This is because multiplication in Computer Science involved number with a lot of digit. Some branches which involved a lot of multiplication of number with a lot of digits are cryptography and cryptanalysis. To do the multiplication, the usual thing which is learned in Primary is no longer enough because not only the computation time becomes very long, some calculators are also unable to give accurate result. Accuracy is a main thing in Cryptography and Cryptanalysis' Therefore Karatsuba multiplication algorithm was introduced in 1963 which has a shorter computation time. This algorithm implements Divide and conquer method, and also implements recursive algorithm. This can reduce the execution time drastically, but there are still potential to reduce the execution time by combining Nikhilam algorithm into Karatsuba algorithm. After the writer combined both algorithms, a combined algorithm is produced which only needs less than half of the execution time of Classical Karatsuba algorithm.