アルゴリズムを学ぼう リスト1-2(perl) 実行される時にwarnだして思い出した感。9行目の条件をクリアした後の18行目のreturnが10行目に帰るっての忘れてたよ...

powmod.pl

warn "結果:", powmod(2,10,5);


sub powmod
{
  my ($a, $k, $m) = @_;
  warn "powmod a:$a, k:$k, m:$m";

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

  warn "keisan t:$t a:$a, k:$k, m:$m";
  $t = ($t * $t) % $m;
  if ($k % 2 == 1){
    $t = ($t * $a) % $m;
  }
  warn "return t:$t a:$a, k:$k, m:$m";
  return $t;
}


# /// 実行結果 ///
powmod a:2, k:10, m:5 at /Users/clicktx/src/powmod.pl line 7.
powmod a:2, k:5, m:5 at /Users/clicktx/src/powmod.pl line 7.
powmod a:2, k:2.5, m:5 at /Users/clicktx/src/powmod.pl line 7.
powmod a:2, k:1.25, m:5 at /Users/clicktx/src/powmod.pl line 7.
powmod a:2, k:0.625, m:5 at /Users/clicktx/src/powmod.pl line 7.
keisan t:1 a:2, k:1.25, m:5 at /Users/clicktx/src/powmod.pl line 12.
return t:2 a:2, k:1.25, m:5 at /Users/clicktx/src/powmod.pl line 17.
keisan t:2 a:2, k:2.5, m:5 at /Users/clicktx/src/powmod.pl line 12.
return t:4 a:2, k:2.5, m:5 at /Users/clicktx/src/powmod.pl line 17.
keisan t:4 a:2, k:5, m:5 at /Users/clicktx/src/powmod.pl line 12.
return t:2 a:2, k:5, m:5 at /Users/clicktx/src/powmod.pl line 17.
keisan t:2 a:2, k:10, m:5 at /Users/clicktx/src/powmod.pl line 12.
return t:4 a:2, k:10, m:5 at /Users/clicktx/src/powmod.pl line 17.
結果:4 at /Users/clicktx/src/powmod.pl line 1.