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 formats: 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