A less recursive variant of Karatsuba-Ofman algorithm for multiplying operands of size a power of two

Abstract

We 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.