Instruction sequences expressing multiplication algorithms
arXiv:1312.1529 · doi:10.7561/SACS.2018.1.39
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 with respect to their binary representation by bit strings of length , for a fixed but arbitrary , 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 . 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 .
arXiv comment14 pages, the preliminaries of this paper and arXiv:1308.0219 are the same; 16 pages, results sharpened and presentation improved; 22 pages, combined with arXiv:1312.1812; 22 pages, typos corrected and explanation added
References in corpus (7)
- Instruction sequence processing operators
- On algorithmic equivalence of instruction sequences for computing bit string functions
- Instruction sequence based non-uniform complexity classes
- On the expressiveness of single-pass instruction sequences
- An Instruction Sequence Semigroup with Involutive Anti-Automorphisms
- Instruction sequence expressions for the secure hash algorithm SHA-256
- Long multiplication by instruction sequences with backward jump instructions
Cited by in corpus (5)
- Instruction sequence expressions for the secure hash algorithm SHA-256
- Quantitative Expressiveness of Instruction Sequence Classes for Computation on Single Bit Registers
- Long multiplication by instruction sequences with backward jump instructions
- Program algebra for Turing-machine programs
- Program algebra for random access machine programs