Your skill will accomplishwhat the force of many cannot PerlMonks

### [Study]: Searching for square roots

by monsieur_champs (Curate)
 on Nov 14, 2006 at 13:46 UTC 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.

```#!/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  ), \$/, \$/;

Replies are listed 'Best First'.
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).

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.

TGI says moo

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 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
```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 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.

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...

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 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

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.

• 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 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).

Create A New User
Domain Nodelet?
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 meditating upon the Monastery: (2)
As of 2021-12-04 17:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
R or B?

Results (30 votes). Check out past polls.

Notices?