Instruction sequence expressions for the Karatsuba multiplication algorithm
Jan Aldert Bergstra, Cornelis A. Middelburg · UvA-DARE (University of Amsterdam) · 2013
The Karatsuba multiplication algorithm is an algorithm for computing the product of two natural numbers represented in the binary number system. This means that the algorithm actually computes a function on bit strings. The restriction of this function to bit strings of any given length can be computed according to the Karatsuba multiplication algorithm by a finite instruction sequence that contains only instructions to set and get the content of Boolean registers, forward jump instructions, and a termination instruction. We describe the instruction sequences concerned for the restrictions to bit strings of the different lengths by uniform terms from an algebraic theory.