Published in Volume XXVIII, Issue 1, 2018, pages 39-66, doi: 10.7561/SACS.2018.1.39

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

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. One of the results obtained is 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.

Full Text (PDF)

References

[1] J. A. Bergstra and M. E. Loots. Program Algebra for Sequential Code. Journal of Logic and Algebraic Programming, 51(2):125–156, 2002. doi:10.1016/S1567-8326(02)00018-8.

[2] J. A. Bergstra and C. A. Middelburg. Instruction Sequence Processing Operators. Acta Informatica, 49(3):139–172, 2012. doi:10.1007/s00236-012-0154-2.

[3] J. A. Bergstra and C. A. Middelburg. Instruction Sequences for Computer Science, volume 2 of Atlantis Studies in Computing. Atlantis Press, Amsterdam, 2012. doi:10.2991/978-94-91216-65-7_2.

[4] J. A. Bergstra and C. A. Middelburg. Instruction Sequence Based Non-uniform Complexity Classes. Scientific Annals of Computer Science, 24(1):47–89, 2014. doi:10.7561/SACS.2014.1.47.

[5] J. A. Bergstra and C. A. Middelburg. On Algorithmic Equivalence of Instruction Sequences for Computing Bit String Functions. Fundamenta Informaticae, 138(4):411–434, 2015. doi:10.3233/FI-2015-1219.

[6] J. A. Bergstra and A. Ponse. An Instruction Sequence Semigroup with Involutive Anti-Automorphisms. Scientific Annals of Computer Science, 19:57–92, 2009.

[7] S. A. Cook. On the Minimum Computation Time of Functions. PhD thesis, Harvard University, Cambridge, MA, 1966.

[8] M. Fürer. Faster Integer Multiplication. SIAM Journal of Computing, 39(3):979–1005, 2009. doi:10.1137/070711761.

[9] A. A. Karatsuba. The Complexity of Computations. Proceedings of the Steklov Institute of Mathematics, 211:169–183, 1995.

[10] A. A. Karatsuba and Y. P. Ofman. Multiplication of Multidigit Numbers on Automata. Doklady Akademii Nauk SSSR, 145(2):293–294, 1962. in Russian.

[11] C. A. Middelburg. Instruction Sequences as a Theme in Computer Science. https://instructionsequence.wordpress.com/, 2015.

[12] A. Schönhage and V. Strassen. Schnelle Multiplikation großer Zahlen. Computing, 7(3–4):281–292, 1971. doi:10.1007/BF02242355.

[13] A. A. Toom. The Complexity of a Scheme of Functional Elements Simulating the Multiplication of Integers. Doklady Akademii Nauk SSSR, 150(2):496–498, 1963. in Russian.

[14] A. M. Turing. On Computable Numbers, With an Application to the Entscheidungs Problem. Proceedings of the London Mathematical Society, Series 2, 42:230–265, 1937. doi:10.1112/plms/s2-42.1.230. Correction: ibid, 43:544–546, 1937. doi:10.1112/plms/s2-43.6.544.

[15] Karatsuba Algorithm. In Wikipedia, 2018. Retrieved on July 1, 2018, from http://en.wikipedia.org/wiki/Karatsuba_algorithm .

[16] Secure Hash Standard. National Institute of Standards and Technology, FIPS PUB 180-4, March 2012.

Bibtex

@article{sacscuza:bergstra2018isema,
  title={Instruction Sequences Expressing Multiplication Algorithms},
  author={J.A. Bergstra and C.A. Middelburg },
  journal={Scientific Annals of Computer Science},
  volume={28},
  number={1},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2018},
  pages={39--66},
  doi={10.7561/SACS.2018.1.39},
  publisher={``A.I. Cuza'' University Press}
}