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

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 $$\ldots \oplus ((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)$$?

• So I'm assuming your integers are arbitrary precision and bitwise operations past $a$'s most significant bit are fed zero bits (I.e. every number is zero-padded so that we can even talk about bitwise (componentwise) operations). Sep 19, 2023 at 20:52
• Question: does the $+_K$ law form a group? I ask because I know that $\oplus$ forms a boolean ring together with $\wedge$ as multiplication. Sep 19, 2023 at 20:54
• Also, why don't you measure density in the bitwise space of numbers $a = (1,0,1,1,\dots)$. As we know that every combination of $0$'s and $1$'s will be occupied by a natural. Sep 19, 2023 at 21:00
• I think this can be tackled as a Markov process with five states: one for rejected pairs and one for each combination of true and approximate carry digit, processing from least significant. Sep 19, 2023 at 22:12
• Sep 19, 2023 at 22:34

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$$.