Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
At first, I tried this simple recursive algorithm:

#!/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;
which yields the results:

root@swill ~/PerlMonks $ ./adder_1.pl 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); 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); } });
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...


In reply to Re: Adding 2 + 2 by roboticus
in thread Adding 2 + 2 by merlyn

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others pondering the Monastery: (10)
    As of 2014-07-11 00:30 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      When choosing user names for websites, I prefer to use:








      Results (217 votes), past polls