# Predecessor on the Ultra-Wide Word RAM††thanks: An extended abstract
appeared at the _18th Scandinavian Symposium and Workshops on Algorithm
Theory_ [13].

Philip Bille111Supported by Danish Research Council grant DFF-8021-002498.
Inge Li Gørtz† Tord Stordalen

###### Abstract

We consider the predecessor problem on the ultra-wide word RAM model of
computation, which extends the word RAM model with _ultrawords_ consisting of
$w^{2}$ bits [TAMC, 2015]. The model supports arithmetic and boolean
operations on ultrawords, in addition to _scattered_ memory operations that
access or modify $w$ (potentially non-contiguous) memory addresses
simultaneously. The ultra-wide word RAM model captures (and idealizes) modern
vector processor architectures.

Our main result is a simple, linear space data structure that supports
predecessor in constant time and updates in amortized, expected constant time.
This improves the space of the previous constant time solution that uses space
in the order of the size of the universe. Our result holds even in a weaker
model where ultrawords consist of $w^{1+\epsilon}$ bits for any $\epsilon>0$.
It is based on a new implementation of the classic $x$-fast trie data
structure of Willard [Inform. Process. Lett. 17(2), 1983] combined with a new
dictionary data structure that supports fast parallel lookups.

Technical University of Denmark, DTU Compute, Kgs. Lyngby, Denmark

<EMAIL_ADDRESS>
##  1 Introduction

Let $S$ be a set of $n$ $w$-bit integers. The _predecessor problem_ is to
maintain $S$ under the following operations.

  * •

$\mathsf{predecessor}(x)$: return the largest $y\in S$ such that $y\leq x$.

  * •

$\mathsf{insert}(x)$: add $x$ to $S$.

  * •

$\mathsf{delete}(x)$: remove $x$ from $S$.

The predecessor problem is a fundamental and well-studied data structure
problem, both from the perspective of upper bounds [32, 34, 39, 40, 24, 2, 5,
38, 8, 7] and lower bounds [1, 5, 29, 30, 36, 32, 33]. The problem has many
applications, for instance integer sorting [2, 3, 24, 26], string sorting [4,
9, 21], and string searching [6, 8, 10, 11, 14]. See Navarro and Rojas-Ledesma
[31] for a recent survey.

On the word RAM model of computation, the complexity of the problem is well-
understood with the following tight upper and lower bound on the time for
operations given by Pătraşcu and Thorup [34].

$\Theta\left(\max\left[1,\min\left\\{\log_{w}n,\frac{\log\frac{w}{\log
w}}{\log\left(\log\frac{w}{\log w}/\log\frac{\log n}{\log
w}\right)},\log\frac{\log(2^{w}-n)}{\log w}\right\\}\right]\right).$ (1)

From the upper bound perspective, the first branch matches dynamic fusion
trees [34], the second branch is based on an extension of the techniques from
Beame and Fich [5], and the last branch is based on an extension of dynamic
van Emde Boas trees [39]. Note that the lower bound implies that we cannot
support operations in constant time for general $n$ and $w$. Hence, a natural
question is if practical models of computation capturing modern hardware can
allow us to overcome the superconstant lower bound.

One such model is the _RAM with byte overlap_ (RAMBO) by Brodnik et al. [15].
This model extends the word RAM model by adding a set of special words that
share bits; flipping a bit in one word will also affect all the other words
that share that bit. The precise model is determined by the layout of the
shared bits. It is feasible to make hardware based on this model, and
prototypes have been built [28]. In the RAMBO model, Brodnik et al. [15] gave
a predecessor data structure using constant time per operation with
$O(2^{w}/w)$ space (counting both regular words and shared words). They also
gave a randomized version of the solution that uses constant time with high
probability and reduces the regular space to $O(n)$ (but still needs
$\Omega(2^{w}/w)$ space for the shared words). In both cases, the total space
is near-linear in the size of the universe.

More recently, Farzan et al. [22] introduced the _ultra-wide word RAM model_
(UWRAM). The UWRAM extends the word RAM model by adding special _ultrawords_
of $w^{2}$ bits. The model supports standard boolean and arithmetic operations
on ultrawords, as well as _scattered_ memory operations that access $w$ words
in memory in parallel. The UWRAM model captures (and idealizes) modern vector
processing architectures [35, 37, 16] (see Section 2 for details of the
model). Farzan et al. [22] showed how to simulate algorithms for the RAMBO
model on the UWRAM at the cost of increasing the space by a polylogarithmic
factor. Simulating the above RAMBO solution for the predecessor problem, they
gave a solution to the predecessor problem on the UWRAM using worst case
constant time for all operations and $O(w2^{w})$ space.

###  1.1 Our Results

We revisit the predecessor problem on the UWRAM and show the following main
result.

###### Theorem 1

Given a set of $n$ $w$-bit integers, we can construct an $O(n)$ space data
structure on a UWRAM that supports $\mathsf{predecessor}$ in constant time and
$\mathsf{insert}$ and $\mathsf{delete}$ in amortized expected constant time.
The result holds even when ultrawords consist of $w^{1+\epsilon}$ bits for any
fixed $\epsilon>0$.

Compared to the previous result of Farzan et al. [22], Theorem 1 significantly
reduces the space from $O(w2^{w})$ to linear while maintaining constant time
for operations (note that query time is worst-case, while updates are
amortized expected). Furthermore, our result works in a weaker model were
ultrawords consist of only $w^{1+\epsilon}$ bits for any arbitrarily small
$\epsilon>0$. In this restricted model we limit our reliance on the powerful
scattered memory operations by allowing them to access only $w^{\epsilon}$
words in memory in parallel.

A key component in our solution is a new dictionary data structure of
independent interest that supports fast parallel lookups on the UWRAM. We
define the problem as follows. Recall that an ultraword $X$ consists of
$w^{2}$ (or $w^{1+\epsilon}$) bits. We view $X$ as divided into $w$ (or
$w^{\epsilon}$) words of $w$ consecutive bits each, numbered from right to
left starting from $0$. The $i$th word in $X$ is denoted $X\langle i\rangle$
(we discuss the model in detail in Section 2). Given a set $S$ of $n$ $w$-bit
integers, the _$w^{\epsilon}$ -parallel dictionary problem_ is to maintain $S$
under the following operations.

  * •

$\mathsf{pMember}(X)$: return an ultraword $I$ where $I\langle i\rangle=1$ if
$X\langle i\rangle\in S$ and $I\langle i\rangle=0$ otherwise.

  * •

$\mathsf{insert}(x)$: Add $x$ to $S$.

  * •

$\mathsf{delete}(x)$: Remove $x$ from $S$.

Thus, $\mathsf{pMember}$ takes an ultraword $X$ of $w^{\epsilon}$ integers and
returns an ultraword encoding which of these integers are in $S$. To the best
of our knowledge, the $w^{\epsilon}$-parallel dictionary problem has not been
studied before. We show the following result.

###### Theorem 2

Given a set of $n$ $w$-bit integers on a UWRAM with $w^{1+\epsilon}$-bit
ultrawords for any fixed $\epsilon>0$, we can construct an
$O(n+w^{\epsilon})$-space data structure that supports $\mathsf{pMember}$
queries in worst case constant time and $\mathsf{insert}$ and
$\mathsf{delete}$ in amortized expected constant time.

Note that the queries are worst-case constant time, while the updates are
amortized expected constant time. The time bounds of Theorem 2 thus match the
well-known dynamic perfect hashing structure of Dietzfelbinger et al. [20]
(which is also the basis of our solution), except that the queries are
parallel. The space is linear except for the additive $w^{\epsilon}$ term,
which is needed even for storing the input to the $\mathsf{pMember}$ query.

###  1.2 Techniques

Our results are achieved by novel and efficient parallel implementations of
well-known sequential data structures.

Our parallel dictionary structure of Theorem 2 is based on the dynamic perfect
hashing structure of Dietzfelbinger et al. [20]. This is a two-level data
structure similar to the classic static perfect hashing structure of Fredman
et al. [23]. At the first level, a universal hash function partitions the
input into smaller subsets, each of which is then resolved at the second level
using another universal hash function mapping the elements into sufficiently
large tables. The structure supports (sequential) membership queries in worst-
case constant time by evaluating the hash functions and navigating the
structure accordingly. Updates are supported in amortized expected constant
time by carefully rebuilding and rehashing the structure during execution. At
any point in time the structure never uses more than $O(n)$ space. We show how
to parallelize the evaluation of a universal hash function (the simple and
practically efficient _multiply-shift_ hash function). Then, using the
scattered memory access operations, we show how to access the corresponding
entries in the structure in parallel. Our technique requires only small
changes to the structure of Dietzfelbinger et al. [20] and we can directly
apply their update operations to our solution. Thus, we are able to
parallelize the worst-case constant time sequential membership query while
maintaining the amortized expected constant update time bound of
Dietzfelbinger et al. [20], leading to the bounds of Theorem 2.

We first show Theorem 1 for the simpler case $\epsilon=1$ that corresponds to
the original UWRAM model by [22]. Our data structure is based on the
emph$x$-fast trie of Willard [40] combined with our parallel dictionary
structure of Theorem 2. The $x$-fast trie consists of the trie $T$ of the
binary representation of the input set. Also, at each level $i$, the structure
stores a dictionary containing the length-$i$ prefixes of the input set. In
total, this uses $O(nw)$ space. The $x$-fast trie supports predecessor queries
in $O(\log w)$ time by binary searching the levels (with the help of the
dictionaries) to find the longest common prefix of the query and the input
set. Though not designed for it, we can implement updates on the $x$-fast trie
in $O(w)$ time by directly updating each level of the dictionary accordingly.
Our new predecessor structure, which we call the _$x$ tra-fast trie_, instead
stores the compact trie of the binary representation of the input set (i.e.,
the trie where paths of nodes with a single child are merged into a single
edge). We store a dictionary representing the prefixes (similar to in the
$x$-fast trie) using our parallel dictionary structure of Theorem 2, but now
only for the branching nodes in the compact trie. This reduces the space to
$O(n)$. To support predecessor queries for an integer $x$, we generate all $w$
prefixes of $x$ and apply a parallel membership query on these in the
dictionary. We show how to identify the longest match in parallel which in
turn allows us to identify the predecessor. In total this takes worst-case
constant time for the predecessor query. To handle updates, we show how to
modify the trie efficiently using scattered memory access operations and a
constant number of dictionary updates, leading to the expected amortized
constant time bound of Theorem 1.

We generalize our result for Theorem 1 to arbitrary $\epsilon>0$ as follows.
The main challenge is that $\mathsf{pMember}{}$ now supports only
$w^{\epsilon}$ member queries in parallel, so we cannot search for all
prefixes of $x$ simultaneously. Instead, we adapt ideas from the $y$-fast trie
by Willard [40] to our $x$tra-fast trie. The $y$-fast trie works as follows.
Partition the input set $S$ into $O(n/w)$ sets $S_{1},\ldots,S_{t}$ where each
$S_{i}$ consists of $w$ consecutive values from $S$, i.e., where
$\max(S_{i})<\min(S_{i+1})$ for each $i$. Build an $x$-fast trie over the set
$S^{\prime}=\\{\max(S_{i})\mid i=1,\ldots,t-1\\}$ — which takes $O(n)$ space
since $|S^{\prime}|=O(n/w)$ — and a balanced binary search tree over each
$S_{i}$. To determine $\mathsf{predecessor}{}(x)$, do a predecessor query in
the $x$-fast trie to determine the set $S_{i}$ containing the predecessor of
$x$ and do a predecessor query in $S_{i}$, both of which takes $O(\log w)$
time. Insertions are supported by instead inserting $x$ in $S_{i}$. If $S_{i}$
subsequently becomes too large (e.g., larger than $2w)$, split $S_{i}$ into
two and add an additional element to $S^{\prime}$ in the $x$-fast trie. This
takes $O(w)$ time, which is constant when amortized over the $\Omega(w)$
insertions necessary for $S_{i}$ to grow too large. Deletions are supported
similarly. In our data structure we use dynamic fusion trees by Pătraşcu and
Thorup [34] for each $S_{i}$, which solves the predecessor problem on sets of
size $w^{O(1)}$ in linear space and constant time per operation. We build an
_uncompacted_ $x$tra-fast trie over $S^{\prime}$, i.e. the $x$tra-fast trie
that also includes non-branching nodes. To support fast queries and updates
for an integer $x$, we use the scattered memory operations to simulate a
$w^{\epsilon}$-way search (as opposed to a binary search) to find the longest
common prefix between $x$ and $S^{\prime}$. This eliminates a factor
$1/w^{\epsilon}$ of the remaining possibilities per round, leading to a
running time of $O(\log_{w^{\epsilon}}w)=O(1/\epsilon)$, i.e., constant for
any fixed $\epsilon$.

In our data structures we only need to store a constant number of ultrawords
during the computation. This is important since modern vector processor
architectures only have a limited number of ultraword registers.

###  1.3 Outline

In Section 2 we describe the UWRAM model of computation and some useful
procedures. In Sections 3 and 4 we show how to do parallel hash function
evaluation and $w^{\epsilon}$-parallel dictionaries, proving Theorem 2.
Finally, in Section 5 we prove Theorem 1 for $\epsilon=1$, which we generalize
to arbitrary $\epsilon>0$ in Section 6.

##  2 The Ultra-Wide Word RAM Model

The _word RAM_ model of computation [25] consists of an unbounded memory of
$w$-bit words and a standard instruction set including arithmetic, boolean,
and bitwise operations (denoted ‘$\&$’, ‘$|$’ and ‘$\sim$’ for and, or and
not) and shifts (denoted ‘$\gg$’ and ‘$\ll$’) such as those available in
standard programming languages (e.g., C). We make the standard assumption that
we can store a pointer into the input in a single word and hence $w\geq\log
n$, where $n$ is the size of the input, and for simplicity we assume that $w$
is even. We denote the address of $x$ in memory as $\mathsf{addr}(x)$, and the
address of an array is the address of its first index. The time complexity of
a word RAM algorithm is the number of instructions and the space is the number
of words stored by the algorithm.

The _ultra-wide word RAM_ (UWRAM) model of computation [22] extends he word
RAM model with special _ultrawords_ of $w^{2}$ bits (in Section 6 we consider
the case where ultrawords have $w^{1+\epsilon}$ bits for any fixed
$\epsilon>0$). As in [22], we distinguish between the _restricted UWRAM_ that
supports a minimal set of instructions on ultrawords consisting of addition,
subtraction, shifts, and bitwise boolean operations, and the _multiplication
UWRAM_ that additionally supports multiplications. We extend the notation for
bitwise operations and shifts to ultrawords. The UWRAM (both restricted and
multiplication) also supports contiguous and scattered memory access
operations, as described below. The time complexity is the number of
instructions (on standard words or ultrawords) and the space complexity is the
number of words used by the algorithms, where each ultraword is counted as $w$
words. The UWRAM model captures (and idealizes) modern vector processing
architectures [35, 37, 16]. See also Farzan et al. [22] for a detailed
discussion of the applicability of the UWRAM model.

Figure 1: The layout of an ultraword $X$.

###  2.1 Instructions and Componentwise Operations

Recall that ultrawords consists of $w^{2}$ bits. We often view an ultraword
$X$ as divided into $w$ words of $w$ consecutive bits each, which we call the
_components_ of $X$. We number the components in $X$ from right-to-left
starting from $0$ and use the notation $X\langle{i}\rangle$ to denote the
$i$th word in $X$ (see Figure 1). We will also use the notation
$X=\langle{x_{w-1},\ldots,x_{0}}\rangle$, denoting that $X\langle
i\rangle=x_{i}$.

We define a number of useful componentwise operations on ultrawords that we
will need for our algorithms in the following. Let $X$ and $Y$ be ultrawords.
The _componentwise addition_ of $X$ and $Y$, denoted $X+Y$, is the ultraword
$Z$ such that $Z\langle{i}\rangle=X\langle{i}\rangle+Y\langle{i}\rangle\mod
2^{w}$. We define _componentwise subtraction_ , denoted $X-Y$, and
_componentwise multiplication_ , denoted $XY$, similarly. The _componentwise
comparison_ of $X$ and $Y$ is the ultraword $Z$ such that
$Z\langle{i}\rangle=1$ if $X\langle{i}\rangle<Y\langle{i}\rangle$ and $0$
otherwise. Given another ultraword $I$ where each component is either $0$ or
$1$, we define the _componentwise blend_ of $X$, $Y$, and $I$ to be the
ultraword $Z$ such that $Z\langle{i}\rangle=X\langle{i}\rangle$ if
$I\langle{i}\rangle=0$ and $Z\langle i\rangle=Y\langle{i}\rangle$ if
$I\langle{i}\rangle=1$.

Except for componentwise multiplication, all of the above componentwise
operations can be implemented in constant time on the restricted UWRAM using
standard word-level parallelism techniques [25, 12] (see Appendix A for
details on blend). For our purposes, we will need componentwise multiplication
as an instruction (for evaluating hash functions in parallel) and thus we
include this in the instruction set of the UWRAM. This is the UWRAM model that
we will use throughout the rest of the paper. Note that all of the
componentwise operations are widely supported directly in modern vector
processing architectures. For instance, a componentwise multiplication (e.g.,
the vpmullw operation) is defined in Intel’s AVX2 vector extension [17].

We will need componentwise operations on components that are small constant
multiples of $w$. In particular, we will need a _$2w$ -bit componentwise
multiplication_ that multiplies $w/2$ components of $w$ bits and returns the
$w/2$ resulting components of $2w$ bits. Specifically, let $X=\langle
0,x_{w-2},\ldots,0,x_{2},0,x_{0}\rangle$ and $Y=\langle
0,y_{w-2},\ldots,0,y_{2},0,y_{0}\rangle$, i.e., $X$ and $Y$ store $w/2$
components aligned at the even positions. The $2w$-bit componentwise
multiplication is the ultraword $Z=\langle
z_{w-2}^{+},z_{w-2}^{-},\ldots,z_{2}^{+},z_{2}^{-},z_{0}^{+},z_{0}^{-}\rangle$
where $z_{i}^{+}$ and $z_{i}^{-}$ is the leftmost and rightmost $w$ bits,
respectively, of the $2w$-bit product of $x_{i}$ and $y_{i}$. We can implement
$2w$-bit componentwise multiplication using standard techniques in constant
time on the UWRAM. See Appendix A for details.

Finally, the UWRAM model supports the $\mathsf{compress}$ operation that,
given $X$, returns the word that results from concatenating the rightmost bit
of each component of $X$. We do not need the corresponding inverse
$\mathsf{spread}$ operation, defined by Farzan et al. [22].

###  2.2 Memory Access

The UWRAM supports standard memory access operations that read or write a
single word or a sequence of $w$ contiguous words. More interestingly, the
UWRAM also supports _scattered_ access operations that access $w$ memory
locations (not necessarily contiguous) in parallel. Given an ultraword $A$
containing $w$ memory addresses, a _scattered read_ loads the contents of the
addresses into an ultraword $X$, such that $X\langle{i}\rangle$ contains the
contents of memory location $A\langle{i}\rangle$. Given ultrawords $X$ and $A$
a _scattered write_ sets the contents of memory location $A\langle{i}\rangle$
to be $X\langle{i}\rangle$. Scattered memory accesses captures the memory
model used in IBM’s _Cell_ architecture [16]. They also appear (e.g.,
vpgatherdd) in Intel’s AVX2 vector extension [17]. Scattered memory access
operations were also proposed by Larsen and Pagh [27] in the context of the
I/O model of computation. Note that while the addresses for scattered writes
must be distinct, we can read simultaneously from the same address. We can use
this to efficiently copy $x$ into all $w$ components of an ultraword $X$. To
do so, create the ultraword $\langle{0,\ldots,0}\rangle$ by left-shifting any
ultraword by $w^{2}$ bits, write $x$ to address $0$, and do a scattered read
on $\langle{0,\ldots,0}\rangle$. We say that we _load_ $x$ into $X$.

##  3 Computing Multiply-Shift in Parallel

We show how to efficiently compute a universal hash function in parallel. The
_multiply-shift_ hashing scheme is a standard and practically efficient family
of universal hash functions due to Dietzfelbinger et al. [19]. For some
integer $1\leq c\leq w$, define the class $H_{c}=\\{h_{a}\mid 0<a<2^{w}\text{
and $a$ is odd}\\}$ of hash functions where ${h_{a}(x)=(ax\mod
2^{w})\gg(w-c)}$. Each function in $H_{c}$ maps from $w$-bit to $c$-bit
integers. The class $H_{c}$ is _universal_ in the sense that for any $x\neq y$
and for $h_{a}\in H_{c}$ selected uniformly at random, it holds that
$P[h_{a}(x)=h_{a}(y)]\leq 2/2^{c}$.

We will show how to evaluate $w$ such functions in constant time. Given
$X\langle i\rangle=x_{i}$, $A\langle i\rangle=a_{i}$ and $C\langle
i\rangle=2^{c_{i}}$ where $h_{i}(x)=(a_{i}x\mod 2^{w})\gg(w-c_{i})$ the goal
is to compute ${H\langle i\rangle=h_{i}(x_{i})}$. To do so we first evaluate
the functions in two rounds of $w/2$ functions each, and then combine the
results.

#### Step 1: Evaluate the hash function on the even indices.

We construct an ultraword $H_{\text{even}}$ containing all the values of
$h_{i}(x_{i})$ at all even indices $i$. First construct the ultrawords

$\displaystyle C^{\prime}$ $\displaystyle=\langle
0,2^{c_{w-2}},\ldots,0,2^{c_{0}}\rangle$ $\displaystyle T^{\prime}$
$\displaystyle=\langle 0,a_{w-2}x_{w-2}\mod 2^{w},\ldots,0,a_{0}x_{0}\mod
2^{w}\rangle.$

To do so, we do componentwise multiplication of $C$ with the constant
$M=\langle{0,1,\ldots,0,1}\rangle$ and componentwise multiplications of $A$,
$X$, and $M$. Then, we do a $2w$-bit multiplication of $C^{\prime}$ and
$T^{\prime}$ and right shift the result by $w$. This produces the ultraword

$H_{\text{even}}=\langle{\star,(a_{w-2}x_{w-2}\mod
2^{w})\gg(w-c_{w-2}),\ldots,\star,(a_{0}x_{0}\mod 2^{w})\gg(w-c_{0})}\rangle$

Thus, all even indices in $H_{\text{even}}$ store the resulting hash values of
the integers at the even indices in the input. We will not need the values in
the odd indices (resulting from the $2w$-bit multiplication and the right
shift) and therefore these are marked with a wildcard symbol $\star$.

#### Step 2: Evaluate the hash function on the odd indices.

Symmetrically, we now construct the ultraword $H_{\text{odd}}$ containing
$h_{i}(x_{i})$ at all odd indices $i$. To do so, repeat step 1 and modify the
shifting to align the computation for the odd indices. More precisely, right
shift $X$, $C$ and $A$ by $w$ and repeat step 1, then left shift the result by
$w$ to align the results back to the odd positions. This produces the
ultraword

$H_{\text{odd}}=\langle{(a_{w-1}x_{w-1}\mod 2^{w})\ll
c_{w-1},\star,\ldots,(a_{1}x_{1}\mod 2^{w})\ll c_{1},\star}\rangle$

#### Step 3: Combine the results.

Finally, we combine the results by blending $H_{\text{even}}$ and
$H_{\text{odd}}$ using $I=\langle{1,\ldots,1}\rangle-M$, producing the
ultraword $H$ of the even indices of $H_{\text{even}}$ and the odd indices of
$H_{\text{odd}}$.

This takes constant time since componentwise multiplication, $2w$-bit
multiplication, shifting, blending, loading $1$ into
$\langle{1,\ldots,1}\rangle$, and componentwise subtraction all run in
constant time. Hence, we can evaluate each case of $w/2$ hash functions in
constant time and combine the results in constant time. In summary, we have
the following result.

###### Lemma 1

Given $X\langle i\rangle=x_{i}$, $\,A\langle i\rangle=a_{i}$, $\,C\langle
i\rangle=2^{c_{i}}$, and the constant $M=\langle{0,1,\ldots,0,1}\rangle$ we
can evaluate each of the $w$ multiply-shift hash functions
$h_{i}(x)=(a_{i}x\mod 2^{w})\gg(w-c_{i})$ by computing the ultraword
$H=\langle{h_{w-1}(x_{w-1}),\ldots,h_{0}(x_{0})}\rangle$ in constant time on a
UWRAM.

##  4 The $\boldsymbol{w^{\epsilon}}$-Parallel Dictionary

We now show how to construct the $w^{\epsilon}$-parallel dictionary of Theorem
2. Throughout the section we assume that $\epsilon=1$, but the result
generalizes to any $\epsilon>0$ in a straight forward manner. Our data
structure is based on a dictionary by Dietzfelbinger et al. that implements a
dynamic perfect hashing strategy [20]. Their dictionary already supports
$\mathsf{insert}$ and $\mathsf{delete}$ in amortized expected constant time.
Furthermore, it supports sequential $\mathsf{member}$ queries (i.e. “is $x\in
S$”) in worst case constant time. We will show that we can use scattered
memory operations to run $w$ $\mathsf{member}$ queries simultaneously, thus
implementing $\mathsf{pMember}$ in constant time.

###  4.1 Dynamic Perfect Hashing

In this section we briefly describe the contents of the data structure of
Dietzfelbinger et al. [20]. Note that we use the multiply-shift hashing
scheme, while they use another class of universal hash functions. Multiply-
shift satisfies all the necessary constraints and the analysis from [20] still
works. It does however incur a multiplicative, constant space overhead for our
arrays since the range of a multiply-shift function is a power of two.

The main idea of the data structure is as follows. Let $S$ be a set of $w$-bit
integers. Choose $h\in H_{c}$ and partition $S$ into $2^{c}=\Theta(n)$ sets
$S_{0},\ldots,S_{2^{c}-1}$ where $S_{i}=\\{x\mid x\in S\text{ and }h(x)=i\\}$.
Each set $S_{i}$ is stored in a separate array using a hash function $h_{i}$.
Dietzfelbinger et al. show how to implement the operations $\mathsf{insert}$
and $\mathsf{delete}$ such that they maintain that $h_{i}$ has no collisions
on $S_{i}$.

The data structure consists of the following.

  * •

For each $S_{i}$, store an array $T_{i}$ of size $2^{c_{i}}$. Let
$h_{i}(x)=(a_{i}x\mod 2^{w})\gg(w-c_{i})$. For each $x\in S_{i}$ let
$T_{i}[h_{i}(x)]=x$, i.e. the position that $x$ hashes to stores $x$. If there
is no $x\in S_{i}$ that hashes to $j$, then $T_{i}[j]=2^{w-1}$ if $j=0$ and
$T_{i}[j]=0$ otherwise. We claim that $h_{i}(0)$ is always zero and
$h_{i}(2^{w-1})$ is never zero, so it follows from this construction that
$x\in S_{i}$ if and only if $T_{i}[h_{i}(x)]=x$. We have that $h_{i}(2^{w-1})$
is not zero because

$h_{i}(2^{w-1})\;\;=\;\;(a_{i}2^{w-1}\mod
2^{w})\gg(w-c_{i})\;\;=\;\;2^{w-1}\gg(w-c_{i})\;\;\geq\;\;1.$

The second step follows since $a_{i}$ is odd; then
$a_{i}2^{w-1}=2^{w-1}+(a_{i}-1)2^{w-1}$, and the latter term is $0$ modulo
$2^{w}$ since $a_{i}-1$ is even. The last step follows because $c_{i}\geq 1$.

  * •

An array $T$ of size $2^{c}$. At index $T[i]$ we store the $5$-tuple
$(\mathsf{addr}(T_{i}),2^{c_{i}},a_{i},\star,\star)$ where $\star$ are book-
keeping values used by $\mathsf{insert}$ and $\mathsf{delete}$. Note that
$2^{c_{i}}$ and $a_{i}$ encode $h_{i}$.

  * •

The integers $a$ and $2^{c}$ representing the top-level hash function
$h(x)=(ax\mod 2^{w})\gg(w-c)$, as well as $\mathsf{addr}(T)$.

It follows from this construction that $x\in S$ if and only if
$T_{i}[h_{i}(x)]=x$ where $i=h(x)$. Dietzfelbinger et al. show that the data
structure uses linear space, that $\mathsf{member}$ runs in worst-case
constant time, and that $\mathsf{insert}$ and $\mathsf{delete}$ run in
amortized expected constant time [20].

#### Extending the Data Structure.

We extend this data structure by storing the constant $M=\langle
0,1,\ldots,0,1,0,1\rangle$ from Section 3 used to evaluate multiply-shift
functions in parallel. This increases the space of the data structure to
$O(n+w)$. Note that linear space in $w$ is needed even to store the input to a
$\mathsf{pMember}$ query.

###  4.2 Parallel Queries

In this section, we begin by describing a single $\mathsf{member}$ query,
before we show how to run $w$ copies of the $\mathsf{member}$ query in
parallel to support $\mathsf{pMember}$. We compute $\mathsf{member}{}(x)$ as
follows.

  1. 1.

Using $a$ and $2^{c}$, compute $j=h(x)$.

  2. 2.

Let $q=\mathsf{addr}(T)+5j=\mathsf{addr}(T[j])$ (recall that each index in $T$
stores five words). Read the values stored at $q$, $q+1$ and $q+2$ to get
respectively $\mathsf{addr}(T_{j})$, $2^{c_{j}}$ and $a_{j}$, the first three
words stored at $T[j]$. Compute $k=h_{j}(x)$.

  3. 3.

Check whether the value stored at
$\mathsf{addr}(T_{j})+k=\mathsf{addr}(T_{j}[k])$ is equal to $x$.

The parallel algorithm runs this algorithm for all $w$ inputs simultaneously.
Given $X=\langle{x_{w-1},\ldots,x_{0}}\rangle$ we implement
$\mathsf{pMember}{}(X)$ as follows. Each of the steps below executes the
corresponding step above in parallel for each of the $w$ inputs.

#### Step 1: Evaluate the top-level hash function.

Load the two ultrawords $A=\langle{a,\ldots,a}\rangle$ and
$C=\langle{2^{c},\ldots,2^{c}}\rangle$. Compute the ultraword
$J=\langle{h(x_{w-1}),\ldots,h(x_{0})}\rangle$ using the multiply-shift
algorithm of Lemma 1.

#### Step 2: Evaluate each of the second-level hash functions.

Load $F=\langle{5,\ldots,5}\rangle$ and
$P=\langle{\mathsf{addr}(T),\ldots,\mathsf{addr}(T)}\rangle$. Compute
$Q=P+FJ$. Then $Q\langle i\rangle=\mathsf{addr}(T)+5J\langle
i\rangle=\mathsf{addr}(T[J\langle i\rangle])$. Do scattered reads of $Q$,
$Q+\langle{1,\ldots,1}\rangle$, and $Q+\langle{2,\ldots,2}\rangle$ to produce
the ultrawords $P^{\prime}$, $C^{\prime}$, and $A^{\prime}$. We have that

$\displaystyle P^{\prime}$ $\displaystyle=\langle\mathsf{addr}(T_{J\langle
w-1\rangle}),\ldots,\mathsf{addr}(T_{J\langle 0\rangle})\rangle$
$\displaystyle C^{\prime}$ $\displaystyle=\langle 2^{c_{J\langle
w-1\rangle}},\ldots,2^{c_{J\langle 0\rangle}}\rangle$ $\displaystyle
A^{\prime}$ $\displaystyle=\langle a_{J\langle w-1\rangle},\ldots,a_{J\langle
0\rangle}\rangle$

Compute the ultraword $K=\langle{h_{J\langle
w-1\rangle}(x_{w-1}),\ldots,h_{J\langle 0\rangle}(x_{0})}\rangle$ using the
multiply-shift algorithm of Lemma 1.

#### Step 3: Check whether the inputs are present in the dictionary.

Do a scattered read of $P^{\prime}+K$ and name the result $R$. Then $R\langle
i\rangle=T_{j}[h_{j}(x_{i})]$ where $j=h(x_{i})$. Return the result $I$ of
componentwise equality between $X$ and $R$. That is

$I\langle i\rangle=\begin{cases}1&\text{ if }X\langle i\rangle=R\langle
i\rangle\\\ 0&\text{ otherwise}\end{cases}$

Evaluating the hash functions in steps 1 and 2 takes constant time according
to Lemma 1. The remaining operations are scattered reads, loads and
componentwise operations, all of which run in constant time. Since there is
only a constant number of operations, $\mathsf{pMember}$ runs in constant
time. This concludes the proof of Theorem 2.

Note that both the algorithm for parallel hashing and the dictionary
generalizes to the case with $w^{1+\epsilon}$-bit ultrawords and
$w^{\epsilon}$ inputs in a straight forward manner. In this case, the space is
$O(n+w^{\epsilon})$ since the ultraword constants use only $w^{\epsilon}$
space.

###  4.3 Satellite Data

Suppose we associate some value $\mathsf{data}(x)$ with each $x\in S$. We
extend the data structure to support the following operation, where
$X=\langle{x_{w-1},\ldots,x_{0}}\rangle$ as above.

  * •

$\mathsf{pRetrieve}{}(X)$: returns a pair $(I,D)$ where $I$ is the result of
$\mathsf{pMember}(X)$ and

$D\langle i\rangle=\begin{cases}\mathsf{addr}(\mathsf{data}(x_{i}))&\text{ if
}I\langle i\rangle=1\text{, i.e if }x_{i}\in S\\\ \text{undefined}&\text{
otherwise}\end{cases}$

We return $\mathsf{addr}(\mathsf{data}(x))$ instead of $\mathsf{data}(x)$
since the data would not fit into an ultraword if $\mathsf{data}(x)$ requires
more than one word to store.

We extend the data structure as follows to support $\mathsf{pRetrieve}$. Store
two words for each index in $T_{i}$. For each $x\in S_{i}$, the first word in
$T_{i}[h_{i}(x)]$ stores $x$ and the second stores
$\mathsf{addr}(\mathsf{data}(x))$. The remaining entries store either $0$ or
$2^{w-1}$, as above.

To do the retrieval, first compute $I=\mathsf{pMember}{}(X)$. However, in step
3, multiply $K$ by $\langle{2,\ldots,2}\rangle$ before the scattered read
since each index in $T_{i}$ now stores two words. Also, add
$\langle{1,\ldots,1}\rangle$ to $P^{\prime}+\langle{2,\ldots 2}\rangle K$ and
do a scattered read to compute the ultraword $D$. The space of the data
structure remains $O(n+w)$ (assuming that $\mathsf{data}(x)$ uses constant
space), and $\mathsf{pRetrieve}$ runs in constant time.

##  5 The $\boldsymbol{x}$tra-fast Trie

In this section we prove Theorem 1 for the special case where $\epsilon=1$,
i.e. where ultrawords consist of $w^{2}$ bits. We generalize our result to
arbitrary $\epsilon>0$ in Section 6. Our data structure, the $x$tra-fast trie,
supports $\mathsf{predecessor}$ in worst case constant time and
$\mathsf{insert}$ and $\mathsf{delete}$ in amortized expected constant time.
In our description we assume that we have keys of $w-1$ bits each and we give
a solution that uses $O(n+w)$ space. At the end of this section we will reduce
the space to $O(n)$ and extend the solution to $w$-bit keys, proving Theorem 1
for $\epsilon=1$.

###  5.1 Data Structure

Consider the compacted trie $T$ over the binary representation of the elements
in $S$. For each node $v\in T$ define $\mathsf{str}(v)$ to be the bitstring
encoded by the path from the root to $v$ in $T$. Also let $\mathsf{min}(v)$
and $\mathsf{max}(v)$ be the smallest and largest leaves in the subtree of
$v$, respectively. By $\mathsf{min}(v)$ and $\mathsf{max}(v)$ we refer both to
a leaf and to the value the leaf represents.

For each edge $(u,v)\in T$, let $\mathsf{label}(u,v)$ be $\mathsf{str}(u)$
followed by the first bit on the edge $(u,v)$. Define $\mathsf{key}(u,v)$ to
be $\mathsf{label}(u,v)$ followed by a single $1$-bit and
$w-|\mathsf{label}(u,v)|-1$ zeroes. Note that $|\mathsf{key}(u,v)|=w$ and that
the keys of two distinct edges in $T$ always differ. See Figure 2 for an
example.

We define the _exit edge_ for an integer $x$ to be the edge in $T$ where the
match of $x$ ends. In other words, it is the edge $(u,v)\in T$ such that
$\mathsf{label}(u,v)$ is a prefix of $x$ and $|\mathsf{label}(u,v)|$ is
maximum. See Figure 2 for an example. It is possible that $x$ has no exit edge
if the root has fewer than two children.

Our data structure consists of the following:

  * •

A sorted, doubly linked list $L$ of the leaves of $T$, i.e., the elements of
$S$.

  * •

A dictionary $D$ supporting parallel queries using Theorem 2. For each edge
$(u,v)\in T$ we store an entry in $D$ with the key $\mathsf{key}(u,v)$ and
$\mathsf{data}(u,v)=(\mathsf{addr}(\mathsf{min}(v)),\mathsf{addr}(\mathsf{max}(v)))$.
Here, $\mathsf{addr}(\mathsf{min}(v))$ and $\mathsf{addr}(\mathsf{max}(v))$
are the addresses to the corresponding elements in $L$, and we denote the
addresses to $\mathsf{min}(v)$ and $\mathsf{max}(v)$ as the _min-_ and _max-
pointer_ of $(u,v)$.

  * •

The two ultraword constants $M^{\prime}$ and $H$ described in the next
section.

Storing $L$ and the ultraword constants takes $O(n+w)$ space combined. Since
$T$ is compacted there are $O(n)$ entries in $D$, so by Theorem 2 the
dictionary also uses $O(n+w)$ space.

Figure 2: An $x$tra-fast trie for
$S=\\{001000,001010,001011,101000,101010,110110,110111,111100\\}$. The dashed
edge and nodes illustrate how the trie would change if $x=110101$ were
inserted. The exit edge for $x$ is $(u,v)$ since we match the bitstring $1101$
but do not match the next $1$ on $(u,v)$. Similarly, the exit edge for
$100100$ is $(s,t)$. We have that
$\mathsf{key}(u,v)=\mathsf{label}(u,v)\underline{1000}=110\underline{1000}$
where the underlined part is what we append to the labels to disambiguate the
keys. Similarly, $\mathsf{key}(r,s)=1\underline{100000}$ and
$\mathsf{key}(s,t)=10\underline{10000}$. The dictionary entry of $(s,u)$ has
$\mathsf{key}(s,u)=11\underline{10000}$, and the min- and max-pointer of
$(s,u)$ are $\mathsf{addr}(\mathsf{min}(u))$ and
$\mathsf{addr}(\mathsf{max}(u))$. Similarly, the min-pointer of $(r,s)$ is to
$\mathsf{min}(s)=\mathsf{min}(t)$ and the max-pointer is to
$\mathsf{max}(s)=\mathsf{max}(u)$. Note that if we insert $x$ we would have to
update the min-pointer of $(s,u)$, since $x<\mathsf{min}(v)$. However, the
min-pointer of $(r,s)$ remains unchanged since $\mathsf{min}(t)<x$.

###  5.2 Predecessor Queries

The main idea of the predecessor query for $x$ is to first find the exit edge
of $x$ by simultaneously searching for all prefixes of $x$ in $D$. Then we use
the min- and max-pointer of the exit edge to find the predecessor of $x$. If
$x$ has no exit edge, then the root does not have an outgoing edge matching
the leftmost bit of $x$. If the leftmost bit of $x$ is $1$, the predecessor of
$x$ is the largest leaf in the left subtree of the root, and otherwise $x$ has
no predecessor. Assuming that $x$ has an exit edge, the procedure has three
steps.

#### Step 1: Compute all prefixes of $x$.

Let $b_{w-2}b_{w-3}\cdots b_{0}$ be the binary representation of $x$ of length
$w-1$. We compute the ultraword

$\overline{X}=\langle{b_{w-2}b_{w-3}\cdots b_{0}1\;\,,\;\,b_{w-2}b_{w-3}\cdots
b_{1}10\;\,,\;\,\ldots\;\,,\;\,10\cdots 0}\rangle.$

That is, $\overline{X}\langle i\rangle$ contains the prefix of $x$ of length
$i$ followed by a $1$-bit and $w-i-1$ zeroes. Thus, for any edge $(u,v)\in T$
such that $\mathsf{label}(u,v)$ is the length-$i$ prefix of $x$, we have
$\overline{X}\langle i\rangle=\mathsf{key}(u,v)$. We compute $\overline{X}$ as
follows.

Let $M^{\prime}$ be the constant such that $M^{\prime}\langle i\rangle$
consists of $i$ consecutive $1$-bits followed by $w-i$ consecutive $0$-bits.
Let $H$ be the constant where the $(i+1)$th leftmost bit in $H\langle
i\rangle$ is $1$ and the remaining bits are zeroes. First load $x$ into $X$
such that $X=\langle x,x,\ldots,x\rangle$. Then compute
$\overline{X}=(X~{}\&~{}M^{\prime})\mid H$.

#### Step 2: Find the exit edge $(u,v)$ of $x$.

First do $(I,P)=\mathsf{pRetrieve}{}(\,\overline{X}\,)$ on $D$. Then compute
$c=\mathsf{compress}(I)$ such that the $i$th rightmost bit in $c$ is $1$ if
$I\langle i\rangle=1$ and zero otherwise. Note that $x$ has no exit edge if
$c=0$. Find the index $k$ of the leftmost bit in $c$ that is $1$ (see [24]).
Then $\overline{X}\langle k\rangle=\mathsf{key}(u,v)$ where $(u,v)$ is the
exit edge of $x$. Furthermore, the values stored at the addresses $P\langle
k\rangle$ and $P\langle k\rangle+1$ are the min- and max-pointers of $(u,v)$,
respectively.

#### Step 3: Find the predecessor of $x$.

Use the min- and max-pointer of $(u,v)$ found in step 2 to retrieve
$\mathsf{min}(v)$ and $\mathsf{max}(v)$. If $x\geq\mathsf{max}(v)$ then return
$\mathsf{max}(v)$, otherwise return the element immediately left of
$\mathsf{min}(v)$ in $L$. Note that there might not be an element immediately
left of $\mathsf{min}(v)$ if $x$ is smaller than than everything in $S$, in
which case $x$ has no predecessor.

Since we search for all prefixes of $x$ and take the edge corresponding to the
longest prefix found, we find the exit edge $(u,v)$ of $x$. If $x\in S$, then
$x=v=\mathsf{max}(v)$ and we correctly return that $x$ is the predecessor of
itself. If $x\not\in S$ then the path to where $x$ would have been located if
it were in $T$ branches off $(u,v)$ either to the left (if
$x<\mathsf{min}(v)$) or right (if $x>\mathsf{max}(v)$). In the first case,
$\mathsf{predecessor}{}(x)$ is the element located immediately left of
$\mathsf{min}(v)$ in $T$, and in the second case $\mathsf{predecessor}{}(x)$
is $\mathsf{max}(v)$.

By Theorem 2 the parallel dictionary query in step 2 takes worst case constant
time. Finding the leftmost bit that is $1$ takes constant time on the word RAM
[24]. The remaining operations are standard operations available in the model,
so the procedure runs in constant time.

###  5.3 Insertions

The main idea of the insertion procedure is as follows. Since $T$ is
compacted, inserting a new leaf $x$ will cause only a constant number of edges
to be inserted and removed, so we can make these changes sequentially.
Furthermore, some of the at most $w-1$ edges on the path from the root to $x$
might have their min- or max-pointers changed, and we will update these edges
in parallel.

Consider inserting $x=110101$ in the trie in Figure 2. When $x$ is inserted we
add a new leaf for $x$, as well as a new node $p$ at the location where the
path to $x$ branches off the exit edge $(u,v)$ of $x$. This removes the edge
$(u,v)$, but adds the three new edges $(u,p)$, $(p,x)$ and $(p,v)$.
Furthermore, we must update the min-pointer of $(s,u)$, because
$\mathsf{min}(v)$ was replaced by $x$ as the smallest leaf under $u$. On the
other hand, we do not update the min-pointer of $(r,s)$ because
$\mathsf{min}(t)$ is smaller than $x$. Note that we do not explicitly store
internal nodes and therefore do not add $p$ anywhere in the data structure.

We now describe the insertion procedure. First we note that if $x$ does not
have an exit edge it is because the root does not have an outgoing edge which
shares the same leftmost bit as $x$. This case is easily solved by adding an
edge from the root to the new leaf $x$ and adding $x$ to either the start or
end of $L$. We will now assume that $x$ has an exit edge, and also that $x$
branches off its exit edge to the left; the other case is symmetric.

#### Step 1: Find the predecessor of $x$.

Do a predecessor query as described in Section 5.2, which determines

  * •

The predecessor of $x$ in $L$.

  * •

The exit edge $(u,v)$ of $x$, $\mathsf{label}(u,v)$ and
$\mathsf{data}(u,v)=(\mathsf{addr}(\mathsf{min}(v)),\mathsf{addr}(\mathsf{max}(v)))$.

  * •

The result $(I,P)$ of $\mathsf{pRetrieve}{}(\,\overline{X}\,)$ on $D$.

#### Step 2: Insert $x$ in $L$.

Insert $x$ immediately to the right of its predecessor in $L$.

#### Step 3: Update edges.

We insert $(u,p)$, $(p,x)$ and $(p,v)$ and remove $(u,v)$ from $D$. We find
the labels of the three edges to insert as follows. We have that
$\mathsf{label}(u,p)=\mathsf{label}(u,v)$ since $(u,p)$ is the edge $(u,v)$
shortened by adding the node $p$ and since only the first character of the
edge affects the label. By definition, $\mathsf{label}(p,x)$ and
$\mathsf{label}(p,v)$ consist of $\mathsf{str}(p)$ with a zero and a one
appended, respectively. We compute $\mathsf{str}(p)$ by finding the longest
common prefix $\hat{p}$ of $x$ and $\mathsf{min}(v)$. To do so, do bitwise XOR
between $x$ and $\mathsf{min}(v)$ and find the index $k$ of the leftmost bit
that is $1$ in the result (see [24]). Now $k$ indicates the leftmost bit where
$x$ and $\mathsf{min}(v)$ differ. To extract the longest common prefix compute
$\hat{p}=x~{}\&~{}{\sim}((1\ll(k+1))-1)$. Given the labels we can easily
construct the keys for the edges.

We now construct the satellite data for the edges. Both the min- and max-
pointer for $(p,x)$ are $\mathsf{addr}(x)$ since $x$ is a leaf. For $(p,v)$
they are $\mathsf{addr}(\mathsf{min}(v))$ and
$\mathsf{addr}(\mathsf{max}(v))$, which were determined during the predecessor
query. Finally, the min-pointer for $(u,p)$ is $\mathsf{addr}(x)$ and the max-
pointer is $\mathsf{addr}(\mathsf{max}(v))$.

#### Step 4: Update min-pointers.

We update the min-pointers for the edges on the path from the root to $u$ that
are incorrect after inserting $x$. Note that inserting $x$ cannot invalidate
any max-pointers since we assumed that $x$ branched off its exit edge to the
left. The edges that must be updated are exactly those that have a min-pointer
to $\mathsf{min}(v)$, since $x$ has replaced $\mathsf{min}(v)$ as the smallest
leaf under $u$.

Consider the result $(I,P)$ from the $\mathsf{pRetrieve}$ query. We begin by
setting $I\langle k^{\prime}\rangle=0$ for the index $k^{\prime}$
corresponding to the exit edge $(u,v)$ of $x$ (we know $k^{\prime}$ from the
predecessor query). The indices in $I$ that now contain $1$ indicate the edges
on the path from the root to $u$.

Next we identify the edges that needs to be updated by creating $I^{\prime}$
where $I^{\prime}\langle i\rangle=1$ if and only if both $I\langle i\rangle=1$
and what is stored at address $P\langle i\rangle$ is the address of
$\mathsf{min}(v)$. To do so, first do a scattered read of $P$ and store the
result in $M$. Now $M$ contains $\mathsf{addr}(\mathsf{min}(b))$ for each edge
$(a,b)$ on the path to $u$.222If $x$ branched off to the right of its exit
edge, we would do a scattered read of $P+\langle{1,\ldots,1}\rangle$ to load
the max-pointers instead of min-pointers. Note the value of $P\langle
i\rangle$ is arbitrary if $I\langle i\rangle=0$, i.e. if no edge has the
length-$i$ prefix of $x$ as its label. Load $\mathsf{addr}(\mathsf{min}(v))$
into the ultraword $V$. Let $E$ be the result of componentwise equality
between $M$ and $V$. Then $E\langle i\rangle=1$ if and only if what is stored
at address $P\langle i\rangle$ is $\mathsf{addr}(\mathsf{min}(v))$. Finally
compute $I^{\prime}=I\;\&\;E$.

Now we use $P$ and $I^{\prime}$ to update the incorrect min-pointers. First,
load the address of the node for $x$ into $U$. Then compute $B$ by blending
$M$ (the result of the scattered read of $P$) and $U$ conditioned on
$I^{\prime}$ such that

$B\langle i\rangle=\begin{cases}M\langle i\rangle&\text{ if }I^{\prime}\langle
i\rangle=0\quad\text{(i.e. the value already at the address $P\langle
i\rangle$) }\\\ U\langle i\rangle&\text{ if }I^{\prime}\langle
i\rangle=1\quad\text{(i.e. the address of $x$) }\\\ \end{cases}$

Finally, do a scattered write of $B$ to the addresses in $P$. Hence, what is
stored at the address $P\langle i\rangle$ remains the same if
$I^{\prime}\langle i\rangle=0$ and is replaced by the address of $x$
otherwise.

The predecessor query in step 1 takes constant time. The operations in step 2
and step 4 are all standard RAM or UWRAM operations, except for finding the
leftmost $1$-bit which takes constant time [24]. The dictionary updates in
step 3 run in amortized expected constant time by Theorem 2. Since the rest of
step 3 consists of standard operations, the running time for insertions is
amortized expected constant.

###  5.4 Deletions

The deletion procedure is essentially the inverse of the insertion procedure.
We assume that $x$ is the left child of its parent $p$; the other case is
symmetric.

#### Step 1: Find $x$.

Do a predecessor query for $x$. Since $x\in S$, the predecessor of $x$ is
itself. This determines

  * •

The position of $x$ in $L$.

  * •

The exit edge $(p,x)$ for $x$, along with $\mathsf{label}(p,x)$. Since $x\in
S$, this edge must end in the leaf for $x$.

  * •

The result $(I,P)$ of $\mathsf{pRetrieve}{}(\,\overline{X}\,)$ on $D$.

#### Step 2: Update min-pointers.

If $p$ is the root (i.e. if $|\mathsf{label}(p,x)|=1$) we remove the edge
$(p,x)$ from $D$ and remove $x$ from $L$ which completes the deletion of $x$.
Otherwise $p$ is an internal node and must have another child which we denote
by $v$. Consider the edges on the path to $p$. Any min-pointer to $x$ should
be replaced by the address of $\mathsf{min}(v)$, since $\mathsf{min}(v)$ is
the successor of $x$ and also in the subtree of all of these edges. We find
$\mathsf{min}(v)$ in the node immediately right of $x$ in $L$. As we did for
insertions, replace any min-pointer that is an address of $x$ by the address
of $\mathsf{min}(v)$ in parallel using $I$ and $P$.

#### Step 3: Delete edges.

We delete $(p,x)$ and $(p,v)$ from $D$. Determine $\mathsf{label}(p,v)$ by
flipping the last bit in $\mathsf{label}(p,x)$. Using the labels we easily
find the keys. Note that we do not explicitly delete the edge $(u,p)$ or
insert the edge $(u,v)$. These two edges share the same key, and the min-
pointer of $(u,p)$ was changed to the address of $\mathsf{min}(v)$ in step 2.

#### Step 4: Update $\mathbf{L}$.

Remove $x$ from $L$.

Steps 1, 2 and 4 all take constant time (see Sections 5.2 and 5.3). The two
deletions in step 3 take amortized constant time according to Theorem 2. The
remainder of step 3 takes constant time, so deletions run in amortized
expected constant time.

###  5.5 Reducing to Linear Space and Supporting $\boldsymbol{w}$-bit Keys

Here, we reduce the space to $O(n)$ and show how to support $w$-bit keys,
concluding the proof of Theorem 1.

The $O(w)$ term in the space bound above is due to the $w^{\epsilon}$-parallel
dictionary $D$ and $O(1)$ ultraword constants. To avoid this when $n=o(w)$, we
will initially support $\mathsf{predecessor}$, $\mathsf{insert}$ and
$\mathsf{delete}$ using the dynamic fusion tree by Pătraşcu and Thorup [34]
(based on the fusion tree by Fredman and Willard [24]), which uses linear
space and supports all three operations in constant time for sets of size
$w^{O(1)}$. Simultaneously, we build the ultraword constants we need over the
course of $\Theta(w)$ insertions, maintaining linear space. When $n\geq w$,
the constants have been built and we move all elements into the trie. If at
any point $n\leq w/2$, we move all elements from the trie into a fusion tree
and remove the trie and the ultraword constants, leaving us with linear space
and $\Theta(w)$ $\mathsf{insert}$ operations in which to rebuild the
constants. Updates still run in amortized expected constant time since we
always do $\Omega(w)$ updates before we move $O(w)$ elements.

To extend the solution to work with $w$-bit keys, we partition the input set
$S$ into $S_{0}$ and $S_{1}$ where $S_{i}=\\{s\mid s\in S\text{ and the
leftmost bit of $s$ is }i\\}$, and store an $x$tra-fast trie for each set.
Suppose the leftmost bit of an integer $x$ is $i$. An $\mathsf{insert}$,
$\mathsf{delete}$ or $\mathsf{predecessor}$ operation on $x$ is performed on
the data structure for $S_{i}$. Additionally, if $i=1$ and the
$\mathsf{predecessor}$ query on $S_{1}$ returns that $x$ has no predecessor,
we return the largest element in $S_{0}$, or report that $x$ has no
predecessor if $S_{0}$ is empty.

##  6 The $\boldsymbol{x}$tra-fast Trie With Smaller Ultrawords

In this section we show how to match the bounds of Theorem 1 when ultrawords
consist of only $w^{1+\epsilon}$ bits (i.e. $w^{\epsilon}$ components) for any
fixed $\epsilon>0$. The model is otherwise exactly as described in Section 2.

As mentioned, our data structure based on the $y$-fast trie by Willard [40]
(see Section 1.2). We partition the input set $S$ into $O(n/w)$ sets
$S_{1},\ldots,S_{t}$ where each $S_{i}$ consists of $w$ consecutive values
from $S$, i.e., where $\max(S_{i})<\min(S_{i+1})$ for each $i$ (note that
$|S_{t}|<w$ is possible). We build a dynamic fusion tree [34] over each
$S_{i}$ and an _uncompacted_ $x$tra-fast trie $\mathcal{T}$ over $S^{\prime}$,
i.e., the $x$tra-fast trie where we include non-branching nodes. The size of
$S^{\prime}$ is $O(n/w)$ and each root-to-leaf path has length $O(w)$, so
storing the uncompacted trie uses $O(n+w^{\epsilon})$ space, where the
additional $w^{\epsilon}$ is due to the $w^{\epsilon}$-parallel dictionary. We
also store a collection $B$ of ultraword constants (to be described shortly)
that increases the space to $O(n+w)$. Note that we use the same trick as in
Section 5.5 to reduce this to linear in $n$.

We answer $\mathsf{predecessor}{}(x)$ as in the $y$-fast trie by first
determining the predecessor of $x$ in $\mathcal{T}$, and then finding the
predecessor in the corresponding dynamic fusion tree, the latter of which
takes constant time [34]. We show that we can find the longest common prefix
between $x$ and $\mathcal{T}$ in constant time, from which it follows that we
can find the predecessor of $x$ in $\mathcal{T}$ in constant time (see Section
5.2). In the $y$-fast trie this is done by binary searching over the binary
representation of $x$, taking $O(\log w)$ time. We speed up the process by
doing a $w^{\epsilon}$-way search instead, reducing the running time to
$O(\log_{w^{\epsilon}}w)=O(1/\epsilon)$, or constant for any fixed $\epsilon$.
To do so, we first construct the ultraword $X_{R}$ that contains the labels
corresponding to the prefixes of $x$ of length
$w^{1-\epsilon},2w^{1-\epsilon},\ldots,w^{\epsilon}w^{1-\epsilon}$. We then do
a $\mathsf{pMember}{}$ query in the dictionary for $\mathcal{T}$,
$\mathsf{compress}{}$ the resulting ultraword (yielding a word indicating
which labels were found), and find the most significant bit to determine the
longest prefix found. This eliminates all but $w/w^{\epsilon}$ prefixes as
candidates for the longest common prefix with $\mathcal{T}$, and we recurse on
this range. To construct the correct labels we use the ultraword constants in
$B$. Recall that in Section 5.2 we use the constants $M^{\prime}$ and $H$ to
compute the labels for the parallel member query by
$\overline{X}=(X~{}\&~{}M^{\prime})\mid H$. We can compute any collection of
$w^{\epsilon}$ prefix-labels of $x$ in this way, provided that we use the
correct constants. We let $B$ encode a B-tree of degree $\Theta(w^{\epsilon})$
over $M^{\prime}$ and $H$, allowing us to perform the $w^{\epsilon}$-way
search. Consider some node $v$ in $B$ that has $k+1$ children. In $v$ we store
$k$ of the values from $M^{\prime}$ in an array $M^{\prime}_{v}$ and the
corresponding $k$ values from $H$ in another array $H_{v}$, ensuring that
$k\leq w^{\epsilon}$ so that each array fits into an ultraword. We
additionally store $k$ and the pointers to the children of $v$. When we visit
$v$ during the search, we read $M^{\prime}_{v}$ and $H_{v}$ into the $k$ least
significant components of two ultrawords. If $k<w^{\epsilon}$, the
$w^{1+\epsilon}-kw$ most significant bits of these ultrawords will contain
some values that are irrelevant to the parallel member query; we zero out
these bits by doing bitwise $\&$ with $(1\ll kw)-1$. This does not cause false
positives to occur in the $\mathsf{pMember}{}$ query since no edges in
$\mathcal{T}$ has the label $0$ due to how labels are constructed. We then
compute the $k$ prefix-labels of $x$, do the parallel lookup in the
dictionary, $\mathsf{compress}{}$ the result, and find the most significant
bit to determine which child of $v$ to continue the search in. Since $B$ is a
B-tree over $O(w)$ values it uses $O(w)$ space. Furthermore, the height of the
tree is $O(1/\epsilon)$ since the branching factor is $\Theta(w^{\epsilon})$.
We use constant time per node, concluding the proof of the predecessor query.

We also support insertions as in the $y$-fast trie. We determine which set
$S_{i}$ to add the new element to and update that dynamic fusion tree in
constant time. If $S_{i}$ becomes too large we split it (by deleting and
reinserting each element in another dynamic fusion tree) and add a separator
element to $\mathcal{T}$. This takes expected $O(w)$ time in total (the
expectation is from adding at most $w$ new edges to the
$w^{\epsilon}$-parallel dictionary), which is expected constant when amortized
over the $\Omega(w)$ updates between splits. Deletions are supported
similarly.

##  7 Conclusion and Open Problems

We have studied the predecessor problem on the UWRAM model of computation. We
have given a linear space data structure that supports predecessor queries in
worst case constant time and updates in amortized expected constant time, even
when ultrawords consist of only $w^{1+\epsilon}$ bits for any fixed
$\epsilon>0$.

Furthermore, we have shown how to implement a $w^{\epsilon}$-parallel
dictionary on the UWRAM. The dictionary supports $w$ (or $w^{\epsilon}$)
simultaneous membership queries in worst case constant time and individual
updates in amortized expected constant time.

We wonder if it is possible to achieve constant time with high probability for
all operations in the predecessor problem. The limiting factor for our
solution is the time for updates in the $w^{\epsilon}$-parallel dictionary.
There are dictionaries that achieve constant time with high probability for
all operations in the word RAM model, e.g. [18]. However, such dictionaries
seem to require hash functions that are difficult to evaluate in parallel on
the UWRAM. For instance, [18] uses the modulo operator, for which we cannot
see an obvious way to make a component-wise version.

#### Acknowledgments

We would like to thank the anonymous reviewers of the conference version of
this paper for their comments, which improved the presentation of the paper.
In particular, we would like to thank the reviewer who suggested that it might
be possible to strengthen the result by restricting the model to
$w^{1+\epsilon}$-bit ultrawords.

## References

  * [1] Miklós Ajtai.  A lower bound for finding predecessors in Yao’s cell probe model.  Comb., 8(3):235–247, 1988.  doi:10.1007/BF02126797.
  * [2] Arne Andersson.  Faster deterministic sorting and searching in linear space.  In Proc. 37th FOCS, pages 135–141, 1996.  doi:10.1109/SFCS.1996.548472.
  * [3] Arne Andersson, Torben Hagerup, Stefan Nilsson, and Rajeev Raman.  Sorting in linear time?  J. Comput. Syst. Sci., 57(1):74–93, 1998.  doi:10.1006/jcss.1998.1580.
  * [4] Lars Arge, Paolo Ferragina, Roberto Grossi, and Jeffrey Scott Vitter.  On sorting strings in external memory (extended abstract).  In Proc. 29th STOC, pages 540–548, 1997.  doi:10.1145/258533.258647.
  * [5] Paul Beame and Faith E. Fich.  Optimal bounds for the predecessor problem and related problems.  J. Comput. Syst. Sci., 65(1):38–72, 2002.  doi:10.1006/jcss.2002.1822.
  * [6] Djamal Belazzougui.  Worst-case efficient single and multiple string matching on packed texts in the word-RAM model.  J. Discrete Algorithms, 14:91–106, 2012.  doi:10.1016/j.jda.2011.12.011.
  * [7] Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna.  Monotone minimal perfect hashing: searching a sorted table with $O(1)$ accesses.  In Proc. 20th SODA, pages 785–794, 2009.  URL: http://dl.acm.org/citation.cfm?id=1496770.1496856.
  * [8] Djamal Belazzougui, Paolo Boldi, and Sebastiano Vigna.  Dynamic z-fast tries.  In Proc. 17th SPIRE, pages 159–172, 2010.  doi:10.1007/978-3-642-16321-0\\_15.
  * [9] Michael A. Bender, Martin Farach-Colton, and Bradley C. Kuszmaul.  Cache-oblivious string B-trees.  In Proc. 25th PODS, pages 233–242, 2006.  doi:10.1145/1142351.1142385.
  * [10] Philip Bille, Mikko Berggren Ettienne, Inge Li Gørtz, and Hjalte Wedel Vildhøj.  Time-space trade-offs for Lempel-Ziv compressed indexing.  Theor. Comput. Sci., 713:66–77, 2018.  doi:10.1016/j.tcs.2017.12.021.
  * [11] Philip Bille, Inge Li Gørtz, and Frederik Rye Skjoldjensen.  Deterministic indexing for packed strings.  In Proc. 28th CPM, pages 6:1–6:11, 2017.  doi:10.4230/LIPIcs.CPM.2017.6.
  * [12] Philip Bille, Inge Li Gørtz, and Frederik Rye Skjoldjensen.  Partial sums on the ultra-wide word RAM.  Theor. Comput. Sci., 905:99–105, 2022.  Announced at TAMC 2020.  doi:10.1016/j.tcs.2022.01.002.
  * [13] Philip Bille, Inge Li Gørtz, and Tord Stordalen.  Predecessor on the ultra-wide word RAM.  In Proc. 18th SWAT, pages 18:1–18:15, 2022.  doi:10.4230/LIPIcs.SWAT.2022.18.
  * [14] Philip Bille, Gad M. Landau, Rajeev Raman, Kunihiko Sadakane, Srinivasa Rao Satti, and Oren Weimann.  Random access to grammar-compressed strings and trees.  SIAM J. Comput., 44(3):513–539, 2015.  doi:10.1137/130936889.
  * [15] Andrej Brodnik, Svante Carlsson, Michael L. Fredman, Johan Karlsson, and J. Ian Munro.  Worst case constant time priority queue.  J. Syst. Softw., 78(3):249–256, 2005.  doi:10.1016/j.jss.2004.09.002.
  * [16] Thomas Chen, Ram Raghavan, Jason N. Dale, and Eiji Iwata.  Cell Broadband engine architecture and its first implementation - A performance view.  IBM J. Res. Dev., 51(5):559–572, 2007.  doi:10.1147/rd.515.0559.
  * [17] Intel Corporation.  Intel® advanced vector extensions programming reference.  Intel Corporation, 2011.
  * [18] Martin Dietzfelbinger and Friedhelm Meyer auf der Heide.  A new universal class of hash functions and dynamic hashing in real time.  In Proc. 17th ICALP, pages 6–19, 1990.  doi:10.1007/BFb0032018.
  * [19] Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen.  A reliable randomized algorithm for the closest-pair problem.  J. Algorithms, 25(1):19–51, 1997.  doi:10.1006/jagm.1997.0873.
  * [20] Martin Dietzfelbinger, Anna R. Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert, and Robert Endre Tarjan.  Dynamic perfect hashing: Upper and lower bounds.  SIAM J. Comput., 23(4):738–761, 1994.  doi:10.1137/S0097539791194094.
  * [21] Martin Farach.  Optimal suffix tree construction with large alphabets.  In Proc. 38th FOCS, pages 137–143, 1997.  doi:10.1109/SFCS.1997.646102.
  * [22] Arash Farzan, Alejandro López-Ortiz, Patrick K. Nicholson, and Alejandro Salinger.  Algorithms in the ultra-wide word model.  In Proc. 12th TAMC, pages 335–346, 2015.  doi:10.1007/978-3-319-17142-5\\_29.
  * [23] Michael L. Fredman, János Komlós, and Endre Szemerédi.  Storing a sparse table with $O(1)$ worst case access time.  J. ACM, 31(3):538–544, 1984.  doi:10.1145/828.1884.
  * [24] Michael L. Fredman and Dan E. Willard.  Surpassing the information theoretic bound with fusion trees.  J. Comput. Syst. Sci., 47(3):424–436, 1993.  doi:10.1016/0022-0000(93)90040-4.
  * [25] Torben Hagerup.  Sorting and searching on the word RAM.  In Proc. 15th STACS, pages 366–398, 1998.  doi:10.1007/BFb0028575.
  * [26] Yijie Han.  Deterministic sorting in $O(n\log\log n)$ time and linear space.  J. Algorithms, 50(1):96–105, 2004.  doi:10.1016/j.jalgor.2003.09.001.
  * [27] Kasper Green Larsen and Rasmus Pagh.  I/O-efficient data structures for colored range and prefix reporting.  In Proc. 23rd SODA, pages 583–592, 2012.  doi:10.1137/1.9781611973099.49.
  * [28] R. Leben, M. Miletic, M. S̆pegel, A. Torst, A. Brodnik, and K. Karlsson.  Design of high performance memory module on PC100.  In Proc. Electrotechnical and Computer Science Conference (ERK), pages 75–78, 1999.
  * [29] Peter Bro Miltersen.  Lower bounds for union-split-find related problems on random access machines.  In Proc. 26th STOC, pages 625–634, 1994.  doi:10.1145/195058.195415.
  * [30] Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson.  On data structures and asymmetric communication complexity.  J. Comput. Syst. Sci., 57(1):37–49, 1998.  doi:10.1006/jcss.1998.1577.
  * [31] Gonzalo Navarro and Javiel Rojas-Ledesma.  Predecessor search.  ACM Comput. Surv., 53(5):105:1–105:35, 2020.  doi:10.1145/3409371.
  * [32] Mihai Pătraşcu and Mikkel Thorup.  Time-space trade-offs for predecessor search.  In Proc. 38th STOC, pages 232–240, 2006.  doi:10.1145/1132516.1132551.
  * [33] Mihai Pătraşcu and Mikkel Thorup.  Randomization does not help searching predecessors.  In Proc. 18th SODA, pages 555–564, 2007.  URL: http://dl.acm.org/citation.cfm?id=1283383.1283443.
  * [34] Mihai Pătraşcu and Mikkel Thorup.  Dynamic integer sets with optimal rank, select, and predecessor search.  In Proc. 55th FOCS, pages 166–175, 2014.  doi:10.1109/FOCS.2014.26.
  * [35] James Reinders.  Intel® AVX-512 instructions.  Intel® Corporation, 2013.
  * [36] Pranab Sen and Srinivasan Venkatesh.  Lower bounds for predecessor searching in the cell probe model.  J. Comput. Syst. Sci., 74(3):364–385, 2008.  doi:10.1016/j.jcss.2007.06.016.
  * [37] Nigel Stephens, Stuart Biles, Matthias Boettcher, Jacob Eapen, Mbou Eyole, Giacomo Gabrielli, Matt Horsnell, Grigorios Magklis, Alejandro Martinez, Nathanaël Prémillieu, Alastair Reid, Alejandro Rico, and Paul Walker.  The ARM scalable vector extension.  IEEE Micro, 37(2):26–39, 2017.  doi:10.1109/MM.2017.35.
  * [38] Peter van Emde Boas.  Preserving order in a forest in less than logarithmic time and linear space.  Inform. Process. Lett., 6(3):80–82, 1977.  doi:10.1016/0020-0190(77)90031-X.
  * [39] Peter van Emde Boas, R. Kaas, and E. Zijlstra.  Design and implementation of an efficient priority queue.  Math. Syst. Theory, 10:99–127, 1977.  doi:10.1007/BF01683268.
  * [40] Dan E. Willard.  Log-logarithmic worst-case range queries are possible in space $\Theta(N)$.  Inform. Process. Lett., 17(2):81–84, 1983.  doi:10.1016/0020-0190(83)90075-3.

##  Appendix A Blend and $\boldsymbol{2w}$-bit Multiplication

###  A.1 Supporting Blend

Given the ultrawords $X$, $Y$ and $I$ where each component of $I$ is either
$0$ or $1$, we define the _componentwise blend_ of $X$, $Y$, and $I$ to be the
ultraword $Z$ such that $Z\langle{i}\rangle=X\langle{i}\rangle$ if
$I\langle{i}\rangle=0$ and $Y\langle{i}\rangle$ if $I\langle{i}\rangle=1$. To
compute the blend in constant time we do as follows. Compute
$I^{\prime}=\langle{0,\ldots,0}\rangle-I$; then $I^{\prime}\langle i\rangle$
contains only $1$-bits if $I\langle i\rangle=1$ and only $0$-bits otherwise,
since $0-1\mod 2^{w}=2^{w}-1$. Then the blend of $X$ and $Y$ can be computed
by $(X~{}\&~{}\sim I^{\prime})~{}\mid~{}(Y~{}\&~{}I^{\prime})$.

###  A.2 Supporting $\boldsymbol{2w}$-Bit Componentwise Multiplication

Figure 3: Illustrates step 3 of $2w$-bit multiplication. Each of the products
$X^{+}Y^{+}$, $X^{+}Y^{-}$, $X^{-}Y^{+}$ and $X^{-}Y^{-}$ are left-shifted by
respectively $w$, $w/2$, $w/2$ and $0$ by shifting in zeroes from the right.
Then they are added together using componentwise addition for $2w$-bit
components. Since what we sum up in a $2w$-bit component adds up to the
product of two $w$-bit integers, we only need $2w$ bits to store the result.
Hence the addition will not overflow.

We show how to implement $2w$-bit componentwise multiplication in constant
time. Let $x^{+}$ and $x^{-}$ denote the leftmost and rightmost half of the
binary representation of $x$, respectively. Then, if $x$ is a $2k$-bit integer
we have that $x=x^{+}2^{k}+x^{-}$ where $x^{+}=x/2^{k}$ and $x^{-}=x\mod
2^{k}$. Given $X=\langle 0,x_{w-2},\ldots,0,x_{2},0,x_{0}\rangle$ and
$Y=\langle 0,y_{w-2},\ldots,0,y_{2},0,y_{0}\rangle$, recall that the $2w$-bit
componentwise multiplication of $X$ and $Y$ is the ultraword $Z=\langle
z_{w-2}^{+},z_{w-2}^{-},\ldots,z_{2}^{+},z_{2}^{-},z_{0}^{+},z_{0}^{-}\rangle$
where $z_{i}$ is the $2w$-bit product of $x_{i}$ and $y_{i}$.

The main idea for computing $Z$ is to use the identity

$\displaystyle xy$ $\displaystyle=(x^{+}2^{w/2}+x^{-})(y^{+}2^{w/2}+y^{-})$
(2) $\displaystyle=x^{+}y^{+}2^{w}+(x^{+}y^{-}+x^{-}y^{+})2^{w/2}+x^{-}y^{-}$

where $x$ and $y$ are $w$-bit integers. We simulate this in parallel as
follows.

#### Step 1: Compute $x_{i}^{+}$, $x_{i}^{-}$, $y_{i}^{+}$ and $y_{i}^{-}$ for
all even $i$.

We first construct $X^{+}$ and $X^{-}$ such that $X^{+}\langle
i\rangle=x_{i}^{+}$ and $X^{-}\langle i\rangle=x_{i}^{-}$ for even $i$ and
zero otherwise, and similarly for $Y$. Compute the integer $m=2^{w/2}-1$ which
consists of $w/2$ zeroes followed by $w/2$ ones. Load $m$ into $M$. Compute
$X^{-}=X~{}\&~{}M$ and $X^{+}=(X\gg w/2)~{}\&~{}M$. Compute $Y^{+}$ and
$Y^{-}$ in the same way.

#### Step 2: Compute the products of the $w/2$-bit integers.

Use componentwise multiplication to compute each of the ultrawords
$X^{+}Y^{+},\>X^{+}Y^{-},\>X^{-}Y^{+}\>\text{and}\>X^{-}Y^{-}$. Since each
component of $X^{+}$, $X^{-}$, $Y^{+}$ and $Y^{-}$ is a $(w/2)$-bit integer,
no overflow occurs. The odd components still store $0$.

#### Step 3: Align and add the products.

Align the products by left-shifting them the amount specified in Equation 2,
i.e.

$X^{+}Y^{+}\ll w\qquad X^{+}Y^{-}\ll w/2\qquad X^{-}Y^{+}\ll w/2\qquad
X^{-}Y^{-}\ll 0$

Add the aligned ultrawords using componentwise addition for $2w$-bit
components (see e.g. Hagerup [25]) and return the result. See Figure 3 for an
illustration. Since the sum of the terms added together in a $2w$-bit
component exactly correspond to the multiplication of two $w$-bit integers,
the addition will not overflow.

Bitwise &, left- and right-shifts, componentwise multiplication and
componentwise additions for arbitrary component sizes all run in constant
time. Each step uses a constant number of these operations, so the procedure
runs in constant time.