Two's complement unexpectedly shows up in infinite series
=========================================================
[Published 2022-10-20, Updated 2023-01-25]
I recently discovered that you can divide by a number x by calculating
an infinite series that divides by x+1. Here is an example:
7/5 = 7/(6) + 7/(6*6) + 7/(6*6*6) + ...
This may be well known but I only knew about the special case of:
x = x/2 + x/4 + x/8 + ...
until recently.
On a computer it may be especially interesting to divide by a power of
2 minus 1 since you can then divide by e.g. 8 instead of the more
difficult number 7. All you need to do is to bit shift:
500/7 = (500 >> 3) + (500 >> 6) + (500 >> 9) + ...
which is equivalent to
500/7 = 500/8 + 500/8/8 + 500/8/8/8 + ...
There is just a slight problem; this doesn't give you the whole result
when using integers because you miss the fractional parts. Here is a
more complete example:
// Calculates `dividend / ((1 << divisor_exponent) - 1)`
void divide(int dividend, int divisor_exponent, int *res, int *rem) {
int divisor = (1 << divisor_exponent) - 1;
*res = 0;
*rem = 0;
while (dividend) {
*rem += dividend & divisor;
dividend >>= divisor_exponent;
*res += dividend;
}
while (*rem >= divisor) {
*res += 1;
*rem -= divisor;
}
}
This function really gives you the exact result, integer part in res
and remainder in rem. Please try it!
- - -
After writing this function I got a weird idea: what if I make the
exponent negative? Let's see what should happen:
1/7 = 1/8 + 1/64 + 1/512 + ... (exponent = 3)
1/3 = 1/4 + 1/16 + 1/64 + ... (exponent = 2)
1/1 = 1/2 + 1/4 + 1/8 + ... (exponent = 1)
So far so good. The next exponent is 0. 2^0-1 = 0. That means we
have to divide by 0.
1/0 = 1/1 + 1/1 + 1/1 + ... (exponent = 0)
That gives us infinity, which I guess makes sense. Now we're getting
into negative numbers. This is where it gets interesting.
1/-0.5 = 1/0.5 + 1/0.25 + 1/0.125 + ... (exponent = -1)
But wait, that can't be true! We can't add positive numbers to get a
negative number, or more precisely -2. Anyway, let's try it with a
computer. Right-shifting -1 steps should mean that we left-shift one
step. Here is a function that can do that:
int divide_inv(int dividend, int neg_exp) {
int res = 0;
while (dividend <<= neg_exp) {
res += dividend;
}
return res;
}
In order to calculate 1/-0.5 we call divide_inv(1, 1) and the function
returns -2. It totally works.
Wait, no, that must have been just luck. Computers use two's
complement but pure math can't know about that! Let's try some other
random number like 469/(2^-3 - 1) which equals -536.
divide_inv(469, 3) returns -536. It totally works.
I don't know why it works. Using pure math doesn't work since we were
just adding positive numbers and could never get a negative number but
when using a two's complement signed integer, the math just seems to
fall into place and these weird impossible results become true.
There is just one limitation; it doesn't work when the result would be
non-integer. Example:
1 / (2^-2 - 1) = -1.33333333333333333333
but divide_inv(1, 2) returns 1431655764.
Spooky.