"John B. Halleck" <nahaj@ocom.cc.utah.edu> wrote:

>  Since the one you gave is in the same family, I'll give the member
>  of that family I normally use, and a derivation.

   Thanks for the thorough explanation.
>
>  I hope that will be close enough for you.
>  If not, sorry to waste your time.

   No waste of time.  I think open discussion is of benefit to all
   of us.

>  I'll pass on the beer.

   OK, your choice of beverage.

>  (There are many other derivations possible, such as reccurence
>  relations...  The methods have been rediscovered so many times
>  that there are many many ways of looking at them.)

   I am not pretending to have 'discovered' this algorithm. As mentioned
   in my answer to Andy, I was taught the basic algorithm in grade
   school many years ago.  Possibly the only times I have ever used it
   was when a slide rule did not have adequate resolution - maybe twice
   in the last 40 years.  Of course, starting around 25 years ago
   calculators did the trick.  Only recently have I run across a
   controller application needing a square root.

   What has surprised me is the small number of people that are aware
   of this algorithm.  Even my wife (who is NOT a math person) remembers
   learning it although she admits to not being able to execute details.
   I have asked at least half a dozen engineer/software types and at
   best they think they may have learned some sort of technique once
   upon a time but have no clue what it was.


> --------------------------
>    portable C code.
> --------------------------
>long isqrt (x) long x;{

   [snip]

   I tried implementing your version directly in PIC code, keeping the
   location of the number fixed, shifting the root and the position
   pointer.  Works like a champ but takes around 90 or 95 program memory
   locations and additional RAM.  It does NOT have the problem Andy
   pointed out in the least significant bit.  Execution time is a little
   longer - around 1000 clock cycles.  The four byte subtract is
   a pain without a subtract-with-borrow.  Maybe it would be worth
   posting that version and letting folks hack it.  Comments anyone?


>---------------------------------------------------------
>For 8 bit quantities, here is a really short algorithm.
>This one is due to Fermat, and is from my division free

   This is basically the sum of the odd digits algorithm which
   is fine, as you point out, for small numbers.  Have you ever
   encountered an application requiring a square root of a
   small number?

--
Bob Fehrenbach    Wauwatosa, WI     bfehrenb@execpc.com