Who are the geniuses behind Unity 3D? Seems, with my limited ken, an incredible piece of work.
Some people, somewhere, decided, wouldn't it be nice to do X, and wrote a proposal for it and got money and hired people and did it! Supermen.
I recently worked through an interesting algorithm for generating the binary digits of a square root. The arithmetic itself is remarkably simple. What makes the algorithm confusing is that several perfectly reasonable mental models turn out to be wrong.
Before looking at the calculation, it is worth identifying the traps.
Three misconceptions that can cause trouble
The first misconception is that an algorithm for finding sqrt(n) ought to terminate once the answer has been found. If n is 4, for example, we already know that:
√4 = 2
So one naturally expects the algorithm to arrive at 2 and stop.
But that is not what this algorithm does. It is a digit-generating algorithm. Each iteration generates another binary digit. It can therefore continue indefinitely, even when the number being represented has an exact finite binary representation.
The second misconception is to regard the variable s itself as the current numerical approximation to the square root. It is not. s is an integer whose binary digits encode the approximation. Its magnitude therefore grows rapidly even though the number represented by those digits is converging to a perfectly ordinary value.
The third misconception is particularly subtle: just as decimal numbers have identities such as
0.999999... = 1,
binary numbers have analogous identities:
1.111111...2 = 10.000000...2 = 2.
That fact turns out to explain exactly what happens when the algorithm is started with n = 4.
The algorithm
The procedure keeps two numbers, r and s. Initially:
r = n, s = 0
At every step, compare r and s.
If r > s, replace them by:
r → 4(r − s − 1)
s → 2(s + 2)
s → 2(s + 2)
Otherwise use:
r → 4r
s → 2s
s → 2s
One new binary digit of the square root is generated at every iteration.
Trying n = 4 in Excel
Suppose columns F and G contain r and s. Start with:
| Step | r | s |
|---|---|---|
| 1 | 4 | 0 |
The Excel formula for the next value of r is:
=IF(F4>G4,4*(F4-G4-1),4*F4)
and the formula for the next value of s is:
=IF(F4>G4,2*(G4+2),2*G4)
Copying the formulas downward produces:
| Step | r | s |
|---|---|---|
| 1 | 4 | 0 |
| 2 | 12 | 4 |
| 3 | 28 | 12 |
| 4 | 60 | 28 |
| 5 | 124 | 60 |
| 6 | 252 | 124 |
| 7 | 508 | 252 |
| 8 | 1020 | 508 |
| 9 | 2044 | 1020 |
| 10 | 4092 | 2044 |
At first sight this looks completely wrong. Instead of settling down to 2, both numbers are exploding.
But the growing size of s is a distraction. We need to look at its binary representation.
Look at s in binary
Converting s to base 2 gives:
| s | s in binary |
|---|---|
| 0 | 0 |
| 4 | 100 |
| 12 | 1100 |
| 28 | 11100 |
| 60 | 111100 |
| 124 | 1111100 |
| 252 | 11111100 |
| 508 | 111111100 |
Now the pattern is obvious.
The significant digits being generated are:
1
11
111
1111
11111
111111
...
Interpreting the binary point as lying after the first digit gives:
1.
1.1
1.11
1.111
1.1111
1.11111
...
These are not integers. They are successive binary fractions.
What do those binary numbers mean?
In decimal:
| Binary approximation | Decimal value |
|---|---|
| 1.02 | 1 |
| 1.12 | 1.5 |
| 1.112 | 1.75 |
| 1.1112 | 1.875 |
| 1.11112 | 1.9375 |
| 1.111112 | 1.96875 |
The sequence approaches 2:
1, 1.5, 1.75, 1.875, 1.9375, 1.96875, ... → 2
So the algorithm has not failed at all.
It is generating:
1.111111111...2
and this infinite binary fraction is exactly equal to:
10.000000000...2 = 2.
The binary analogue of 0.999...
This is the same phenomenon as the familiar decimal identity:
0.999999... = 1.
To see why, expand the binary number:
1.111111...2
=
1 +
1/2 +
1/4 +
1/8 +
1/16 + ...
Everything after the binary point is a geometric series:
1/2 + 1/4 + 1/8 + ... = 1.
Therefore:
1.111111...2 = 1 + 1 = 2.
The important lesson: a number that has a terminating representation in some base also has a second representation ending in an infinite sequence of the largest possible digit. In binary, that digit is 1.
Making the result visible in Excel
Suppose column H contains the binary version of s:
0
100
1100
11100
111100
1111100
...
For example, this can be generated from s with an Excel binary-conversion formula appropriate to the values involved.
We now want a final column that interprets those bits as a binary fraction with the point immediately after the first digit.
If H4 contains the binary digits, use:
=DECIMAL(H4,2)/2^(LEN(H4)-1)
For example, if:
H4 = 1100
then:
11002 = 12
There are four binary digits, so divide by:
24−1 = 8.
Hence:
12 / 8 = 1.5.
This is exactly:
1.1002 = 1.5.
The resulting Excel table
| s | s2 | Interpreted value |
|---|---|---|
| 4 | 100 | 1 |
| 12 | 1100 | 1.5 |
| 28 | 11100 | 1.75 |
| 60 | 111100 | 1.875 |
| 124 | 1111100 | 1.9375 |
| 252 | 11111100 | 1.96875 |
| 508 | 111111100 | 1.984375 |
| 1020 | 1111111100 | 1.9921875 |
Now the convergence is visually obvious.
Showing the binary point explicitly
It can also be helpful to have Excel produce a textual version with the binary point inserted.
If the binary representation is in H4, use:
=LEFT(H4,1)&"."&MID(H4,2,LEN(H4)-1)
This turns:
100
1100
11100
111100
into:
1.00
1.100
1.1100
1.11100
The extra trailing zeros are part of the way s is stored and updated; they do not change the represented value.
An even simpler way to watch the generated digits
There is another useful observation hidden in the recurrence.
The branch chosen at each iteration directly tells us the next binary digit:
- If
r > s, the next digit is 1. - Otherwise, the next digit is 0.
So an Excel column containing:
=IF(F4>G4,1,0)
lets us watch the digit stream directly.
For n = 4, the comparison keeps producing:
1 1 1 1 1 1 1 1 ...
which corresponds to:
1.111111...2 = 2.
For a non-square such as √2, the output instead begins with a nonrepeating sequence of bits corresponding to its binary expansion.
Why n = 4 is a slightly awkward example
Using 4 as the starting value is mathematically valid, but it happens to land exactly on a boundary where the answer has two binary representations:
10.000000...2
and
1.111111...2.
That makes it a particularly good example for understanding positional notation, but perhaps not the easiest first example for understanding the square-root algorithm itself.
A value such as 2 makes the digit-generation behavior more apparent because √2 has an infinite, nonrepeating binary expansion.
The deeper lesson
The interesting part of this exercise is not really Excel, and it is not even square roots. It is the danger of confusing an algorithm's internal state with the mathematical object that state represents.
The variable s becomes:
4
12
28
60
124
252
508
...
and if we treat those values as approximations to √4, the algorithm looks absurd.
But those integers are really containers for an ever-growing string of binary digits. Once we interpret them correctly, the same computation becomes:
1,
1.5,
1.75,
1.875,
1.9375,
1.96875,
...
and suddenly the design of the algorithm makes sense.
A useful general rule when studying unfamiliar algorithms:
before deciding that an intermediate variable is behaving incorrectly, ask what that variable is intended to represent. Its numerical value may be much less important than its structure, digits, bits, indices, or invariants.
In this case, the apparently runaway calculation was doing exactly what it was supposed to do: generating one more binary digit of the square root at every step.