4
$\begingroup$

Motivation. In their paper about the cryptographic scheme NORX, the authors use a fast approximation of + by bitwise operations (taking fewer CPU cycles than proper addition) using the formula $$a+b \; \approx \; a \oplus b \oplus ((a \land b) \ll 1)$$ where $\oplus$ is bitwise XOR and $\land$ is bitwise AND, and $\ll$ is left-shift by 1 position. (The purpose of $((a \land b) \ll 1)$ is to simulate the "carry-bit" operation.) I am wondering "how well" this approximation works in terms of the expected value of the Hamming distance between $a+b$ and $a \oplus b \oplus ((a \land b) \ll 1).$

So let's make this more precise.

Formal version. Let $\{0,1\}^\mathbb{N}$ denote the collection of functions $f:\mathbb{N}\to \{0,1\}$ and let $$\{0,1\}^* = \{x \in \{0,1\}^\mathbb{N}: \exists N\in\mathbb{N}(\forall k\in\mathbb{N}(k\geq N\implies x(k)=0))\}.$$ Every member of $\{0,1\}^*$ can be viewed as the binary expansion of a natural number; this is a unique correspondence. This correspondence gives rise to the addition $+:\{0,1\}^* \times \{0,1\}^* \to \{0,1\}^*$. Denote by $\ll 1$ the left-shift by one position, i.e. $$\ll 1 : x \in \{0,1\}^* \mapsto x'\in \{0,1\}^*$$ where $x'(0) = 0$ and $x'(n+1) = x(n)$ for all $n\in \mathbb{N}$. We usually write $x \ll 1$ instead of $\ll 1(x)$.

For $x\in\{0,1\}^*$ we set $\text{len}(x) = \max\{k\in\mathbb{N}:x(k) = 1\}$.

For $a,b\in\mathbb{N}$ we denote by $\text{diff}(a,b)$ the Hamming distance between $a+b$ and $a \oplus b \oplus ((a \land b) \ll 1)$.

For a positive integer $n\in\mathbb{N}$ we let $$A_n = \frac{1}{2^{2n}} \sum\{\text{diff}(a,b): \text{len}(a), \text{len}(b) \leq n\}$$ be the average Hamming distance that $a+b$ has from $a\oplus b \oplus ((a \land b) \ll 1)$ when we limit the length of $a,b$ to at most $n$.

An experiment seems to imply that $A_n \sim \log(n)$ as $n$ grows large.

Question. Does $(A_n / \log(n))_{n\in\mathbb{N}}$ converge to a finite value?

$\endgroup$
2
  • 1
    $\begingroup$ Note that as $a+ b = (a\oplus b) \stackrel{(1)}{+} ((a\land b)\ll 1)$, the approximation can be seen to be an equality provided that $a,b\in\{0,1\}^n$ are such that one only needs to "propagate carries" once (meaning the operation marked (1) produces no carries). It seems plausible that counting the number of $(a, b)$ such that the operation marked (1) produces no carries is an exercise in simple combinatorics, but I don't have time to think about it right now. $\endgroup$
    – Mark
    Jun 3 at 8:58
  • 1
    $\begingroup$ I'm ready to bet the house on yes, and something on that limit being a simple fraction [update: when we take the log to base 2, of course... or how to loose a bet with self by insufficient attention to detail]. $\endgroup$
    – fgrieu
    Jun 3 at 11:31
4
$\begingroup$

The NORX operation $a \oplus b \oplus (a \land b) \ll 1$, a simplification of the well-known identity $a\oplus b + (a \land b) \ll 1$ is essentially a parallel round of carry propagation.

The question here poses the question of what the average weight of $(a+b) \oplus (a \oplus b) \oplus (a \land b) \ll 1$. But this is directly related to computing how many more rounds of carry propagation would be necessary if one were to perform the addition as follows: $$ a, b = (a \oplus b, (a\land b) \ll 1) $$ until $b = 0$. This addition features in von Neumann's report on the EDVAC (page 17), and has also been analyzed by Knuth, Pippenger, and others.

The answer is that this number is the number of carry chains longer than $1$. The probability that a carry chain of length $l$ occurs is given by the event that the first pair of bits in the sequence is $(1,1)$, and the subsequent pairs are all either $(0, 1)$ or $(1, 0)$. This translates to a probability of $1/4 \times (1/2)^{l-1} = 2^{-(l+1)}$. Given there are $n - l + 1$ possible blocks of $l$ bits, the expected number of carry chains of length $l$ is $\frac{n-l+1}{2^{l+1}}$.

For the sake of Hamming weight, each carry chain at step $i$ contributes one bit to the total sum. Thus the total average weight will be the expected number of carry chains of length $2, 3, \dots, n$.

Now we have everything we need to obtain the solution. We consider all carry chain sizes except the ones of length $0$ and $1$, which are handled by the NORX operation. This gives us

$$ \sum_{i=2}^n \frac{n-i+1}{2^{i+1}} = \sum_{i=0}^n \frac{n-i+1}{2^{i+1}} - \sum_{i=0}^2 \frac{n-i+1}{2^{i+1}} = \frac{n-2}{4} + \frac{1}{2^{n+1}}\,. $$ Because in modular addition the most significant bit does not propagate, we consider $n-1$ instead; in this case it becomes $\frac{n-3}{4} + \frac{1}{2^n}$.

$\endgroup$
1
  • $\begingroup$ Thanks to both poncho and Samuel for your answers; I am a bit unhappy that I cannot accept both answers...! $\endgroup$ Jun 4 at 7:02
2
$\begingroup$

If we actually run the search on various word sizes, we see that $A_n$ converges quite rapidly to either $(n-2)/4$ or $(n-3)/4$ (the former if the operations are taken on integers, the latter if the operation it taken modulo $2^n$).

Here are the values I got:

n=1: An(no modulo)=0.000000 An(modulo)=0.000000
n=2: An(no modulo)=0.125000 An(modulo)=0.000000
n=3: An(no modulo)=0.312500 An(modulo)=0.125000
n=4: An(no modulo)=0.531250 An(modulo)=0.312500
n=5: An(no modulo)=0.765625 An(modulo)=0.531250
n=6: An(no modulo)=1.007812 An(modulo)=0.765625
n=7: An(no modulo)=1.253906 An(modulo)=1.007812
n=8: An(no modulo)=1.501953 An(modulo)=1.253906
n=9: An(no modulo)=1.750977 An(modulo)=1.501953
n=10: An(no modulo)=2.000488 An(modulo)=1.750977
n=11: An(no modulo)=2.250244 An(modulo)=2.000488
n=12: An(no modulo)=2.500122 An(modulo)=2.250244
n=13: An(no modulo)=2.750061 An(modulo)=2.500122
n=14: An(no modulo)=3.000031 An(modulo)=2.750061
n=15: An(no modulo)=3.250015 An(modulo)=3.000031
n=16: An(no modulo)=3.500008 An(modulo)=3.250015
$\endgroup$
1
  • 1
    $\begingroup$ Addition: the answer is not 42. Poncho shows it's 1/4 when we take the log to base 2. $\endgroup$
    – fgrieu
    Jun 3 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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