Instruction Sequences Expressing
Multiplication Algorithms

arXiv:1312.1529v3 [cs.PL] 29 Nov 2017

J.A. Bergstra and C.A. Middelburg
Informatics Institute, Faculty of Science, University of Amsterdam,
Science Park 904, 1098 XH Amsterdam, the Netherlands
J.A.Bergstra@uva.nl,C.A.Middelburg@uva.nl

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.
Keywords: bit string function, single-pass instruction sequence, backward
jump instruction, long multiplication algorithm, Karatsuba multiplication algorithm, halting problem.
1998 ACM Computing Classification: F.1.1, F.2.1.

1

Introduction

This paper belongs to a line of research in which issues relating to various
subjects from computer science, including programming language expressiveness, computability, computational complexity, algorithm efficiency, algorithmic
equivalence of programs, program verification, program performance, program
compactness, and program parallelization, are rigorously investigated thinking
in terms of instruction sequences. An enumeration of most papers belonging to
this line of research is available at [15]. The work on computational complexity
presented in [7,9] and the work on algorithmic equivalence of programs presented
in [8] were prompted by the fact that, 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.

This fact also incited us to look for finite instruction sequences containing
only the above-mentioned instructions that compute a well-known function on
bit strings of a given length. In [5], we did so taking the hash function SHA-256
from the Secure Hash Standard [20] as the well-known function on bit strings.
In the current paper, we do so taking the function 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, as the well-known function
on bit strings.
We describe finite instruction sequences containing only the above-mentioned
instructions that compute this function according to the standard multiplication
algorithm, which is known as the long multiplication algorithm, and according
to the Karatsuba multiplication algorithm [13,14]. We calculate the exact size of
the instruction sequence expressing the long multiplication algorithm and lower
and upper estimates for the size of the instruction sequence expressing the Karatsuba multiplication algorithm. We find among other things that the instruction
sequence expressing the former algorithm is longer than the instruction sequence
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. We describe a finite
instruction sequence containing a backward jump instruction, in addition to
the above-mentioned instructions, that expresses a minor variant of the long
multiplication algorithm. We calculate the exact size of this instruction sequence
and find among other things that it is shorter than the other two if the length
of the bit strings involved is greater than 2. In addition, we argue that the
instruction sequences expressing the long multiplication algorithm form a hard
witness of the inevitable existence of a halting problem in the practice of imperative programming.
The Karatsuba multiplication algorithm was devised by Karatsuba in 1962
to disprove the conjecture made by Kolmogorov that any algorithm to compute the function that models multiplication on natural numbers with respect
to their representations in the binary number system has time complexity Ω(n2 ).
Shortly afterwards, this divide-and-conquer algorithm was generalized by Toom
and Cook [11,17]. Later, asymptotically faster multiplication algorithms, based
on fast Fourier transforms, were devised by Schönhage and Strassen [16] and
Fürer [12]. To our knowledge, except for the Schönhage-Strassen algorithm, only
informal (natural language or pseudo code) descriptions of these multiplication
algorithms are available. In this paper, we provide a mathematically precise
alternative to the informal descriptions of the Karatsuba multiplication algorithm, using terms from an algebraic theory of single-pass instruction sequences
introduced in [1].
It is customary that computing practitioners phrase their explanations of
issues concerning programs from an empirical perspective such as the perspective
that a program is in essence an instruction sequence. An attempt to approach the
semantics of programming languages from this perspective is made in [1]. The

2

groundwork for the approach is an algebraic theory of single-pass instruction
sequences, called program algebra, and an algebraic theory of mathematical
objects that represent the behaviours produced by instruction sequences under
execution, called basic thread algebra.1 The line of research referred to at the
beginning of this introduction originates from the above-mentioned work on an
approach to programming language semantics.
The general aim of this line of research is to bring instruction sequences as
a theme in computer science better into the picture. This is the general aim of
the work presented in the current paper as well. However, different from usual
in the work referred to above, the accent is this time mainly on a practical
problem, namely the problem to devise instruction sequences that express the
long multiplication algorithm and the Karatsuba multiplication algorithm. As
in the work referred to above, the work presented in the current paper is carried
out in the setting of program algebra.
This paper is organized as follows. First, we survey program algebra and the
particular fragment and instantiation of it that is used in this paper (Section 2)
and sketch the Karatsuba multiplication algorithm (Section 3). Next, we describe
how we deal with n-bit words by means of Boolean registers (Section 4) and how
we compute the operations on n-bit words that are used in the long multiplication algorithm and/or the Karatsuba multiplication algorithm (Section 5).
Then, we describe and analyze instruction sequences that express these algorithms (Section 6). After that, we go into the use of an instruction sequence
with backward jump instructions for expressing the long multiplication algorithm (Sections 7) and relate the findings to the halting problem (Section 8).
Finally, we make some concluding remarks (Section 9).
We rely in this paper on an intuitive understanding of what is an algorithm
and when an instruction sequence expresses an algorithm. A rigorous study
of these issues and related ones, carried out in the same setting as the work
presented in this paper, is presented in [8].
The preliminaries to the work presented in this paper are the same as the
preliminaries to the work presented in [5], which are in turn a selection from
the preliminaries to the work presented in [7]. For this reason, there is some
text overlap with those papers. The preliminaries concern program algebra. We
only give a brief summary of program algebra. A comprehensive introduction,
including examples, can among other things be found in [3].
This paper consolidates material from [4,6].

2

Program Algebra

In this section, we present a brief outline of PGA (ProGram Algebra) and the
particular fragment and instantiation of it that is used in the remainder of this
paper. A mathematically precise treatment can be found in [7].
1

In [1], basic thread algebra is introduced under the name basic polarized process
algebra.

3

The starting-point of PGA is the simple and appealing perception of a sequential program as a single-pass instruction sequence, i.e. a finite or infinite
sequence of instructions of which each instruction is executed at most once and
can be dropped after it has been executed or jumped over.
It is assumed that a fixed but arbitrary set A of basic instructions has been
given. The intuition is that the execution of a basic instruction may modify a
state and produces a reply at its completion. The possible replies are 0 and 1.
The actual reply is generally state-dependent. Therefore, successive executions
of the same basic instruction may produce different replies. The set A is the basis
for the set of instructions that may occur in the instruction sequences considered
in PGA. The elements of the latter set are called primitive instructions. There
are five kinds of primitive instructions, which are listed below:
–
–
–
–
–

for each a ∈ A, a plain basic instruction a;
for each a ∈ A, a positive test instruction +a;
for each a ∈ A, a negative test instruction −a;
for each l ∈ N, a forward jump instruction #l;
a termination instruction !.

We write I for the set of all primitive instructions.
On execution of an instruction sequence, these primitive instructions have
the following effects:
– the effect of a positive test instruction +a is that basic instruction a is
executed and execution proceeds with the next primitive instruction if 1
is produced and otherwise the next primitive instruction is skipped and
execution proceeds with the primitive instruction following the skipped one
— if there is no primitive instruction to proceed with, inaction occurs;
– the effect of a negative test instruction −a is the same as the effect of +a,
but with the role of the value produced reversed;
– the effect of a plain basic instruction a is the same as the effect of +a, but
execution always proceeds as if 1 is produced;
– the effect of a forward jump instruction #l is that execution proceeds with
the lth next primitive instruction of the instruction sequence concerned —
if l equals 0 or there is no primitive instruction to proceed with, inaction
occurs;
– the effect of the termination instruction ! is that execution terminates.
To build terms, PGA has a constant for each primitive instruction and two
operators. These operators are: the binary concatenation operator ; and the
n
unary repetition operator ω . We use the notation i=0 Pi , where P0 , . . . , Pn are
PGA terms, for the PGA term P0 ; . . . ; Pn . We also use the notation P n . For
each PGA term P and n > 0, P n is the PGA term defined by induction on n as
follows: P 1 = P and P n+1 = P ; P n .
The instruction sequences that concern us in the remainder of this paper
are the finite ones, i.e. the ones that can be denoted by closed PGA terms in
which the repetition operator does not occur. Moreover, the basic instructions

;

4

that concern us are instructions to set and get the content of Boolean registers.
More precisely, we take the set
{in:i.get | i ∈ N+ } ∪ {out:i.set:b | i ∈ N+ ∧ b ∈ {0, 1}}
∪ {aux:i.get | i ∈ N+ } ∪ {aux:i.set:b | i ∈ N+ ∧ b ∈ {0, 1}}
as the set A of basic instructions.
Each basic instruction consists of two parts separated by a dot. The part on
the left-hand side of the dot plays the role of the name of a Boolean register and
the part on the right-hand side of the dot plays the role of a command to be
carried out on the named Boolean register. For each i ∈ N+ :
– in:i serves as the name of the Boolean register that is used as ith input
register in instruction sequences;
– out:i serves as the name of the Boolean register that is used as ith output
register in instruction sequences;
– aux:i serves as the name of the Boolean register that is used as ith auxiliary
register in instruction sequences.
On execution of a basic instruction, the commands have the following effects:
– the effect of get is that nothing changes and the reply is the content of the
named Boolean register;
– the effect of set:0 is that the content of the named Boolean register becomes
0 and the reply is 0;
– the effect of set:1 is that the content of the named Boolean register becomes
1 and the reply is 1.
Let n, m ∈ N, let f : {0, 1}n → {0, 1}m , and let X be a finite instruction
sequence that can be denoted by a closed PGA term in the case that A is taken
as specified above. Then X computes f if there exists a k ∈ N such that for all
b1 , . . . , bn ∈ {0, 1}: if X is executed in an environment with n input registers,
m output registers, and k auxiliary registers, the content of the input registers
with names in:1, . . . , in:n are b1 , . . . , bn when execution starts, and the content of
the output registers with names out:1, . . . , out:m are b′1 , . . . , b′m when execution
terminates, then f (b1 , . . . , bn ) = b′1 , . . . , b′m .

3

Sketch of the Karatsuba Multiplication Algorithm

Suppose that x and y are two natural numbers with a binary representation of n
bits. As a first step toward multiplying x and y, split each of these representations
into a left part of length ⌊n/2⌋ and a right part of length ⌈n/2⌉. Let us say that
the left and right part of the representation of x represent natural numbers xL
and xR and the left and right part of the representation of y represent natural
numbers yL and yR . It is obvious that x = 2⌈n/2⌉ ·xL +xR and y = 2⌈n/2⌉ ·yL +yR .
From this it follows immediately that
x · y = 22·⌈n/2⌉ · (xL · yL ) + 2⌈n/2⌉ · (xL · yR + xR · yL ) + xR · yR .
5

In addition to this, it is known that
xL · yR + xR · yL = (xL + xR ) · (yL + yR ) − xL · yL − xR · yR .
Moreover, it is easy to see that multiplications by powers of 2 are merely bit shifts
on the binary representation of the natural numbers involved. All this means
that, on the binary representations of x and y, the multiplication x · y can be
replaced by three multiplications: xL ·yL , xR ·yR , and (xL +xR )·(yL +yR ). These
three multiplications concern natural numbers with binary representations of
length ⌊n/2⌋, ⌈n/2⌉, and ⌈n/2⌉+1, respectively. For each of these multiplications
it holds that, if the binary representation length concerned is greater than 3, the
multiplication can be replaced by three multiplications of natural numbers with
binary representations of even shorter length.
The Karatsuba multiplication algorithm is the algorithm that computes the
binary representation of the product of two natural numbers with binary representations of the same length by dividing the computation into the computation
of the binary representations of three products as indicated above and doing
so recursively until it not any more leads to further length reduction. The remaining products are usually computed according to the standard multiplication
algorithm, which is known as the long multiplication algorithm.
Both the Karatsuba multiplication algorithm and the long multiplication algorithm can actually be applied to natural numbers represented in the binary
number system as well as natural numbers represented in the decimal number
system. The long multiplication algorithm is the multiplication algorithm that is
taught in schools for computing the product of natural numbers represented in
the decimal number system. It is known that the long multiplication algorithm
has uniform time complexity Θ(n2 ) and the the Karatsuba multiplication algorithm has uniform time complexity Θ(nlog2 (3) ) = Θ(n1,5849... ), so the Karatsuba
multiplication algorithm is asymptotically faster than the long multiplication
algorithm.

4

Dealing with n-Bit Words

This section is concerned with dealing with bit strings of length n by means
of Boolean registers. It contains definitions which facilitate the description of
instruction sequences that express the long multiplication algorithm and the
Karatsuba multiplication algorithm.
Henceforth, it is assumed that a fixed but arbitrary positive natural number
N has been given. The above-mentioned algorithms compute the binary representation of the product of two natural numbers represented by bit strings of the
same length. In Section 6, the instruction sequences expressing these algorithms
will be described for the case where this length is N .
In the sequel, bit strings of length n will mostly be called n-bit words. The
prefix “n-bit” is left out if n is irrelevant or clear from the context.
Let κ:i (κ ∈ {in, out, aux}, i ∈ N+ ) be the name of a Boolean register. Then κ
and i are called the kind and number of the Boolean register. Successive Boolean
6

registers are Boolean registers of the same kind with successive numbers. Words
are stored by means of Boolean registers such that the successive bits of a stored
word are the contents of successive Boolean registers.
Henceforth, the name of a Boolean register will mostly be used to refer to
the Boolean register in which the least significant bit of a word is stored. Let κ:i
and κ′ :i′ be the names of Boolean registers and let n ∈ N+ . Then we say that κ:i
and κ′ :i′ lead to partially coinciding n-bit words if k = k ′ and 0 < |i − i′ | < n.
The N -bit words representing the two natural numbers for which the binary
representation of their product is to be computed are stored in advance of the
computation in input registers, starting with the input register with number 1.
It is convenient to have available the names I1 and I2 for the input registers
in which the least significant bit of these words are stored. The 2N -bit word
representing the product is stored just before the end of the computation in
output registers, starting with the output register with number 1. It is convenient
to have available the name O for the output register in which the least significant
bit of this word is stored. The words representing intermediate values that arise
during the computation are temporarily stored in auxiliary registers, starting
with the auxiliary register with number 1.
In the case of the Karatsuba algorithm, the binary representation of the
product of two natural numbers with binary representations of the same length
is computed by dividing the computation into the computation of the binary
representations of three products and doing so recursively until it not any more
leads to further length reduction. Therefore, it is convenient to have available,
for sufficiently many natural numbers i, the names I1i , I2i and Oi for the auxiliary registers in which the least significant bit of the binary representations of
smaller natural numbers and their product are stored. Because at each level of
recursion, except the last level, the computation of the binary representation of
a product involves the computation of the binary representations of three products at the next level, it is convenient to have available, for sufficiently many
natural numbers i, the names P1i , P2i and P3i for the auxiliary registers in which
the least significant bit of these binary representations of products are stored.
It is also convenient to have available the names S1 , S2 , T1 , T2 for the auxiliary registers in which the least significant bit of the words that represent the
intermediate values that arise, other than the ones mentioned in the previous
paragraph, are stored. Moreover, it is convenient to have available the name c
for the auxiliary register that contains the carry/borrow bit that is repeatedly
stored when computing the operations that model addition and subtraction on
natural numbers with respect to their binary representation.
Therefore, we define:
I1
I2
O
c
S1

, in:1,
, in:k
where k = N + 1,
, out:1,
, aux:1,
, aux:2,
7

S2
T1
T2
I1i
I2i
Oi
P1i
P2i
P3i

, aux:k
, aux:k
, aux:k
, aux:k
, aux:k
, aux:k
, aux:k
, aux:k
, aux:k

where k
where k
where k
where k
where k
where k
where k
where k
where k

= 2 · N + 2,
= 4 · N + 2,
= 6 · N + 2,
= 10 · N · i + 8 · N + 2
= 10 · N · i + 9 · N + 2
= 10 · N · i + 10 · N + 2
= 10 · N · i + 12 · N + 2
= 10 · N · i + 14 · N + 2
= 10 · N · i + 16 · N + 2

(0 ≤ i ≤ ⌈log2 (N
(0 ≤ i ≤ ⌈log2 (N
(0 ≤ i ≤ ⌈log2 (N
(0 ≤ i ≤ ⌈log2 (N
(0 ≤ i ≤ ⌈log2 (N
(0 ≤ i ≤ ⌈log2 (N

− 2)⌉),
− 2)⌉),
− 2)⌉),
− 2)⌉),
− 2)⌉),
− 2)⌉).

Here i ranges over natural numbers in the interval with lower endpoint 0 and
upper endpoint ⌈log2 (N − 2)⌉. This needs some explanation.
Proposition 1. The recursion depth of the Karatsuba multiplication algorithm
applied to bit strings of length N is ⌈log2 (N − 2)⌉.
Proof. Let n ≤ N . In the Karatsuba multiplication algorithm, the binary representation of the product of two natural numbers with binary representations of
length n is computed by dividing the computation into the computation of the
binary representation of a product of two natural numbers with binary representations of length ⌊n/2⌋, the binary representation of a product of two natural
numbers with binary representations of length ⌈n/2⌉, and the binary representation of a product of two natural numbers with binary representations of length
⌈n/2⌉ + 1. The function f defined by f (n) , ⌈n/2⌉ + 1 has the following properties: (a) f (n) < n iff n > 3; and (b) for n > 3, the least m such that f m (n) = 3
is ⌈log2 (n − 2)⌉. This implies that the recursion depth is ⌈log2 (N − 2)⌉.
⊓
⊔
Proposition 1 tells us that the maximum level of recursion that can be reached
is ⌈log2 (N − 2)⌉. So there are ⌈log2 (N − 2)⌉ + 1 possible levels of recursion,
viz. 0, . . . , ⌈log2 (N − 2)⌉. This means that there are sufficiently many natural
numbers i for which the names I1i , I2i , Oi , P1i , P2i , and P3i have been introduced
above. In Section 6, we will use the names I1i , I2i , Oi , P1i , P2i , and P3i at the level
of recursion ⌈log2 (N − 2)⌉ − i.

5

Computing Operations on n-Bit Words

This section is concerned with computing operations on bit strings of length n.
It contains definitions which facilitate the description of instruction sequences
that express the long multiplication algorithm and the Karatsuba multiplication
algorithm.
In this section, we will write ββ ′ , where β and β ′ are bit strings, for the
concatenation of β and β ′ . In other words, we will use juxtaposition for concatenation. Moreover, we will use the bit string notation bn . For n > 0, the bit
string bn , where b ∈ {0, 1}, is defined by induction on n as follows: b1 = b and
bn+1 = b bn .
8

The basic operations on words that are relevant to the long multiplication
algorithm and/or the Karatsuba multiplication algorithm are the operations that
model addition, subtraction, and multiplication by 2m , modulo 2n , on natural
numbers less than 2n , with respect to their binary representation by n-bit words
(0 < n ≤ N , 0 < m < n). The operation modeling multiplication by 2m is
commonly known as “shift left by m positions”. For these operations, we define
parameterized instruction sequences computing them in case the parameters are
properly instantiated (see below):
ADD n (s1 :k1 , s2 :k2 , d:l) ,
c.set:0 ;
n−1
i=0 (+s1 :k1 +i.get ; #8 ; +s2 :k2 +i.get ; #8 ; −c.get ; #14 ;
d:l+i.set:1 ; c.set:0 ; #13 ; +s2 :k2 +i.get ; #4 ; +c.get ; #7 ; #7 ;
+c.get ; #5 ; d:l+i.set:0 ; c.set:1 ; #3 ; +d:l+i.set:0 ; d:l+i.set:1) ,

;

SUB n (s1 :k1 , s2 :k2 , d:l) ,
c.set:0 ;
n−1
i=0 (−s1 :k1 +i.get ; #8 ; +s2 :k2 +i.get ; #8 ; −c.get ; #14 ;
d:l+i.set:0 ; c.set:0 ; #13 ; +s2 :k2 +i.get ; #4 ; +c.get ; #7 ; #7 ;
+c.get ; #5 ; d:l+i.set:1 ; c.set:1 ; #3 ; −d:l+i.set:1 ; d:l+i.set:0) ,

;

SHLm
n (s:k, d:l) ,
n−1−m
(+s:k+n−1−m−i.get ; −d:l+n−1−i.set:1 ; d:l+n−1−i.set:0) ;
i=0

;
;

m−1
i=0 (d:l+m−1−i.set:0)

,

where s, s1 , s2 range over {in, aux}, d ranges over {aux, out}, and k, k1 , k2 , l range
over N+ . For each of these parameterized instruction sequences, all but the last
parameter correspond to the operands of the operation concerned and the last
parameter corresponds to the result of the operation concerned. The intended
operations are computed provided that the instantiation of the last parameter
and the instantiation of none of the other parameters lead to partially coinciding
n-bit words. In this paper, this condition will always be satisfied.
Proposition 2. Let n, m ∈ N be such that 0 < n ≤ N and 0 < m < m. Then
the function on bit strings of length n computed by
1. ADD n (I1 , I2 , O) ; ! models addition modulo 2n on natural numbers less than
2n with respect to their binary representation by n-bit words;
2. SUB n (I1 , I2 , O) ; ! models subtraction modulo 2n on natural numbers less
than 2n with respect to their binary representation by n-bit words;
m
3. SHLm
modulo 2n on natural numbers
n (I1 , O) ; ! models multiplication by 2
n
less than 2 with respect to their binary representation by n-bit words.
Proof. In the case of the first and second property, we prove a stronger property that also covers the final content of the auxiliary register containing the
9

carry/borrow bit. Each of the stronger properties is easy to prove by induction
on n with case distinction on the contents of the input registers containing the
most significant bits of the operands of the operation concerned and the content
of the auxiliary register containing the carry/borrow bit in both the basis step
and the inductive step. The third property is easy to prove by induction on n
with case distinction on the content of the input register containing the most
significant bit of the operand of the operation concerned in both the basis step
and the inductive step.
⊓
⊔
Transferring n-bit words (0 < n ≤ N ) is also relevant to the multiplication
algorithms. For this, we define parameterized instruction sequences as well. By
one the successive bits in a constant n-bit word become the content of n successive Boolean registers and by the other the successive bits in a n-bit word that
are the content of n successive Boolean registers become the content of n other
successive Boolean registers:
SET n (b0 . . . bn−1 , d:l) ,
MOV n (s:k, d:l) ,

;

;

n−1
i=0 (d:l+i.set:bi )

n−1
i=0 (+s:k+i.get

,

; −d:l+i.set:1 ; d:l+i.set:0) ,

where b0 , . . . , bn−1 range over {0, 1}, s ranges over {in, aux}, d ranges over
{aux, out}, and k, l range over N+ . In the case of MOV n , the intended transfer
is performed provided that the instantiation of the last parameter and the instantiation of the first parameter do not lead to partially coinciding n-bit words.
In this paper, this condition will always be satisfied.
Proposition 3. Let n ∈ N be such that 0 < n ≤ N . Then the function on bit
strings of length n computed by
1. SET n (b0 . . . bn−1 , O) ; ! models the natural number constant with binary representation b0 . . . bn−1 ;
2. MOV n (I1 , O) ; ! models the identity function on natural numbers less than
2n with respect to their binary representation by n-bit words.
Proof. Each of these properties is trivial to prove by induction on n with case
distinction on bn−1 and the content of the input register containing the most
significant bits of the operand of the operation, respectively, in both the basis
step and the inductive step.
⊓
⊔
For convenience’s sake, we define some special cases of the parameterized
instruction sequences for transferring n-bit words (0 < m < n):
n−m
ZPAD m
, d:l+m) ,
n (d:l) , SET n−m (0

MVH m
n (s:k, d:l) , MOV m (s:k+(n−m), d:l) ,
MVLm
n (s:k, d:l) , MOV m (s:k, d:l) ,
where s ranges over {in, aux}, d ranges over {aux, out}, and k, l range over N+ .
ZPAD m
n is meant for turning a stored m-bit word into a stored n-bit word by
10

m
zero padding. MVH m
n and MVLn are meant for transferring only the m most
significant bits and the m least significant bits, respectively, of a stored n-bit
word.
The Karatsuba multiplication algorithm as usually described involves multiplication on n-bit words (0 < n ≤ 3). For multiplication, which can be defined in
terms of the above-mentioned basic operations, we also define a parameterized
instruction sequence computing it according to the long multiplication algorithm:

MULn (s1 :k1 , s2 :k2 , d:l) ,
MOV n (s1 :k1 , S1 ) ; ZPAD n2n (S1 ) ; SET 2n (02n , S2 ) ;
n−1
1
i=0 (−s2 :k2 +i.get ; #li ; ADD n+i+1 (S1 , S2 , S2 ) ; SHLn+i+1 (S1 , S1 )) ;
MOV 2n (S2 , d:l) ,
where li = len(ADD n+i+1 (S1 , S2 , S2 )) + 1 ,

;

where s1 , s2 range over {in, aux}, d ranges over {aux, out}, and k1 , k2 , l range over
N+ . The additions are done on the fly and the shifts are restricted to shifts by
one position by shifting the result of all preceding shifts.
Proposition 4. Let n ∈ N be such that 0 < n ≤ N . Then the function on
bit strings of length n computed by MULn (I1 , I2 , O) ; ! models multiplication on
natural numbers less than 2n with respect to their binary representation by n-bit
words.
Proof. We prove a stronger property that also covers the final contents of the
2n successive auxiliary registers starting with the one named S1 and the 2n
successive auxiliary registers starting with the one named S2 . This stronger
property is easy to prove, using Propositions 2 and 3, by induction on n with case
distinction on the content of the input register containing the most significant
bit of the second operand of the operation concerned in both the basis step and
the inductive step.
⊓
⊔
The calculation of the lengths of the parameterized instruction sequences
defined above is a matter of simple additions and multiplications. The lengths
of these instruction sequences are as follows:
len(SHLm
n (s:k, d:l)) = 3 · n − 2 · m ,
len(ADD n (s1 :k1 , s2 :k2 , d:l)) = 21 · n + 1 ,
len(SUB n (s1 :k1 , s2 :k2 , d:l)) = 21 · n + 1 ,
len(SET n (b0 . . . bn−1 , d:l)) = n ,
len(MOV n (s:k, d:l)) = 3 · n ,
len(ZPAD m
n (d:l)) = n − m ,
m
len(MVH n (s:k, d:l)) = 3 · m ,
len(MVLm
n (s:k, d:l)) = 3 · m ,
len(MULn (s1 :k1 , s2 :k2 , d:l)) = 36 · n2 + 24 · n + 1 .
11

The instruction sequences defined in this section do compute the intended
operations in case of fully coinciding n-bit words. The instruction sequences
defined for addition and transfer of a stored word in [5] do not compute the
intended operations in case of fully coinciding n-bit words.

6

Long Multiplication and Karatsuba Multiplication

In this section, we describe and analyze instruction sequences that express the
long multiplication algorithm and the Karatsuba multiplication algorithm, using
the definitions given in Sections 4 and 5. The latter algorithm is applicable only
if N ≥ 3.
LMULN is the instruction sequence described by
MULN (I1 , I2 , O) ; ! .
We know by Proposition 4 that LMULN computes the function on bit strings
that models multiplication on natural numbers less than 2N with respect to
their binary representation by N -bit words. It does so according to the long
multiplication algorithm.
Proposition 5. len(LMULN ) = 36 · N 2 + 24 · N + 2.
Proof. This is trivial because len(LMULN ) = len(MULN (I1 , I2 , O)) + 1.

⊓
⊔

KMULN , where N ≥ 3, is the instruction sequence described by
⌈log (N −2)⌉

⌈log2 (N −2)⌉

MOV N (I1 , I1 2
) ; MOV N (I2 , I2
⌈log 2 (N −2)⌉
KMAN ; MOV 2N (O
, O) ; ! ,

);

where KMAn is inductively defined in Table 1. KMULN computes the function
on bit strings that models multiplication on natural numbers less than 2N with
respect to their binary representation by n-bit words according to the Karatsuba
multiplication algorithm.
In order to compute the binary representation of the product of two natural
numbers with binary representations of length n by dividing the computation
into the computations of the binary representations of three products as required
by the Karatsuba multiplication algorithm, the instruction sequence KMAn contains the instruction sequences KMA⌊n/2⌋ , KMA⌈n/2⌉ , and KMA⌈n/2⌉+1 . Each
of these three instruction sequences is immediately preceded by an instruction
sequence that transfers the binary representations of the two natural numbers
of which it has to compute the binary representation of their product into the
appropriate Boolean registers for the instruction sequence concerned. Moreover,
each of these three instruction sequences is immediately followed by an instruction sequence that transfers the binary representation of the product that it
has computed into the appropriate Boolean registers for KMAn . The tail end
of KMAn completes the computation by performing some operations on the
three binary representations of products computed before as required by the
12

Table 1. Definition of KMAn (1 ≤ n ≤ N )

if n ≤ 3 then:
ℓ(n)

KMAn = MULn (I1

ℓ(n)

, I2

,O

ℓ(n)

),

if n > 3 then:
KMAn =
ℓ(n)

MVH n⌊n/2⌋ (I1

ℓ(⌊n/2⌋)

, I1

ℓ(n)

) ; MVH n⌊n/2⌋ (I2

KMA⌊n/2⌋ ; MOV 2⌊n/2⌋ (O
ℓ(n) ℓ(⌈n/2⌉)
MVLn⌈n/2⌉ (I1 , I1
)

ℓ(⌊n/2⌋)

;

KMA⌈n/2⌉ ; MOV 2⌈n/2⌉ (O

ℓ(n)
, P1 )

ℓ(⌊n/2⌋)

, I2

;

ℓ(n) ℓ(⌈n/2⌉)
MVLn⌈n/2⌉ (I2 , I2
)

ℓ(⌈n/2⌉)

ℓ(n)

, P2

);

;

);

ℓ(n)
MVH n⌊n/2⌋ (I1 , T1 )

⌊n/2⌋
; ZPAD ⌈n/2⌉+1 (T1 ) ;
ℓ(⌈n/2⌉+1)
⌈n/2⌉
ℓ(n)
)
MVLn⌈n/2⌉ (I1 , T2 ) ; ZPAD ⌈n/2⌉+1 (T2 ) ; ADD ⌈n/2⌉+1 (T1 , T2 , I1
ℓ(n)

MVH n⌊n/2⌋ (I2

ℓ(n)

MVLn⌈n/2⌉ (I2

⌊n/2⌋

, T1 ) ; ZPAD ⌈n/2⌉+1 (T1 ) ;

KMA⌈n/2⌉+1 ; MOV 2(⌈n/2⌉+1) (O
ℓ(n)

ZPAD 2(⌈n/2⌉+1) (P1
2(⌈n/2⌉+1)

ℓ(n)

(P1

ℓ(⌈n/2⌉+1)

ℓ(n)
, P3 )
ℓ(n)

2⌈n/2⌉

) ; ZPAD 2(⌈n/2⌉+1) (P2

ℓ(n)
ℓ(n)
SUB 2(⌈n/2⌉+1) (P3 , P1 , T1 )

ZPAD 2n

ℓ(⌈n/2⌉+1)

⌈n/2⌉

, T2 ) ; ZPAD ⌈n/2⌉+1 (T2 ) ; ADD ⌈n/2⌉+1 (T1 , T2 , I2

2⌊n/2⌋

;

;

);
ℓ(n)

; SUB 2(⌈n/2⌉+1) (T1 , P2

2(⌈n/2⌉+1)

) ; ZPAD 2n

⌈n/2⌉
SHL2n (T1 , T1 )

ℓ(n)

(P2

2⌈n/2⌉
ℓ(n)
SHL2n
(P1 , T2 )

;

ADD 2n (T2 , T1 , T1 ) ;

ℓ(n)
ℓ(n)
ADD 2n (T1 , P2 , O
)

);

, T1 ) ;

2(⌈n/2⌉+1)

) ; ZPAD 2n

(T1 ) ;

;
,

where ℓ(m) = ⌈log2 (m − 2)⌉.
Karatsuba multiplication algorithm. For the rest, instruction sequences for zero
padding are scattered over KMAn where necessary to obtain the locally right
length of binary representations of natural numbers.
Proposition 6. If N ≥ 3, then the function on bit strings of length N computed
by KMULN models multiplication on natural numbers less than 2N with respect
to their binary representation by N -bit words.
Proof. It is straightforward to prove this by induction on N , using the equations
from Section 3 that form the basis of the Karatsuba multiplication algorithm
and Propositions 2, 3, and 4.
⊓
⊔
The following proposition gives a lower estimate and an upper estimate for
the length of KMULN .
13

Proposition 7. If N ≥ 3, then:
len(KMULN ) ≥ 1184 · 3⌊log2 (N )⌋−1 − 716 · 2⌊log2 (N )⌋−1 + 12 · N − 70 ,
len(KMULN ) ≤ 1005 · 3⌈log2 (N −2)⌉ − 358 · 2⌈log2 (N −2)⌉ + 12 · N − 249 .
Proof. Because len(KMULN ) = len(KMAN ) + 16 · N + 1, we have to prove that
len(KMAN ) ≥ 1184 · 3⌊log2 (N )⌋−1 − 716 · 2⌊log2 (N )⌋−1 − 71 ,
len(KMAN ) ≤ 1005 · 3⌈log2 (N −2)⌉ − 358 · 2⌈log2 (N −2)⌉ − 250 .
Let c1 = len(MUL1 ), c2 = len(MUL2 ), c3 = len(MUL3 ), and for each n > 3,
cn = len(KMAn ) − len(KMA⌊n/2⌋ ) − len(KMA⌈n/2⌉ ) − len(KMA⌈n/2⌉+1 ). Using
the already calculated lengths of the parameterized instruction sequences defined
in Section 5, we obtain by simple calculations that c1 = 61, c2 = 193, c3 = 397,
and for each n > 3, cn = 126 · ⌈n/2⌉ + 116 · n + 142. Let c′0 = c3 , c′′0 = c3 , and for
each m > 0, c′m = c2m +2 and c′′m = c2m+1 . In other words, c′0 = 397, c′′0 = 397,
and for each m > 0, c′m = 358 · 2m−1 + 500 and c′′m = 358 · 2m + 142. Because
⌊x⌋ = k iff k ≤ x < k + 1, ⌈x⌉ = k iff k − 1 < x ≤ k, and log2 (x) = y iff x = 2y ,
it is clear that cn ≤ c′m if m = ⌈log2 (n − 2)⌉ and cn ≥ c′′m if m = ⌊log2 (n)⌋ − 1.
Let M = ⌈log2 (N − 2)⌉, and let m ≤ M . It follows directly from the proof of
the proposition at the end of Section 4 that, for all n such that m = ⌈log2 (n − 2)⌉,
the deepest level of recursion at which KMAn occurs is M − m. Moreover, it
follows directly from the definition of KMAn that, for all n > 0, KMAn occurs at this level only if n is less than or equal to the greatest n′ such that
m = ⌈log2 (n′ − 2)⌉. We also have that cn ≤ cn′ if n ≤ n′ , and cn′ ≤ c′m if
P
′
M−i
m = ⌈log2 (n′ − 2)⌉. All this means that len(KMAN ) ≤ M
). In other
i=0 (ci · 3
P
M
M
i−1
M−i
words, len(KMAN ) ≤ 397 · 3 + i=1 ((358 · 2
+ 500) · 3
). Using elemenP
tary properties of sums and the property that ki=0 xi = (1 − xk+1 )/(1 − x), we
PM
obtain 397 · 3M + i=1 ((358 · 2i−1 + 500) · 3M−i ) = 397 · 3M + 358 · (3M − 2M ) +
500 · ((3M − 1)/2) = 1005 · 3M − 358 · 2M − 250. Hence, because M =
⌈log2 (N − 2)⌉, len(KMAN ) ≤ 1005 · 3⌈log2 (N −2)⌉ − 358 · 2⌈log2 (N −2)⌉ − 250.
Let M ′ = ⌊log2 (N )⌋ − 1, and let m ≤ M ′ . We can show similarly to above
that, for all n such that m = ⌊log2 (n)⌋ − 1, the least deep level of recursion
at which KMAn occurs is M ′ − m. Moreover, it follows directly from the definition of KMAn that, for all n > 0, KMAn occurs at this level only if n is
greater than or equal to the least n′ such that m = ⌊log2 (n′ )⌋ − 1. We also
have that cn ≥ cn′ if n ≥ n′ , and cn′ ≥ c′′m if m = ⌊log2 (n′ )⌋ − 1. All this
PM ′ ′′ M ′ −i
). In other words, len(KMAN ) ≥
means that len(KMAN ) ≥
i=0 (ci · 3
PM ′
i
M ′ −i
M′
). Using the same properties of sums
397 · 3 + i=1 ((358 · 2 + 142) · 3
PM ′
′
′
M′
as before, we obtain 397 · 3 + i=1 ((358 · 2i + 142) · 3M −i ) = 397 · 3M +
′
′
′
′
′
358 · (2 · (3M − 2M )) + 142 · ((3M − 1)/2) = 1184 · 3M − 716 · 2M − 71.
Hence, because M ′ = ⌊log2 (N )⌋ − 1, len(KMAN ) ≥ 1184 · 3⌊log2 (N )⌋−1 −
716 · 2⌊log2 (N )⌋−1 − 71.
⊓
⊔
It is unclear to us whether it is practically possible to improve the lower estimate
and upper estimate for the length of KMULN considerably.
14

The following is a corollary of Propositions 5 and 7.
Corollary 1. len(LMULN ) = Θ(N 2 ) and len(KMULN ) = Θ(N log2 (3) ) =
Θ(N 1,5849... ).
This corollary can be paraphrased as follows: the length of the instruction sequences LMULN and KMULN , which express the long multiplication algorithm
and the Karatsuba multiplication algorithm, are asymptotically bounded, up to
a constant factor, both above and below by N 2 and N log2 (3) , respectively. It
is striking because these algorithms are known to compute the function that
models multiplication on natural numbers less than 2N with respect to their binary representation by N -bit words also in time asymptotically bounded, up to
a constant factor, both above and below by N 2 and N log2 (3) , respectively. This
suggests, like some results from [7], that instruction sequence size and computation time are polynomially related measures.
Using Propositions 5 and 7, it is easy to check that (a) LMULN is longer than
KMULN only if N > 264 and (b) LMULN is longer than KMULN if N > 6666.
On that account, the following is another corollary of Propositions 5 and 7.
Corollary 2. N > 28 if len(LMULN ) > len(KMULN ) and len(LMULN ) >
len(KMULN ) if N > 213 .
In the area of algorithm efficiency, like in the area of computational complexity,
the focus is mainly on asymptotic properties of algorithms, like Corollary 1. To
our knowledge, there is virtually no attention in this area to properties related to
crossover points between algorithms, like Corollary 2. We think that properties
of the latter kind are frequently more relevant to practice than properties of
the former kind. However, existing knowledge about crossover points between
algorithms is mainly based on experimental data which are highly dependent on
the computer, operating system, programming language and compiler used in
the experiment. Moreover, if this kind of knowledge is referred to at all, it is often
turned into the form of a rule of thumb. For example, the following statement
and minor variants of it can be found at many places (webpages, articles, and
books) without further justification: “As a rule of thumb, Karatsuba is usually
faster when the multiplicands are longer than 320-640 bits” (see e.g. [19]).
It is obvious that LMULN and KMULN need the same number of input
registers and the same number of output registers. However, the number of auxiliary registers used by KMULN is always greater than the number of auxiliary
registers used by LMULN . The number of auxiliary registers used by KMULN is
10 · N · ⌈log2 (N − 2)⌉ + 18 · N + 1 and the number of auxiliary registers used by
LMULN is only 4 ·N + 1. In the instance that N = 28 , these numbers correspond
to ±3K bytes and ±128 bytes, respectively; and in the instance that N = 213 ,
these numbers correspond to ±148K bytes and ±4K bytes, respectively.
In this paper, we do not answer the question whether there exist instruction sequences shorter than LMULN and KMULN that express the long multiplication algorithm and Karatsuba multiplication algorithm, respectively. The
practical problem with proving or disproving the existence of shorter instruction
sequences is that it needs basically an extremely extensive case distinction. We
15

expect that, if the length of LMULN and/or KMULN can be reduced, it cannot
be reduced much. The reason for this is that we have striven in Section 5 for
instruction sequences without unreachable subsequences, different suffixes with
the same behaviour on execution, and jump instruction that can be eliminated
without introducing different suffixes with the same behaviour on execution.

7

Long Multiplication and Backward Jump Instructions

In this section, a minor variant of the long multiplication algorithm is expressed
by an instruction sequence that contains a backward jump instruction in addition
to instructions to set and get the content of Boolean registers, forward jump
instructions, and a termination instruction.
We use the fragment without repetition operator of an extension of PGA
with, for each l ∈ N, a backward jump instruction \#l as additional primitive
instruction. On execution of an instruction sequence, the effect of a backward
jump instruction \#l is that execution proceeds with the lth previous primitive
instruction of the instruction sequence concerned — if l equals 0 or there is
no primitive instruction to proceed with, inaction occurs. We write PGAbj for
the above-mentioned extension of PGA. For a mathematically precise treatment
of PGAbj without repetition operator, we refer to the treatment of C, which
is a variant of PGA, in [10]. The fragment of PGAbj without the repetition
operator coincides with the fragment of C without backward instructions other
than backward jump instructions.
The additional basic operations on words that are relevant in this section
are the operations that model Euclidean division by 2m , decrement by 1, and
nonzero test on natural numbers less than 2n , with respect to their representation
by n-bit words (0 < n ≤ N , 0 < m < n). The operation modeling Euclidean
division by 2m is commonly known as “shift right by m positions”. For these
operations, we define parameterized instruction sequences computing them in
case the parameters are properly instantiated (see below):
SHRm
n (s:k, d:l) ,
n−1−m
(+s:k+m+i.get ; −d:l+i.set:1 ; d:l+i.set:0) ;
i=0

;
; (d:l+n−m+i.set:0) ,
DEC (s:k, d:l) ,
; (−s:k+i.get ; #3 ; d:l+i.set:0 ; #5 ; d:l+i.set:1) ; #1 ; #1 ; #1 ,
ISNZ (s:k) ,
; (+s:k+i.get ; #2) ; #2 ,
m−1
i=0
n
n−1
i=0

n
n−1
i=0

where s ranges over {in, aux}, d ranges over {aux, out}, and k, l range over N+ .
For each of the first two parameterized instruction sequences, the first parameter
correspond to the operand of the operation concerned and the second parameter
corresponds to the result of the operation concerned. The intended operations
16

are computed provided that the instantiation of the first parameter and the
instantiation of the second parameters do not lead to partially coinciding n-bit
words. In this section, this condition will always be satisfied. No result is stored
on execution of ISNZ n . Instead, the first primitive instruction following ISNZ n
is skipped if the nonzero test fails.
Proposition 8. Let n, m ∈ N be such that 0 < n ≤ N and 0 < m < m. Then
the function on bit strings of length n computed by
m
1. SHRm
modulo 2n on natural numn (I1 , O) ; ! models Euclidean division by 2
n
bers less than 2 with respect to their binary representation by n-bit words;
2. DEC n (I1 , O) ; ! models subtraction by 1 modulo 2n on natural numbers less
than 2n with respect to their binary representation by n-bit words;
3. ISNZ n (I1 ) ; +O.set:1 ; O.set:0 ; ! models the function isnz from natural numbers less than 2n to natural numbers less than 21 defined by isnz (0) = 0 and
isnz (k + 1) = 1 with respect to their binary representation by n-bit words
and 1-bit words, respectively.

Proof. Each of these properties is easy to prove by induction on n with case
distinction on the content of the input register containing the most significant
bit of the operand of the operation concerned in both the basis step and the
inductive step.
⊓
⊔
The lengths of the parameterized instruction sequences defined above are as
follows:
len(SHR m
n (s:k, d:l)) = 3 · n − 2 · m ,
len(DEC n (s:k, d:l)) = 5 · n + 3 ,
len(ISNZ n (s:k)) = 2 · n + 1 .
For each bit of the representation of the multiplier, LMULN contains a different instruction sequence. This seems to exclude the use of backward jump
instructions to obtain an instruction sequence of significantly shorter length, unless provision is made for some form of indirect addressing for Boolean registers.
However, there exists a minor variant of the long multiplication algorithm that
makes it possible to have the same instruction sequence for each bit of the representation of the multiplier. From the least significant bit of the representation
of the multiplier onwards, the algorithm concerned shifts the representation of
the multiplier by one position to the right after it has dealt with a bit. In this
way, the next bit remains the least significant one throughout.
We proceed with describing an instruction sequence without backward jump
instructions that expresses this minor variant of the long multiplication algorithm.
LMUL′N is the instruction sequence described by
2N
, S2 ) ; MOV N (I2 , T1 ) ;
MOV N (I1 , S1 ) ; ZPAD N
2N (S1 ) ; SET 2N (0

N
−T1 .get ; #l ; ADD 2N (S1 , S2 , S2 ) ; SHL12N (S1 , S1 ) ; SHR1N (T1 , T1 ) ;
MOV 2N (S2 , O) ; ! ,
17

where
l = len(ADD 2N (S1 , S2 , S2 )) + 1 = 42 · N + 2 .
Proposition 9. The function on bit strings of length N computed by LMUL′N
models multiplication on natural numbers less than 2N with respect to their binary representation by N -bit words.
Proof. We prove a stronger property that also covers the final contents of the
2N successive auxiliary registers starting with the one named S1 , the 2N successive auxiliary registers starting with the one named S2 , and the N successive
auxiliary registers starting with the one named T1 . This stronger property is
straightforward to prove, using Propositions 2, 3, and 8, by induction on N with
case distinction on the content of the input register containing the most significant bit of the second operand of the operation concerned in both the basis step
and the inductive step.
⊓
⊔
Proposition 10. len(LMUL′N ) = 51 · N 2 + 14 · N + 1.
Proof. This is a matter of simple additions, subtractions, and multiplications.
⊓
⊔
The following is a corollary of Propositions 5 and 10.
Corollary 3. len(LMUL′N ) > len(LMULN ).
For each bit of the representation of the multiplier, LMUL′N contains the same
instruction sequence. That is, it contains N duplicates of the same instruction
sequence. This duplication can be eliminated by implementing a for loop by
means of a backward jump instruction.
We proceed with describing an instruction sequence with a backward jump
instruction that expresses the minor variant of the long multiplication algorithm.
We write N for the shortest representation of the natural number N in the binary
number system.
LMUL′′N is the instruction sequence described by
2N
MOV N (I1 , S1 ) ; ZPAD N
, S2 ) ; MOV N (I2 , T1 ) ;
2N (S1 ) ; SET 2N (0
SET ⌊log2 (N )⌋+1 (N , T2 ) ;
−T1 .get ; #l1 ; ADD 2N (S1 , S2 , S2 ) ; SHL12N (S1 , S1 ) ; SHR1N (T1 , T1 ) ;
DEC ⌊log2 (N )⌋+1 (T2 , T2 ) ; ISNZ ⌊log2 (N )⌋+1 (T2 ) ; \#l2 ;
MOV 2N (S2 , O) ; ! ,

where
l1 = len(ADD 2N (S1 , S2 , S2 )) + 1 = 42 · N + 2 ,
l2 = len(−T1 .get ; . . . ; ISNZ ⌊log2 (N )⌋+1 (T2 )) = 51 · N + 7 · ⌊log2 (N )⌋ + 10 .
Proposition 11. The function on bit strings of length N computed by LMUL′′N
models multiplication on natural numbers less than 2N with respect to their binary representation by N -bit words.
18

Proof. We prove a stronger property that also covers the final contents of the
2N successive auxiliary registers starting with the one named S1 , the 2N successive auxiliary registers starting with the one named S2 , the N successive
auxiliary registers starting with the one named T1 , and the ⌊log2 (N )⌋ + 1 successive auxiliary registers starting with the one named T2 . This stronger property
is straightforward to prove, using Propositions 2, 3, and 8, by induction on N
with case distinction on the content of the input register containing the most
significant bit of the second operand of the operation concerned in both the basis
step and the inductive step.
⊓
⊔
Proposition 12. len(LMUL′′N ) = 66 · N + 8 · ⌊log2 (N )⌋ + 13.
Proof. This is a matter of simple additions, subtractions, and multiplications.
⊓
⊔
The following is a corollary of Propositions 5, 10, and 12.
Corollary 4. len(LMUL′′N ) = Θ(N ) while both len(LMULN ) = Θ(N 2 ), and
len(LMUL′N ) = Θ(N 2 ).
Hence, LMUL′′N is asymptotically shorter than both LMULN and LMUL′N . By
Corollary 1, we know that LMUL′′N is asymptotically shorter than KMULN too.
The following is a corollary of Propositions 5, 7, 10, and 12.
Corollary 5. len(LMUL′′N ) < len(LMULN ) and len(LMUL′′N ) < len(LMUL′N )
if N > 1, and what is more, len(LMUL′′N ) < len(KMULN ) if N > 2.
Hence, LMUL′′N is already shorter than LMULN , LMUL′N , and KMULN if N
is still very small. In fact, long multiplication is non-trivial only if N > 1 and
Karatsuba multiplication is applicable only if N > 2.

8

Long Multiplication and the Halting Problem

In this section, we argue that the instruction sequences LMUL′N and LMUL′′N
from Section 7 form a hard witness of the inevitable existence of a halting problem in the practice of imperative programming.
Turing’s result regarding the undecidability of the halting problem (see
e.g. [18]) is a result about Turing machines. In [2], we consider it as a result about
programs rather than machines, taking instruction sequences as programs. The
instruction sequences concerned are essentially the finite instruction sequences
that can be denoted by closed PGAbj terms. Unlike in the current paper, the
basic instructions are not fixed, but their effects are restricted to the manipulation of something that can be understood as the content of the tape of a Turing
machine with a specific tape alphabet, together with the position of the tape
head. Different choices of basic instructions give rise to different halting problem instances and one of these instances is essentially the same as the halting
problem for Turing machines. Because of their orientation to Turing machines,
we consider all instances treated in [2] theoretical halting problem instances.
19

All halting problem instances would evaporate if the instruction sequences
concerned would be restricted to the ones without backward jump instructions.
This is irrespective of whether the effects of the basic instructions have anything to do with the manipulation of a Turing machine tape. In the case that we
have basic instructions to set and get the content of Boolean registers, instruction sequences without backward jump instructions are sufficient to compute all
n
m
functions f :{0, 1} → {0, 1} (n, m ∈ N). This raises the question whether there
exists a good reason for not abandoning backward jump instructions altogether
in such cases. The function that models multiplication on natural numbers less
than 2N with respect to their binary representation by N -bit words offers a good
reason: the length of the instruction sequence that computes it according to the
long multiplication algorithm can be reduced significantly by the use of backward jump instructions. The length of the instruction sequence that computes
this function can be reduced even more by the use of backward jump instructions
than by going over to one of the multiplication algorithms that are known to
yield shorter instruction sequences without backward jump instructions than the
long multiplication algorithm such as for example the Karatsuba multiplication
algorithm.
Thus, the instruction sequences LMUL′N and LMUL′′N form a hard witness
of the inevitable existence of a halting problem in the practice of imperative programming, where programs must have manageable size. Because of its orientation to actual programming, we consider the halting problem for the instruction
sequences with forward and backward jump instructions, and with only basic
instructions to set and get the content of Boolean registers, a practical halting
problem. It is unknown to us whether there is a connection between the solvability or unsolvability of the halting problem for these instruction sequences
and some form of diagonal argument. It is easy to prove that this halting problem is both NP-hard and coNP-hard. We do not know whether stronger lower
bounds for its complexity can be found in the literature. An extensive search for
such lower bounds and other result concerning this halting problem or a similar
halting problem has been unsuccessful.

9

Concluding Remarks

We have described finite instruction sequences, containing only instructions to
set and get the content of Boolean registers, forward jump instructions, and a
termination instruction, that compute the function that models multiplication
on natural numbers less than 2N with respect to their binary representation
by N -bit words according to the long multiplication algorithm and the Karatsuba multiplication algorithm. We have described those instruction sequences by
means of terms of PGA, an algebraic theory of single-pass instruction sequences.
Thus, we have provided mathematically precise alternatives to the natural language and pseudo code descriptions of these multiplication algorithms
found in mathematics and computer science literature on multiplication algorithms. Moreover, we have calculated the exact size of the instruction se20

quence LMULN expressing the long multiplication algorithm and lower and upper estimates for the size of the instruction sequence KMULN expressing the
Karatsuba multiplication algorithm. We have among other things found that:
(a) len(LMULN ) = Θ(N 2 ) and len(KMULN ) = Θ(N log2 (3) ); (b) N > 28 if
len(LMULN ) > len(KMULN ), and len(LMULN ) > len(KMULN ) if N > 213 .
It is suggested by (a) that instruction sequence size and computation time are
polynomially related measures. It is still an open question whether this is the
case.
As a bonus, we have found that the number of auxiliary registers used by
LMULN is 4 · N + 1 and the number of auxiliary registers used by KMULN is
10 ·N · ⌈log2 (N − 2)⌉+ 18 · N + 1. It is also an open question whether the number
of auxiliary registers that are used by an instruction sequence and computation
space are related measures.
We have also gone into the use of an instruction sequence with backward
jump instructions for expressing the long multiplication algorithm. We have
described a finite instruction sequence LMUL′′N containing a backward jump instruction, in addition to the instructions to set and get the content of Boolean
registers, forward jump instructions, and a termination instruction, that expresses a minor variant of the long multiplication algorithm. We have calculated
the exact size of this instruction sequence and have among other things found
that: (a) len(LMUL′′N ) = Θ(N ); (b) len(LMUL′′N ) < len(LMULN ) if N > 1,
and len(LMUL′′N ) < len(KMULN ) if N > 2. Furthermore, we have related these
findings to the halting problem.
Acknowledgements
We thank Dimitri Hendriks from the VU University Amsterdam for carefully
reading a draft of this paper and for pointing out an error in it.

References
1. Bergstra, J.A., Loots, M.E.: Program algebra for sequential code. Journal of Logic
and Algebraic Programming 51(2), 125–156 (2002)
2. Bergstra, J.A., Middelburg, C.A.: Instruction sequence processing operators. Acta
Informatica 49(3), 139–172 (2012)
3. Bergstra, J.A., Middelburg, C.A.: Instruction Sequences for Computer Science,
Atlantis Studies in Computing, vol. 2. Atlantis Press, Amsterdam (2012)
4. Bergstra, J.A., Middelburg, C.A.: Instruction sequence expressions for the Karatsuba multiplication algorithm. arXiv:1312.1529v2 [cs.PL] (2013)
5. Bergstra, J.A., Middelburg, C.A.: Instruction sequence expressions for the secure
hash algorithm SHA-256. arXiv:1308.0219v6 [cs.PL] (2013)
6. Bergstra, J.A., Middelburg, C.A.: Long multiplication by instruction sequences
with backward jump instructions. arXiv:1312.1812v3 [cs.PL] (2013)
7. Bergstra, J.A., Middelburg, C.A.: Instruction sequence based non-uniform complexity classes. Scientific Annals of Computer Science 24(1), 47–89 (2014)

21

8. Bergstra, J.A., Middelburg, C.A.: On algorithmic equivalence of instruction sequences for computing bit string functions. Fundamenta Informaticae 138(4), 411–
434 (2015)
9. Bergstra, J.A., Middelburg, C.A.: Instruction sequence size complexity of parity.
Fundamenta Informaticae 149(3), 297–309 (2016)
10. Bergstra, J.A., Ponse, A.: An instruction sequence semigroup with involutive antiautomorphisms. Scientific Annals of Computer Science 19, 57–92 (2009)
11. Cook, S.A.: On the Minimum Computation Time of Functions. Ph.D. thesis, Harvard University, Cambridge, MA (1966)
12. Fürer, M.: Faster integer multiplication. SIAM Journal of Computing 39(3), 979–
1005 (2009)
13. Karatsuba, A.A.: The complexity of computations. Proceedings of the Steklov
Institute of Mathematics 211, 169–183 (1995)
14. Karatsuba, A.A., Ofman, Y.P.: Multiplication of multidigit numbers on automata.
Doklady Akademii Nauk SSSR 145(2), 293–294 (1962), in Russian
15. Middelburg, C.A.: Instruction sequences as a theme in computer science. https:
//instructionsequence.wordpress.com/ (2015)
16. Schönhage, A., Strassen, V.: Schnelle Multiplikation großer Zahlen. Computing
7(3–4), 281–292 (1971)
17. Toom, A.A.: The complexity of a scheme of functional elements simulating the
multiplication of integers. Doklady Akademii Nauk SSSR 150(2), 496–498 (1963),
in Russian
18. Turing, A.M.: On computable numbers, with an application to the Entscheidungs
problem. Proceedings of the London Mathematical Society, Series 2 42, 230–265
(1937), correction: ibid, 43, 544–546 (1937)
19. Karatsuba algorithm. In Wikipedia (2017), retrieved on November 12, 2017, from
http://en.wikipedia.org/wiki/Karatsuba algorithm
20. Secure Hash Standard. National Institute of Standards and Technology, FIPS PUB
180-4 (2012)

22

