Instruction sequences expressing multiplication algorithms

DOI10.7561/SACS.2018.1.39MaRDI QIDQ4621216zbMATH OpenWikidataFDO

Authors J. A. Bergstra, C. A. Middelburg

Publication date 8 February 2019

Published in Scientific Annals of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.1529

zbMATH Keywords

halting problemsingle-pass instruction sequencebit string functionbackward jump instructionKaratsuba multiplication algorithm

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

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 $2^N$ 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 $2^8$. 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$.

Recommendations

• On algorithmic equivalence of instruction sequences for computing bit string functions
• How fast can we multiply large integers on an actual computer?
• Quantitative expressiveness of instruction sequence classes for computation on single bit registers
• Algorithms for Iterative Array Multiplication
• scientific article; zbMATH DE number 4203715

Cited in

(1)

• On algorithmic equivalence of instruction sequences for computing bit string functions

This page was built for publication: Instruction sequences expressing multiplication algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4621216)