10
$\begingroup$

Is it true that the number of carries, when calculating the sum of a finite set of finite positive integers, is constant (i.e. independent of their permutation and the order in which the additions are carried out)? Carries are computed in base 2, so that 1+3 is $01_2+11_2=100_2$, which involves 2 carries: the least significant digits resulted in a carry, which then causes a second carry of the 2's digit.

In case the assumption is wrong, I would also like some ideas for determining the optimal permutation and order of additions.

$\endgroup$
  • $\begingroup$ How do you define "carry"? $\endgroup$ – joro Sep 18 '15 at 6:27
  • $\begingroup$ @joro I thought that it should be clear, what a carry or carry-bit is in the context of addition. An explanation can be found here: en.wikipedia.org/wiki/Carry_flag $\endgroup$ – Manfred Weis Sep 18 '15 at 6:44
  • $\begingroup$ So you do addition of words modulo $2^n$ and count carries between words? $\endgroup$ – joro Sep 18 '15 at 6:46
  • 17
    $\begingroup$ The number of carries when adding $a$ and $b$ in base $p$ is the power of $p$ that divides ${a+b \choose a}$. Thus the total number of carries in evaluating e.g. $(a+b)+c$ is the power of $p$ dividing ${a+b \choose a}{a+b+c \choose c} = \frac{(a+b+c)!}{a!b!c!}$, which is symmetric in $a,b,c$. Hope I haven't made a mistake! $\endgroup$ – alpoge Sep 18 '15 at 7:25
  • 3
    $\begingroup$ @alpoge I agree with Anthony; could you please post your comment as answer? $\endgroup$ – Manfred Weis Sep 18 '15 at 7:38
10
$\begingroup$

In base $b$, let $G_n$ be the set of $n$-digit integers, thought of as the integers mod $b^n$. Then we have an exact sequence $$0\rightarrow G_1\rightarrow G_n\rightarrow G_{n-1}\rightarrow 0$$

For $n-1$ digit numbers, the leftmost carry digit is the two-cocycle associated to this group extension and therefore satisfies the cocycle condition $$c(x,y)+c(x+y,z)=c(y,z)+c(x,y+z)$$ In other words, the sum of the leftmost carry digits does not depend on the order of the summands.

After reducing mod $b^k$, the same argument holds for any other carry digit.

$\endgroup$
  • $\begingroup$ That was probably the most unexpected SES I have ever seen... $\endgroup$ – Per Alexandersson Sep 18 '15 at 14:41
12
$\begingroup$

For any base $b$, if we add $a$ and $c$ with $k$ carries, then $S_b(a+c)=S_b(a)+S_b(c)-(b-1)k$, where $S_b$ denotes the sum of digits. Since the resulting sum is independent of the order of addition, the total number of carries is independent as well.

$\endgroup$
  • $\begingroup$ I've edited so that $b$ doesn't mean two different things. But yes, isn't it really this simple, or am I missing something? $\endgroup$ – Jeremy Rickard Sep 18 '15 at 15:07
3
$\begingroup$

Alpoge's comment gives a beautiful answer for prime bases. Of course this answers the original question for binary addition.

I can't see how to extend it to composite bases. For instance in base $6$, the addition $2+7 = 9 = 13_6$ has one carry, but the highest power of $6$ dividing $\binom{9}{2} = 36$ is $2$.

Here is an alternative argument. Work in base $d$. If $x = x_r d^r + \cdots + x_jd^j + \cdots x_1 d + x_0$ then say $x_j$ is in position $j$. Suppose we are adding $a^{(1)}, \ldots, a^{(n)}$ and that there is a carry of $r$ into position $j$. Consider the sum $r + a^{(1)}_j + \cdots + a^{(n)}_j$, computed in $\mathbb{N}_0$. We get a carry every time a partial sum $r + a^{(1)} + \cdots + a^{(m)}_j$ is $< ds$ (for some $s$) and the next addition makes it $\ge ds$ (but necessarily $< (d+1)s$). Since addition in $\mathbb{N}_0$ is commutative and associative, the number of such 'crossings' does not depend on the order of the numbers. Neither does the carry going into position $j+1$. So by induction, the total number of carries is independent of the order of the numbers.

$\endgroup$

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.