🚀 go-pugleaf

In article <491@watshine.waterloo.edu> pfratar@watshine.waterloo.edu (Paul Frattaroli - DCS) writes:
>                                              The root is the number of
>times you subtract + any decimal from the long division.

This algorithm requires OMEGA( root n ) steps to find the square root and
is analogous to division by successive subtraction (without shifts).

The earlier algorithm requires OMEGA( log n ) steps and is analogous to
the standard long division algorithm (subtraction with shifts).  It is
easy to derive this directly from the binomial theorem:

	Let sqrt(X) = 10a + b,

	then X = (10a + b)**2 = 100a**2 + 20ab + b**2

	The first division step finds a, then the iterative step finds
	b (note that 20ab is twice a in the tens place plus b).