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 ), $/, $/;
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). | [reply] |
|
I'd like to second the above recomendation. HOP is a magnificent book.
The rest of Dominus' site has some really good resources (not necessarily about recursion) as well.
some functional programming links:
| [reply] |
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.
a number between 0 and 1 can be written as 1/x, where x > 1. Then the sqrt(1/x) is sqrt(1)/sqrt(x) = 1/sqrt(x). Now sqrt(x) is < x, so the max value of sqrt(1/x) is 1/x.
- j | [reply] |
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
| [reply] [d/l] [select] |
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. | [reply] [d/l] [select] |
|
sub middle {
return ($_[0] + $_[1]) / 2;
}
But that's probably just me.
| [reply] [d/l] [select] |
|
| [reply] |
|
| [reply] [d/l] [select] |
|
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.
| [reply] [d/l] |
|
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
| [reply] [d/l] [select] |
|
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...
| [reply] [d/l] |
|
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. | [reply] [d/l] |
Re: [Study]: Searching for square roots
by ikegami (Patriarch) 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.
| [reply] [d/l] [select] |
|
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.
| [reply] |
Re: [Study]: Searching for square roots
by roboticus (Chancellor) 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
| [reply] [d/l] |
|
| [reply] [d/l] [select] |
|
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.
| [reply] [d/l] [select] |
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. | [reply] |
|
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).
| [reply] |
|
|