A Less Recursive Variant of Karatsuba-Ofman Algorithm for Multiplying Operands of Size a Power of TwoS. S. Erdem and C. K. KocProceedings, 16th IEEE Symposium on Computer Arithmetic, J.-C. Bajard and M. Schulte, editors, pages 28-35, IEEE Computer Society Press, Santiago de Compostela, Spain, June 15-18, 2003.AbstractWe propose a new algorithm for fast multiplication of large integers having a precision of 2^k computer words, where k is an integer. The algorithm is derived from the Karatsuba-Ofman Algorithm and has the same asymptotic complexity. However, the running time of the new algorithm is slightly better, and it makes one third as many recursive calls. |