アルゴリズムで学ぼうのリスト1-1と1-2をperlで書いてCore 2 Duo 2GhzでBenchmark取ってみた

powmod-benchmark.pl

use strict;
use warnings;
use Benchmark qw(:all);

sub powmod1_1 {
  my ($a, $k, $m) = @_;
  my $t = 1;
  for (my $i = 0; $i < $k; $i++){
    $t = ($t * $a) % $m;
  }
  return $t;
}

sub powmod1_2 {
  my ($a, $k, $m) = @_;

  if (int $k == 0){ return 1; }
  my $t = powmod1_2($a, $k /2, $m);

  $t = ($t * $t) % $m;
  if ($k % 2 == 1){
    $t = ($t * $a) % $m;
  }
  return $t;
};

my ($a, $k, $m); 
$a = 2; $k = 2**31-1; $m = 5;
my $results = timethese(1, {
  'powmod1_1' => sub { powmod1_1($a, $k, $m); },
  'powmod1_2' => sub { powmod1_2($a, $k, $m); },
});

cmpthese($results);


# // 結果 //
Benchmark: timing 1 iterations of powmod1_1, powmod1_2...
 powmod1_1: 541 wallclock secs (539.17 usr +  0.34 sys = 539.51 CPU) @  0.00/s (n=1)
            (warning: too few iterations for a reliable count)
 powmod1_2:  0 wallclock secs ( 0.00 usr +  0.00 sys =  0.00 CPU)
            (warning: too few iterations for a reliable count)
            s/iter             powmod1_1             powmod1_2
powmod1_1      540                    --                 -100%
powmod1_2 1.00e-15 53951000000000000000%                    --
[Finished in 540.9s]