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  ), $/, $/;

[download]

-- monsieur_champs

In reply to [Study]: Searching for square roots by monsieur_champs

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.