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$
14
  • $\begingroup$ How do you define "carry"? $\endgroup$
    – joro
    Sep 18, 2015 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$ Sep 18, 2015 at 6:44
  • $\begingroup$ So you do addition of words modulo $2^n$ and count carries between words? $\endgroup$
    – joro
    Sep 18, 2015 at 6:46
  • 18
    $\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, 2015 at 7:25
  • 3
    $\begingroup$ @alpoge I agree with Anthony; could you please post your comment as answer? $\endgroup$ Sep 18, 2015 at 7:38

3 Answers 3

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$
2
  • $\begingroup$ That was probably the most unexpected SES I have ever seen... $\endgroup$ Sep 18, 2015 at 14:41
  • $\begingroup$ @PerAlexandersson, it depends on your perspective: a $p$-adic analyst (or I suppose $b$-adic, here) would expect no other SES! $\endgroup$
    – LSpice
    Jan 28, 2020 at 15:16
15
$\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$
1
  • $\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$ Sep 18, 2015 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 and acknowledge you have read our privacy policy.

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