The Digital Square Root of Two

For the last couple of days, my sister and I have been super-geeking out about this sequence that was in a decision maths mock paper I took. It was a trace table question, where you have to step through some awful, obfuscated BASIC code with a pencil and paper:

AQA Decision Maths Trace Table Question

The question itself was easy, but the entailed problem was more interesting. How was this magic program making root 2? It obviously created a sequence of fractions, which I stepped out to a short extent on my calculator. Not satisfied, I programmed it on PC and generated a whole load of data. I came up with a recursive sequence which described the top or bottom of the fraction sequence… it turned out to be quite close to an actual solution, but no cigar for how it was working.

So Alisha (my sister) came round, and we were talking about the problem. She tried to do some maths-fu on it with no success. However, in studying for her post-graduate maths course, she came across the exact problem in her work, and the method for producing numerical solutions of a square root: The Newton-Raphson method. Wikipedia gives a very poor explanation, and I feel kind of bad for linking that text there, but it will give you an outline. The algorithm is so simple it can be accomplished in a 6 line, 100 byte program on my fx-9750GII. I like that fact.

We laughed at the coincidence, programmed it up on calc and computer, and found it to produce the same sequence of numbers (except more efficiently).

This is really interesting, because I’m trying to write a Maths library for VB, and knowing how computers solve problems like roots and division is very interesting to me. I’ve finished my square root function, now I just want to know the most effective ways of finding other roots.

We’re so cool.