Path: utzoo!utgpu!watmath!watcgl!ksbooth
From: ksbooth@watcgl.waterloo.edu (Kelly Booth)
Newsgroups: uw.general
Subject: Re: Pencil & Paper Square root method
Message-ID: <11255@watcgl.waterloo.edu>
Date: 25 Aug 89 00:36:12 GMT
References: <16075@watdragon.waterloo.edu> <491@watshine.waterloo.edu>
Reply-To: ksbooth@watcgl.waterloo.edu (Kelly Booth)
Distribution: uw
Organization: U. of Waterloo, Ontario
Lines: 17

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).