Beefy Boxes and Bandwidth Generously Provided by pair Networks Cowboy Neal with Hat
Just another Perl shrine
 
PerlMonks  

[Study]: Searching for square roots

by monsieur_champs (Curate)
on Nov 14, 2006 at 13:46 UTC ( #583961=perlquestion: print w/ replies, xml ) Need Help??
monsieur_champs has asked for the wisdom of the Perl Monks concerning the following question:

Dear Monks

I'm training to implement recursive functions based on iteractive processes. For this, I decided to implement a binary search function to finding square roots of numbers without using loops. This is a personal study project, not a school task of any form.

At this moment, I already have a fair good implementation that fit my study needs. I'm not looking for the best solution for the problem of finding square roots. Isaac Newton toke care of this many years ago. ;-) I'm trying to learn better recursive programming techniques.

But I'm facing a funny problem here: I'm not sure how to make the search converge for numbers greather than zero and smaller than 1. Maybe someone here could give me a hand suggesting a method for handling those cases, without using loop keywords.

Thanks in advance for your help. Code follows.

#!/usr/bin/perl use strict; use warnings; sub middle ($$) { my ( $a, $b ) = ( shift, shift ); return ($a + $b) / 2 } sub square ($) { my $x = shift; return $x**2; } sub abs ($) { my $n = shift; return $n < 0 ? -$n : $n; } sub sqrt_search{ my ( $x, $base, $top, $guess, $counter ) = ( shift, shift, shift, sh +ift, shift ); print "sqrt-search( $x, $base, $top, $guess )\n"; return $guess if( abs($x - square $guess) < 0.0001); return undef if $counter == 0; return sqrt_search( $x, $guess, $top, middle( $guess, $top ), --$cou +nter) if( ($x > 0) and (square $guess < $x) ); return sqrt_search( $x, $base, $guess, middle( $base, $guess ), --$c +ounter) if( ($x > 0) and (square $guess > $x) ); return undef; } sub sqrt ($) { my $x = shift; return sqrt_search( $x, 0, $x, middle(0, $x), 50); } # Tests print "SQRT 16:\n", &sqrt( 16 ), $/, $/; print "SQRT 4:\n", &sqrt( 4 ), $/, $/; print "SQRT 2:\n", &sqrt( 2 ), $/, $/; print "SQRT 0.5:\n", &sqrt( .5 ), $/, $/; print "SQRT -1:\n", &sqrt( -1 ), $/, $/; print "SQRT 0:\n", &sqrt( 0 ), $/, $/;

Comment on [Study]: Searching for square roots
Download Code
Re: [Study]: Searching for square roots
by roboticus (Canon) on Nov 14, 2006 at 13:59 UTC
    Remove those semicolons after the if statements--the then clause is always being executed.

    UPDATE: Gah! Immediately upon pressing the "create" button, I realized it was totally wrong. Please ignore this post...

    UPDATE 2: L~R pointed out that removing the node contents isn't cricket. So I'm sticking in my original comment (as best as I can remember it). The only thing I can say in my defense is that I was embarrassed by such a boneheaded mistake. Ah, well, heavy coding in C++ for a few weeks certainly warps your perception of syntax. ;^)

    --roboticus

      Nothing is totally wrong :)

      The only thing that you did not consider is that x*x < x for x < 1. That's why your code doesn't work for input < 1.

      Apart from that a couple of small comments concerning your code.

      • Don't use prototypes for your subroutines unless you know exactly what you are doing.
      • Don't use the variables $a and $b, they are special and used for sort.
      • Instead of writing my ($x, $y, $z) = (shift, shift, shift); simply write my ($x, $y, $z) = @_;.

      -- Hofmator

      Code written by Hofmator and posted on PerlMonks is public domain. It is provided as is with no warranties, express or implied, of any kind. Posted code may not have been tested. Use of posted code is at your own risk.

      roboticus,
      Removing a node's content is generally frowned upon regardless of correctness. It is best to strike what is wrong or add an update then to remove it entirely. People do learn from other's mistakes.

      FWIW, here is my take without having looked any other solutions to include monsieur_champs'.

      print sqrt($_), "\t", mysqrt($_, .0000001), "\n" for qw/.25 .50 .75 1 +10 50 100 1000 31415926/; sub mysqrt { my ($tgt, $err, $try, $len) = @_; return 1 if $tgt == 1; if (! defined $try) { ($len, $try) = $tgt < 1 ? ((1 - $tgt) / 2, $tgt + (1 - $tgt) / 2) : ($tgt / 2, $tgt / 2); return mysqrt($tgt, $err, $try, $len); } my $dif = $tgt - ($try * $try); return $try if abs($dif) < $err; $len /= 2; $try = $dif > 0 ? $try + $len : $try - $len; return mysqrt($tgt, $err, $try, $len); }
      If it isn't obvious, it is a binary search.

      Update: The adjustment for values < 1 can be mathematically simplified. Additionally, a much faster converging algorithm would be $try = (($tgt / $try) + $try) / 2.

      Cheers - L~R

Re: [Study]: Searching for square roots
by jimbojones (Friar) on Nov 14, 2006 at 14:07 UTC
    Hi,

    I think your problem is in your assumption of the maximum possible value for the square root of numbers in the range of 0 to 1.

    I managed to fix your code with one line to handle the 0.5 case, but I'll leave it to you to find it.

    - j

Re: [Study]: Searching for square roots
by geekphilosopher (Friar) on Nov 14, 2006 at 14:47 UTC
    Just a general note - if you're looking to work on recursion with perl, you should check out Higher Order Perl, which covers it in some detail (including some of the reasons why you may not want to use it).
Re: [Study]: Searching for square roots
by rhesa (Vicar) on Nov 14, 2006 at 15:25 UTC
    Yep, your initial guess doesn't work for $x < 1. I suggest just starting out with 1 instead:
    sub sqrt ($) { my $x = shift; return sqrt_search( $x, 0, $x, 1, 50); } # Tests sub test { my $n = shift; print "SQRT $n: ", &sqrt( $n ), ' ?= ', eval { CORE::sqrt( $n ) } +, $/, $/; } test( $_ ) for( 16, 9, 4, 2, 0.5, -1, 0, 0.001 );
    Output:
    SQRT 16: 4.0000114440918 ?= 4 SQRT 9: 3 ?= 3 SQRT 4: 1.99998474121094 ?= 2 SQRT 2: 1.4141845703125 ?= 1.4142135623731 SQRT 0.5: 0.7071533203125 ?= 0.707106781186548 SQRT -1: ?= SQRT 0: 0.0078125 ?= 0 SQRT 0.001: 0.03125 ?= 0.0316227766016838
Re: [Study]: Searching for square roots
by blazar (Canon) on Nov 14, 2006 at 16:57 UTC
    A few side comments:
    sub middle ($$) { my ( $a, $b ) = ( shift, shift ); return ($a + $b) / 2 }

    Don't pass parameters like that, it's confusing: which shift gets executed first? I'd either use it if only one is involved at a time, and possibly if I have to use the rest of @_ as a whole, or stick with:

    my ($n,$m)=@_;

    (I tend not to use $a and $b as general purpose variables even when they wouldn't be error prone because... their use is potentially error prone.)

    It's a commonly recommended style to put a semicolon on the last line too.

    Oh, and there's no need to use prototypes. Actually many people deprecate them. I find them useful for code and autorefs, but other than that they don't buy you much.

    print "SQRT 16:\n", &sqrt( 16 ), $/, $/;

    &-form of sub call is now obsolete and most likely not to do what you want. Read more about this in perldoc perlsub.

      If I needed to pull more than one value off the front of @_ and leave the rest I'd possibly use splice:

      my ($arg1, $arg2) = splice 0, 2, @_;

      but more likely I'd pull the tail elements out into an array:

      my ($arg1, $arg2, @tail) = @_;

      DWIM is Perl's answer to Gödel

        Well, I do use splice occasionally, but not for argument passing. I'd either do

        my $arg1=shift; my $arg2=shift;

        or as in your second alternative, the point still being that multiple shift's on one line can be confusing albeit potentially correct, and IMHO clearly neither particularly concise nor expressive in terms of readability. Anyway what I choose depends on the emphasis I want to put on each argument. Fortunately in a not (any more) so remote future we will avoid all these parameter passing acrobatics...

      If I were writing the middle subroutine, I wouldn't copy the values into other variables before use:

      sub middle { return ($_[0] + $_[1]) / 2; }

      But that's probably just me.

        Indeed: YAWTDI!

      Oh, and there's no need to use prototypes. Actually many people deprecate them.

      The OP's code even does what you've said "many people" do. Using the & prefix to call a sub disables prototype checking. The combination of both &sub and prototypes should be a red flag (in addition to each being a red flag in and of themselves).

        The OP's code even does what you've said "many people" do. Using the & prefix to call a sub disables prototype checking. The combination of both &sub and prototypes should be a red flag (in addition to each being a red flag in and of themselves).

        I second that thoroughly. And it was very good of you to underline this sort of "synergy", because I didn't. Actually since there are prototypes, this may be one situation in which &sub may have sense, to overcome them. But it does not have sense to overcome them, so just as in the vast majority of cases, it's not needed and better avoided, period.

      And remember that $a and $b are the special comparison variables for sort(). It's a bad habit to use meaningless variable names anyway - let's move on past FORTRAN!

      I'd recommend maybe

      sub middle { my($low, $high) = @_; return ($low + $high) / 2; }
      because it's now much more evident that the "middle" is the value between low and high.
Re: [Study]: Searching for square roots
by ikegami (Pope) on Nov 14, 2006 at 22:54 UTC

    A very important skill in writting recursive functions is knowing how to get rid of trivial recursion.

    Functions of the form

    sub func { ... if (...) { ... return ...; } elsif (...) { ... return ...; } elsif (...) { ... return func(...); } elsif (...) { ... return func(...); } }

    including the trivial case

    sub func { ... return func(...); }

    can be made non-recursive trivially. They are said to be "tail recursive". Your function is tail recursive, so it can be optimized. After removing tail recursion, your code looks like the following:

    use constant SQRT_EPSILON => 0.0001; use constant SQRT_MAX_ITER => 50; sub sqrt ($) { my $x = shift; return undef if $x < 0; my $base = 0; my $top = $x; my $guess = middle($base, $top); my $counter = SQRT_MAX_ITER; while (abs($x - square $guess) >= SQRT_EPSILON) { # Avoid looping for too long. return undef unless $counter--; if ( square $guess < $x ) { $base = $guess; $guess = middle( $guess, $top ); } elsif ( square $guess > $x ) { $top = $guess; $guess = middle( $base, $guess ); } } return $guess; }

    Update:

    Any loop can be converted into a recursive solution, but not all recursive solutions can be made into a (simple) loop. A recursive algorithm that doesn't use tail recursion is a depth-first visit of a tree.

    sub in_order_visit { my ($node, $visitor) = @_; return unless defined $node; in_order_visit($node->left(), $visitor); $visitor->($node); in_order_visit($node->right(), $visitor); }

    Recursion can still be eliminated by replacing the call stack with a local stack.

    sub in_order_visit { my ($node, $visitor) = @_; my @to_process; for (;;) { if (defined $node) { push(@to_process, $node); $node = $node->left(); } else { return if not @to_process; $node = pop(@to_process); $visitor->($node); $node = $node->right(); } } }

    However, this makes the function much more complicated with little or no benefit.

      They are said to be "tail recursive". Your function is tail recursive, so it can be optimized. After removing tail recursion, your code looks like the following:

      Incidentally, one can fine a thorough discussion of these matters, and one likely to be particularly suited for the OP's (and everyone else's) learning purposes, in chapter 13 of the book that one of our monks is writing.

Re: [Study]: Searching for square roots
by Anonymous Monk on Nov 15, 2006 at 13:08 UTC
    If you didn't try to invent a new algo (binary search with squaring) but sticked to ol' Newton (n=middle(n,x/n)) then your problem won't exist.
      Right, but his point was that he wanted to try something, which is an attitude to be encouraged. Maybe it's not effective, or better, or useful, but it's exploring to find out how to do something in a different way, and understanding how to use the tools to do it.

      If you're comfortable with thinking about a problem in multiple ways, you can learn when to use one versus another. If you only know how to do iterative solutions, recursive ones look strange and challenging (or vice versa, for those whose first language was LISP).

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://583961]
Approved by robartes
Front-paged by andyford
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (6)
As of 2014-04-20 15:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (485 votes), past polls