perlquestion
monsieur_champs
<p>Dear Monks
<p>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 <b>without</b> using loops. This is a personal study project, not a school task of any form.</p>
<p>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. <a href="http://en.wikipedia.org/wiki/Isaac_newton">Isaac Newton</a> toke care of this many years ago. ;-) I'm trying to learn better <a href="http://en.wikipedia.org/wiki/Recursion_(computer_science)">recursive</a> programming techniques.
<p>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.
<p>Thanks in advance for your help. Code follows.
<p>
<code>
#!/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, shift, 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 ), --$counter)
if( ($x > 0) and (square $guess < $x) );
return sqrt_search( $x, $base, $guess, middle( $base, $guess ), --$counter)
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 ), $/, $/;
</code></p>
<!-- Node text goes above. Div tags should contain sig only -->
<div class="pmsig"><div class="pmsig-260843">
<p align="right"><small>-- [monsieur_champs]</small></p>
</div></div>