How can I average two integers digit by digit?

Question

I would like to take two integers of similar size (about the same number of digits) and average them, without having to first add them, and then divide the result by two.

Let's say I have the numbers 7284 and 389. The sum is 7673, and this divided by 2 is 3836 (rounding down). Is there a way to start at one end, for example the ones (3 and 6), and calculate digit by digit?

I have tried for a while, and found algorithms that "almost" work (they work for many integers, but then I find examples where they don't work, proving that the algorithm is no good).

An example of an algorithm that almost worked:

Start at the first (least significant) digit. For each pair of digits, take the sum of the digits. If the next pair of digits (the more significant) sums to an odd number, add 10 to the sum. If the previous pair of digits (the less significant) sums to 10 or more, add the sum of that pair divided by 10, rounding down, to the sum. Divide the sum by 2, round down if odd. Take the remainder of the sum divided by 10 (sum mod 10). This is the correct digit.

Example:

Find the average of 257 and 798.

First digit:
  7+8 = 15
  The next pair (5 and 9) is not odd
  Divide 15 by 2 to get the correct digit, which is 7

Second digit:
  5+9=14
  The next pair (2 and 7) is odd, so add 10 (14+10=24)
  The previous pair (7 and 8) is over 10, so add 1 (24+1=25)
  Divide 25 by 2 to get 12. The next digit is 12 mod 10 = 2

Third digit:
  2+7 = 9
  The previous pair (5 and 9) sums to over 10, so add 1 (9+1=10)
  Divide by 2 to get correct digit: 10 / 2 = 5

We now have the digits 5,2 and 7, which is indeed correct: (257+798)/2 = 527.

So my question is: Does there exist an algorithm I can use to take two random multidigit integers and averaging them digit by digit? (I also need to do this in other bases (base 256 typically), but if I can get an algorithm that works for base 10 it should work in other bases to, shouldn't it?)

Answer 1

Does there exist an algorithm I can use to take two random multidigit integers and averaging them digit by digit?

If you have the numbers $a$, $b$ with the base $10$ representations \begin{align} a &= (d_{m-1} d_{m-2} \dotsm d_0)_{10} = \sum_{k=0}^{m-1} d_k \, 10^k \\ b &= (D_{M-1} D_{M-2} \dotsm D_0)_{10} = \sum_{k=0}^{M-1} D_k \, 10^k \end{align} assuming $m \le M$, the average $c$ is $$ c = \frac{a + b}{2} = \sum_{k=0}^{m-1} \frac{d_k + D_k}{2} \, 10^k + \sum_{k=m}^{M-1} D_k \, 10^k $$ where the second sum is for the case that $m < M$. For the coefficients of the first sum we have $$ 0 \le \frac{d_k + D_k}{2} \le 9 $$ with the complication that fractional parts can occur
$$ \frac{d_k + D_k}{2} = \left\lfloor \frac{d_k + D_k}{2} \right\rfloor + \left\{ \frac{d_k + D_k}{2} \right\} = \left\lfloor \frac{d_k + D_k}{2} \right\rfloor + \frac{1}{2} r_k $$ where $$ r_k = (d_k + D_k) \bmod 2 \in \{ 0, 1 \} $$ This fractional part influences the lower order digits. One order down we have $$ \left\lfloor \frac{d_{k-1} + D_{k-1}}{2} \right\rfloor + 5 r_k \le 13 $$ This can yield an overflow which goes the other direction, influencing the higher order digits.

We end up with $$ \newcommand{\D}{\mathfrak{D}} c = (\D_M \D_{M-1} \dotsm \D_0 . \D_{-1})_{10} $$ with the last two digits $$ \D_{-1} = 5 r_0 $$ and \begin{align} x_0 &= 5 r_1 + \left\lfloor \frac{d_0 + D_0}{2} \right\rfloor \le 14 \\ \D_0 &= x_0 \bmod 10 \\ o_0 &= \left\lfloor x_0 / 10 \right\rfloor \in \{ 0, 1 \} \end{align} The overflow $o_0$ is only non-zero, if the fractional contribution $r_1$ is non-zero. The next digit is \begin{align} x_1 &= 5 r_2 + \left\lfloor \frac{d_1 + D_1}{2} \right\rfloor + o_0 \le 14 \\ \D_1 &= x_1 \bmod 10 \\ o_1 &= \left\lfloor x_1 / 10 \right\rfloor \in \{ 0, 1 \} \end{align} For the other digits $k \in \{ 1, \dotsc, M \}$ we have \begin{align} x_k &= 5 r_{k+1} + \left\lfloor \frac{d_k + D_k}{2} \right\rfloor + o_{k-1} \le 14 \\ \D_k &= x_k \bmod 10 \\ o_k &= \left\lfloor x_k / 10 \right\rfloor \in \{ 0, 1 \} \end{align} where we assume $d_k = 0$ for $k \ge m$, $D_M = 0$, $r_{M+1} = 0$.

So if I made no error, the answer is that one can calculate the individual digits, from right to left as above.

I also need to do this in other bases (base 256 typically)

This changes how to account for the fractional contribution $r_k / 2$. It would show up as $(B/2) r_k$ one order lower, if $B$ is an even number. If $B$ is odd, it would need to get spread over more lower order terms.

So for even $B$ just replace the $10$ by $B$ and $5$ by $B / 2$ in the procedure above.

Update: It seems to work. This is what I told my friend Ruby. And this is what she responded.

Update: I upgraded the script to handle arbitrary even bases ($B \ge 2$).