Keep It Simple, Stupid PerlMonks

### Re: Adding 2 + 2

by roboticus (Chancellor)
 on Jan 31, 2007 at 03:53 UTC ( #597495=note: print w/replies, xml ) Need Help??

At first, I tried this simple recursive algorithm:

```#!/usr/bin/perl -w
use strict;
use warnings;

my (\$first, @rest) = @_;

if (!defined \$first) {
0;
}
else {
die "operand may not be negative!" unless \$first >= 0;
if (\$first == 0) {
}
else {
}
}
}

print join(" + ", @_), " = ", add(@_), "\n";
}

which yields the results:

```root@swill ~/PerlMonks
2 + 2 = 4
2 + 2 + 2 = 6
4 + 8 + 12 = 24
But I then realized that the algorithm used is essentially tail-recursive. Thus, it can be optimized! Converting the add routine from tail-recursive form to an iterative form yields:

```sub add {
my \$accumulator = 0;
for my \$op (@_) {
for my \$i (1 .. \$op) {
\$accumulator = \$accumulator+1;
}
}
\$accumulator;
}
Now all that remained is to verify that the conversion was worthwhile:

```#!/usr/bin/perl -w
use strict;
use warnings;

use Benchmark qw(timethese cmpthese);

my (\$first, @rest) = @_;

if (!defined \$first) {
0;
}
else {
die "operand may not be negative!" unless \$first >= 0;
if (\$first == 0) {
}
else {
}
}
}

my \$accumulator = 0;
for my \$op (@_) {
for my \$i (1 .. \$op) {
\$accumulator = \$accumulator+1;
}
}
\$accumulator;
}

cmpthese(100000, {
'Recursive' => sub { 2 == add_rec(2,2); },
'Iterative' => sub { 2 == add_iter(2,2); }
});
Running the benchmarking program shows:

```\$ ./adder_bench.pl
Rate Recursive Iterative
Recursive  79051/s        --      -48%
Iterative 152207/s       93%        --
Success!

The iterative version is *much* faster than the recursive one. I'm certain that this new algorithm for adding should be used in all future programs, as the iterative version is better both in speed (it's nearly twice as fast!) as well as consuming far less memory than it's recursive counterpart when adding large numbers.

--roboticus

Awaiting his Turing prize for this valuable discovery...

Create A New User
Node Status?
node history
Node Type: note [id://597495]
help
Chatterbox?
 [choroba]: "for tomorrow" [Discipulus]: Let's perl: from cpan website how can thou/you tell how many namespaces are beyond App::* ? [LanX]: cpan serach? [Discipulus]: about bred: 'let our bred levitate (well)' [Discipulus]: I love maps! [Discipulus]: also App::* works in cpan search, i tried App::

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (8)
As of 2017-11-23 20:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In order to be able to say "I know Perl", you must have:

Results (338 votes). Check out past polls.

Notices?