Season 6 Episode 4

On this episode, we look at some techniques for evaluating square roots quickly.

Further Reading

Newton-Raphson iteration

There’s a Brilliant page on the method we looked at on the livestream. There are some A-level-like problems to download here from MathsGenie.

If you want to see how this is taught at Oxford, see the Computer Science course page or the Maths course page.

Q_RSQRT

There's a really excellent YouTube video explaining the Fast Inverse Square Root algorithm from Quake here.

This skips a little bit of the mathematical detail; see this paper for more of the detail.

If you like this, then you might also like the CORDIC algorithm for some insight into how a computer might quickly calculate trigonometric functions.

What about -1?

We looked at Heron’s method for calculating the square root of a positive number $a$;

• Guess a value $x$ for the square root.
• Calculate $\frac{1}{2}(x+a/x)$ and that’s your new guess. Repeat.

Someone in chat asked the brilliant question of what happens if $a=-1$. Throughout the rest of the livestream, I really wanted to go and try it, and I could tell that some people in chat were giving it a go too. Before I tell you about what’s going on, you should give it a try yourself. Pick a starting number and calculate $\frac{1}{2}(x-1/x)$. Keep going. What do you see?

OK, let’s break this down. I could just tell you the answer for what’s happening, but I think it’s perhaps more helpful if I describe how I got there. First I tried this on my calculator, and I couldn’t see it settling down to any particular number. So I got my computer to try different starting numbers and apply that function many times, so I could visualise it or perhaps look at some statistics of the distribution. It gave me a mix of large and small numbers (interestingly, the natural logarithm of the absolute value of these numbers looks to be normally distributed to me).

The mix of large and small numbers reminded me of other problems I’ve seen where a good trick to try was to write $x=\tan(\theta)$. That variable transformation works quite well here, because if

$$x_{n+1}=\frac{1}{2}\left(x_n-\frac{1}{x_n}\right)$$

then

$$\theta_{n+1}=\arctan \left( \frac{\tan\theta_n-\cot\theta_n}{2} \right) = \arctan\left( \frac{1}{\tan(2\theta_n)} \right)$$

I’ll admit that it took me a really long time to spot the trigonometric identity there, and even longer to get it right. Identities to do with arctan now give us

$$\theta_{n+1}=\arctan\left( \frac{1}{\tan(2\theta_n)} \right)=\frac{\pi}{2}-2\theta_n+k\pi$$

for some integer $k$ (that’s not very important here, it’s just to do with how arctan works).

So up to factors of $\pi$ and $\pm$ signs, the operation just doubles the value of $\theta_n$. That’s a much simpler transformation, which I recognise from a course I once took on chaos theory.

As an illustration, let’s look at the simpler operation "multiply your number by ten and throw away anything in front of the decimal point". That’s got some pretty weird behaviour. If you start with a number with a repeating decimal expansion, then as you repeatedly apply the operation you’ll get a cyclic pattern, seeing the same numbers over and over. If you start with an irrational number though, you get something aperiodic. And that’s slightly weird because there are irrational numbers really close to rational numbers, so the behaviour is very sensitive on your precise starting number. That’s a hallmark of chaos.

So conclusion then; the operation that someone invented in chat of trying to find the square root of minus one with Heron’s method, is actually chaotic.

For more on chaos, see this Mathworld page or James Gleick’s book Chaos. For a concrete example to play with, see this transformation on Wikipedia, which is related to the "multiply by ten" operation above.

If you want to get in touch with us about any of the mathematics in the video or the further reading, feel free to email us on oomc [at] maths.ox.ac.uk.