the size of $\mathcal{I}$. This problem trivially belongs to
$\operatorname{\mathtt{CONST}_{\mathtt{lin}}}$ but it does not belongs to
$\operatorname{\mathtt{CONST}_{\mathtt{lin}}^{\mathtt{succ,pred}}}$ by
Proposition 4. ∎

We ignore if Corollary 6 can be “extended” to the other “minimal” complexity
classes.

######  Open problem 2.

Is the inclusion
$\operatorname{\mathtt{LIN}^{\mathtt{succ,pred}}}\subseteq\mathtt{LIN}$
strict?

######  Open problem 3.

Is the inclusion
$\operatorname{\mathtt{CONST}-\mathtt{DELAY}_{\mathtt{lin}}^{\mathtt{succ,pred}}}\subseteq\operatorname{\mathtt{CONST}-\mathtt{DELAY}_{\mathtt{lin}}}$
strict?

The difficulty comes from the fact that RAM with successor, also known as
successor RAM, is much more powerful than it seems at first glance. As a
striking example, Schönhage [72] showed as early as 1980 that integer-
multiplication, which is the problem of computing the product of two integers
in binary notation, i.e., with one bit per input register 161616Note that in
our formalism, the input of this problem is of the form
$\mathcal{I}\coloneqq(N,I[0]=a_{0},\ldots,I[n-1]=a_{n-1},I[n]=2,I[n+1]=b_{0},\ldots,I[2n]=b_{n-1})$,
where $N=2n+1$ and the $a_{i},b_{i}$ belongs to $\\{0,1\\}$, and its output is
$(2n,p_{0},\ldots,p_{2n-1})$, where $p=a\times b$, for
$a=\overline{a_{n-1}\ldots a_{1}a_{0}}$, $b=\overline{b_{n-1}\ldots
b_{1}b_{0}}$, and $p=\overline{p_{2n-1}\ldots p_{1}p_{0}}$., is computed in
linear time on a successor RAM and therefore belongs to
$\operatorname{\mathtt{LIN}^{\mathtt{succ,pred}}}$. Moreover, Schönhage [72]
proved that the successor RAM is equivalent to what he calls the “Storage
Modification Machine”, also called “Pointer Machine” by Knuth [55] and Tarjan
[82], who proves that in this computational model, Union-Find operations can
be performed in amortized quasi-constant time $\alpha(n)$, where $\alpha(n)$
is the inverse of Ackermann’s function $A(n,n)$.

##### Why does our RAM model model the algorithms in the literature?

Our RAM model faithfully mimics/reproduces the computations of the algorithms
on the combinatorial structures: trees, formulas, graphs, hypergraphs, etc.
The reason is twofold:

  1. 1.

Such a structure $\mathcal{S}$, e.g. a tree or a graph, is naturally encoded
by a RAM input $\mathcal{I}=(N,I[0],\ldots,I[N-1])$, with $I[j]=O(N)$ and
$N=\Theta(L)$, where $L$ is the “natural length” of the structure
$\mathcal{S}$, which is $L=n$ if $\mathcal{S}$ is a tree of $n$ nodes, or
$L=m+n$ if $\mathcal{S}$ is a graph of $m$ edges and $n$ vertices, etc.

  2. 2.

The structure and acting of the RAM model are homogeneous: on the one hand,
its input array $\mathcal{I}=(N,I[0],\ldots,I[N-1])$ is of the same nature as
the array $R[0],R[1],\ldots$ of its registers of contents also $O(N)$; on the
other hand, a read/write instruction is a random access instruction like all
other instructions.

##### Why RAM linear time is intuitive linear time under unit cost criterion?

By our conventions, any _linear-time_ (and linear-space171717As is the case
with almost all linear-time algorithms in the literature and as required for
RAMs, we require that a linear-time algorithm use linear space.) algorithm
from the literature on combinatorial structures (trees, graphs, etc.) is
modeled/implemented by a RAM algorithm that uses $O(N)$ registers and executes
$O(N)$ instructions, each involving $O(1)$ registers of bit length
$\Theta(\log N)$. Consequently, its time complexity under unit cost criterion
is $O(N)$, which is $O(L)$, where $L$ is the “natural length” of the input
structure, by item 1 of the above paragraph.

What about linear time under logarithmic cost criterion? Since a linear-time
algorithm performs $O(N)$ instructions, each of cost $O(\log N)$, its time is
$O(N\log N)$ under logarithmic cost criterion. Is it a linear time for this
criterion?

##### Linear-time algorithms on combinatorial structures are also linear under
logarithmic cost criterion.

Let us justify this assertion for graph algorithms. (The proof is similar for
algorithms on other structures: trees, formulas, etc.) A graph without
isolated vertex whose vertices are $1,\ldots,n$ and edges are
$(a_{1},b_{1}),\ldots,(a_{m},b_{m})$ is “naturally represented” by the
standard input $\mathcal{I}=(N,I[0],\ldots,I[N-1])$ where $N\coloneqq 2m+2$,
$I[0]\coloneqq m$, $I[1]\coloneqq n$, and finally $I[2j]\coloneqq a_{j}$ and
$I[2j+1]\coloneqq b_{j}$ for $j=1,\ldots,m$. Recall that we have $n\leq
2m=N-2$.

If $\mathcal{I}$ is encoded by a binary word, its bit length, called
$\textsc{length}(\mathcal{I})$, is
$\Theta(\textsc{length}(N)+\sum_{j=1}^{m}\textsc{length}(\textsc{binarycode}(a_{j},b_{j})))$,
which is $O(N\log N)$. On the other hand, since the $m$ edges $(a_{j},b_{j})$
are pairwise distinct, we have

$\displaystyle\sum_{j=1}^{m}\textsc{length}(\textsc{binarycode}(a_{j},b_{j}))\geq\sum_{j=1}^{m}\textsc{length}(w_{j})$
(31)

where $w_{1},\ldots,w_{m}$ is the list of the $m$ shortest nonempty binary
words numbered in increasing length, that means
$\textsc{length}(w_{j})\leq\textsc{length}(w_{j+1})$, for each $j<m$. The
inequality (31) is justified by the following points:

  * •

without loss of generality, assume that the $m$ edges
$(a_{1},b_{1}),\ldots,(a_{m},b_{m})$ are numbered in increasing length of
their (pairwise distinct) encodings $\textsc{binarycode}(a_{j},b_{j})$,
$j=1,\ldots,m$;

  * •

consequently, we have
$\textsc{length}(\textsc{binarycode}(a_{j},b_{j}))\geq\textsc{length}(w_{j})$,
for each $j\leq m$.

Moreover, the (in)equality $\sum_{j=1}^{m}\textsc{length}(w_{j})=\Omega(m\log
m)$ is intuitive and not hard to prove181818 Note the sequence of equivalences
$\textsc{length}(w_{j})=\ell$ $\iff$
$\sum_{i=1}^{\ell-1}2^{i}<j\leq\sum_{i=1}^{\ell}2^{i}$ $\iff$
$2^{\ell}-2<j\leq 2^{\ell+1}-2$ $\iff$ $2^{\ell}<j+2\leq 2^{\ell+1}$ $\iff$
$\ell=\left\lceil\log_{2}(j+2)\right\rceil-1$. Hence,
$\textsc{length}(w_{j})=\left\lceil\log_{2}(j+2)\right\rceil-1$. Therefore, we
get $\sum_{j=1}^{m}\textsc{length}(w_{j})\geq\sum_{j=\left\lceil
m/2\right\rceil}^{m}\textsc{length}(w_{j})\geq(m/2)\textsc{length}(w_{\left\lceil
m/2\right\rceil})=(m/2)\left\lceil\log_{2}(\left\lceil
m/2\right\rceil+2)\right\rceil-1$, from which
$\sum_{j=1}^{m}\textsc{length}(w_{j})=\Omega(m\log m)$ is deduced. . By (31),
this implies $\textsc{length}(\mathcal{I})=\Omega(m\log m)=\Omega(N\log N)$.
Thus, we have proved191919 Note that the truth of (32) is largely independent
of the representation of the graph provided it is “natural”. E.g., if the
vertices of the graph are $1,\ldots,n$, some of which may be isolated, and its
edges are $(a_{1},b_{1}),\ldots,(a_{m},b_{m})$, the graph is “naturally”
represented by the standard input $\mathcal{I}=(N,I[0],\ldots,I[N-1])$ where
$N\coloneqq 2m+n+1$, $I[0]\coloneqq m$, $I[j]\coloneqq j$ for $j=1,\ldots,n$,
and finally $I[2j+n-1]\coloneqq a_{j}$ and $I[2j+n]\coloneqq b_{j}$ for
$j=1,\ldots,m$. We still have $\textsc{length}(\mathcal{I})=O(N\log N)$.
Moreover, by the same reasoning as above, we get
$\textsc{length}(\mathcal{I})=\Omega(n\log n+m\log m)=\Omega(N\log N)$
(because $N=\Theta(max(m,n))$) and therefore
$\textsc{length}(\mathcal{I})=\Theta(N\log N)$.

$\displaystyle\textsc{length}(\mathcal{I})=\Theta(N\log N)$ (32)

Consequently, a graph algorithm running in linear time under unit cost
criterion, therefore in time $O(N\log N)$ under logarithmic cost criterion,
runs in time $O(\textsc{length}(\mathcal{I}))$ under the same criterion,
according to (32). This is true linear time under the logarithmic cost
criterion!

Thus, algorithms on graphs or similar combinatorial structures (trees,
formulas, hypergraphs, etc.) running in linear time under the unit cost
criterion also run in linear time, i.e. time
$O(\textsc{length}(\mathcal{S}))$, under the logarithmic cost criterion, where
$\textsc{length}(\mathcal{S})$ is the length in bits of the input structure
$\mathcal{S}$.

However, our argument above for combinatorial structures does _not_ apply to
_word structures_.

##### Which linear time complexity for algorithms on words?

As seems most natural, it is the rule for a text algorithm (see e.g. the
reference book [25] or Chapter 32 of [23]) to represent an input word (text,
string) $w=w_{0}\ldots w_{n-1}\in\Sigma^{n}$ over a finite fixed alphabet
$\Sigma$, identified with the set of integers $\\{0,1,\ldots,b-1\\}$ for
$b=\mathtt{card}(\Sigma)$, by an array $\mathtt{W}[0..n-1]$ where
$\mathtt{W}[j]=w_{j}$. Thus, the text algorithm is faithfully simulated by a
RAM whose input is $\mathcal{I}=(N,I[0],\ldots,I[N-1])$ where $N\coloneqq n$
and $I[j]\coloneqq w_{j}$; this means $0\leq I[j]<b=O(1)$.

Many word algorithms of the literature, e.g. the well-known string-matching
algorithm of Knuth, Morris and Pratt [56, 25, 47], are executed in the RAM
model in time $O(N)$ under the unit cost criterion, where $N$ is the length of
the input word $w$ (or the maximum of the lengths of the two input words).
Therefore, such an algorithm runs in time $O(N\log N)$ under the logarithmic
cost criterion, for $N=\textsc{length}(w)$. A priori, it is not
$O(\textsc{length}(w))$… This corresponds to the fact that the input elements
$I[j]$ are in $O(1)$ while the contents of the memory registers are in $O(N)$:
here, there is _heterogeneity between input and memory_.

To recover homogeneity, we can adopt a technical solution already introduced
in [40, 73, 42]: partition any input word $w\in\Sigma^{n}$ (where
$\Sigma=\\{0,\ldots,b-1\\}$) into $N=\Theta(n/\log n)$ factors of length
$\Theta(\log n)=\Theta(\log N)$. More precisely, using the parameters
$\ell\coloneqq\left\lceil(\log_{b}n)/2\right\rceil$ and $N\coloneqq\left\lceil
n/\ell\right\rceil$, we partition $w$ into the concatenation $w=f_{0}\ldots
f_{N-1}$ of $N$ factors $f_{j}$, with $\textsc{length}(f_{j})=\ell$ for
$j<N-1$ and $1\leq\textsc{length}(f_{N-1})\leq\ell$. The word $w\in\Sigma^{n}$
is represented by the input $\mathcal{I}=(N,I[0],\ldots,I[N-1])$ defined by
$I[j]\coloneqq f_{j}$ for each $j<N$. Many other variants of this
representation can also be adopted, the important point being the orders of
magnitude obtained:

$N=\Theta(n/\log n$) ;
$I[j]=O(b^{\ell})=O(b^{(\log_{b}n)/2})=O(n^{1/2})=O(N)$, for each $j<N$.

With such a word representation, the time complexity of a RAM operating in
time $O(N)$, which is $O(n/\log n)$, under the unit cost criterion, is
$O(N\log N)=O(n)$, i.e.  _truly_ linear, under the logarithmic cost criterion.
It would be a large and challenging goal to determine which word problems
known to be computable in “linear time” can be computed in time $O(n/\log n)$
under the unit cost criterion using our word representation. For example, it
is true for the following “sorting” problem [40] from
$(\Sigma\cup\\{\sharp\\})^{+}$ to $(\Sigma\cup\\{\sharp\\})^{+}$, for
$\sharp\not\in\Sigma$, defined as

$x_{1}\sharp x_{2}\sharp\cdots\sharp x_{q}\mapsto x_{\pi(1)}\sharp
x_{\pi(2)}\sharp\cdots\sharp x_{\pi(q)}$

where $x_{1},x_{2},\ldots,x_{q}$ are words in $\Sigma^{+}$, and $\pi$ is a
permutation of $\\{1,2,\ldots,q\\}$ such that $x_{\pi(1)}\leq
x_{\pi(2)}\leq\ldots\leq x_{\pi(q)}$ for the lexicographic order $\leq$ of
$\Sigma^{+}$.

##### Is multiplication more difficult than addition in the RAM model?

We mentioned above that Schönhage [72] surprisingly proved that the successor
RAM, equivalent to his “storage modification machine” (but seemingly weaker
than our addition RAM!) can compute in time $O(n)$ the product of two integers
of length $n$ in binary notation, each contained in $n$ input registers (one
bit per input register).

On this point, in his lecture on receiving the ACM Turing award [21] in 1982,
Stephen Cook expressed his astonishment as follows: “ Schönhage [72] recently
showed$\dots\dots$that his storage modification machines can multiply in time
$O(n)$ (linear time!). We are forced to conclude that either multiplication is
easier than we thought or that Schönhage’s machines cheat.”

Although we agree that Schönhage’s result is very beautiful and strong (it is
all the more powerful that it uses a successor RAM instead of an addition
RAM!), we believe that the paradox highlighted by Cook is only apparent. The
product of two integers of binary length $n$ is computed by a successor RAM in
time $O(n)$ under the unit cost criterion, and therefore in time $O(n\log n)$
under the logarithmic cost criterion. This is not real linear time!

At the opposite, we have noticed, see Remark 9, that our addition RAM can
compute the sum (resp. difference) of two integers of binary length $n$ in
time $O(n/\log n)$ under the unit cost criterion (by representing each input
integer by the array of binary words of length
$\left\lceil(\log_{2}n)/2\right\rceil$ whose concatenation is its binary
notation, like the word representation we suggest in the previous paragraph).
This is $O(n)$ time under the logarithmic cost criterion, which is _really_
linear time. This is not the case with the Schönhage multiplication algorithm
or the Fast Fourier multiplication and we conjecture that our RAM model cannot
compute the product of two integers of binary length $n$ in time $O(n/\log n)$
under the unit cost criterion as its does for their sum and difference.
Multiplication continues to seem harder than addition and subtraction!

##### Linear space or larger space?

The RAM model we have chosen uses _linear space_. This means that the
addresses and contents of registers $R[0],R[1],\dots$ are integers in $O(N)$;
in particular, no $k$-dimensional array $N_{1}\times N_{2}\times\dots\times
N_{k}$ is allowed unless it uses $N_{1}\times N_{2}\times\dots\times
N_{k}=O(N)$ registers so that it can be represented by a one-dimensional array
of size $O(N)$. This is justified by two arguments:

  * •

our RAM model models the vast majority of linear-time algorithms in the
literature: they use a linear space;

  * •

our RAM model is very “robust”: its complexity classes are invariant for many
variations, in particular with respect to the primitive operations of the RAM,
as established at length in this paper.

Nevertheless, we have noticed that several recent papers about queries in
logic and databases, see e.g. [31, 77, 12, 13], present algorithms which use
$k$-dimensional arrays $\mathbf{A}$ with $O(N^{k})$ available registers, such
that for given $(n_{1},\dots,n_{k})\in\mathbb{N}^{k}$, with each $n_{i}=O(N)$,
the entry $\mathbf{A}[n_{1},\dots,n_{k}]$ at position $(n_{1},\dots,n_{k})$
can be accessed in constant time. Although this “multidimensional” RAM model
is “unrealistic for real-world computers”, as [12] writes, it is robust in two
respects:

  * •

it inherits all the invariance properties of our (stricter) RAM model
according to the primitive operations;

  * •

it is invariant according to the dimensions of arrays: Theorem 1 states that
the RAM model with arrays of arbitrary dimensions is equivalent to the RAM
model using only 2-dimensional arrays, and even, arrays of dimensions $N\times
N^{\epsilon}$, for any $\epsilon>0$, hence with $O(N^{1+\epsilon})$ registers
available.

It remains the open and difficult question of whether the RAM model with
$k$-dimensional arrays but only using $O(N)$ cells is equivalent to the RAM
model with only $1$-dimensional arrays of $O(N)$ size. Answering this question
is crucial to determine whether the algorithms of [31, 77, 12, 13] can be
implemented in linear space in “real-world computers”.

##### Which space complexity to choose for enumeration algorithms?

In accordance with and in the spirit of the definition of the complexity class
$\operatorname{\mathtt{CONST}_{\mathtt{lin}}}$, whose second phase uses
constant time and therefore constant space, the “minimal” enumeration
complexity class that we have chosen as the standard (when each solution to be
enumerated is of constant size202020Note that if the solutions are not of
constant size, e.g. if they are subsets of vertices of an input graph, then
the “minimal” (standard) enumeration complexity class is the class of
problems, called $\operatorname{\mathtt{LIN}-\mathtt{DELAY}_{\mathtt{lin}}}$,
whose preprocessing phase uses $O(N)$ time and space and enumeration phase
uses $O(|S|)$ delay and space, for each solution $S$, see [6, 7, 24]. Of
course, belonging to
$\operatorname{\mathtt{LIN}-\mathtt{DELAY}_{\mathtt{lin}}}$ amounts to
belonging to $\operatorname{\mathtt{CONST}-\mathtt{DELAY}_{\mathtt{lin}}}$ for
an enumeration problem whose size of solutions is constant.) is the class
$\operatorname{\mathtt{CONST}-\mathtt{DELAY}_{\mathtt{lin}}}$ whose second
phase uses constant time _and also_ constant space. This is justified by two
points:

  * •

some basic enumeration algorithms in combinatorics, logic and database theory
[34, 8, 30, 7, 29] belong to
$\operatorname{\mathtt{CONST}-\mathtt{DELAY}_{\mathtt{lin}}}$;

  * •

this complexity class is as “robust” (and for the same reasons) as the classes
$\mathtt{LIN}$ and $\operatorname{\mathtt{CONST}_{\mathtt{lin}}}$.

The a priori larger complexity class
$\operatorname{\mathtt{CONST}-\mathtt{DELAY}-\mathtt{LIN}-\mathtt{SPACE}_{\mathtt{lin}}}$,
which allows the enumeration phase to use $O(N)$ space, instead of constant
space, is also realistic (its two phases use a linear space) and as robust as
$\operatorname{\mathtt{CONST}-\mathtt{DELAY}_{\mathtt{lin}}}$.

Again, the question of whether the inclusion
$\operatorname{\mathtt{CONST}-\mathtt{DELAY}_{\mathtt{lin}}}\subseteq\operatorname{\mathtt{CONST}-\mathtt{DELAY}-\mathtt{LIN}-\mathtt{SPACE}_{\mathtt{lin}}}$
is strict remains an open and difficult problem.

##### What other operations are computed in constant time?

We have the feeling that our addition RAM can compute in constant time (with
linear-time preprocessing) any operation on “polynomial” integers defined from
the usual arithmetic operations (whose versions on $\mathbb{R}$ are
continuous), plus the rounding functions $x\mapsto\left\lfloor x\right\rfloor$
and $x\mapsto\left\lceil x\right\rceil$, and the compositions of such
operations, provided that the intermediate results are “polynomial”. We
managed to prove this for all the operations we studied in Sections 4 to 7,
except for the general root operation $(x,y)\mapsto\left\lfloor
x^{1/y}\right\rfloor$ for which Subsection 7.3 gives only a partial proof.
However, we have failed to prove any general result – except for the set of
linear-time computable operations on cellular automata — and our proofs are
“ad hoc” even though a discrete analog of Newton’s approximation method used
in Section 7 might be repeated or “generalized” in some way.

##### Final remarks on the RAM model.

As observed and discussed in the introduction to this paper, on the one hand
the RAM model is generally considered to be the standard model in the
foundations of algorithm design and algorithm analysis, and on the other hand,
surprisingly, the literature does not agree on a standard definition of the
RAM model and its complexity classes.

Although in the past some papers [39, 38, 40, 42, 41, 30, 7] have defined and
started to study the $\mathtt{LIN}$ class of our RAM model with addition and
its subclass of decision problems called $\mathtt{DLIN}$, so far no systematic
work has investigated from scratch the robustness and extent of computational
power of this model and its complexity classes.

Having such a systematic and unified study was all the more urgent as the many
recent studies on the algorithms and the complexity of “dynamic” problems, and
especially of enumeration problems [76, 77, 3, 14, 54, 81, 20, 11, 29],
essentially refer to the reference book [2] (excellent but almost half a
century old!) and to the scattered and incomplete papers cited above. This
gives an impression of imprecision and approximation and can lead to
ambiguities or even errors212121Most of the papers cite the book [2] which
considers the four operations $+,-,\times$ and $/$ as primitive operations of
RAMs without limiting the values of their operands. However, Schönhage [71]
proved that the class of languages recognized by such RAMs in polynomial time
under the unit cost criterion contains the entire class NP!.

We hope that this self-contained article meets this need for precision. We
have designed our paper as a progressive, detailed and systematic study.

We consider that the main arguments in favor of adopting the addition RAM as
the basic algorithmic model are as follows:

  * •

its simplicity/minimality and its homogeneity;

  * •

its ability to represent usual data structures and in particular tables,
essential for preprocessing;

  * •

the robustness and computing power of its complexity classes (Corollary 5):
the most important and surprising result that this paper establishes is that
the addition RAM can compute the Euclidean division in constant time with
linear-time preprocessing; as we also proved, this allows to compute many
other arithmetic operations on “polynomial” integers in constant time with
linear-time preprocessing.

##### Open problems.

Even if we have positively solved in this paper the main (old) open question,
which is the equivalence of the addition RAM with the RAM equipped with the
four operations $+,-,\times$ and $/$ acting on “polynomial” integers, for the
complexity classes under the unit cost criterion, there remain many other
interesting open questions regarding the RAM model, several of which have been
presented throughout this paper.

We have tried to establish the most complete list of integer operations that
an addition RAM is able to compute in constant time with linear-time
preprocessing. In fact, many algorithms deal with combinatorial structures
such as trees, circuits, graphs, etc. The next step would therefore be to
undertake a similar systematic study of operations on combinatorial structures
computable in constant time (or quasi-constant time) on addition RAMs with
linear-time preprocessing. For example, although a lot of work has been done
in this direction, it would be very useful to establish the “largest” set of
“atomic” tree operations computable in constant (or quasi-constant) time after
a linear (or quasi-linear) time preprocessing222222For instance, as soon as
1984, Harel and Tarjan [48] proved that the closest common ancestor of any two
nodes $x,y$ of a tree $T$ of $N$ nodes can be computed in constant time after
a preprocessing of time $O(N)$ and depending only on $T$.. This would
constitute a toolbox to optimize algorithms for “dynamic” problems such as
those studied in [3, 12, 15, 14, 4].

_Acknowledgments:_ This work was partly supported by the PING/ACK project of
the French National Agency for Research (ANR-18-CE40-0011). We thank Antoine
Amarilli and Luc Segoufin for their proofreading of the manuscript. In
particular, we thank Luc for his comment that led to the drafting of
Subsection 2.5 “RAM models with a different space usage”.

## References

  * [1] Alok Aggarwal, Ashok K. Chandra, and Marc Snir.  Hierarchical memory with block transfer.  In 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987, pages 204–216. IEEE Computer Society, 1987.
  * [2] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman.  The Design and Analysis of Computer Algorithms.  Addison-Wesley, 1974.
  * [3] Antoine Amarilli, Pierre Bourhis, Louis Jachiet, and Stefan Mengel.  A circuit-based approach to efficient enumeration.  In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 111:1–111:15, 2017.
  * [4] Antoine Amarilli, Louis Jachiet, and Charles Paperman.  Dynamic membership for regular languages.  CoRR, abs/2102.07728, 2021.
  * [5] Dana Angluin and Leslie G. Valiant.  Fast probabilistic algorithms for hamiltonian circuits and matchings.  J. Comput. Syst. Sci., 18(2):155–193, 1979.
  * [6] Guillaume Bagan.  MSO queries on tree decomposable structures are computable with linear delay.  In Zoltán Ésik, editor, Computer Science Logic, 20th International Workshop, CSL 2006, 15th Annual Conference of the EACSL, Szeged, Hungary, September 25-29, 2006, Proceedings, volume 4207 of Lecture Notes in Computer Science, pages 167–181. Springer, 2006.
  * [7] Guillaume Bagan.  Algorithmes et complexité des problèmes d’énumération pour l’évaluation de requêtes logiques. (Algorithms and complexity of enumeration problems for the evaluation of logical queries).  PhD thesis, University of Caen Normandy, France, 2009.
  * [8] Guillaume Bagan, Arnaud Durand, and Etienne Grandjean.  On acyclic conjunctive queries and constant delay enumeration.  In Jacques Duparc and Thomas A. Henzinger, editors, Computer Science Logic, 21st International Workshop, CSL 2007, 16th Annual Conference of the EACSL, Lausanne, Switzerland, September 11-15, 2007, Proceedings, volume 4646 of Lecture Notes in Computer Science, pages 208–222. Springer, 2007.
  * [9] Guillaume Bagan, Arnaud Durand, Etienne Grandjean, and Frédéric Olive.  Computing the jth solution of a first-order query.  ITA, 42(1):147–164, 2008.
  * [10] José L. Balcázar, Josep Díaz, and Joaquim Gabarró.  Structural Complexity I, volume 11 of EATCS Monographs on Theoretical Computer Science.  Springer, 1990.
  * [11] Christoph Berkholz, Fabian Gerhardt, and Nicole Schweikardt.  Constant delay enumeration for conjunctive queries: a tutorial.  ACM SIGLOG News, 7(1):4–33, 2020.
  * [12] Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt.  Answering conjunctive queries under updates.  CoRR, abs/1702.06370, 2017.
  * [13] Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt.  Answering FO+MOD Queries Under Updates on Bounded Degree Databases.  In Michael Benedikt and Giorgio Orsi, editors, 20th International Conference on Database Theory (ICDT 2017), volume 68 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:18, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [14] Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt.  Answering FO+MOD queries under updates on bounded degree databases.  ACM Trans. Database Syst., 43(2):7:1–7:32, 2018.
  * [15] Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt.  Answering ucqs under updates and in the presence of integrity constraints.  In Benny Kimelfeld and Yael Amsterdamer, editors, 21st International Conference on Database Theory, ICDT 2018, March 26-29, 2018, Vienna, Austria, volume 98 of LIPIcs, pages 8:1–8:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [16] Andreas Blass, Yuri Gurevich, Dean Rosenzweig, and Benjamin Rossman.  Interactive small-step algorithms I: axiomatization.  Log. Methods Comput. Sci., 3(4), 2007.
  * [17] Andreas Blass, Yuri Gurevich, Dean Rosenzweig, and Benjamin Rossman.  Interactive small-step algorithms II: abstract state machines and the characterization theorem.  Log. Methods Comput. Sci., 3(4), 2007.
  * [18] Egon Börger and James K. Huggins.  Abstract state machines 1988-1998: Commented ASM bibliography.  Bull. EATCS, 64, 1998.
  * [19] Marco Cadoli and Francesco M. Donini.  A survey on knowledge compilation.  AI Communications, 10(3-4):137–150, 1998.
  * [20] Nofar Carmeli, Shai Zeevi, Christoph Berkholz, Benny Kimelfeld, and Nicole Schweikardt.  Answering (unions of) conjunctive queries using random access and random-order enumeration.  In Dan Suciu, Yufei Tao, and Zhewei Wei, editors, Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, June 14-19, 2020, pages 393–409. ACM, 2020.
  * [21] Stephen A. Cook.  An overview of computational complexity.  Commun. ACM, 26(6):400–408, 1983.
  * [22] Stephen A. Cook and Robert A. Reckhow.  Time bounded random access machines.  J. Comput. Syst. Sci., 7(4):354–375, 1973.
  * [23] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.  Introduction to Algorithms, 3rd Edition.  MIT Press, 2009.
  * [24] Bruno Courcelle.  Linear delay enumeration and monadic second-order logic.  Discret. Appl. Math., 157(12):2675–2700, 2009.
  * [25] Maxime Crochemore and Wojciech Rytter.  Text Algorithms.  Oxford University Press, 1994.
  * [26] Adnan Darwiche and Pierre Marquis.  A knowledge compilation map.  J. Artif. Intell. Res., 17:229–264, 2002.
  * [27] Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani.  Algorithms.  McGraw-Hill, 2008.
  * [28] Scott D. Dexter, Patrick Doyle, and Yuri Gurevich.  Gurevich Abstract State Machines and Schoenhage Storage Modification Machines.  J. Univers. Comput. Sci., 3(4):279–303, 1997.
  * [29] Arnaud Durand.  Fine-grained complexity analysis of queries: From decision to counting and enumeration.  In Dan Suciu, Yufei Tao, and Zhewei Wei, editors, Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, June 14-19, 2020, pages 331–346. ACM, 2020.
  * [30] Arnaud Durand and Etienne Grandjean.  First-order queries on structures of bounded degree are computable with constant delay.  ACM Trans. Comput. Log., 8(4):21, 2007.
  * [31] Arnaud Durand, Nicole Schweikardt, and Luc Segoufin.  Enumerating answers to first-order queries over databases of low degree.  In Richard Hull and Martin Grohe, editors, Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS’14, Snowbird, UT, USA, June 22-27, 2014, pages 121–131. ACM, 2014.
  * [32] Calvin C. Elgot and Abraham Robinson.  Random-access stored-program machines, an approach to programming languages.  J. ACM, 11(4):365–399, 1964.
  * [33] Shimon Even.  Systolic modular multiplication.  In Alfred Menezes and Scott A. Vanstone, editors, Advances in Cryptology - CRYPTO ’90, 10th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11-15, 1990, Proceedings, volume 537 of Lecture Notes in Computer Science, pages 619–624. Springer, 1990.
  * [34] Tomás Feder.  Network flow and 2-satisfiability.  Algorithmica, 11(3):291–319, 1994.
  * [35] Jörg Flum and Martin Grohe.  Parameterized Complexity Theory.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006\.
  * [36] Lakshmi N. Goyal.  A note on atrubin’s real-time iterative multiplier.  IEEE Trans. Computers, 25(5):546–548, 1976.
  * [37] Anaël Grandjean, Gaétan Richard, and Véronique Terrier.  Linear functional classes over cellular automata.  In Enrico Formenti, editor, Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires, AUTOMATA & JAC 2012, La Marana, Corsica, September 19-21, 2012, volume 90 of EPTCS, pages 177–193, 2012.
  * [38] Etienne Grandjean.  Invariance properties of rams and linear time.  Computational Complexity, 4:62–106, 1994.
  * [39] Etienne Grandjean.  Linear time algorithms and NP-complete problems.  SIAM J. Comput., 23(3):573–597, 1994.
  * [40] Etienne Grandjean.  Sorting, linear time and the satisfiability problem.  Ann. Math. Artif. Intell., 16:183–236, 1996.
  * [41] Etienne Grandjean and Frédéric Olive.  Graph properties checkable in linear time in the number of vertices.  J. Comput. Syst. Sci., 68(3):546–597, 2004.
  * [42] Etienne Grandjean and Thomas Schwentick.  Machine-independent characterizations and complete problems for deterministic linear time.  SIAM J. Comput., 32(1):196–230, 2002.
  * [43] Yuri Gurevich.  Evolving algebras: an attempt to discover semantics.  In Grzegorz Rozenberg and Arto Salomaa, editors, Current Trends in Theoretical Computer Science - Essays and Tutorials, volume 40 of World Scientific Series in Computer Science, pages 266–292. World Scientific, 1993.
  * [44] Yuri Gurevich.  Sequential abstract-state machines capture sequential algorithms.  ACM Trans. Comput. Log., 1(1):77–111, 2000.
  * [45] Yuri Gurevich.  What is an algorithm?  In Mária Bieliková, Gerhard Friedrich, Georg Gottlob, Stefan Katzenbeisser, and György Turán, editors, SOFSEM 2012: Theory and Practice of Computer Science - 38th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 21-27, 2012. Proceedings, volume 7147 of Lecture Notes in Computer Science, pages 31–42. Springer, 2012.
  * [46] Yuri Gurevich and Saharon Shelah.  Nearly linear time.  In Albert R. Meyer and Michael A. Taitslin, editors, Logic at Botik ’89, Proceedings, volume 363 of Lecture Notes in Computer Science, pages 108–118. Springer, 1989.
  * [47] Dan Gusfield.  Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology.  Cambridge University Press, 1997.
  * [48] David Harel and Robert Tarjan.  Fast algorithms for finding nearest common ancestors.  SIAM J. Comput., 13(2):338–355, 1984.
  * [49] Juris Hartmanis.  Computational complexity of random acess stored program machines.  Math. Syst. Theory, 5(3):232–245, 1971.
  * [50] John E. Hopcroft and Jeffrey D. Ullman.  Introduction to Automata Theory, Languages and Computation.  Addison-Wesley, 1979.
  * [51] Jarkko Kari.  Basic concepts of cellular automata.  In Grzegorz Rozenberg, Thomas Bäck, and Joost N. Kok, editors, Handbook of Natural Computing, pages 3–24. Springer, 2012.
  * [52] Wojciech Kazana and Luc Segoufin.  First-order query evaluation on structures of bounded degree.  Log. Methods Comput. Sci., 7(2), 2011.
  * [53] Wojciech Kazana and Luc Segoufin.  Enumeration of monadic second-order queries on trees.  ACM Trans. Comput. Log., 14(4):25:1–25:12, 2013.
  * [54] Wojciech Kazana and Luc Segoufin.  First-order queries on classes of structures with bounded expansion.  Log. Methods Comput. Sci., 16(1), 2020.
  * [55] Donald E. Knuth.  The Art of Computer Programming, Volume I: Fundamental Algorithms.  Addison-Wesley, 1968.
  * [56] Donald E. Knuth, James H. Morris Jr., and Vaughan R. Pratt.  Fast pattern matching in strings.  SIAM J. Comput., 6(2):323–350, 1977.
  * [57] Dexter C. Kozen.  Design and Analysis of Algorithms.  Texts and Monographs in Computer Science. Springer, 1992.
  * [58] Clemens Lautemann and Bernhard Weinzinger.  Monadic nlin and quantifier-free reductions.  In Jörg Flum and Mario Rodríguez-Artalejo, editors, Computer Science Logic, 13th International Workshop, CSL ’99, Proceedings, volume 1683 of Lecture Notes in Computer Science, pages 322–337. Springer, 1999.
  * [59] Pierre Marquis.  Compile!  In Blai Bonet and Sven Koenig, editors, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA, pages 4112–4118. AAAI Press, 2015.
  * [60] Farhad Mavaddat and Behrooz Parhami.  Urisc: the ultimate reduced instruction set computer.  The International Journal of Electrical Engineering and Education, 25(4):327–334, 1988.
  * [61] Jacques Mazoyer.  An overview of the firing squad synchronization problem.  In Christian Choffrut, editor, Automata Networks, LITP Spring School on Theoretical Computer Science, Angelès-Village, France, May 12-16, 1986, Proceedings, volume 316 of Lecture Notes in Computer Science, pages 82–94. Springer, 1986.
  * [62] Jacques Mazoyer.  A six-state minimal time solution to the firing squad synchronization problem.  Theor. Comput. Sci., 50:183–238, 1987.
  * [63] Jacques Mazoyer.  On optimal solutions to the firing squad synchronization problem.  Theor. Comput. Sci., 168(2):367–404, 1996.
  * [64] Jacques Mazoyer and Jean-Baptiste Yunès.  Computations on cellular automata.  In Grzegorz Rozenberg, Thomas Bäck, and Joost N. Kok, editors, Handbook of Natural Computing, pages 159–188. Springer, 2012.
  * [65] Bernard ME Moret and Henry D Shapiro.  Algorithms from P to NP (vol. 1) design and efficiency.  Benjamin-Cummings Publishing Co., Inc., 1991.
  * [66] Rajeev Motwani and Prabhakar Raghavan.  Randomized Algorithms.  Cambridge University Press, 1995.
  * [67] Rolf Niedermeier.  Invitation to fixed-parameter algorithms.  Oxford Lecture Series in Mathematics and its Applications 31, 2006.
  * [68] Christos H. Papadimitriou.  Computational complexity.  Addison-Wesley, 1994.
  * [69] Christos H. Papadimitriou and Kenneth Steiglitz.  Combinatorial Optimization: Algorithms and Complexity.  Prentice-Hall, 1982.
  * [70] Kenneth W. Regan.  Linear time and memory-efficient computation.  SIAM J. Comput., 25(1):133–168, 1996.
  * [71] Arnold Schönhage.  On the power of random access machines.  In Hermann A. Maurer, editor, Automata, Languages and Programming, 6th Colloquium, Graz, Austria, July 16-20, 1979, Proceedings, volume 71 of Lecture Notes in Computer Science, pages 520–529. Springer, 1979.
  * [72] Arnold Schönhage.  Storage modification machines.  SIAM J. Comput., 9(3):490–508, 1980.
  * [73] Thomas Schwentick.  Algebraic and logical characterizations of deterministic linear time classes.  In Rüdiger Reischuk and Michel Morvan, editors, STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27 - March 1, 1997, Proceedings, volume 1200 of Lecture Notes in Computer Science, pages 463–474. Springer, 1997.
  * [74] Thomas Schwentick.  Descriptive complexity, lower bounds and linear time.  In Georg Gottlob, Etienne Grandjean, and Katrin Seyr, editors, Computer Science Logic, 12th International Workshop, CSL ’98, Annual Conference of the EACSL, Brno, Czech Republic, August 24-28, 1998, Proceedings, volume 1584 of Lecture Notes in Computer Science, pages 9–28. Springer, 1998.
  * [75] Robert Sedgewick and Kevin Wayne.  Algorithms (Fourth edition deluxe).  Addison-Wesley, 2016.
  * [76] Luc Segoufin.  Enumerating with constant delay the answers to a query.  In Joint 2013 EDBT/ICDT Conferences, ICDT ’13 Proceedings, Genoa, Italy, March 18-22, 2013, pages 10–20, 2013.
  * [77] Luc Segoufin.  A glimpse on constant delay enumeration (invited talk).  In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France, pages 13–27, 2014.
  * [78] John C. Shepherdson and Howard E. Sturgis.  Computability of recursive functions.  J. ACM, 10(2):217–255, 1963.
  * [79] Steven Skiena.  The Algorithm Design Manual, Third Edition.  Texts in Computer Science. Springer, 2020.
  * [80] Alvy Ray Smith.  Simple computation-universal cellular spaces.  J. ACM, 18(2):339–353, 1971.
  * [81] Yann Strozecki.  Enumeration complexity.  Bull. EATCS, 129, 2019.
  * [82] Robert Endre Tarjan.  Efficiency of a good but not linear set union algorithm.  J. ACM, 22(2):215–225, 1975.
  * [83] Robert Endre Tarjan.  Data structures and network algorithms, volume 44 of CBMS-NSF regional conference series in applied mathematics.  SIAM, 1983.
  * [84] Véronique Terrier.  Language recognition by cellular automata.  In Grzegorz Rozenberg, Thomas Bäck, and Joost N. Kok, editors, Handbook of Natural Computing, pages 123–158. Springer, 2012.
  * [85] Takeaki Uno.  Constant time enumeration by amortization.  In Frank Dehne, Jörg-Rüdiger Sack, and Ulrike Stege, editors, Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, volume 9214 of Lecture Notes in Computer Science, pages 593–605. Springer, 2015\.
  * [86] Klaus Wagner and Gerd Wechsung.  Computational Complexity.  Springer, 1986.
  * [87] Kunihiro Wasa.  Enumeration of enumeration algorithms.  CoRR, abs/1605.05102, 2016.
  * [88] Wikipedia.  Church-Turing thesis.  https://en.wikipedia.org/wiki/Church-Turing_thesis.
  * [89] Wikipedia.  Random access machine.  https://en.wikipedia.org/wiki/Random-access_machine.

##  11 Appendix: Proof of Theorem 3 of Subsection 8.2

Let us first recall the result.

Theorem 3. _Let $d\geq 1$ be a constant integer and let
$\mathtt{op}:\mathbb{N}^{r}\to\mathbb{N}$ be an operation of arity $r\geq 1$,
computable in linear time on a cellular automaton (CA). There is a RAM with
addition, such that, for any input integer $N>0$:_

  1. 1.

_Pre-computation:__the RAM computes some tables in time_ $O(N)$;

  2. 2.

_Operation:__from these pre-computed tables and after reading_ $r$ integers
$X_{1},\ldots,X_{r}<N^{d}$, the RAM computes in constant time the integer
$\mathtt{op}(X_{1},\ldots,X_{r})$.

###### Proof.

Let $\mathcal{A}=(Q,\delta)$ be a CA that computes in linear time an operation
$\mathtt{op}$, i.e. the function
$f_{\mathtt{op}}:X_{1};\cdots;X_{r}\mapsto\mathtt{op}(X_{1},\ldots,X_{r})$.
Before building a RAM that simulates the CA, let us slightly tweak the CA
input configuration. In particular, we add the integer $N$ to the input as a
reference to the upper bound $N^{d}$ of the operands
$X_{1},\ldots,X_{r}<N^{d}$.

Let us represent the $(r+1)$-tuple of integers $(N,X_{1},\ldots,X_{r})$, for
$X_{1},\ldots,X_{r}<N^{d}$, by the word, called
$\mathtt{code}(N,X_{1},\ldots,X_{r})\coloneqq u_{L-1}\cdots
u_{1}u_{0}\in\Gamma^{L}$, on the alphabet
$\Gamma\coloneqq\\{0,1,\ldots,\gamma-1\\}$ where $\gamma\coloneqq 2^{r+1}$,
which is defined as follows:

Length of the code:

$L\coloneqq\mathtt{length}(N^{d})$;

Letters of the code:

$u_{j}\coloneqq\sum_{i=0}^{r}x_{i,j}2^{i}$, for $0\leq j<L$, where
$x_{i,L-1}\dots x_{i,1}x_{i,0}$ denotes the binary representation of $X_{i}$
in $L$ bits, for $i\in\\{0,1,\ldots,r\\}$ and $X_{0}\coloneqq N$. In other
words, $u_{j}$ is the integer whose binary representation is column $j$ of the
0/1 matrix $(x_{i,j})_{0\leq i\leq r,0\leq j<L}$ when the columns are numbered
from $L-1$ (left) downto 0 (right).

_Example:_ For $r=2$, $d=1$, and the size integer $N=13$, which has the binary
representation $1101$ of length $L=4$, and for $X_{1}=7$ and $X_{2}=9$, which
have the binary representations (of length $L=4$) $0111$ and $1001$,
respectively, we obtain $\gamma=2^{r+1}=8$,
$\Gamma=\\{0,1,\ldots,\gamma-1=7\\}$ and
$\mathtt{code}(N,X_{1},\ldots,X_{r})=5327\in\Gamma^{4}$, see Table 12.

$X_{2}=9$ | 1 | 0 | 0 | 1
---|---|---|---|---
$X_{1}=7$ | 0 | 1 | 1 | 1
$X_{0}=N=13$ | 1 | 1 | 0 | 1
$\mathtt{code}(N,X_{1},X_{2})$ | $u_{3}=5$ | $u_{2}=3$ | $u_{1}=2$ | $u_{0}=7$
Table 12: Encoding the input $(N,X_{1},\ldots,X_{r})$

It is tedious but routine to build a cellular automaton that computes in
linear time the function $g:\mathtt{code}(N,X_{1},\ldots,X_{r})\mapsto
X_{1};\cdots;X_{r}$. By Lemma 15, the composition of functions
$f_{\mathtt{op}}\circ
g:\mathtt{code}(N,X_{1},\ldots,X_{r})\mapsto\mathtt{op}(X_{1},\ldots,X_{r})$
is computed in linear time on a CA, also called for simplicity
$\mathcal{A}=(Q,\delta)$, with the set of output states $Q_{out}\subset Q$. By
Definition 10 supplemented by Lemma 17 and Remark 18, this means that there
exist a constant integer $c\geq 1$ and a projection
$\pi:Q_{out}\cup\\{\sharp\\}\to\\{0,1,\sharp\\}$ such that, for all integers
$N>0$ and $X_{1},\ldots,X_{r}<N^{d}$, we have
$\delta^{cL}(\sharp\mathtt{Input}\sharp)=\sharp Y\sharp$,

  * •

with $\mathtt{Input}\coloneqq\mathtt{code}(N,X_{1},\ldots,X_{r})$ and
$L\coloneqq\mathtt{length}(\mathtt{Input})=\mathtt{length}(N^{d})$,

  * •

and for a word $Y=y_{cL-1}\cdots y_{0}\in(Q_{out})^{cL}$ such that
$\mathtt{Output}\coloneqq\pi(y_{cL-1})\cdots\pi(y_{0})\in\\{0,1\\}^{cL}$ is
the binary notation of the integer $\mathtt{op}(X_{1},\ldots,X_{r})$ written
to $cL$ bits.

We can assume $Q\coloneqq\\{0,1,\ldots s-1\\}$ with
$\Gamma\coloneqq\\{0,1,\ldots,\gamma-1\\}$, $\gamma\coloneqq 2^{r+1}$,
$\sharp\coloneqq\gamma$, and
$\Gamma\cup\\{\sharp\\}\subseteq\leavevmode\nobreak\ Q$, which implies
$s\geq\gamma+1$. For convenience, the active cells of the computation are
numbered $cL-1,\ldots,1,0$, increasing from right to left (like the
representation of integers in any base). Thus, at any time $t\in[0,cL]$ of the
computation, the configuration has the form $\sharp q_{cL-1}\cdots
q_{1}q_{0}\sharp$, where $q_{i}\in Q$ is the state of cell $i$ (possibly
$\sharp$) at time $t$.

We are now ready to present the simulation of the CA by a RAM. Before
describing it with all the necessary details, let us first give the guiding
ideas of this simulation.

##### A simplified view of the simulation.

The trick is to divide the active interval of the computation, of length $cL$,
into a constant number of consecutive blocks of “small” length $\ell$, called
$\ell$-blocks, numbered $\ldots 2,1,0$ (increasing from right to left!). We
take $\ell\coloneqq\epsilon\log_{2}N$ for a “small” constant $\epsilon$.
(Precisely, we will define $\ell\coloneqq\left\lceil L/D\right\rceil$, for a
large fixed integer $D$.) Similarly, we divide the computation, of time $cL$,
into a constant number of computation intervals of duration $\ell$, called
“global $\ell$-transitions”.

By abuse of language, the string of states $B_{j}^{t}\in Q^{\ell}$ of an
$\ell$-block at some time $t$ is called an $\ell$-block at time $t$.
Therefore, the configuration at any time $t$ is the concatenation $\sharp
B_{c_{0}}^{t}\cdots B_{1}^{t}\sharp$, for the constant
$c_{0}\coloneqq\left\lceil cL/\ell\right\rceil$.

The essential point is the “locality” of the cellular automaton: the state of
any cell $x$ at any time $t+1$ (resp. $t+\ell$) is entirely determined by the
states of the three cells $x-1,x,x+1$ (resp. the state string of the cell
interval $[x-\ell,x+\ell]$) at time $t$. As a consequence, an $\ell$-block
$B_{j}^{t+\ell}$, i.e. the $\ell$-block $j$ at time $t+\ell$, is determined by
the three $\ell$-blocks, $B_{j+1}^{t}$, $B_{j}^{t}$, $B_{j-1}^{t}$, which are
the $\ell$-block itself and its left and right neighboring $\ell$-blocks at
time $t$. In other words, the $\ell$-block $B_{j}^{t+\ell}\in Q^{\ell}$ is
determined by the concatenation $B_{j+1}^{t}B_{j}^{t}B_{j-1}^{t}\in
Q^{3\ell}$. Such a concatenation is called a “local configuration” and the
transformation $B_{j+1}^{t}B_{j}^{t}B_{j-1}^{t}\mapsto B_{j}^{t+\ell}$ from
$Q^{3\ell}$ to $Q^{\ell}$ is called a “local $\ell$-transition”. There are two
crucial points:

What preprocessing in linear time?

The number of possible “local configurations”, therefore the number of
possible “local $\ell$-transitions” for the parameter $N$, called
$\mathtt{NbLocalConf}(N)$, is the cardinality of the set $Q^{3\ell}$, which is
“small”, precisely $s^{3\ell}$; this will make it possible to pre-compute in
$O(N)$ time a table of all possible “local $\ell$-transitions” for the integer
$N$;

How to compute $\mathtt{op}$ in constant time?

Since the time (resp. length of the active interval) of the computation is
$cL$, then the computation (resp. the active interval) is the concatenation of
$cL/\ell=O(1)$ global $\ell$-transitions (resp. $\ell$-blocks), and all the
computation on $\mathtt{Input}\coloneqq\mathtt{code}(N,X_{1},\ldots,X_{r})$
can be done by performing $(cL/\ell)^{2}=O(1)$ local $\ell$-transitions; it is
a constant time since each local $\ell$-transition is performed by consulting
a single element in the table of local $\ell$-transitions.

######  Remark 22 (processing the input and output in constant time).

In this simplified view, we have not mentioned the reading of the operands
$X_{1},\ldots,X_{r}<N^{d}$, with the encoding process giving the initial
configuration $\sharp\mathtt{Input}\sharp$, for
$\mathtt{Input}\coloneqq\mathtt{code}(N,X_{1},\ldots,X_{r})$, nor the final
output process building $\mathtt{op}(X_{1},\ldots,X_{r})$ by the projection of
the final configuration. We will explain below how these input and output
processes can also be performed in constant time.

######  Remark 23.

Our simplified view also overlooked the fact that in general, the time $cL$ of
the computation is not a multiple of $\ell$. In general, we have
$cL=(c_{0}-1)\ell+\rho$, for the “constant” $c_{0}\coloneqq\left\lceil
cL/\ell\right\rceil$ and an integer $\rho\in[1,\ell]$. Therefore, the
computation breaks down into $c_{0}-1$ global $\ell$-transitions, each
composed of $c_{0}$ local $\ell$-transitions, and one global $\rho$-transition
composed of $c_{0}$ local $\rho$-transitions of time $\rho$. Like a local
$\ell$-transition, a local $\rho$-transition produces, from a local
configuration $(B_{2},B_{1},B_{0})\in(Q^{\ell})^{3}$ of adjacent $\ell$-blocks
at some time $t$, the value $B^{\prime}_{1}\in Q^{\ell}$ of the intermediate
$\ell$-block at time $t+\rho$ (instead of time $t+\ell$ for a local
$\ell$-transition).

##### The number of local configurations.

Let us now determine the value of the “cutting” constant $D$ which determines
the block length $\ell(N)\coloneqq\left\lceil L(N)/D\right\rceil$, for
$L(N)\coloneqq\mathtt{length}(N^{d})$, so that the number
$\mathtt{NbLocalConf}(N)$ of the possible local configurations, for an input
$\mathtt{code}(N,X_{1},\ldots,X_{r})$, is $O(N^{\sigma})$, for some
$\sigma<1$. By definition of local configurations, we have

$\mathtt{NbLocalConf}(N)=s^{3\ell}=s^{3\left\lceil
L/D\right\rceil}<s^{3}s^{3L/D}$

because of $\left\lceil L/D\right\rceil<L/D+1$. We also have
$L=\mathtt{length}(N^{d})\leq 1+\log_{2}N^{d}=1+d\log_{2}N$. It comes
$s^{3L/D}\leq s^{3/D}s^{(3d/D)\log_{2}N}=s^{3/D}N^{(3d/D)\log_{2}s}$. from
which we deduce

$\mathtt{NbLocalConf}(N)<s^{3+3/D}\times N^{(3d/D)\log_{2}s}$

This implies $\mathtt{NbLocalConf}(N)<c_{1}N^{\sigma}$, for the constant
factor $c_{1}\coloneqq s^{3+3/D}$ and the constant exponent
$\sigma\coloneqq(3d/D)\log_{2}s$, which is less than 1 if we fix the value of
our constant integer $D$ to more than $3d\log_{2}s$. Therefore, setting
$D\coloneqq 1+\left\lfloor 3d\log_{2}s\right\rfloor$ is suitable.

It is time to present in detail how a RAM can simulate in constant time the
cellular automaton $\mathcal{A}=(Q,\delta)$ thanks to pre-computed tables in
linear time. It is convenient to confuse the active part (resp. any
$\ell$-block) of a computation of $\mathcal{A}$, which is a non-empty word
over the alphabet $Q=\\{0,1,\ldots,s-1\\}$, with the integer represented by
this word in the base $s$. As we have already seen, we can easily go from a
string of $s$-digits to the integer represented by this string in the base
$s$, by Horner’s method, and vice versa.

##### Computation of local transition tables.

First, to represent the transition function $\delta$ of the CA, let us define
the 3-dimensional array $\mathtt{DELTA}[0..s-1][0..s-1][0..s-1]$ by

$\mathtt{DELTA}[x_{2}][x_{1}][x_{0}]\coloneqq\delta(x_{2},x_{1},x_{0})$

The $\mathtt{DELTA}$ array can be computed in constant time $s^{3}$ since for
each $(x_{0},x_{1},x_{2})\in[0..s-1]^{3}$, $\delta(x_{2},x_{1},x_{0})$ is an
explicit integer.

Let us now represent the table of local $\rho$-transitions
$B_{j+1}^{t}B_{j}^{t}B_{j-1}^{t}\mapsto B_{j}^{t+\ell}$ from $Q^{3\ell}$ to
$Q^{\ell}$, for all the $\rho\in[1,\ell]$, by the 2-dimensional array
$\texttt{LT}[1..\ell][0..s^{3\ell}-1]$ defined, for $1\leq\rho\leq\ell$,
$B_{0},B_{1},B_{2}\in Q^{\ell}$ and $B=B_{2}s^{2\ell}+B_{1}s^{\ell}+B_{0}$, by
$\texttt{LT}[\rho][B]\coloneqq R$, which is interpreted as follows: if, at any
time $t$, three consecutive $\ell$-blocks numbered $j+1$, $j$, $j-1$ are
respectively $B_{2},B_{1},B_{0}$, then at time $t+\rho$, the middle
$\ell$-block (numbered $j$) is $R$.

The following code computes the LT array thanks to the $\mathtt{DELTA}$ array:

Algorithm 21 Computation of the LT array

1: for $\texttt{B}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
0\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\
\texttt{s}^{3\times\ell}-1$ do

2: for $\texttt{B}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
0\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\
\texttt{s}^{3\times\ell}-1$ do for $\rho\leavevmode\nobreak\
\textbf{from}\leavevmode\nobreak\ 1\leavevmode\nobreak\
\textbf{to}\leavevmode\nobreak\ \ell$ do

3: $\texttt{R}\leftarrow\texttt{B}$

4: $\texttt{R}\leftarrow\texttt{B}$ for $\texttt{x}\leavevmode\nobreak\
\textbf{from}\leavevmode\nobreak\ 0\leavevmode\nobreak\
\textbf{to}\leavevmode\nobreak\ 3\times\ell-1$ do

5: $\texttt{C}[\texttt{x}][0]\leftarrow\texttt{R}\;\mathtt{mod}\;\texttt{s}$

6: $\texttt{R}\leftarrow\texttt{R}\;\mathtt{div}\;\texttt{s}$
$\texttt{R}\leftarrow\texttt{R}\;\mathtt{div}\;\texttt{s}$

7: $\texttt{R}\leftarrow\texttt{R}\;\mathtt{div}\;\texttt{s}$ for
$\texttt{t}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
1\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \rho$ do

8: for $\texttt{t}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
1\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \rho$ do for
$\texttt{x}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
\ell-\rho+\texttt{t}\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\
2\times\ell-1+\rho-\texttt{t}$ do

9:
$\texttt{C}[\texttt{x}][\texttt{t}]\leftarrow\texttt{DELTA}[\texttt{C}[\texttt{x}+1][\texttt{t}-1]][\texttt{C}[\texttt{x}][\texttt{t}-1]][\texttt{C}[\texttt{x}-1][\texttt{t}-1]]$
$\texttt{C}[\texttt{x}][\texttt{t}]\leftarrow\texttt{DELTA}[\texttt{C}[\texttt{x}+1][\texttt{t}-1]][\texttt{C}[\texttt{x}][\texttt{t}-1]][\texttt{C}[\texttt{x}-1][\texttt{t}-1]]$
$\texttt{C}[\texttt{x}][\texttt{t}]\leftarrow\texttt{DELTA}[\texttt{C}[\texttt{x}+1][\texttt{t}-1]][\texttt{C}[\texttt{x}][\texttt{t}-1]][\texttt{C}[\texttt{x}-1][\texttt{t}-1]]$
$\texttt{C}[\texttt{x}][\texttt{t}]\leftarrow\texttt{DELTA}[\texttt{C}[\texttt{x}+1][\texttt{t}-1]][\texttt{C}[\texttt{x}][\texttt{t}-1]][\texttt{C}[\texttt{x}-1][\texttt{t}-1]]$

10: $\texttt{R}\leftarrow 0$

11: $\texttt{R}\leftarrow 0$ for $\texttt{x}\leavevmode\nobreak\
\textbf{from}\leavevmode\nobreak\ 2\times\ell-1\leavevmode\nobreak\
\textbf{downto}\leavevmode\nobreak\ \ell$ do

12:
$\texttt{R}\leftarrow\texttt{R}\times\texttt{s}+\texttt{C}[\texttt{x}][\ell]$
$\texttt{R}\leftarrow\texttt{R}\times\texttt{s}+\texttt{C}[\texttt{x}][\ell]$

13: $\texttt{LT}[\rho][\texttt{B}]\leftarrow\texttt{R}$
$\texttt{LT}[\rho][\texttt{B}]\leftarrow\texttt{R}$
$\texttt{LT}[\rho][\texttt{B}]\leftarrow\texttt{R}$
$\texttt{LT}[\rho][\texttt{B}]\leftarrow\texttt{R}$

_Justification:_ First, note that the main loop (line 1) goes through the
integers $B<s^{3\ell}$ encoding local configurations (triplets of adjacent
$\ell$-blocks). Of course, $C[x,t]$ represents the state of a cell
$x\in[0,3\ell-1]$ of the local configuration at an instant numbered
$t\in[0,\rho]$ of a time interval of duration $\rho$, and the main assignment
(line 9) is a paraphrase of the transition function

$\displaystyle C[x][t]=\delta(C[x+1][t-1],C[x][t-1],C[x-1][t-1])$ (33)

The loop condition $x\in[\ell-\rho+t,\;2\ell-1+\rho-t]$ of line 8 for the
application of (33) is justified inductively by the locality of the transition
function: obviously, the sequence of states at time $t$ of the cell interval
$[\ell-\rho+t,\;2\ell-1+\rho-t]$ (which is equal to the middle $\ell$-block
interval $[\ell,\;2\ell-1]$ for $t=\rho$) are determined by the sequence of
states at time $t-1$ of the cell interval
$[\ell-\rho+(t-1),\;2\ell-1+\rho-(t-1)]$, which has one more cell, numbered
$\ell-\rho+t-1$ (resp. $2\ell-1+\rho-t+1$), at each end.

In addition, lines 3-6 of the algorithm transform an integer $B<s^{3\ell}$
(representing a local configuration) into the array of its $3\ell$ $s$-digits:
the initial string $C[x][0]$, for $0\leq x\leq 3\ell-1$.

Conversely, lines 10-12 transform the final string $C[x][\rho]$, for $\ell\leq
x\leq 2\ell-1$, into the integer $R<s^{\ell}$ it represents: this is the
resulting middle $\ell$-block of the local $\rho$-transition (line 13).

##### Representing the computation by a two-dimensional array of
$\ell$-blocks.

We represent the computation of the CA by the sequence of its $c_{0}+1$ global
configurations $\mathcal{C}_{t\ell}\coloneqq\sharp B_{c_{0}}^{t\ell}\cdots
B_{1}^{t\ell}\sharp$ at time $t\ell$, for $0\leq t\leq c_{0}$, where
$B_{i}^{t\ell}$ is the $i$th $\ell$-block, $1\leq i\leq c_{0}$, of
$\mathcal{C}_{t\ell}$ from the right. Since we have $cL=(c_{0}-1)\ell+\rho$,
for the constant $c_{0}\coloneqq\left\lceil cL/\ell\right\rceil$ and an
integer $\rho$ such that $1\leq\rho\leq\ell$, note that, in case $\rho<\ell$,
we need to add $\ell-\rho$ symbols $\sharp$ at the left of the $\rho$-block
numbered $c_{0}$ to make it an $\ell$-block.

For convenience, we add to each global configuration $\mathcal{C}_{t\ell}$ two
$\ell$-blocks, $B_{0}^{t\ell}\coloneqq\sharp^{\ell}$ at its right, and
$B_{c_{0}+1}^{t\ell}\coloneqq\sharp^{\ell}$ at its left. Thus, the global
configuration $\mathcal{C}_{t\ell}$ is now written
$B_{c_{0}+1}^{t\ell}B_{c_{0}}^{t\ell}\cdots B_{1}^{t\ell}B_{0}^{t\ell}$. Note
that the string $\sharp^{\ell}$ is assimilated to the integer represented in
base $s$ by $\ell$ digits $\gamma$, $\overline{\gamma\cdots\gamma}$, which, by
our convention $\sharp\coloneqq\gamma\coloneqq 2^{r+1}$, is equal to
$2^{r+1}(s^{\ell-1}+\cdots+s+1)=2^{r+1}(s^{\ell}-1)/(s-1)$.

##### Computing the initial configuration.

This is the most technical and most tedious part of the simulation. Recall
$cL=(c_{0}-1)\ell+\rho$, for the “constant” $c_{0}\coloneqq\left\lceil
cL/\ell\right\rceil$ and the integer $\rho$, which satisfies
$1\leq\rho\leq\ell$. Similarly, $L=(c_{1}-1)\ell+\lambda$, for the “constant”
$c_{1}\coloneqq\left\lceil L/\ell\right\rceil$ and the integer $\lambda$,
which satisfy $1\leq\lambda\leq\ell$ and $c_{1}\leq c_{0}$. (We write that
$c_{0}$ and $c_{1}$ are “constant” in quotation marks because, even if they
depend on $N$, they are bounded by constants: precisely, we have
$c_{1}=\left\lceil L/\ell\right\rceil=\left\lceil L/\left\lceil L/D
\right\rceil\right\rceil\leq\left\lceil L/(L/D)\right\rceil=D$ and, likewise,
$c_{0}\leq cD$.) Also, recall the definition
$\mathtt{code}(X_{0},X_{1},\ldots,X_{r})\coloneqq u_{L-1}\cdots
u_{1}u_{0}\in\Gamma^{L}$ where $u_{j}\coloneqq\sum_{i=0}^{r}x_{i,j}2^{i}$, for
$0\leq j<L$, and $x_{i,L-1}\cdots x_{i,1}x_{i,0}$ denotes the binary
representation of $X_{i}$ in $L$ bits. In other words, the $j$th
$\gamma$-digit $u_{j}$ of $\mathtt{code}(X_{0},X_{1},\ldots,X_{r})$, where
$\gamma\coloneqq 2^{r+1}$, is

$\sum_{i=0}^{r}(j\mathtt{th}\;\mathtt{bit}\;\mathtt{of}\;X_{i})\times 2^{i}$.

We obtain the initial configuration
$\mathcal{C}_{0}=B_{c_{0}+1}^{0}B_{c_{0}}^{0}\cdots B_{1}^{0}B_{0}^{0}$ by the
four following steps.

  1. 1.

Decompose each of the binary strings $X_{i}\in\\{0,1\\}^{L}$, $0\leq j\leq r$,
as a concatenation $X_{i}=X_{c_{1},i}X_{c_{1}-1,i}\cdots X_{1,i}$ of, from
right to left, $c_{1}-1$ $\ell$-blocks
$X_{1,i},\ldots,X_{c_{1}-1,i}\in\\{0,1\\}^{\ell}$ and a $\lambda$-block
$X_{c_{1},i}\in\\{0,1\\}^{\lambda}$;

  2. 2.

Compute the decomposition of
$\mathtt{Input}\coloneqq\mathtt{code}(X_{0},X_{1},\ldots,X_{r})\in\Gamma^{L}$
as a concatenation $U=U_{c_{1}}U_{c_{1}-1}\cdots U_{1}$ of $c_{1}-1$
$\ell$-blocks $U_{1},\ldots,U_{c_{1}-1}\in\Gamma^{\ell}$ and a $\lambda$-block
$U_{c_{1}}\in\Gamma^{\lambda}$; here again, for each $h\in[1,c_{1}]$, we write
$U_{h}=\mathtt{code}(X_{h,0},X_{h,1},\ldots,X_{h,r})$ to mean that for each
rank $i$, $0\leq i<\ell$, the $i$th $\gamma$-digit of $U_{h}$ is
$\sum_{j=0}^{r}(i\mathtt{th}\;\mathtt{bit}\;\mathtt{of}\;X_{h,j})\times
2^{j}$;

  3. 3.

Compute the $\ell$-blocks $B_{j}^{0}$, for $j\in[1,c_{1}-1]$, of the global
configuration $\mathcal{C}_{0}=B_{c_{0}+1}^{0}B_{c_{0}}^{0}\cdots B_{0}^{0}$
at time 0; note that, for each $j\in[1,c_{1}-1]$, the representation of
$U_{j}$ in base $\gamma$, denoted $\overline{a_{\ell-1}\cdots
a_{1}a_{0}}^{\gamma}$, “is” the representation of $B_{j}^{0}$ in base $s$,
i.e. the same string of digits: $B_{j}^{0}=\overline{a_{\ell-1}\cdots
a_{1}a_{0}}^{s}$; in terms of integers, this means that if we have
$U_{j}=\sum_{i=0}^{\ell-1}a_{i}\gamma^{i}$ ($0\leq a_{i}\leq\gamma-1$), then
we obtain $B_{j}^{0}=\sum_{i=0}^{\ell-1}a_{i}s^{i}$, which we write
$B_{j}^{0}=\mathtt{convert}_{\gamma\to s}(U_{j})$;

  4. 4.

Compute the other $\ell$-blocks of $\mathcal{C}_{0}$:

    1. (a)

as seen above, we have $B_{j}^{0}=\sharp^{\ell}=2^{r+1}(s^{\ell}-1)/(s-1)$,
for $j\in\\{0\\}\cup[c_{1}+1,c_{0}+1]$ (recall $\sharp\coloneqq\gamma\coloneqq
2^{r+1}$);

    2. (b)

finally, the representation of the integer $B_{c_{1}}^{0}$ in the base $s$
corresponds to the concatenation of strings $\sharp^{\ell-\lambda}$ and
$U_{c_{1}}$. Thus we obtain

$B_{c_{1}}^{0}=2^{r+1}(s^{\ell}-s^{\lambda})/(s-1)+U^{\prime}_{c_{1}}$

with $U^{\prime}_{c_{1}}\coloneqq\mathtt{convert}_{\gamma\to s}(U_{c_{1}})$,
which means that $U_{c_{1}}=\sum_{i=0}^{\lambda-1}a_{i}\gamma^{i}$ ($0\leq
a_{i}\leq\gamma-1$) implies
$U^{\prime}_{c_{1}}=\sum_{i=0}^{\lambda-1}a_{i}s^{i}$.

To compute the initial configuration in constant time by the previous
algorithm (1-4), we need to pre-compute two arrays in linear time.

##### Computing the tables $\mathtt{CODE}$ and $\mathtt{CONVERT}$.

Let
$\mathtt{CODE}[1..\ell][0..2^{\ell}-1][0..2^{\ell}-1]\cdots[0..2^{\ell}-1]$ be
the array defined, for each $\lambda\in[1,\ell]$ and all
$X_{0},X_{1},\ldots,X_{r}\in[0,2^{\lambda}-1]$, by

$\mathtt{CODE}[\lambda][X_{0}],[X_{1}]\cdots[X_{r}]\coloneqq\mathtt{code}(X_{0},X_{1},\ldots,X_{r})$

where $\mathtt{code}(X_{0},X_{1},\ldots,X_{r})$ is the integer in
$[0,\gamma^{\lambda}-1]$ ($\gamma=2^{r+1}$) defined by item 2 above. The
$\mathtt{CODE}$ array is computed by the following algorithm:

Algorithm 22 Computation of the CODE array

1: for $\lambda\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
1\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \ell$ do

2: for $\lambda\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
1\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \ell$ do for
$(\texttt{X}_{0},\texttt{X}_{1},\ldots,\texttt{X}_{\texttt{r}})\in[0,2^{\lambda}-1]^{\texttt{r}+1}$
do

3: for
$(\texttt{X}_{0},\texttt{X}_{1},\ldots,\texttt{X}_{\texttt{r}})\in[0,2^{\lambda}-1]^{\texttt{r}+1}$
do for $\texttt{j}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
0\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \texttt{r}$ do

4: for $\texttt{j}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
0\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \texttt{r}$ do for
$\texttt{i}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
0\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \lambda-1$ do

5:
$\texttt{BIT}_{\texttt{j}}[\texttt{i}]\leftarrow\texttt{X}_{\texttt{j}}\;\mathtt{mod}\;2$

6: $\texttt{X}_{\texttt{j}}\leftarrow\texttt{X}_{\texttt{j}}\;\mathtt{div}\;2$
$\texttt{X}_{\texttt{j}}\leftarrow\texttt{X}_{\texttt{j}}\;\mathtt{div}\;2$
$\texttt{X}_{\texttt{j}}\leftarrow\texttt{X}_{\texttt{j}}\;\mathtt{div}\;2$
$\texttt{X}_{\texttt{j}}\leftarrow\texttt{X}_{\texttt{j}}\;\mathtt{div}\;2$

7: $\texttt{X}_{\texttt{j}}\leftarrow\texttt{X}_{\texttt{j}}\;\mathtt{div}\;2$
for $\texttt{i}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
0\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \lambda-1$ do

8: $\texttt{DIGIT}[\texttt{i}]\leftarrow 0$

9: $\texttt{DIGIT}[\texttt{i}]\leftarrow 0$ for
$\texttt{j}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
\texttt{r}\leavevmode\nobreak\ \textbf{downto}\leavevmode\nobreak\ 0$ do

10: $\texttt{DIGIT}[\texttt{i}]\leftarrow
2\times\texttt{DIGIT}[\texttt{i}]+\texttt{BIT}_{\texttt{j}}[\texttt{i}]$
$\texttt{DIGIT}[\texttt{i}]\leftarrow
2\times\texttt{DIGIT}[\texttt{i}]+\texttt{BIT}_{\texttt{j}}[\texttt{i}]$
$\texttt{DIGIT}[\texttt{i}]\leftarrow
2\times\texttt{DIGIT}[\texttt{i}]+\texttt{BIT}_{\texttt{j}}[\texttt{i}]$
$\texttt{DIGIT}[\texttt{i}]\leftarrow
2\times\texttt{DIGIT}[\texttt{i}]+\texttt{BIT}_{\texttt{j}}[\texttt{i}]$

11: $\texttt{V}\leftarrow 0$

12: $\texttt{V}\leftarrow 0$ for $\texttt{i}\leavevmode\nobreak\
\textbf{from}\leavevmode\nobreak\ \lambda-1\leavevmode\nobreak\
\textbf{downto}\leavevmode\nobreak\ 0$ do

13: $\texttt{V}\leftarrow\gamma\times\texttt{V}+\texttt{DIGIT}[\texttt{i}]$
$\texttt{V}\leftarrow\gamma\times\texttt{V}+\texttt{DIGIT}[\texttt{i}]$

14:
$\texttt{CODE}[\lambda][\texttt{X}_{0}][\texttt{X}_{1}]\cdots[\texttt{X}_{\texttt{r}}]\leftarrow\texttt{V}$
$\texttt{CODE}[\lambda][\texttt{X}_{0}][\texttt{X}_{1}]\cdots[\texttt{X}_{\texttt{r}}]\leftarrow\texttt{V}$
$\texttt{CODE}[\lambda][\texttt{X}_{0}][\texttt{X}_{1}]\cdots[\texttt{X}_{\texttt{r}}]\leftarrow\texttt{V}$
$\texttt{CODE}[\lambda][\texttt{X}_{0}][\texttt{X}_{1}]\cdots[\texttt{X}_{\texttt{r}}]\leftarrow\texttt{V}$

_Comment:_ Lines 3-6 of the algorithm compute the $\lambda$ bits of each
integer $X_{0},\dots,X_{r}<2^{\lambda}$. Lines 7-10 and Lines 11-14 compute
respectively the $\lambda$ $\gamma$-digits of the integer
$\texttt{CODE}[\lambda][\texttt{X}_{0}][\texttt{X}_{1}]\cdots[\texttt{X}_{\texttt{r}}]$
and its value.

Similarly, let $\mathtt{CONVERT}[1..\ell][0..\gamma^{\ell}-1]$ be the array
defined, for each length $\lambda\in[1,\ell]$ and each integer
$B\in[0,\gamma^{\lambda}-1]$, by
$\mathtt{CONVERT}[\lambda][B]\coloneqq\mathtt{convert}_{\gamma\to s}(B)$ where
$\mathtt{convert}_{\gamma\to s}(B)$ is the integer in $[0,s^{\lambda}-1]$
defined by the following implication (see items 3 and 4 above):
$B=\sum_{i=0}^{\lambda-1}a_{i}\gamma^{i}$, for $0\leq a_{i}<\gamma$, implies
$\mathtt{convert}_{\gamma\to s}(B)\coloneqq\sum_{i=0}^{\lambda-1}a_{i}s^{i}$.
We can easily verify that the $\mathtt{CONVERT}$ array is computed by the
following algorithm:

Algorithm 23 Computation of the CONVERT array

1: for $\lambda\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
1\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \ell$ do

2: for $\lambda\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
1\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \ell$ do for
$\texttt{B}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
0\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \gamma^{\lambda}-1$ do

3: $\texttt{U}\leftarrow\texttt{B}$

4: $\texttt{U}\leftarrow\texttt{B}$ for $\texttt{i}\leavevmode\nobreak\
\textbf{from}\leavevmode\nobreak\ 0\leavevmode\nobreak\
\textbf{to}\leavevmode\nobreak\ \lambda-1$ do

5: $\texttt{DIGIT}[\texttt{i}]\leftarrow\texttt{U}\;\mathtt{mod}\;\gamma$

6: $\texttt{U}\leftarrow\texttt{U}\;\mathtt{div}\;\gamma$
$\texttt{U}\leftarrow\texttt{U}\;\mathtt{div}\;\gamma$

7: $\texttt{U}\leftarrow 0$

8: $\texttt{U}\leftarrow 0$ for $\texttt{i}\leavevmode\nobreak\
\textbf{from}\leavevmode\nobreak\ \lambda-1\leavevmode\nobreak\
\textbf{downto}\leavevmode\nobreak\ 0$ do

9: $\texttt{U}\leftarrow\texttt{s}\times\texttt{U}+\texttt{DIGIT}[\texttt{i}]$
$\texttt{U}\leftarrow\texttt{s}\times\texttt{U}+\texttt{DIGIT}[\texttt{i}]$

10: $\texttt{CONVERT}[\lambda][\texttt{B}]\leftarrow\texttt{U}$
$\texttt{CONVERT}[\lambda][\texttt{B}]\leftarrow\texttt{U}$
$\texttt{CONVERT}[\lambda][\texttt{B}]\leftarrow\texttt{U}$
$\texttt{CONVERT}[\lambda][\texttt{B}]\leftarrow\texttt{U}$

##### Computing the output by projecting the final configuration.

This step is similar but much simpler than the computation of the initial
configuration from the input.

For simplicity, we define $\pi(x)$ for each $x\in Q$ and not only for $x\in
Q_{out}\cup\\{\sharp\\}$ as it is necessary. It also convenient to set
$\pi(\sharp)\coloneqq 0$ (instead of $\pi(\sharp)\coloneqq\sharp$) to take
account of the possible $\sharp$ symbols at the left end of the leftmost
$\ell$-block, the $c_{0}$-th $\ell$-block. More generally, we set
$\pi:Q\to\\{0,1\\}$ with $\pi(q)\coloneqq 0$ for each $q\in Q\setminus
Q_{out}$.

Here again, by its locality, the projection is done for each symbol $x\in Q$
of each $\ell$-block of the final configuration. It uses the array
$\mathtt{PROJECT}[0..s^{\ell}-1]$ defined by
$\mathtt{PROJECT}[B]\coloneqq\sum_{i=0}^{\ell-1}\pi(x_{i})\times 2^{i}$ where
$B$ is any $\ell$-block $x_{\ell-1}\cdots x_{1}x_{0}\in Q^{\ell}$, or
equivalently, $B=\sum_{i=0}^{\ell-1}x_{i}\times s^{i}$, for $x_{i}\in[0,s-1]$.
The $\mathtt{PROJECT}$ array is computed by the following algorithm where
$\mathtt{PI}[0..s-1]$ denotes the array defined by
$\mathtt{PI}[x]\coloneqq\pi(x)$, for $x\in Q=[0..s-1]$.

Algorithm 24 Computation of the PROJECT array

1: for $\texttt{B}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
0\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \texttt{s}^{\ell}-1$ do

2: $\texttt{R}\leftarrow\texttt{B}$

3: $\texttt{R}\leftarrow\texttt{B}$ for $\texttt{i}\leavevmode\nobreak\
\textbf{from}\leavevmode\nobreak\ 0\leavevmode\nobreak\
\textbf{to}\leavevmode\nobreak\ \ell-1$ do

4:
$\texttt{DIGIT}[\texttt{i}]\leftarrow\texttt{PI}[\texttt{R}\;\mathtt{mod}\;\texttt{s}]$

5: $\texttt{R}\leftarrow\texttt{R}\;\mathtt{div}\;\texttt{s}$
$\texttt{R}\leftarrow\texttt{R}\;\mathtt{div}\;\texttt{s}$

6: $\texttt{R}\leftarrow 0$

7: $\texttt{R}\leftarrow 0$ for $\texttt{i}\leavevmode\nobreak\
\textbf{from}\leavevmode\nobreak\ \ell-1\leavevmode\nobreak\
\textbf{downto}\leavevmode\nobreak\ 0$ do

8: $\texttt{R}\leftarrow 2\times\texttt{R}+\texttt{DIGIT}[\texttt{i}]$
$\texttt{R}\leftarrow 2\times\texttt{R}+\texttt{DIGIT}[\texttt{i}]$

9: $\texttt{PROJECT}[\texttt{B}]\leftarrow\texttt{R}$
$\texttt{PROJECT}[\texttt{B}]\leftarrow\texttt{R}$

##### Putting things together: simulation of the cellular automaton.

Recall that, for $cL=(c_{0}-1)\ell+\rho$ with $1\leq\rho\leq\ell$, i.e. for
$c_{0}\coloneqq\left\lceil cL/\ell\right\rceil$ and $\rho\coloneqq
cL-(c_{0}-1)\ell$, the computation of the automaton $\mathcal{A}=(Q,\delta)$
decomposes into

  * •

$c_{0}-1$ global $\ell$-transitions, each composed of $c_{0}$ local
$\ell$-transitions, and

  * •

one global $\rho$-transition composed of $c_{0}$ local $\rho$-transitions of
time $\rho$.

Let $B_{x}^{T}$ be the $\ell$-block numbered $x$, $0\leq x\leq c_{0}+1$, of
the global configuration $\mathcal{C}_{T}$ at time $T$, $0\leq T\leq cL$. The
$\mathtt{op}$ operation is computed by the following procedure, called op,
which simulates the automaton $\mathcal{A}=(Q,\delta)$ with its projection
$\pi:Q\to\\{0,1\\}$. The main data structure of the op procedure is a two-
dimensional array, called $\mathtt{BK}[0..c_{0}+1][0..c_{0}]$ and defined by

$\mathtt{BK}[x][t]\coloneqq B_{x}^{t\ell}$ for $0\leq t\leq c_{0}-1$, and
$\mathtt{BK}[x][c_{0}]\coloneqq B_{x}^{cL}$.

Algorithm 25 Constant-time computation of the $\mathtt{op}$ operation

1: procedure op($\texttt{X}_{1},...,\texttt{X}_{\texttt{r}}$)

2: $\texttt{X}_{0}\leftarrow\texttt{N}$

3: $\texttt{X}_{0}\leftarrow\texttt{N}$ for $\texttt{j}\leavevmode\nobreak\
\textbf{from}\leavevmode\nobreak\ 0\leavevmode\nobreak\
\textbf{to}\leavevmode\nobreak\ \texttt{r}$ do

4: for $\texttt{j}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
0\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \texttt{r}$ do for
$\texttt{x}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
1\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \texttt{c}_{1}$ do

5:
$\texttt{X}[\texttt{j}][\texttt{x}]\leftarrow\texttt{X}_{\texttt{j}}\;\mathtt{mod}\;2^{\ell}$

6:
$\texttt{X}_{\texttt{j}}\leftarrow\texttt{X}_{\texttt{j}}\;\mathtt{div}\;2^{\ell}$
$\texttt{X}_{\texttt{j}}\leftarrow\texttt{X}_{\texttt{j}}\;\mathtt{div}\;2^{\ell}$
$\texttt{X}_{\texttt{j}}\leftarrow\texttt{X}_{\texttt{j}}\;\mathtt{div}\;2^{\ell}$
$\texttt{X}_{\texttt{j}}\leftarrow\texttt{X}_{\texttt{j}}\;\mathtt{div}\;2^{\ell}$

7:
$\texttt{X}_{\texttt{j}}\leftarrow\texttt{X}_{\texttt{j}}\;\mathtt{div}\;2^{\ell}$
for $\texttt{x}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
1\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \texttt{c}_{1}-1$ do

8:
$\texttt{U}[\texttt{x}]\leftarrow\texttt{CODE}[\ell][\texttt{X}[0][\texttt{x}]]\cdots[\texttt{X}[\texttt{r}][\texttt{x}]]$
$\texttt{U}[\texttt{x}]\leftarrow\texttt{CODE}[\ell][\texttt{X}[0][\texttt{x}]]\cdots[\texttt{X}[\texttt{r}][\texttt{x}]]$

9:
$\texttt{U}[\texttt{c}_{1}]\leftarrow\texttt{CODE}[\lambda][\texttt{X}[0][\texttt{c}_{1}]]\cdots[\texttt{X}[\texttt{r}][\texttt{c}_{1}]]$

10: $\texttt{BK}[0][0]\leftarrow
2^{\texttt{r}+1}\times(\texttt{s}^{\ell}-1)/(\texttt{s}-1)$

11: $\texttt{BK}[0][0]\leftarrow
2^{\texttt{r}+1}\times(\texttt{s}^{\ell}-1)/(\texttt{s}-1)$ for
$\texttt{x}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
1\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \texttt{c}_{1}-1$ do

12:
$\texttt{BK}[\texttt{x}][0]\leftarrow\texttt{CONVERT}[\ell][\texttt{U}[\texttt{x}]]$
$\texttt{BK}[\texttt{x}][0]\leftarrow\texttt{CONVERT}[\ell][\texttt{U}[\texttt{x}]]$

13:
$\texttt{BK}[\texttt{c}_{1}][0]\leftarrow\texttt{CONVERT}[\lambda][\texttt{U}[\texttt{c}_{1}]]+2^{\texttt{r}+1}\times(\texttt{s}^{\ell}-\texttt{s}^{\lambda})/(\texttt{s}-1)$

14:
$\texttt{BK}[\texttt{c}_{1}][0]\leftarrow\texttt{CONVERT}[\lambda][\texttt{U}[\texttt{c}_{1}]]+2^{\texttt{r}+1}\times(\texttt{s}^{\ell}-\texttt{s}^{\lambda})/(\texttt{s}-1)$
for $\texttt{x}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
\texttt{c}_{1}+1\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\
\texttt{c}_{0}+1$ do

15: $\texttt{BK}[\texttt{x}][0]\leftarrow
2^{\texttt{r}+1}\times(\texttt{s}^{\ell}-1)/(\texttt{s}-1)$
$\texttt{BK}[\texttt{x}][0]\leftarrow
2^{\texttt{r}+1}\times(\texttt{s}^{\ell}-1)/(\texttt{s}-1)$

16: $\texttt{BK}[\texttt{x}][0]\leftarrow
2^{\texttt{r}+1}\times(\texttt{s}^{\ell}-1)/(\texttt{s}-1)$ for
$\texttt{t}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
1\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \texttt{c}_{0}-1$ do

17: for $\texttt{t}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
1\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \texttt{c}_{0}-1$ do for
$\texttt{x}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
1\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \texttt{c}_{0}$ do

18:
$\texttt{BK}[\texttt{x}][\texttt{t}]\leftarrow\texttt{LT}[\ell][\textsc{Conc}(\texttt{BK}[\texttt{x}+1][\texttt{t}-1],\texttt{BK}[\texttt{x}][\texttt{t}-1],\texttt{BK}[\texttt{x}-1][\texttt{t}-1])]$
$\texttt{BK}[\texttt{x}][\texttt{t}]\leftarrow\texttt{LT}[\ell][\textsc{Conc}(\texttt{BK}[\texttt{x}+1][\texttt{t}-1],\texttt{BK}[\texttt{x}][\texttt{t}-1],\texttt{BK}[\texttt{x}-1][\texttt{t}-1])]$
$\texttt{BK}[\texttt{x}][\texttt{t}]\leftarrow\texttt{LT}[\ell][\textsc{Conc}(\texttt{BK}[\texttt{x}+1][\texttt{t}-1],\texttt{BK}[\texttt{x}][\texttt{t}-1],\texttt{BK}[\texttt{x}-1][\texttt{t}-1])]$
$\texttt{BK}[\texttt{x}][\texttt{t}]\leftarrow\texttt{LT}[\ell][\textsc{Conc}(\texttt{BK}[\texttt{x}+1][\texttt{t}-1],\texttt{BK}[\texttt{x}][\texttt{t}-1],\texttt{BK}[\texttt{x}-1][\texttt{t}-1])]$

19:
$\texttt{BK}[\texttt{x}][\texttt{t}]\leftarrow\texttt{LT}[\ell][\textsc{Conc}(\texttt{BK}[\texttt{x}+1][\texttt{t}-1],\texttt{BK}[\texttt{x}][\texttt{t}-1],\texttt{BK}[\texttt{x}-1][\texttt{t}-1])]$
for $\texttt{x}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
1\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \texttt{c}_{0}$ do

20:
$\texttt{BK}[\texttt{x}][\texttt{c}_{0}]\leftarrow\texttt{LT}[\rho][\textsc{Conc}(\texttt{BK}[\texttt{x}+1][\texttt{c}_{0}-1],\texttt{BK}[\texttt{x}][\texttt{c}_{0}-1],\texttt{BK}[\texttt{x}-1][\texttt{c}_{0}-1])]$
$\texttt{BK}[\texttt{x}][\texttt{c}_{0}]\leftarrow\texttt{LT}[\rho][\textsc{Conc}(\texttt{BK}[\texttt{x}+1][\texttt{c}_{0}-1],\texttt{BK}[\texttt{x}][\texttt{c}_{0}-1],\texttt{BK}[\texttt{x}-1][\texttt{c}_{0}-1])]$

21: $\texttt{R}\leftarrow 0$

22: $\texttt{R}\leftarrow 0$ for $\texttt{x}\leavevmode\nobreak\
\textbf{from}\leavevmode\nobreak\ \texttt{c}_{0}\leavevmode\nobreak\
\textbf{downto}\leavevmode\nobreak\ 1$ do

23:
$\texttt{R}\leftarrow\texttt{s}^{\ell}\times\texttt{R}+\texttt{PI}[\texttt{BK}[\texttt{x}][\texttt{c}_{0}]]$
$\texttt{R}\leftarrow\texttt{s}^{\ell}\times\texttt{R}+\texttt{PI}[\texttt{BK}[\texttt{x}][\texttt{c}_{0}]]$

24: return R return R

_Comments:_ Lines 2-15 (the major part of the op procedure!) construct the
part of the BK array, $BK[x][0]$, $0\leq x\leq c_{0}+1$, that represents the
initial configuration $\mathcal{C}_{0}$ of $\mathcal{A}$ on the input
$\mathtt{code}(N,X_{1},\ldots,X_{r})$. More precisely, the construction
decomposes into the following steps:

  * •

from the integers $X_{0}\coloneqq N,$ $X_{1},\ldots,X_{r}$, lines 2-6 of the
op procedure compute the array $\texttt{X}[0..r][1..c_{1}]$ such that
$\texttt{X}[i][x]$ is the $x$-th bit of $X_{i}$;

  * •

from the array $\texttt{X}[0..r][1..c_{1}]$, lines 7-9 compute the array
$\texttt{U}[1..c_{1}]$ such that $\texttt{U}[x]$ is the $x$-th $\gamma$-digit
of $\mathtt{code}(X_{0},X_{1},\ldots,X_{r})$ (for $\gamma\coloneqq 2^{r+1}$),
which is $\texttt{U}[x]=\sum_{i=0}^{r}2^{i}\times\texttt{X}[i][x]$;

  * •

from the $\texttt{U}[1..c_{1}]$ array, lines 10-15 construct the part
$\mathtt{BK}[0..c_{0}+1][0]$ of the $\mathtt{BK}$ array that encodes the
initial configuration $\mathcal{C}_{0}=\sharp B^{0}_{c_{0}+1}\cdots
B^{0}_{1}B^{0}_{0}\sharp$ with the $\ell$-blocks $B^{0}_{x}$ among which

    * –

$B^{0}_{0}$ and $B^{0}_{c_{1}+1},\ldots,B^{0}_{c_{0}+1}$ are equal to the
string $\sharp^{\ell}$ encoded by the integer $2^{r+1}(s^{\ell}-1)/(s-1)$
(line 10 and lines 14-15, respectively, corresponding to item 4.a above), and

    * –

corresponding to the “input”, each $\mathtt{BK}[j]$, $1\leq j\leq c_{1}-1$, is
the integer whose string of ($\ell$) digits in base $s$ is equal to
$B^{0}_{j}$ (lines 11-12 corresponding to item 3), and $\mathtt{BK}[c_{1}]$ is
the integer whose string of ($\ell$) digits in base $s$ is
$B^{0}_{c_{1}}=\sharp^{\ell-\lambda}U_{c_{1}}$ (line 13 corresponding to item
4.b; recall that $\lambda$ is the length of $U_{c_{1}}$).

Lines 16-20 simulate the computation of $\mathcal{A}$: the $c_{0}-1$ global
$\ell$-transitions (lines 16-18) and the final global $\rho$-transition (lines
19-20).

Finally, lines 21-24 compute and return the output integer by projecting the
final configuration $\mathcal{C}_{cL}$ with the $\pi$ projection.

It is immediate to check that the body of each “for” loop of the op procedure
is repeated a number of times bounded by $r+1$, $c_{0}$ or $c_{1}$, therefore
by a constant, and therefore the op procedure executes in constant time as
claimed.

##### Why is the preprocessing time linear?

Our constant-time procedure op uses five pre-computed tables: $\mathtt{PI}$,
computed in constant time, and LT, CODE, CONVERT and PROJECT. By examining the
structure of the loops of the above algorithms, it is easy to verify that

  * •

LT is computed in time
$O(\mathtt{NbLocalConf}(N)\times\ell^{3})=O(N^{\sigma}\times(\log
N)^{3})=O(N)$ (recall $\mathtt{NbLocalConf}(N)=s^{3\ell}=O(N^{\sigma})$, for a
fixed $\sigma<1$),

  * •

CODE and CONVERT are computed in time
$O((2^{\ell})^{r+1}\times\ell^{2})=O(\gamma^{\ell}\times\ell^{2})$, and
$O(\gamma^{\ell}\times\ell^{2})$, respectively, and therefore in time
$O(s^{\ell}\times\ell^{2})$, and PROJECT is computed in time
$O(s^{\ell}\times\ell$), and therefore, a fortiori, all these tables are
computed in time $O(N)$.

This completes the proof of Theorem 3. ∎

##  12 Appendix: Another constant-time algorithm for division

While multiplication can be computed in linear time on a cellular automaton,
so Theorem 3 applies to it, it is unknown if division is. However, the
intuitive principle of the usual division algorithm is also “local”: to
compute the most significant (leftmost) digit of the quotient of integers
$\left\lfloor A/B\right\rfloor$, the first step is to “try” to divide the
integer $a$ consisting of the 1, 2, 3, or 4 leftmost digits of $A$ by the
integer $b$ consisting of the 1, 2, or 3 leftmost digits of $B$.

We are going to design a new constant-time algorithm for division by a careful
adaptation of the usual division principle combined with a judicious choice of
the base $K$ in which the integers are represented. To avoid any vicious
circle here, we will only use the addition, subtraction, multiplication and
base change of “polynomial” integers, and the procedure
$\textsc{DivBySmall}(A,B)$ of Subsection 5.1, which returns $\left\lfloor
A/B\right\rfloor$ for $A<\beta^{d}$, $0<B<\beta$, for a fixed integer $d\geq
1$ and $\beta\coloneqq\left\lceil N^{1/6}\right\rceil^{3}$.

##### Analyzing and optimizing the usual division algorithm.

Assume the dividend $A$ and the divisor $B$ are represented in any fixed base
$K\geq 2$ and let $a$ (resp. $b$) be the integer represented by the 1, 2, 3,
or 4 (resp. 1, 2, or 3) leftmost digits of $A$ (resp. $B$). Each positive
integer is assimilated to the string $\overline{x_{p-1}\cdots x_{1}x_{0}}$ of
digits $x_{i}$, $0\leq x_{i}<K$, which represents it in base $K$, with leading
digit $x_{p-1}>0$. Clearly, we get the inequalities $aK^{m}\leq A<(a+1)K^{m}$
and $bK^{n}\leq B<(b+1)K^{n}$, for some integers $a,b\geq 1$ and $m,n$.
Because of $A\geq B$, we can assume $m\geq n$. It implies
$\frac{a}{b+1}K^{m-n}<A/B<\frac{a+1}{b}K^{m-n}$. To do _one_ test instead of
several tests to get the _most significant_ digit of the quotient $A/B$ in
base $K$, we want the difference between the bounds to be less than $K^{m-n}$,
it means $\frac{a+1}{b}-\frac{a}{b+1}\leq 1$. Noticing the identity
$\frac{a+1}{b}-\frac{a}{b+1}=\frac{a}{b(b+1)}+\frac{1}{b}$, this can be
rephrased as

$\displaystyle\frac{a}{b(b+1)}+\frac{1}{b}\leq 1.$ (34)

######  Lemma 18.

Assume $aK^{m}\leq A<(a+1)K^{m}$ and $bK^{n}\leq B<(b+1)K^{n}$, for some
integers $K\geq 2$, and $A,B$ such that $A>B\geq 1$, and $m,n,a,b$ such that
$m\geq n\geq 0$, and $a>b\geq 1$, and $\frac{a}{b(b+1)}+\frac{1}{b}\leq 1$. We
then get

$qK^{m-n}\leq A/B<(q+1)K^{m-n}$ for $q=\left\lfloor\frac{a}{b+1}\right\rfloor$
or $q=\left\lfloor\frac{a}{b+1}\right\rfloor+1$,

which implies $A=BqK^{m-n}+R$ for some integer $R<BK^{m-n}$, and therefore

$\displaystyle\left\lfloor A/B\right\rfloor=qK^{m-n}+\left\lfloor
R/B\right\rfloor$ (35)

with $q\geq 1$ and $\left\lfloor R/B\right\rfloor<K^{m-n}$.

###### Proof.

From the inequalities $\frac{a}{b+1}K^{m-n}<A/B<\frac{a+1}{b}K^{m-n}$ we
deduce $\left\lfloor\frac{a}{b+1}\right\rfloor
K^{m-n}<A/B<\left\lceil\frac{a+1}{b}\right\rceil K^{m-n}$. Besides, the
inequality $\frac{a+1}{b}-\frac{a}{b+1}\leq 1$ implies
$\left\lceil\frac{a+1}{b}\right\rceil\leq\left\lfloor\frac{a}{b+1}\right\rfloor+2$.
This yields $qK^{m-n}<A/B<(q+2)K^{m-n}$ for
$q=\left\lfloor\frac{a}{b+1}\right\rfloor\geq 1$, which proves the lemma. ∎

######  Remark 24.

Lemma 18 gives and justifies the principle of a recursive division algorithm
in any fixed base $K\geq 2$: to compute $\left\lfloor A/B\right\rfloor$,
compute the integers $q$ and $\left\lfloor R/B\right\rfloor$ in base $K$; the
representation of the integer $\left\lfloor A/B\right\rfloor$ in base $K$ is
the concatenation of the string representing the integer $q\geq 1$ and the
string of $m-n$ digits representing the integer $\left\lfloor
R/B\right\rfloor<K^{m-n}$ (possibly with leading zeros).

##### How to use Lemma 18?

How many leftmost (most significant) digits of $A$ and $B$, written in base
$K$, should we take to obtain integers $a$ and $b$, with $a\geq b\geq 1$, that
satisfy the condition $\frac{a}{b(b+1)}+\frac{1}{b}\leq 1$ of Lemma 18? This
is expressed precisely by the following question: for which integers $i,j$ is
the implication $K^{i}\leq a<K^{i+1}\land K^{j}\leq
b<K^{j+1}\Rightarrow\frac{a}{b(b+1)}+\frac{1}{b}\leq 1$ true for all $a,b$?

######  Lemma 19.

Let $i,j$ be two positive integers. Then the condition $i<2j$ is equivalent to
the condition

$\forall(a,b)\in[K^{i},K^{i+1}[\times[K^{j},K^{j+1}[\;\;\left(\frac{a}{b(b+1)}+\frac{1}{b}\leq
1\right)$

###### Proof.

The maximum of the numbers $\frac{a}{b(b+1)}+\frac{1}{b}$ for all pairs of
integers $(a,b)\in[K^{i},K^{i+1}[\times[K^{j},K^{j+1}[$ is
$\frac{K^{i+1}-1}{K^{j}(K^{j}+1)}+\frac{1}{K^{j}}=\frac{K^{i+1}+K^{j}}{K^{2j}+K^{j}}$,
which is at most 1 if and only if $i+1\leq 2j$. This proves the lemma. ∎

We are now ready to give our new division algorithm using the principle given
by Lemma 18. Here again, we must choose carefully the base $K$.

##### The choice of the base.

We take $K\coloneqq\left\lceil N^{1/7}\right\rceil$ and we assume that each
“polynomial” operand $X<N^{d}$, for a fixed integer $d$, is written
$\overline{x_{m-1}\cdots x_{1}x_{0}}$, $0\leq x_{i}\leq K-1$, in base $K$,
with one digit $x_{i}$ per register, and is therefore stored in $m\leq 7d$
registers, since $X<N^{d}\leq K^{7d}$. In particular, the following functions
can be computed in constant time for their argument $X$ so represented:
$\mathtt{length}_{\mathtt{K}}(X)\coloneqq m$;
$\mathtt{Substring}_{\mathtt{K}}(X,i,j)\coloneqq\overline{x_{i-1}\cdots
x_{j}}$, for $m\geq i>j\geq 0$.

######  Notation.

For an integer $X$ written $\overline{x_{m-1}\cdots x_{1}x_{0}}$ in base $K$,
$0\leq x_{i}\leq K-1$, and a positive integer $p\leq m$, denote by $X_{(p)}$
the prefix of the $p$ most significant digits of $X$:
$X_{(p)}\coloneqq\overline{x_{m-1}\cdots x_{m-p}}=X\;\mathtt{div}\;K^{m-p}$.

##### The division algorithm.

Let $A,B$ be two “polynomial” integers such that $0<B\leq A<K^{d}$, for a
fixed integer $d$. To divide $A$ by $B$, we consider four cases:

  1. 1.

$B<K^{2}$;

  2. 2.

$K^{p}\leq B\leq A<K^{p+1}$, for an integer $p\geq 2$, and $A_{(3)} =B_{(3)}$;

  3. 3.

$K^{2}\leq B\leq A$ and $A_{(3)}>B_{(3)}$;

  4. 4.

$K^{p}\leq B<K^{p+1}\leq A$, for an integer $p\geq 2$, and $A_{(3)} \leq
B_{(3)}$.

Obviously, these four cases are mutually exclusive. To ensure that there is no
other case than these four cases, just note that if condition 2 is false when
$K^{2}\leq B\leq A<K^{d}$, then either we have $A_{(3)}>B_{(3)}$ (case 3), or
we have $A_{(3)}\leq B_{(3)}$ _and_ $A$ has _more_ digits than $B$ in base $K$
(case 4).

  * •

Case 1 is handled by the procedure $\textsc{DivBySmall}(A,B)$ of Subsection
5.1 (note that $K^{2}=\left\lceil N^{1/7}\right\rceil^{2}\leq\left\lceil
N^{1/6}\right\rceil^{3}=\beta$).

  * •

In case 2, we clearly get $A-B<K^{p-2}<B$, which implies $A<2B$ and therefore
$\left\lfloor A/B\right\rfloor=1$.

  * •

Cases 3 and 4 are handled by Lemma 18. In case 3 (resp. case 4), take
$a=A_{(3)}$ and $b=B_{(3)}$ (resp. $a=A_{(4)}$ and $b=B_{(3)}$), which implies
$K^{2}\leq b<a<K^{3}$ (resp. $K^{2}\leq b<K^{3}\leq a<K^{4}$).

The integers $i=2$ and $j=2$ (resp. $i=3$ and $j=2$) satisfy the condition
$i<2j$ of Lemma 19. Thus, in cases 3 and 4, the condition
$\frac{a}{b(b+1)}+\frac{1}{b}\leq 1$ of Lemma 18 is satisfied. Therefore,
Lemma 18 proves the correctness of the following Division procedure which
implements cases 1-4 for $A\geq B$. More precisely, the lines 17-21 of the
algorithm compute $\left\lfloor A/B\right\rfloor$ in cases 3 and 4 by using
the pre-computed array $\texttt{DIV}[0..K^{4}-1][2..K^{3}]$ defined by
$\texttt{DIV}[x][y]\coloneqq\left\lfloor x/y\right\rfloor$, for $0\leq
x<K^{4}$ and $2\leq y\leq K^{3}$ (see the pre-computation code of the DIV
array presented after the Division procedure).

Algorithm 26 Constant-time computation of the $\mathtt{division}$ operation

1: procedure Division($\texttt{A},\texttt{B}$)

2: procedure Division($\texttt{A},\texttt{B}$) if $\texttt{A}<\texttt{B}$ then

3: return $0$ return $0$

4: return $0$ if $\texttt{B}<\texttt{K}^{2}$ then $\triangleright$ case 1

5: return $\textsc{DivBySmall}(\texttt{A},\texttt{B})$ return
$\textsc{DivBySmall}(\texttt{A},\texttt{B})$

6: $\ell_{\texttt{A}}\leftarrow\mathtt{length}_{\texttt{K}}(\texttt{A})$

7:
$\texttt{a}\leftarrow\mathtt{Substring}_{\texttt{K}}(\texttt{A},\ell_{\texttt{A}},\ell_{\texttt{A}}-3)$
$\triangleright$ $a\leftarrow A_{(3)}$

8: $\texttt{m}\leftarrow\ell_{\texttt{A}}-3$

9: $\ell_{\texttt{B}}\leftarrow\mathtt{length}_{\texttt{K}}(\texttt{B})$

10:
$\texttt{b}\leftarrow\mathtt{Substring}_{\texttt{K}}(\texttt{B},\ell_{\texttt{B}},\ell_{\texttt{B}}-3)$
$\triangleright$ $b\leftarrow B_{(3)}$

11: $\texttt{n}\leftarrow\ell_{\texttt{B}}-3$

12: $\texttt{n}\leftarrow\ell_{\texttt{B}}-3$ if
$\ell_{\texttt{A}}=\ell_{\texttt{B}}\leavevmode\nobreak\
\mathbf{and}\leavevmode\nobreak\ \texttt{a}=\texttt{b}$ then

13: return $1$ $\triangleright$
$\mathtt{length}_{\texttt{K}}(\texttt{A})=\mathtt{length}_{\texttt{K}}(\texttt{B})$
and $A_{(3)}=B_{(3)}$: case 2 return $1$ $\triangleright$
$\mathtt{length}_{\texttt{K}}(\texttt{A})=\mathtt{length}_{\texttt{K}}(\texttt{B})$
and $A_{(3)}=B_{(3)}$: case 2

14: return $1$ $\triangleright$
$\mathtt{length}_{\texttt{K}}(\texttt{A})=\mathtt{length}_{\texttt{K}}(\texttt{B})$
and $A_{(3)}=B_{(3)}$: case 2 if $\texttt{a}\leq\texttt{b}$ then
$\triangleright$ $A_{(3)}\leq B_{(3)}$: case 4

15:
$\texttt{a}\leftarrow\mathtt{Substring}_{K}(\texttt{A},\ell_{\texttt{A}},\ell_{\texttt{A}}-4)$
$\triangleright$ $a\leftarrow A_{(4)}$, so $b=B_{(3)}<a<(b+1)K$

16: $\texttt{m}\leftarrow\ell_{\texttt{A}}-4$
$\texttt{m}\leftarrow\ell_{\texttt{A}}-4$

17: $\texttt{q}\leftarrow\texttt{DIV}[\texttt{a}][\texttt{b}+1]$
$\triangleright$ $b+1\leq a<(b+1)K$ and therefore $1\leq q<K$
$\triangleright$ common treatment of cases 3 and 4 justified by Lemma 18

18: $\texttt{q}\leftarrow\texttt{DIV}[\texttt{a}][\texttt{b}+1]$
$\triangleright$ $b+1\leq a<(b+1)K$ and therefore $1\leq q<K$
$\triangleright$ common treatment of cases 3 and 4 justified by Lemma 18 if
$\texttt{A}\geq\texttt{B}\times(\texttt{q}+1)\times\texttt{K}^{\texttt{m}-\texttt{n}}$
then

19: $\texttt{q}\leftarrow\texttt{q}+1$ $\texttt{q}\leftarrow\texttt{q}+1$

20:
$\texttt{R}\leftarrow\texttt{A}-\texttt{B}\times\texttt{q}\times\texttt{K}^{\texttt{m}-\texttt{n}}$

21: return
$\texttt{q}\times\texttt{K}^{\texttt{m}-\texttt{n}}+\textsc{Division}(\texttt{R},\texttt{B})$
$\triangleright$ justified by equality 35 return
$\texttt{q}\times\texttt{K}^{\texttt{m}-\texttt{n}}+\textsc{Division}(\texttt{R},\texttt{B})$
$\triangleright$ justified by equality 35

##### Comments:

In case 4 ($a=A_{(3)}\leq B_{(3)}=b$), after the assignment $a\leftarrow
A_{(4)}$ of line 15, we have $a=A_{(4)}<(A_{(3)}+1)K$. Now, by the hypothesis
$A_{(3)}\leq B_{(3)}=b$ (line 14), we get
$b=B_{(3)}<a=A_{(4)}<(A_{(3)}+1)K\leq(b+1)K$, and thus $b<a<(b+1)K$, as the
comment of line 15 claims.

In case 3, i.e. for $a=A_{(3)}>B_{(3)}=b$, we also have
$a=A_{(3)}<B_{(4)}<(B_{(3)}+1)K=(b+1)K$. This justifies, for cases 3 and 4,
the assertion given as a comment of line 17: $b+1\leq a<(b+1)K$.

It remains to describe the preprocessing and to prove that the claimed
complexity is achieved.

##### Pre-computation of the $\mathtt{DIV}$ array.

Note that in the Division procedure, we compute $q=\left\lfloor
a/(b+1)\right\rfloor$ when $2\leq b+1\leq K^{3}$ and $1\leq q\leq K-1$.
Therefore, the following algorithm constructs the $\mathtt{DIV}$ array.

Algorithm 27 Pre-computation of the DIV array

1: for $\texttt{y}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
2\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \texttt{K}^{3}$ do

2: for $\texttt{y}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
2\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \texttt{K}^{3}$ do for
$\texttt{q}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
1\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \texttt{K}-1$ do

3: for $\texttt{q}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
1\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \texttt{K}-1$ do for
$\texttt{r}\leavevmode\nobreak\ \textbf{from}\leavevmode\nobreak\
0\leavevmode\nobreak\ \textbf{to}\leavevmode\nobreak\ \texttt{y}-1$ do

4: $\texttt{x}\leftarrow\texttt{q}\times\texttt{y}+\texttt{r}$

5: $\texttt{DIV}[\texttt{x}][\texttt{y}]\leftarrow\texttt{q}$
$\texttt{DIV}[\texttt{x}][\texttt{y}]\leftarrow\texttt{q}$
$\texttt{DIV}[\texttt{x}][\texttt{y}]\leftarrow\texttt{q}$
$\texttt{DIV}[\texttt{x}][\texttt{y}]\leftarrow\texttt{q}$
$\texttt{DIV}[\texttt{x}][\texttt{y}]\leftarrow\texttt{q}$
$\texttt{DIV}[\texttt{x}][\texttt{y}]\leftarrow\texttt{q}$

##### Complexity of the preprocessing and division algorithm.

We immediately see that the time of the above algorithm which constructs the
array $\texttt{DIV}[0..K^{4}-1][2..K^{3}]$ is $O(K^{3}\times K\times
K^{3})=O(K^{7})=O(N)$.

The complexity of the Division procedure is determined by its recursive depth
(number of recursive calls). By equation 35 (implemented by line 21), which is
$\left\lfloor A/B\right\rfloor=qK^{m-n}+\left\lfloor R/B\right\rfloor$ with
$q\geq 1$ and $\left\lfloor R/B\right\rfloor<K^{m-n}$, the quotient
$\left\lfloor R/B\right\rfloor$ has at least one digit less than $\left\lfloor
A/B\right\rfloor$ when represented in base $K$ (the digit $q$, multiplied by
$K^{m-n}$). Therefore, the recursive depth is bounded by the number of digits
of the representation of $\left\lfloor A/B\right\rfloor$ in base $K$, which is
less than $7d$ because of $\left\lfloor A/B\right\rfloor<K^{7d}$. Since the
most time consuming instruction is the multiplication, executed $O(d)$ times
(lines 18, 20, 21) and whose time cost is $O(d^{2})$, the time of the Division
procedure is $O(d^{3})$, at compare to the time $O(d^{4})$ of the Division
procedure of Section 5, see Theorem 2.