Long Multiplication by Instruction Sequences
with Backward Jump Instructions

arXiv:1312.1812v3 [] 6 Apr 2014

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. Backward
jump instructions are not necessary for this, but instruction sequences
can be significantly shorter with them. We take the function on bit strings
that models the multiplication of natural numbers on their representation in the binary number system to demonstrate this by means of a
concrete example. The example is reason to discuss points concerning
the halting problem and the concept of an algorithm.
Keywords: single-pass instruction sequence, backward jump instruction,
bit string function, long multiplication, algorithm, halting problem, indirect addressing.
1998 ACM Computing Classification: F.1.1, F.2.1.

1

Introduction

In [5], an approach to non-uniform complexity is presented which is based on
the simple idea that, for each function on bit strings, its restriction to bit strings
of any given length can be computed by an instruction sequence that contains
only instructions to set and get the content of Boolean registers, forward jump
instructions, and a termination instruction. It is among other things shown that
a function on bit strings whose result is a bit string of length 1 belongs to
P/poly iff it can be computed by polynomial-length instruction sequences of
this kind. In [1], instruction sequences are considered which contain backward
jump instructions in addition to the above-mentioned instructions. It is among
other things shown that a function on bit strings whose result is a bit string of
length 1 belongs to PSPACE/poly iff it can be computed by polynomial-length
instruction sequences of this latter kind.
It is known that NP ⊆ PSPACE/poly (see e.g. [15]). Under the assumption
that the reasonable complexity theoretic conjecture that NP 6⊆ P/poly (see
e.g. [18]) is right, it then follows that there exists a function on bit strings that can
be computed by polynomial-length instruction sequences with backward jump
instructions and cannot be computed by polynomial-length instruction sequences

without backward jump instructions. With this it remains among other things
unanswered whether there exists a function on bit strings that can be computed
by linear-length instruction sequences with backward jump instructions while
it is commonly assumed that the function concerned cannot be computed by
linear-length instruction sequences without backward jump instructions. In this
paper, we answer this question in the affirmative by means of a concrete example
from binary arithmetic.
In [7], a description is given of instruction sequences of the kind used in [5]
that compute the hash function SHA-256 according to the algorithm whose
pseudo-code description serves as the definition of SHA-256 in the Secure Hash
Standard [27]. In [6], a description is given of instruction sequences of the kind
used in [5] that compute the function on bit strings that models the multiplication of natural numbers on their binary representation according to the
Karatsuba multiplication algorithm [16,17] and a description is given of instruction sequences of this kind that compute this function according to the standard
multiplication algorithm, which is known as the long multiplication algorithm.
Thus, mathematically precise alternatives are provided to the natural language
and pseudo-code descriptions of these algorithms found in the literature on them.
In [6], the descriptions are further used to determine lower and upper estimates for the length of the representation in the binary number system of natural
numbers at which the Karatsuba multiplication algorithm becomes more efficient
than the long multiplication algorithm. As expected, the function on bit strings
that models the multiplication of natural numbers on their representation in the
binary number system can be computed according to the long multiplication
algorithm by quadratic-length instruction sequences without backward jump instructions. Although it would not make the algorithm more efficient, it would be
of practical value if this could be reduced to linear-length instruction sequences
with backward jump instructions. At first sight, this seems impossible unless
provision is made for some form of indirect addressing for Boolean registers.
However, using a minor variant of the long multiplication algorithm, we will
show in this paper that such a reduction is possible without making provision
for some form of indirect addressing. Riding off on an interesting side-issue, we
will also sketch that even further reduction is possible if provision is made for
some form of indirect addressing for Boolean registers.
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 [2]. The
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
1

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

2

As a continuation of this work on an approach to programming language
semantics, (a) the notion of an instruction sequence was subjected to systematic
and precise analysis using the groundwork laid earlier and (b) selected issues
relating to well-known subjects from the theory of computation and the area of
computer architecture were rigorously investigated thinking in terms of instruction sequences (see e.g. [4]). As in the work referred to above, the work presented
in this paper is carried out in the setting of program algebra. Different from usual
in the work referred to above, but as in the work presented in [6,7], the accent is
this time on a practical issues such as efficiency of algorithms and compactness
of instruction sequences.
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).
Next, we describe how we deal with n-bit words by means of Boolean registers
(Section 3) and how we compute the basic operations on n-bit words that are
used in the multiplication algorithms (Section 4). Then, we show that the function that models the multiplication of natural numbers on their representation in
the binary number system can be computed according to a minor variant of the
long multiplication algorithm by quadratic-length instruction sequences without backward jump instructions and by linear-length instruction sequences with
backward jump instructions (Section 5). After that, we discuss two points, concerning the halting problem and the concept of an algorithm, which were raised
by the preceding material (Sections 6 and 7). Following this, we sketch that
for the algorithm under consideration further reduction is possible if provision
is made for some form of indirect addressing for Boolean registers (Section 8).
Finally, we make some concluding remarks (Section 9).
The preliminaries to the work presented in this paper are the same as the
preliminaries to the work presented in [6,7], which are in turn a selection from
the preliminaries to the work presented in [5]. 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 [4].

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 [5].
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
3

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
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
4

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.
We are also interested in the 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 PGA with these additional primitive
instructions.
Regarding the behaviours produced by finite instruction sequences with backward jump instructions under execution, we refer to the treatment of C, which
is a variant of PGA, in [9]. The fragment of PGAbj without the repetition operator coincides with the fragment of C without backward instructions other than
backward jump instructions.
n
m
Let n, m ∈ N, let f : {0, 1} → {0, 1} , and let X be a finite instruction
sequence that can be denoted by a closed PGA or PGAbj 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 .
∗
∗
∗
Let f : {0, 1} → {0, 1} be such that for all β, β ′ ∈ {0, 1} , len(β) = len(β ′ )
implies len(f (β)) = len(f (β ′ )), and let F ⊆ {g | g : N → N}. Then f can be
computed by F -length instruction sequences if there exists a g ∈ F such that,
for all n ∈ N, there exists a finite instruction sequence X that can be denoted
by a closed PGA or PGAbj term such that X computes the restriction of f to
n
{0, 1} and len(X) ≤ g(n). We write polynomial-length instead of F -length if F
is the set of all polynomial functions g : N → N. The phrases quadratic-length
and linear-length are used similarly.
5

3

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 compute the function on bit strings that models the
multiplication of natural numbers on their representation in the binary number
system according to the long multiplication algorithm or a minor variant thereof.
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
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 content 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 |i − i′ | < n.
The words that represent the two natural numbers whose product is to be
computed are stored in advance of the whole computation in input registers,
starting with the input register with number 1. It is convenient to have available,
(n)
(n)
for each n > 0, the names I1 and I2 for the input registers in which the least
significant bit of these words are stored. The word that represents the product
is stored before the end of the whole computation in output registers, starting
with the output register with number 1. It is convenient to have available, for
each n > 0, the name O(n) for the output register in which the least significant
bit of this word is stored.
A number of words that represent intermediate values computed are temporarily stored during the whole computation in auxiliary registers, starting
with the auxiliary register with number 1. It is convenient to have available, for
(n)
(n)
each n > 0, names T1 , T2 , . . . for auxiliary registers in which the least significant bit of these words are stored. Moreover, it is convenient to have available
the name c for the auxiliary register that contains the carry bit that is repeatedly
stored when computing the function on bit strings that models the addition of
natural numbers on their representation in the binary number system.
Therefore, we define for each n > 0 and i > 0:
I1

(n)

, in:1,

(n)
I2
(n)

, in:k

O

, out:1,

(n)
Ti

, aux:k where k = 2 · n · (i − 1) + 2,

c

, aux:1.

(n)

(n)

where k = n + 1,

(n)

(n)

(n)

(n)

For each n > 0, I1 , I2 , O(n) , T1 , T2 , T3 , and T4 are the names that will
be used in Section 5 to define instruction sequences that compute the function
6

on bit strings of length n that models the multiplication of two natural numbers
less than 2n on their representation in the binary number system. Moreover, we
(n)
(n)
will write Ii [j] (0 ≤ j < n) for in:k where k = (i − 1) · n + j + 1 and Ti [j]
(0 ≤ j < 2 · n) for aux:k where k = 2 · (i − 1) · n + j + 2.

4

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
compute the function on bit strings that models the multiplication of natural
numbers on their representation in the binary number system according to the
long multiplication algorithm or a minor variant thereof.
Henceforth, 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 .
The basic operations on words that are relevant to the different multiplication algorithms are test on nonzero, decrement by one, shift left m positions
(0 < m < n), shift right m positions (0 < m < n), and addition on n-bit words
(n > 0). For these operations, we define parameterized instruction sequences
computing them in case the parameters are properly instantiated (see below):
ISNZ n (s:k) ,

;

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

; #2 ; #3) ; #1 ,

DEC n (s:k, d:l) ,

;

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

; #3 ; d:l+i.set:0 ; #5 ; d:l+i.set:1) ; #1 ; #1 ; #1 ,

SHLm
n (s:k, d:l) ,

;
;

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

; #2 ; +d:l+n−1−i.set:0 ; d:l+n−1−i.set:1) ;

SHRm
n (s:k, d:l) ,

;
;

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

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

ADD n (s1 :k1 , s2 :k2 , d:l) ,
c.set:0 ;

;

n−1
i=0 (+s1 :k1 +i.get

; #4 ; +s2 :k2 +i.get ; #7 ; #9 ; +s2 :k2 +i.get ; #10 ;

+c.get ; #10 ; #16 ; +c.get ; #7 ; #13 ; +c.get ; #11 ; #9 ; +c.get ; #4 ;
d:l+i.set:0 ; c.set:1 ; #6 ; d:l+i.set:1 ; c.set:1 ; #3 ;
+d:l+i.set:0 ; d:l+i.set:1) ,
7

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 except the first
one, 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. No result is stored on execution of ISNZ n . Instead, the first
primitive instruction following ISNZ n is skipped if the test on nonzero fails.
Transferring n-bit words (n > 0) is also relevant to 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 ;

;

,

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

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.
For convenience’s sake, we define a special case of the parameterized instruction sequences for transferring n-bit words (0 < m < n):
n−m
, d:l+m) ,
ZPAD m
n (d:l) , SET n−m (0

where d ranges over {aux, out} and l range over N+ . ZPAD m
n is meant for turning
a stored m-bit word into a stored n-bit word by zero padding.
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(ISNZ n (s:k)) = 3 · n + 1 ,
len(DEC n (s:k, d:l)) = 5 · n + 3 ,
len(SHLm
n (s:k, d:l)) = 4 · n − 3 · m ,
len(SHR m
n (s:k, d:l)) = 4 · n − 3 · m ,
len(ADD n (s1 :k1 , s2 :k2 , d:l)) = 26 · n + 1 ,
len(SET n (b0 . . . bn−1 , d:l)) = n ,
len(MOV n (s:k, d:l)) = 4 · n ,
len(ZPAD m
n (d:l)) = n − m .
8

Note that the instruction sequences defined in this section do compute the
intended operations in case of fully coinciding n-bit words. Slightly shorter instruction sequences are defined for addition on n-bit words and transfer of a
stored n-bit word in [7], but those instruction sequences do not compute the
intended operations in case of fully coinciding n-bit words.

5

Long Multiplication and Backward Jump Instructions

This section shows that the function on bit strings that models the multiplication
of natural numbers on their representation in the binary number system can be
computed according to a minor variant of the long multiplication algorithm by
quadratic-length instruction sequences without backward jump instructions and
by linear-length instruction sequences with backward jump instructions.
We begin with defining instruction sequences without backward jump instructions that compute this function according to the long multiplication algorithm.
The additions are done on the fly and the shifts are restricted to one position
by shifting the result of all preceding shifts.
We uniformly define instruction sequences LMULn (n > 0) by
(n)

(n)

(n)

(n)

MOV n (I1 , T1 ) ; ZPAD n2n (T1 ) ; SET 2n (02n , T2 ) ;
(n)
−I2 [i].get ; #li ;
(n)
MOV 2n (T2 , O(n) ) ; ! ,
n−1
i=0

;

(n)
(n)
(n)
ADD n+i+1 (T1 , T2 , T2 )

(n)
(n) 
; SHL1n+i+1 (T1 , T1 ) ;

where
(n)

(n)

(n)

li = len(ADD n+i+1 (T1 , T2 , T2 )) + 1 = 26 · n + 26 · i + 28 (0 ≤ i ≤ n − 1).
Pk
Using the property that i=0 i = (k ·(k +1))/2, we obtain by simple calculations
that
len(LMULn ) = 45 · n2 + 30 · n + 1 .
This means that the function on bit strings that models the multiplication of
natural numbers on their representation in the binary number system can be
computed by quadratic-length instruction sequences without backward jump
instructions if it is computed according to the long multiplication algorithm.
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 linear-length instruction sequences, 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 one
position to the right after it has dealt with a bit. In this way, the next bit remains
the least significant one throughout.

9

We proceed with defining instruction sequences without backward jump instructions that compute the function on bit strings that models the multiplication of natural numbers on their representation in the binary number system
according to this minor variant of the long multiplication algorithm.
We uniformly define instruction sequences LMUL′n (n > 0) by
(n)

(n)

(n)

(n)

(n)

(n)

MOV n (I1 , T1 ) ; ZPAD n2n (T1 ) ; MOV n (I2 , T2 ) ; SET 2n (02n , T3 ) ;
(n)

(n)

(n)

(n)

−T2 [0].get ; #l ; ADD 2n (T1 , T3 , T3 ) ;
(n)
(n) n
(n)
(n)
SHL12n (T1 , T1 ) ; SHR1n (T2 , T2 ) ;
(n)

MOV 2n (T3 , O(n) ) ; ! ,
where
(n)

(n)

(n)

l = len(ADD 2n (T1 , T3 , T3 )) + 1 = 52 · n + 2 .
We obtain by simple calculations that
len(LMUL′n ) = 64 · n2 + 16 · n + 1 .
This means that the function on bit strings that models the multiplication of
natural numbers on their representation in the binary number system can still
be computed by quadratic-length instruction sequences without backward jump
instructions if it is computed according to the minor variant of the long multiplication algorithm. Moreover, we have that len(LMUL′n ) > len(LMULn ) for all
n > 0.
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 defining instruction sequences with backward jump instructions that compute the function on bit strings that models the multiplication of
natural numbers on their representation in the binary number system according
to the minor variant of the long multiplication algorithm. In the definition to
come, we write n for the shortest representation of the natural number n in the
binary number system.
We uniformly define instruction sequences LMUL′′n (n > 0) by
(n)

(n)

(n)

(n)

(n)

(n)

MOV n (I1 , T1 ) ; ZPAD n2n (T1 ) ; MOV n (I2 , T2 ) ; SET 2n (02n , T3 ) ;
(n)
SET ⌊log2 (n)⌋+1 (n, T4 ) ;
(n)
(n)
(n)
(n)
−T2 [0].get ; #l1 ; ADD 2n (T1 , T3 , T3 ) ;
(n)
(n)
(n)
(n)
SHL12n (T1 , T1 ) ; SHR1n (T2 , T2 ) ;
(n)
(n)
(n)
DEC ⌊log2 (n)⌋+1 (T4 , T4 ) ; ISNZ ⌊log2 (n)⌋+1 (T4 )
(n)
MOV 2n (T3 , O(n) ) ; ! ,

10

; \#l2 ;

where
(n)

(n)

(n)

l1 = len(ADD 2n (T1 , T3 , T3 )) + 1 = 52 · n + 2 ,
(n)

(n)

l2 = len(−T2 [0].get ; . . . ; ISNZ ⌊log2 (n)⌋+1 (T4 )) = 64 · n + 9 · ⌊log2 (n)⌋ + 11 .
We obtain by simple calculations that
len(LMUL′′n ) = 83 · n + 9 · ⌊log2 (n)⌋ + 12 .
This means that the function on bit strings that models the multiplication of
natural numbers on their representation in the binary number system can be
computed by linear-length instruction sequences with backward jump instructions if it is computed according to the minor variant of the long multiplication
algorithm. Moreover, we have that len(LMUL′′n ) < len(LMULn ) for all n > 1.

6

Long Multiplication and the Halting Problem

In this section, a point concerning the halting problem is discussed which was
raised by the material in Section 5, but for which space could not be found there.
Turing’s result regarding the undecidability of the halting problem (see
e.g. [24]) is a result about Turing machines. In [3], 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 [3] theoretical halting problem instances.
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 the multiplication of natural numbers
on their representation in the binary number system offers a good reason: the
length of the instruction sequences that compute it according to the long multiplication algorithm can be reduced significantly by the use of backward jump
instructions, even more than by going over to one of the multiplication algorithms that are known to yield shorter instruction sequences without backward
11

jump instructions than the long multiplication algorithm such as for example
the Karatsuba multiplication algorithm (see e.g. [6]).
Thus, the instruction sequences LMUL′n and the instruction sequences
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.

7

Long Multiplication and the Concept of an Algorithm

In this section, another point is discussed which was raised by the material in
Section 5. This point concerns the concept of an algorithm.
At the end of Section 5, we implicitly state that the instruction sequences
LMUL′n and the instruction sequences LMUL′′n realize the same algorithm. We
have asked ourselves the question why this is an acceptable statement and what
this says about the definition of an algorithm. We consider it an acceptable
statement because all the different views on what characterizes an algorithm
lead to the conclusion that we have to do here with different realizations of the
same algorithm. We cannot prove this due to the absence of a generally accepted
mathematically precise definition of the concept of an algorithm. The cause
of this absence seems to be the general acceptance of the exact mathematical
concept of a Turing machine and equivalent mathematical concepts as adequate
replacements of the intuitive concept of an algorithm.
Unfortunately, Turing machines are quite remote from anything related to
actual programming. Moreover, we can construct at least two different Turing machines for the one algorithm realized by both the instruction sequences
LMUL′n and the instruction sequences LMUL′′n : one without a counterpart of
a for loop and one with a counterpart of a for loop. So Turing machines do
not enforce a level of abstraction that is sufficient for algorithms. Therefore,
we doubt whether the mathematical concept of a Turing machine is an adequate replacement of the intuitive concept of an algorithm. This means that we
consider a generally accepted mathematically precise definition of the concept
of an algorithm still desirable. Below, we outline a possible avenue to such a
definition.
We restrict ourselves to algorithms for computing functions on bit strings.
This has the advantage that data representation is hardly an issue in the realizations of algorithms. Moreover, we adopt the common practice among math12

ematicians to treat the length of the input of an algorithm as a parameter of
the algorithm. In the perspective that a program is in essence an instruction
sequence, taking into account the experience gained in this paper with realizing algorithms by instruction sequences, we consider the following to be a first
approximation of a mathematically precise definition of the concept of an algorithm: “an algorithm is a mapping from the set of natural numbers to the set
of equivalence classes of the instruction sequences with backward jumps used in
this paper with respect to an appropriate equivalence relation”. The underlying
idea is that for each algorithm, for each n, there is a class of algorithmically
equivalent instruction sequences that realize the algorithm for that n. This idea
refines an idea that was already put forward by Milner in 1971 (see [20]).
What exactly should be considered algorithmically equivalent instruction sequences is a matter of further study. Some requirements for algorithmic equivalence are:
– each instruction sequence is algorithmically equivalent to each instruction
sequence that produces the same behaviour;
– each instruction sequence is algorithmically equivalent to the instruction
sequence obtained from it by consistently exchanging 0 and 1;
– each instruction sequence is algorithmically equivalent to each instruction sequence obtained from it by renumbering the auxiliary Boolean registers used;
– each instruction sequence is algorithmically equivalent to each instruction
sequence obtained from it by transposing basic instructions that have no
influence on each other;
– each instruction sequence is algorithmically equivalent to each instruction
sequence obtained from it by replacing subsequences that are the result of
the concatenation of an instruction sequence a number of times with itself
by an implementation of a for loop of which it is the unwinding.
Of course, there is a possibility that additional requirements are necessary. Note
that LMUL′n and LMUL′′n are algorithmically equivalent according to the lastmentioned requirement. It is mainly this requirement that makes it difficult
to give an exact mathematical definition of an algorithmic equivalence relation
satisfying the above-mentioned requirements. We further remark that it is not
clear to us whether such a definition is relevant at all if the conceivable viewpoint
is taken that there may be different degrees to which an instruction sequence
realizes an algorithm.
Above, we have restricted ourselves to algorithms for computing functions
on bit strings. We could restrict ourselves further to algorithms for computing
projective functions on bit strings, i.e. functions on bit strings for which the
restriction to bit strings of any given length can handle each restriction to bit
strings of a shorter length if sufficiently many leading zeros are added (see [5]).
This means that an instruction sequence that computes the restriction of such
a function to bit strings of a certain length can also be used to compute the
restriction of the function concerned to bit strings up to that length. The projective functions on bit strings include all functions that model operations on
natural numbers on their representation in the binary number system.
13

8

Further Reduction of Instruction Sequence Length

In Section 5, it is demonstrated that the function on bit strings that models the
multiplication of natural numbers on their representation in the binary number
system can be computed according to a minor variant of the long multiplication
algorithm by linear-length instruction sequences with backward jump instructions. The alteration of the long multiplication algorithm seems inescapable in
this case unless provision is made for some form of indirect addressing for Boolean
registers. If such a provision is made, however, the function concerned cannot
only be computed according to the unaltered long multiplication algorithm, but
also by logarithmic-length instruction sequences with backward jump instructions.
The expression defining LMULn contains a subexpression of the form
n−1
i=0 Pi . It is easy to see that, if provision is made for some form of indirect
addressing for Boolean registers, there exists an instruction sequence P such
that this subexpression can be replaced by P n . The duplication of P can then
be eliminated by implementing a for loop like in LMUL′′n . Because these remarks
m
apply to SHLm
n , ADD n , SET n , MOV n , and ZPAD n as well, indirect addressing
of Boolean registers makes logarithmic-length instruction sequences possible.
Some of the for loops that has to be implemented to obtain logarithmic-length
instruction sequences require an increasing loop counter. Instead of instruction
sequences for test on nonzero (ISNZ n ) and decrement by one (DEC n ), instruction sequences for test on not equal to n and increment by one are needed to
implement such a for loop. An instruction sequence for setting the loop counter to
its initial value is needed as well to implement a for loop. To obtain logarithmiclength instruction sequences, it is sufficient to use SET n as defined in Section 5
for this purpose.
The form of indirect addressing known as indexed addressing in the area of
computer architecture is most appropriate for the algorithm under consideration.
In the case of indexed addressing of a Boolean register, its number is obtained by
adding the number whose representation in the binary number system is formed
by the contents of specified successive Boolean registers to a specified number.
In the area of computer architecture, the latter number is usually called the base
address and the former number is usually called the index. In the case of direct
addressing, we use an expression of the form κ:i, where κ ∈ {in, out, aux} and
i ∈ N+ , on the left-hand side of the dot in basic instructions to refer to the
Boolean register of kind κ whose number is i. In the case of indexed addressing,
we could use an expression of the form κ:i(aux:j:l), where κ ∈ {in, out, aux} and
i, j, l ∈ N+ , on the left-hand side of the dot in basic instructions to refer to
the Boolean register of kind κ whose number is the sum of i and the number
represented by the contents of the l successive Boolean registers of kind aux of
which the first one has number j.
If LMULn is adapted as outlined above, the length of the adapted instruction sequence is c · ⌊log2 (n)⌋ + c′ · ⌊log2 (2n − 1)⌋ + c′′ , where c, c′ , and c′′ are
constants greater than zero. With indexed addressing, it is straightforward to
′
′′
obtain an instruction sequence LMUL′′′
n such that c < 100, c < 10, and c < 250.

;

14

This means that the function on bit strings that models the multiplication of
natural numbers on their representation in the binary number system can be
computed by logarithmic-length instruction sequences with backward jump instructions according to the long multiplication algorithm if provision is made
for some form of indirect addressing for Boolean registers. Moreover, we have
′′
that len(LMUL′′′
n ) < len(LMULn ) for all n > 5. This reduction of instruction sequence length is obtained by instructions that provide for backward jumping and
a form of indirect addressing. It is an open question whether it can be reduced
further with instructions that provide for additional facilities.

9

Concluding Remarks

We have demonstrated that, in the case that the other instructions are only instructions to set and get the content of Boolean registers, forward jump instructions, and a termination instruction, the function that models the multiplication
of natural numbers on their representation in the binary number system can be
computed according to a minor variant of the long multiplication algorithm
by quadratic-length instruction sequences without backward jump instructions
and by linear-length instruction sequences with backward jump instructions. Be
aware that we have not shown that this function cannot be computed by linearlength instruction sequences without backward jump instructions. However, the
scientific literature on multiplication algorithms (see e.g. [13,17,22,23]) indicates
that it is likely that it cannot be computed by linear-length instruction sequences
without backward jump instructions.
We have also gone into the observations that the demonstration provides a
hard witness of the inevitable existence of a halting problem in the practice of
imperative programming and that it makes manifest the lack of a definition of the
concept of an algorithm that makes it possible to prove whether two instruction
sequences realize the same algorithm.
The viewpoints on what is an algorithm are diverse in character. Milner’s idea
that algorithms are equivalence classes of programs can also be found in [26].
A rather strange twist is that constructions of primitive recursive functions are
considered to be programs. In [21], algorithms are viewed as isomorphism classes
of tuples of recursive functionals that can be defined by repeated application of
certain schemes. In [10], which is concerned with algorithms on Kahn-Plotkin’s
concrete data structures, algorithms are viewed as pairs of a function and a computation strategy that resolves choices between possible ways of computing the
function. In [14], an algorithm is defined as an object that satisfy certain postulates. According to this definition, Gurevich’s abstract state machines capture
algorithms. In [19], it is claimed that the only algorithms are those realized by
Kolmogorov machines and that therefore the concept of a Kolmogorov machine
can be regarded as an adequate formal characterization of the concept of an
algorithm (see also [25]).
In [11], it is argued that the intuitive notion of algorithmic equivalence of
programs cannot be captured by an equivalence relation. This is also argued
15

in the philosophical discussion of the view that algorithms are mathematical
objects presented in [12]. The given arguments are no reason for us to doubt the
usefulness of studying equivalence relations that capture algorithmic equivalence
to a certain degree. After the appearance of the first version of the current paper,
we have looked for such equivalence relations. The results of that search are
presented in [8].

References
1. Bergstra, J.A., Bethke, I.: On the contribution of backward jumps to instruction
sequence expressiveness. Theory of Computing Systems 50(4), 706–720 (2012)
2. Bergstra, J.A., Loots, M.E.: Program algebra for sequential code. Journal of Logic
and Algebraic Programming 51(2), 125–156 (2002)
3. Bergstra, J.A., Middelburg, C.A.: Instruction sequence processing operators. Acta
Informatica 49(3), 139–172 (2012)
4. Bergstra, J.A., Middelburg, C.A.: Instruction Sequences for Computer Science,
Atlantis Studies in Computing, vol. 2. Atlantis Press, Amsterdam (2012)
5. Bergstra, J.A., Middelburg, C.A.: Instruction sequence based non-uniform complexity classes. arXiv:1301.3297v2 [cs.CC] (July 2013)
6. Bergstra, J.A., Middelburg, C.A.: Instruction sequence expressions for the Karatsuba multiplication algorithm. arXiv:1312.1529v1 [] (December 2013)
7. Bergstra, J.A., Middelburg, C.A.: Instruction sequence expressions for the secure
hash algorithm SHA-256. arXiv:1308.0219v5 [] (November 2013)
8. Bergstra, J.A., Middelburg, C.A.: On algorithmic equivalence of instruction sequences for computing bit string functions. arXiv:1402.4950v2 [cs.LO] (April
2014)
9. Bergstra, J.A., Ponse, A.: An instruction sequence semigroup with involutive antiautomorphisms. Scientific Annals of Computer Science 19, 57–92 (2009)
10. Berry, G., Curien, P.L.: Sequential algorithms on concrete data structures. Theoretical Computer Science 20(3), 265–321 (1982)
11. Blass, A., Dershowitz, N., Gurevich, Y.: When are two algorithms the same? The
Bulletin of Symbolic Logic 15(2), 145–168 (2009)
12. Dean, W.: What Algorithms Could Not Be. Ph.D. thesis, Rutgers, The State University of New Jersey, New Brunswick, NJ (2007)
13. Fürer, M.: Faster integer multiplication. SIAM Journal of Computing 39(3), 979–
1005 (2009)
14. Gurevich, Y.: Sequential abstract-state machines capture sequential algorithms.
ACM Transactions on Computational Logic 1(1), 77–111 (2000)
15. Homer, S., Selman, A.L.: Computability and Complexity Theory. Springer-Verlag,
Berlin (2001)
16. Karatsuba, A.A.: The complexity of computations. Proceedings of the Steklov
Institute of Mathematics 211, 169–183 (1995)
17. Karatsuba, A.A., Ofman, Y.P.: Multiplication of multidigit numbers on automata.
Doklady Akademii Nauk SSSR 145(2), 293–294 (1962), in Russian
18. Karp, R.M., Lipton, R.J.: Some connections between nonuniform and uniform
complexity classes. In: STOC ’80. pp. 302–309. ACM Press (1980)
19. Kolmogorov, A.N., Uspensky, V.A.: On the definition of an algorithm. Uspekhi
Matematicheskikh Nauk 13(4(82)), 3–28 (1958), in Russian

16

20. Milner, R.: An algebraic definition of simulation between programs. In: IJCAI ’71.
pp. 481–489. Morgan Kaufmann, San Francisco (1971)
21. Moschovakis, Y.N.: What is an algorithm? In: Engquist, B., Schmid, W. (eds.)
Mathematics Unlimited – 2001 and Beyond, pp. 919–936. Springer-Verlag, Berlin
(2001)
22. Schönhage, A., Strassen, V.: Schnelle Multiplikation großer Zahlen. Computing
7(3–4), 281–292 (1971)
23. 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
24. 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
25. Uspensky, V.A., Semenov, A.L.: What are the gains of the theory of algorithms. In:
Ershov, A.P., Knuth, D.E. (eds.) Algorithms in Modern Mathematics and Computer Science. Lecture Notes in Computer Science, vol. 122, pp. 100–234. SpringerVerlag (1981)
26. Yanofsky, N.S.: Towards a definition of an algorithm. Journal of Logic and Computation 21(2), 253–286 (2011)
27. Secure Hash Standard. National Institute of Standards and Technology, FIPS PUB
180-4 (March 2012)

17

