Written by Roy van Rijn (royvanrijn.com) on
Dec 31, 2021 09:01:25
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).
The 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: