DIY Square Roots

Everyone knows how to calculate a square root: you press the button with the funny squiggly/V shape  on your calculator! And of course Sniff has a "sqrt of" function built in, but what if it didn't. Someone has to know how to actually do the maths, otherwise how did the code get written to actually implement those functions?

I like to set calculating a square root (without using any builtin functions - no cheating and using powers or log's either!) as a programming exercise to older students. Its fun because there's a relatively simple solution, that can be coded up in a single lesson, but chances are that the students will have no idea what that solution is. They have to research (google!) an algorithm, but there are several to choose from, and while one is easy to implement its not obvious which one that is.

Of course there's always a couple of "clever" students who decide they can just copy and paste the code they find during this research. I really love it when they do this, because most of the examples out there don't work! This is pretty obvious if you know what's going on, but if you've just downloaded the code then you've got some thinking to do after all! Teaching moment: most code online sucks! Or at least you should evaluate it carefully before just grabbing it.

Here's some code that does (almost!) work:

make x number

make guess number

make otherGuess number

when start

.ask "give me a number:" and wait

.set x to value of answer

.set guess to x/2

.repeat 20

..set otherGuess to x/guess

..set guess to (guess+otherGuess)/2

.say join "Square root is:" [guess]

We start with a number "x" that we want to find the square root of. We then need to make a guess. This is where many implementations come unstuck, and try to use some kind of linear search to find a good starting point. Given a big enough value of x they break! It turns out that the initial value of guess really doesn't matter - the rest of the code will turn any guess into a better guess so even a terrible guess is perfectly good enough.

If you think about square roots, guesses come in pairs: for each value of guess, theres another value "otherGuess" which would give us x if we multiplied guess by otherGuess. So given guess we can find otherGuess.

Now if guess is too small (< sqrt of x), then otherGuess will be too big (after all they multiply to give x). If we have an upper bound and a lower bound then we can make a better guess by picking a value in the middle (technically we're approximating the geometric mean, with the arithmetic mean, but that's not important).

If we repeat this a few times, then for each guess we get a better guess, until we decide we're close enough. What's surprising is how well this actually works. Here we go round the loop 20 times, but for most regular small-medium size numbers it gets as accurate as we're likely to need far more quickly.

One interesting aspect of square roots is that they're a tricky to calculate, but their inverse is easy. If we x=y*y, then calculating x from y is far easier than finding y given x. That means we can check our answer to see how good it is. Rather than looping a fixed number of times we could loop until our answer is close enough by checking guess*guess against x. Functions like these are actually pretty common, and are a good way to test/debug code. Sorting a list is hard, while checking that a list is sorted is easy, so you can add code to your sort function to check that its worked without signifigantly affecting performance.

One final aspect to note is that the code behaves very badly for negative numbers. Here's not the place to get into what the sqrt of -1 is, but its not whatever this code prints. This is bad. The code really needs a test in to prevent negative numbers getting in. It's better to bail out and fail than silently produce a wrong answer. This is another "extra" you can throw in for students who get a working solution quickly.