in reply to Re: Square Root algorithm
in thread Square Root algorithm

Taking <var>xn+1</var> = (<var>xn</var>+<var>a</var>/<var>xn</var>) is Newton's method for taking the square root! (But one should note the name of the method is the Babylonian square root algorithm).

Also, why is everyone saying ".000000000000000001" as the accuracy? Am I the only one who's having trouble counting? Isn't "1e-18" a bit easier on the eyes and the screen?

Replies are listed 'Best First'.
Re: Re: Re: Square Root algorithm
by mamut (Sexton) on Jun 26, 2001 at 12:07 UTC
    I remeber for One funny alogorith for fined square root from some numbers :-)

    add together odd-numbers from 1 while total sum is greater or equal to input number :-). Count of numbers is root :-))

    exam.
    root from 9 : 1+3+5=9 number 3
    root from 25 : 1+3+5+7+9=25 number 5
    root from 100: 1+3+5+7+9+11+13+15+17+19=100 number 10 :-)
     easy and funny but works :-)
    It's usefull for locating starting number for iteration process.

    This algorithm is very fast because use only adding and testing :-)
    but today it's irelevant becuase processor are very fast and using math-coprocessor :-).

    several years ago thas was easy to creat it for lots of ASM instructions :-))
[reply]
      (<var>n</var>+1)2-<var>n</var>2 = 2<var>n</var>+1. </blockquote

      So your algorithm works for any square integer. But it's not very fast, as it takes time proportional to O(sqrt(<var>n</var>)), where <var>n</var> is the number you're rooting, not its size!

      For comparison, Newton-Raphson / the Babylonian algorithm double the number of correct digits at each iteration.

[reply]
      Moin,

      by mamut on Jun 25, 2001 at 21:07 I remeber for One funny alogorith for fined square root from some numbers :-)

      Cool! ;o) I am currently optimizing the square-root in BigFloat/BigInt, that might come in handy!

      Cheers, Tels (at bloodgate dot com)

[reply]

In Section Seekers of Perl Wisdom