comment on

I believe

Benchmark: timing 1000000 iterations of iterative_c, iterative_p, recu
+rsive_c, recursive_p...
iterative_c:  1 wallclock secs ( 1.10 usr +  0.00 sys =  1.10 CPU) @ 9
+07441.02/s (n=1000000)
iterative_p: 19 wallclock secs (19.52 usr +  0.00 sys = 19.52 CPU) @ 5
+1234.76/s (n=1000000)
recursive_c:  1 wallclock secs ( 1.16 usr +  0.00 sys =  1.16 CPU) @ 8
+60585.20/s (n=1000000)
recursive_p: 36 wallclock secs (36.26 usr +  0.00 sys = 36.26 CPU) @ 2
+7576.32/s (n=1000000)
                Rate recursive_p iterative_p recursive_c iterative_c
recursive_p  27576/s          --        -46%        -97%        -97%
iterative_p  51235/s         86%          --        -94%        -94%
recursive_c 860585/s       3021%       1580%          --         -5%
iterative_c 907441/s       3191%       1671%          5%          --
[download]

use Inline 'C';

use Benchmark 'cmpthese';

cmpthese( 1_000_000, { iterative_c => sub{guess_it_c(4999,1,10000)},
                       recursive_c => sub{guess_rec_c(4999,1,10000)},
                       iterative_p => sub{guess_it_p(4999,1,10000)},
                       recursive_p => sub{guess_rec_p(4999,1,10000)},}
+);

sub guess_it_p {
    my ( $ans, $lower, $higher ) = @_;
    my $guess;
    while(1) {
        $guess = int(($lower + $higher)/2);
      last if $ans == $guess;
        if ( $guess > $ans ) {
            $higher = $guess -1;
        }
        else {
            $lower = $guess +1;
        }
    }
  return $guess;
}

sub guess_rec_p {
    my ( $ans, $lower, $higher ) = @_;
    my $guess = int(($lower + $higher)/2);
    if ($ans == $guess) {
        return $guess;
    }
    if ( $guess > $ans ) {
            guess_rec_p( $ans, $lower, $guess -1 );
    }
    else {
        guess_rec_p( $ans, $guess +1, $higher );
    }
}

__END__
__C__
int guess_it_c( int ans, int lower, int higher ) {
    int guess;
    for(;;) {
        guess = (int)((lower + higher)/2);
        if ( ans == guess ) break;
        if ( guess > ans )
            higher = guess -1;
        else
            lower = guess +1;
    }
  return guess;
}

int guess_rec_c( int ans, int lower, int higher ) {
    int guess;
    guess = (int)((lower + higher)/2);
    if (ans == guess) return guess;
    if ( guess > ans ) {
         guess_rec_c( ans, lower, guess -1 );
    }
    else {
        guess_rec_c( ans, guess +1, higher );
    }
}
[download]

cheers

tachyon

In reply to Re^3: Behold! The power of recursion. by tachyon
in thread Behold! The power of recursion. by DigitalKitty

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


Perl: the Markov chain saw
	PerlMonks