Cryptology ePrint Archive: Report 2010/072

Approximating Addition by XOR: how to go all the way

Didier Alqui\'e

Abstract: In this paper, we study approximation of addition by XOR, taking P. Sarkar's publication~\cite{bib:sarkar} as the reference work and starting point. In this work, among various results, it was claimed that explicit formulas seemed difficult to obtain when the number $n$ of summands is more than $5$. In the first part of our work, we show a systematic way to find explicit formulas: the complexity to compute them is $O(n^3)$, which allows large values of $n$. We present some numerical computation and point out a - conjectural - observation on the coefficients.

In the second part, we study a generalization of P. Sarkar's work to $q$-ary addition, instead of binary. We show that the mechanics of the addition is essentially the same as in the binary case. In particular, sequence of carries behaves very similarly: it is a Markov chain whose transition matrix can be computed. Running some experiments on small values of $n$ leads us to a conjecture, the first part of which is intuitive and the second part of which reveals an amazing coincidence (and is probably not!).

Finally, in a section titled ``very last news'', we refer to a paper published by Holte in 1997, that was brought to us after our first post and that we had missed before. It happens that this paper studies the topic and solves a major part of our open problems. Henceforth, the present post is an updated version of our previous ``Approximating Addition by XOR: how to go (a little) further than P. Sarkar'', taking into account this previous Holte's reference.

Category / Keywords: foundations / xor addition arithmetic Markov chain Bernoulli Eulerian numbers

Publication Info: Presented at C2 2009 (NB: French-speaking conference)

Date: received 10 Feb 2010, last revised 24 Jun 2010

Contact author: didier alquie at laposte net

Available format(s): PDF | BibTeX Citation

Note: We had missed some crucial publication that had already dealt with the topic. It was brought to us after our first post.

Version: 20100624:082258 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]