Karatsuba Multiplication Algorithm Optimization by Using Nikhilam II Method
Abstract
Multiplication is an essential operation in informatics engineering,for example in cryptography, cryptanalysis, and image processing fields.Researchesabout multiplication algorithmhave been conducted and improved by experts in numerous field,ranging from mathematics, informatics engineering, to electrical engineering. The most popular multiplication algorithm is created by Anatoly Karatsuba in 1960 in Soviet Union. Although it is old and many new multiplication algorithms arise, still this algorithm is chosen for middle to large size number category. Divide and conquer technique is implemented in this algorithm to speed up the multiplication process. The weakness of Karatsuba algorithm is the excessive recursive process,causing a longer execution time. Nikhilam II method is an algorithm founded in India and is included in Vedic Mathematics. Usually,Nikhilam II method is used by common people in India to ease daily multiplication calculation. This method can replace some of the multiplication operationswith addition, therefore it can be more optimum. In this paper, Nikhilam II method is implemented in the base case part of Karatsuba algorithm to reduce the recursive call. Hence, Karatsuba algortihm can be optimized from time execution point of view. As the result, this new algorithm can optimize time execution up to thrice faster than the original algorithm.
References
T. Baruchel, “Flattening Karatsuba’s Recursion Tree into a Single Summation,” SN Computer Science, Vol. 1, No. 48, hal 1–9, Nov. 2020.
Ç.K. Koç, Open Problems in Mathematics and Computational Science, 1st ed., Cham, Switzerland: Springer International Publishing, 2014.
A. Karatsuba dan Y. Ofman, “Multiplication of Multidigit Numbers on Automata,” English Translation in Soviet Physics Doklady, Vol. 7, hal. 595–596, Jan. 1963.
S.A. Cook dan S.O. Aanderaa, “On the Minimum Computation Time of Functions,” Transactions of the American Mathematical Society, Vol. 142, hal. 291–314, Agu. 1969.
A. Schönhage dan V. Strassen, “Schnelle Multiplikation großer Zahlen,” Computing, Vol. 7, No. 3-4, hal. 281–292, Sep. 1971.
M. Fürer, “Faster Integer Multiplication,” SIAM Journal on Computing, Vol. 39, No. 3, hal. 979–1005, Sep. 2009.
D. Harvey, J.V.D. Hoeven, dan G. Lecerf, “Even Faster Integer Multiplication,” Journal of Complexity, Vol. 36, hal. 1–30, Okt. 2016.
S. Covanov dan E. Thomé, “Fast Arithmetic for Faster Integer Multiplication,” HAL-Inria preprints, hal. 1-8, Jan. 2015.
Felix, “Analisis Waktu Eksekusi Algoritma Perkalian Karatsuba dan Nikhilam,” JSM (Jurnal SIFO Mikroskil), Vol. 17, No. 2, hal. 153–162, Okt. 2016.
T. Jebelean, “Using the Parallel Karatsuba Algorithm for Long Integer Multiplication and Division,” Euro-Par '97: Proceedings of the Third International Euro-Par Conference on Parallel Processing, 1997, hal. 1169–1172.
F.O. Ehtiba and A. Samsudin, "Multiplication and Exponentiation of Big Integers with Hybrid Montgomery and Distributed Karatsuba Algorithm," Proceedings. 2004 International Conference on Information and Communication Technologies: From Theory to Applications, 2004, hal. 421–422.
F. Tsang, “A Comparison of Traditional, Karatsuba and Fourier Big Integer Multiplication,” B.Sc. dissertation, University of Bath, Somerset, United Kingdom, Mei 2004.
J.B. Lima, D. Panario, dan Q. Wang, “A Karatsuba-Based Algorithm for Polynomial Multiplication in Chebyshev Form,” IEEE Transactions on Computers, Vol. 59, No. 6, hal. 835–841, Jun. 2010.
M. Bodrato dan A. Zanoni, “Karatsuba and Toom-Cook Methods for Multivariate Polynomials,” Acta Universitatis Apulensis Special Issue ICTAMI 2011, hal. 11–60, Jul. 2011.
B.K. Tirthaji, Vedic Mathematics, Delhi, India: Motilal Banarsidass Publishers, 1965.
S.P. Dwivedi, "An Efficient Multiplication Algorithm using Nikhilam Method," Fifth International Conference on Advances in Recent Technologies in Communication and Computing (ARTCom 2013), 2013, hal. 223–228.
C. Eyupoglu, “Investigation of the Performance of Nikhilam Multiplication Algorithm,” Procedia - Social and Behavioral Sciences, Vol. 195, hal. 1959–1965, Jul. 2015.
© Jurnal Nasional Teknik Elektro dan Teknologi Informasi, under the terms of the Creative Commons Attribution-ShareAlike 4.0 International License.
1.png)
