Skip to navigation

Elite on the BBC Micro and NES

Calculating square roots

The algorithm behind the square root routine

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

It also turns out that the LL5 routine in Elite is identical to the SQR16 routine from the March 1983 issue of Personal Computer World. The same routine also appears in the book Assembler Routines for the 6502 by Dave Barrow. Thanks to TobyLobster and Rocketeer for some top-tier detective work in tracking this down - see this thread from Stardot for more details.

This algorithm is definitely one for the "must study later" pile...