Re: Binary sqrt

From: AlanGLLoyd (alanglloyd_at_aol.com)
Date: 11/03/03 

Date: 03 Nov 2003 07:43:37 GMT

In article <3fa5a7cf@news.leadingedgeinternet.net.au>, "rob wise"
<rweiz@dcsi.net.au> writes:

>I am wanting to perform a square root to a very long binary number to
>produce its root and any remainder.
>
>I understand it is possible to square root a binary number (in fact any
>number) by working through it from left to right working on pairs bits of
>the number. Much like long division.
>
>Can anyone assist me with a Pascal algorithm to do this please, or a place I
>can find pointers to the procedure.
>

I would think you do it the same as for any number. AFAICR for 54321 with
square root in square brackets ...

1) Mark off in blocks of pairs from right to left.
5'43'21'

2) Starting from left take first block as active-value
5

3) Get largest digit which when squared is less than value from 2
2

4) Put value from 3 as left-most number of Result.
[2]

5) Subtract value in 4 squared from active-value
1

6) Append numbers of next block to remainder
143

7) Multiply Result by 2
4

8) Find largest digit which when appended to value from 7 and that number
multplied by digit, is less than value from 6
3

9) Append that digit to Result and get remainder of (7 appended by 8) * 8 from
6
[23] 143 - (43 * 3) == 14

10) GoTo 6

6) 1421

7) 46

8) 3

9) [233] 1421 - (463 * 3) == 32

6) 3200

7) 466

8) 0

9) [233.0] 466 - 0 == 466

6) 46600

7) 320000

8) 6

9) [233.06] 320000 - (46606 * 6) == 40364

6) 4036400

7) etc etc

SqRt(54321) == 233.0686594

Binary is the same, just remember your binary tables ...

0 x 1 == 0
1 x 1 == 1
2 x 1 == 10

... and when subtracting carry the same as in decimal subtraction.

Alan Lloyd
alanglloyd@aol.com

Relevant Pages

  • Re: Babylonian root 2 (was: Waradpande seems to have destroyed PIE already)
    ... 'Square Root Approximations in Old Babylonian ... told me time and again that the Babylonians find the ...
    (sci.lang)
  • Re: Liskov substitution principle
    ... for square root calculation, which is hard for people to write a unified ... verification function (your example, verifiesOK)? ... It means base and derive do not follow the same contract to implement square ... The magic Quake implementation for square root ...
    (microsoft.public.vc.language)
  • Re: Plausibility Check
    ... Brian Irrelephant Scott forever. ... case of the square root of 2, ... mathematicians of ancient Egypt and Mesopotamia. ...
    (sci.lang)
  • >>>> FIND SQUARE <<<<
    ... How To Find Square Footage ... How To Find The Square Footage ... How To Find Square Root ... How To Find Square Feet ...
    (sci.lang.japan)
  • Fermats Last Theorum
    ... so, you have 3 dimensions, add one, and now you need a factor of 4, ... does the square of the hypotenuse equal ... unique properties of 2 and 1 and the fact that the square root of two, ... One multiplied by one, equals two, but one times one, equals one. ...
    (sci.physics)