0
$\begingroup$

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?)

$\endgroup$
8
  • 1
    $\begingroup$ Well...in base $2$ you are just talking about $\frac a2+\frac b2$. So...just divide your numbers by $2$, which (in base $2$) is essentially just a shift of digits. Then add the two numbers, which can be done entry by entry. This only works in base $2$, though...as the division by $2$ is simple there. $\endgroup$
    – lulu
    Jan 27 '16 at 10:14
  • $\begingroup$ In a general base...well, I doubt you can even do the division by $2$ in the way you want. If my base $10$ number ends in $4$, does half of it end in $2$ or $7$? (of course, division by $2$ is just averaging with $0$ so you have to solve this problem). $\endgroup$
    – lulu
    Jan 27 '16 at 10:20
  • $\begingroup$ How is this fundamentally different from first adding and then dividing by two? You’re still adding the two numbers digit by digit, handling carries and dealing with remainders when dividing by two. The only advantage might be when the numbers are large and you don’t have to store as large an intermediate result. $\endgroup$
    – amd
    Jan 27 '16 at 10:30
  • $\begingroup$ I think it's actually faster to just add them up and divide by $2$ instead of doing this digit by digit (especially for base $256$, see @lulu's answer). Also, multiplication is (I think, correct me if I'm wrong) 'heavier' for a computer, that is, it'll take up more time than adding, and since division is multiplication by an inverse, I think it'd also be more efficient to just apply the straightforward method if you're going to program this. $\endgroup$ Jan 27 '16 at 10:35
  • 1
    $\begingroup$ Your "almost working" algorithm is similar to mvw's correct answer, except that your "add 1" step is a less-accurate version of the carry bit $o^{k-1}$. For example, averaging $145$ and $255$, it seems to me your algorithm's result is $100$ rather than $200$, because you only look one place to the right to decide whether to add $1$, but the carry is actually the result of two places' digits. Note that your algorithm works exactly the same if you go left to right; each digit is affected only by the input on the right, not by any results on the right. $\endgroup$
    – David K
    Jan 27 '16 at 15:28
4
$\begingroup$

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$).

$\endgroup$
7
  • $\begingroup$ Thank you for a very thorough answer. I'm no mathematician, so I struggled a bit with the notation, but I think I understand it well enough to implement it :-) $\endgroup$ Jan 27 '16 at 20:44
  • $\begingroup$ @SveinBringsli What notation, the funny brackets? The curly ones mean take the fractional part, thus the non-integer part $\{ 4.3 \} = 0.3$, the $\lfloor x \rfloor$ stand for the floor function, the biggest integer less than $x$ (truncation), e.g. $\lfloor 7.9 \rfloor = 7$. $\bmod$ is the remainder function. $\endgroup$
    – mvw
    Jan 27 '16 at 20:47
  • $\begingroup$ @SveinBringsli what bases do you need? $\endgroup$
    – mvw
    Jan 27 '16 at 20:48
  • $\begingroup$ Base 256, I only used base 10 to try to figure out the algorithm. $\endgroup$ Jan 27 '16 at 21:34
  • $\begingroup$ @SveinBringsli I updated the script. As expected, for even bases it works. The odd case is more complicated. You can try it with an odd base and see it fail. $\endgroup$
    – mvw
    Jan 27 '16 at 23:27

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.