群馬でアルゴリズムを学ぼうに参加したよ

2/16 邑楽町公民館にて開催された 群馬でアルゴリズムを学ぼう : ATND に参加して来ました。

ASCIIから出版されているアルゴリズムを学ぼうが教科書で、@tsurumau先生のもとで学びます。今回は「第1講 アルゴリズムと計算量」

前日に軽く読む程度で参加したのですが、実際の内容は第1講から深い内容でした。普段アルゴリズムを考えたりする深いコーディングはしない（主義）なので、頭から煙が出る勢い。

aのk乗をmで割った余りを求める関数、int powmod(int a, int k, int m)を書け。ただし、a,k,mは1以上の整数で、すべてJavaのintの範囲に入るとする

このような問題でしたが、Javaで書かれた例がすでに深いと気が付きませんでした。このような問題は単純にループで回す事で実現可能ですが、アルゴリズムを使えば一瞬で計算が終わる、という。

家に帰って写経してみました（Perlですが）

ｋ=2の31乗-1で試した結果。
https://gist.github.com/4971027.git

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]

MacBook Core 2 Duoなので最近のマシンと比べると遅いのでしょうね。それはともかく、この歴然の差。アルゴリズムすげーぜよ。

また、二分探索というアルゴリズム（の基礎）も初めて知ったのですが、面白い考え方でした。仕組みを聞けば単純だけれど、思いつくかと言われれば簡単にはいかないでしょう。こういう知識があるかないかだけでも大きく違うんでしょうね。

今回の勉強会では、普段なかなか手を出さないことに触れる事ができました。数学の知識とか、忘れていることも多いし、知らないことも多い。すごく勉強になりました。先生、次回もよろしくお願いします。

ところで、ソースコード書く男の人って皆んなこんなことやっているのでしょうか？