Divide by three using shift and add
Today I stumbled across this excellent short video bij Mathologer:
This simple proof shows that 1/3 is the same as: 1/4 + 1/4^2 + 1/4^3 + 1/4^N…
As a programmer I wanted to try and program this.
Dividing by multiples of two (like 4^3) is extremely easy in binary, we just shift a number to the right. So if you have some integer X and we want to divide by 4, we do X >> 2, if we want to divide by 4^2 we shift X >> 4 etc.
This means we can just add these fractions together and approximate the result, just by dividing (shifting) up to >> 30 for an integer (which is 32-bit).
int bignr = 612644632;
// Approximate Using: 1/3 = 1/4 + 1/4^2 + 1/4^3 + etc
int divless = (bignr >> 2) + (bignr >> 4) + (bignr >> 6) + (bignr >> 8) +
(bignr >> 10) + (bignr >> 12) + (bignr >> 14) + (bignr >> 16) +
(bignr >> 18) + (bignr >> 20) + (bignr >> 22) + (bignr >> 24) +
(bignr >> 26) + (bignr >> 28) + (bignr >> 30);
System.out.println(bignr + " / 3 = " + (bignr / 3));
System.out.println(bignr + " + magic = " + divless);
// 612644632 / 3 = 204214877
// 612644632 + magic = 204214872 <- close, a bit too lowThe accuracy isn’t great… but it’s pretty close. We’re always a bit below the actual sum because for each part we add, we lose a bit of information which we’re shifted away. To counter this we could first add things and shift the final result, making the accuracy a bit better:
int bignr = 612644632;
// Approximate Using: 1/3 = 1/4 + 1/4^2 + 1/4^3 + etc
int divless = (bignr + (bignr >> 2) + (bignr >> 4) + (bignr >> 6) + (bignr >> 8) +
(bignr >> 10) + (bignr >> 12) + (bignr >> 14) + (bignr >> 16) +
(bignr >> 18) + (bignr >> 20) + (bignr >> 22) + (bignr >> 24) +
(bignr >> 26) + (bignr >> 28) + (bignr >> 30)) >> 2;
System.out.println(bignr + " / 3 = " + (bignr / 3));
System.out.println(bignr + " + magic = " + divless);
// 612644632 / 3 = 204214877
// 612644632 + magic = 204214876 <- off by one hahaProbably a useless trick, but fun nonetheless.