Skip to navigation

BBC Micro Elite

Calculating square roots

The algorithm behind the square root routine

References: LL5

The algorithm used to calculate square roots in routine LL5 is related to the division algorithm in TIS2 (see the deep dive on "Shift-and-subtract division" for details), though with a couple of twists. If you think about the division algorithm, it calculates the quotient and remainder from a given dividend and divisor, and the following holds:

  dividend = (quotient * divisor) + remainder

The problem of calculating the square root is related to this, except we have the following relationship between the arguments and results, where "number" is the number we want to find the square root of:

  number = (root * root) + remainder

So the number we want to find the root of is equivalent to the dividend in the shift-and-subtract algorithm, and instead of the divisor being fixed, we instead build up the root bit by bit and use that in place of the divisor.

When generalised to calculate the n-th root, this approach is called the "shifting nth-root" algorithm, and it is explained in various places on the web by minds more devious than mine. The LL5 routine is an application of the algorithm for n = 2, which is why the number ("dividend") and remainder get shifted by two places in each iteration.

There is a deeper explanation of this exact routine here, though I have to say it makes my head spin more than a little:

   http://6502org.wikidot.com/software-math-sqrt

Definitely one for the "must study later" pile...