How "correct" is Knuth's fast addition $(a,b) \mapsto (a \oplus b) \oplus ((a\land b) \ll 1)$?

Question

Donald Knuth suggested a bitwise approximation for addition on the non-negative integers that is very fast on common processors:

$(a,b)\mapsto (a\oplus b) \oplus ((a\land b) \ll 1)$,

where $a,b$ are given in binary format, $\oplus$ denotes bitwise XOR, $\land$ is bitwise AND, and $\ll 1$ is the left shift by one position. We denote this operation by $+_K: \mathbb{N}\times\mathbb{N}\to\mathbb{N}$.

The purpose of

$(a\land b) \ll 1$

is to simulate carry propagation.

If $A\subseteq \mathbb{N}\times\mathbb{N}$, we define its ($2$-dimensional) lower density by $$\mu_2(A) = \liminf_{n\to\infty}\frac{|A\cap(\{0,\ldots,n\}\times \{0,\ldots,n\})|}{(n+1)^2}.$$

Let $A = \{(a,b)\in\mathbb{N}\times\mathbb{N}: a+_K b = a+b\}$.

What is the value of $\mu_2(A)$?

Answer 1

Note that we have $$a + b = (a \oplus b) + ((a \land b) \ll 1). \tag{1}$$ So asking whether $a + b = a +_K b$ is asking when $x \oplus y = x + y$ where $x = a \oplus b$ and $y = ((a\land b) \ll 1)$. On the other hand by the same expansion as (1), we have $x \oplus y = x + y$ if and only if $x \land y = 0$.

Let us draw $a, b$ uniformly at random from the set of $n$ bit non-negative integers. This is the same as picking each bit of $a$ and $b$ independently at random (with uniform probability over $1$ and $0$).

We have $\Pr(x\land y \not=0) = \Pr(\exists i\,\, x_i \land y_i = 1)$, and expanding $x_i, y_i$ this is equal to $\Pr(\exists i\,\, (a_i \oplus b_i) \land a_{i-1} \land b_{i-1}=1)$. We can now lower bound this probability, by $\Pr(x \land y \not=0) \geq \Pr(\exists i \textrm{ even},\, (a_i \oplus b_i) \land a_{i-1} \land b_{i-1} = 1) = 1 - (7/8)^{n/2}$ since those events are independent for different even $i$.

To provide a more precise estimate, let us consider a three-state Markov chain which is processing bits $a_{i}, b_{i}$ in the order of decreasing $i$, and keeps as its state $a_{i} \oplus b_{i}$.

I.e. we have three states $0, 1, F$, and the transition matrix is given by $$A = \left(\begin{matrix} 1/2 & 1/2 & 0 \\ 1/4 & 1/2 & 1/4 \\ 0 & 0 & 1 \end{matrix}\right)$$ That is, if we are in the $F$ state, we stay in the $F$ state, if we are in the $0$ state we move to state $0$ or $1$ with probability $1/2$, if we are in the $1$ state we have probability $1/4$ of moving to the $1$ state and $1/4$ of moving to the $F$ state.

We are starting in the state $0$, and are interested in what is the probability of being in the state $F$ after $n$ steps. That quantity is given by $e_0^T A^n e_F$.

Using some standard tool (I used Wolfram alpha), we can diagonalize $A = S \Sigma S^{-1}$, where $$S = \left(\begin{matrix} 1 & -\sqrt{2} & \sqrt{2} \\ 1 & 1 & 1 \\ 1 & 0 & 0 \end{matrix}\right)$$ and $$\Sigma = \left(\begin{matrix} 1 & 0 & 0 \\ 0 & \frac{1}{4}(2 - \sqrt{2}) & 0 \\ 0 & 0 & \frac{1}{4} (2 + \sqrt{2}) \end{matrix}\right),$$ moreover $$S^{-1}= \left(\begin{matrix} 0 & 0 & 1 \\ \frac{-1}{2\sqrt{2}} & \frac{1}{2} & \frac{1}{4} (\sqrt{2} - 2) \\ \frac{1}{2\sqrt{2}} & \frac{1}{2} & \frac{1}{4}(-2 - \sqrt{2})\end{matrix}\right).$$

Hence $e_0^T A^n e_F = (e_0^T S) \Sigma^n (S^{-1} e_F) = \alpha_1 \sigma_1^n + \alpha_2 \sigma_2^n + \alpha_3 \sigma_3^n$ where $\alpha = (1, \frac{1}{4}(2 \sqrt{2} - 2), -\frac{1}{4}(2 \sqrt{2} + 2))$ and $\sigma = (1,\frac{1}{4}(2 - \sqrt{2}), \frac{1}{4} (2 + \sqrt{2}) )$.

I.e. the failure probability looks a bit like $1 + 0.2 \cdot 0.15^n- 1.2 \cdot 0.85^n $.