in reply to Adding 2 + 2
At first, I tried this simple recursive algorithm:
which yields the results:#!/usr/bin/perl -w use strict; use warnings; sub add { my ($first, @rest) = @_; if (!defined $first) { 0; } else { die "operand may not be negative!" unless $first >= 0; if ($first == 0) { add(@rest); } else { 1 + add($first-1, @rest); } } } sub print_add { print join(" + ", @_), " = ", add(@_), "\n"; } print_add 2,2; print_add 2,2,2; print_add 4,8,12;
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:root@swill ~/PerlMonks $ ./adder_1.pl 2 + 2 = 4 2 + 2 + 2 = 6 4 + 8 + 12 = 24
Now all that remained is to verify that the conversion was worthwhile:sub add { my $accumulator = 0; for my $op (@_) { for my $i (1 .. $op) { $accumulator = $accumulator+1; } } $accumulator; }
Running the benchmarking program shows:#!/usr/bin/perl -w use strict; use warnings; use Benchmark qw(timethese cmpthese); sub add_rec { my ($first, @rest) = @_; if (!defined $first) { 0; } else { die "operand may not be negative!" unless $first >= 0; if ($first == 0) { add_rec(@rest); } else { 1 + add_rec($first-1, @rest); } } } sub add_iter { 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); } });
Success!$ ./adder_bench.pl Rate Recursive Iterative Recursive 79051/s -- -48% Iterative 152207/s 93% --
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...
|
---|
In Section
Cool Uses for Perl