Abstract
For each function on bit strings, its restriction to bit strings of any
given length can be computed 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 instruction sequences of this kind that compute the function
on bit strings that models multiplication on natural numbers less than
2N with respect to their binary representation by bit strings of
length N, for a fixed but arbitrary N > 0, according to the long
multiplication algorithm and the Karatsuba multiplication algorithm.
We find among other things that the instruction sequence expressing the
former algorithm is longer than the one expressing the latter algorithm
only if the length of the bit strings involved is greater than 28.
We also go into the use of an instruction sequence with backward jump
instructions for expressing the long multiplication algorithm.
This leads to an instruction sequence that it is shorter than the other
two if the length of the bit strings involved is greater than 2.
Preprint available:
arXiv:1312.1529 [cs.PL]