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