4
$\begingroup$

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)$?

$\endgroup$
5
  • $\begingroup$ 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). $\endgroup$ Sep 19, 2023 at 20:52
  • $\begingroup$ Question: does the $+_K$ law form a group? I ask because I know that $\oplus$ forms a boolean ring together with $\wedge$ as multiplication. $\endgroup$ Sep 19, 2023 at 20:54
  • $\begingroup$ 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. $\endgroup$ Sep 19, 2023 at 21:00
  • $\begingroup$ 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. $\endgroup$ Sep 19, 2023 at 22:12
  • $\begingroup$ Related: mathoverflow.net/questions/394296/… $\endgroup$
    – Turbo
    Sep 19, 2023 at 22:34

1 Answer 1

9
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.