In 1770 Lagrange http://www-groups.dcs.st-and.ac.uk/~history/...range.html showed that any natural number can be written as a sum of at most four squares, a conjecture dating back to the days of Diophantus:- 2 = 1^2 + 1^2;34 = 3^2 + 3^2 + 4^2
A simple but not very efficient solution of how we can decompose a natural number into a sum of squares is as follows
The simplest solution one can think of works by subtracting a trial square from the number to be decomposed and then trying to decompose the resulting number into a sum of three squares. Using the same idea, this problem is then reduced to the representation of two squares. The final step of this algorithm asks to decompose an integer into just one square which boils down to checking whether a number D is a square. This can easily be accomplished by adopting the Newton iteration
xn+1 = (xn + D / xn) / 2
for finding the square root of D to the integers.
Can anyone find a simpler and more efficient method and more inportantly can you implement it on a 8052?