in reply to Square Root algorithm

Beatnik he's trying to do it without useing the built in square root function.

Well, first up your regex fails on an integer.

Update:

Well there ya go, I should have paid attention in class. Go read ariels tract on finding roots, he's clearly done this in a lot more detail than I have.

And I usually shy away from ariels notation, because to me 1e-18 says e^-18 rather than 10^-18. That always bugged me. Personally I'd rather use 10**(-18).

/Update

Since the way to find roots with maximum speed is to use hand-tuned assembler that exploits the quirks of the processor, there's no need to stress speed.

As for your concern about calling new_guess twice, why not try this?

my $n=0;
Hahaha:


$guess = new_guess($guess, $x); # MAKE OLD GUESS THE NEW GUESS AND RUN
+ WHILE LOOP AGAIN

$n=new_guess($guess, $x);

goto Hahaha if get_accuracy($guess, $n)  > .000000000000000001 { # CHE
+CK DIFFERENCE BETWEEN OLD GUESS AND NEW GUESS

[download]

Actually this should work fine: 


        my ($guess, $x) = @_;
 my $n=0;
        while ( get_accuracy($guess, $n)  > .000000000000000001) { # C
+HECK DIFFERENCE BETWEEN OLD GUESS AND NEW GUESS
                $guess = $n;
  $n=new_guess($guess, $x); # MAKE OLD GUESS THE NEW GUESS AND RUN WHI
+LE LOOP AGAIN
        }

[download]

____________________
Jeremy
I didn't believe in evil until I dated it.

Replies are listed 'Best First'.
Re: Re: Square Root algorithm
by ariels (Curate) on Jun 25, 2001 at 13:42 UTC
    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?

[reply]
      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