Project Eulerというコンピュータ向けの数学の問題集がある。
問題の日本語での説明はProject Euler Wikiに書いてあるからこれを見ればいい。
まぁさすがコンピュータ向けだけあって、計算がすごくめんどくさい。
それで何問かPerlで解いてたのだが進めて行くにつれて問題が出てきた。
Problem 16、21000の各桁の数字の和を求めよ、
という問題ですがこれはかなり厳しいことがわかります。
対数を使って21000がどんな大きさの数字か概算してみると、
1000×log102=301.03というわけで、10301よりは大きな数字であることがわかると。
これはPerlで取り扱える整数の限界を超えている。Perl 6ではいけるかもしれんけど。
なので普通の方法では各桁の数字はわからない。
となると、自分でどうにかしないといけないと。
そこでBignumクラスを作ってみた。
まぁこんなのCPANに転がってるのは考えるまでもないことだが、自分で実装してみることにした。
数字を1桁ずつ分けて、下の位から上の位の順に配列に入れて持っておくと。
1234という数字なら[4,3,2,1]という形で持っておくと言うこと。
というわけでクラス作るよ。
package Bignum;
sub new{
my $package=shift;
my @num=split //,$_[0];
return bless([reverse @num],$package);
}
実は配列のリファレンスをblessしてもインスタンスは作れるんですね。普通はハッシュのリファレンスをblessするんだけどね。
ハッシュよりも配列の方が性能がいいから、$self->{foo}とするのを$self->[0]としてまで配列リファレンスをblessする人がいるのだとか。
それとは違う理由だけど、どうせ配列だけだからと配列リファレンスをblessしてみた。
さて、かけ算を定義してみよう。
sub mul{
my $self=shift;
my $c=0;
for(@$self){
my $t=$_*$_[0] + $c;
$_ = $t%10;
$c=int($t/10);
}
while(1){
last if($c==0);
push @$self,$c%10;
$c=int($c/10);
}
return $self;
}
実はこれ、人間がやる筆算と同じ事をしてるんですね。いや、ちょっと違うか。
$cは繰り上がりの桁をメモしておくもの。
1234*12の計算であれば、
まず4*12を計算する、すると28だが、1の位だけ書いておく。残りの桁は繰り上がりとしてメモ、
次に3*12を計算して、これと繰り上がりの桁の和を考える…
とやっていって、桁が足りなければpushして増やしてると。
あと、連結した文字列、桁数、数字の配列を得るメソッドだけ作っておけばいいでしょう。
sub getnum{
my $self=shift;
return join '',@$self;
}
sub length{
my $self=shift;
return scalar @$self;
}
sub getdigits{
my $self=shift;
return @$self;
}
これを使えば簡単なことです。この問題を解くために作ったものだから当然ですが。
my $x=Bignum->new(1);
$x->mul(2) for 1..1000;
my $s=0;
$s+=$_ for $x->getdigits;
print $s,"\n";
まぁコンピュータはこれを一瞬で計算してくれます。
ただ、この問題では気にするほどじゃないけど、実は結構遅いんですよ。
Problem 29を解こうと思い、2
そこで3桁ごとに処理するように改造したらなんとかというぐらい。けど結構厳しい。
まぁ人間の筆算そのままというのはわかりやすいが、コンピュータに都合がいいかはよくわからない。
これはuse Math::Bigint;すべきか…実は標準で付いてるっぽいです。
RubyではBignum、Pythonではlongとかimportするまでもなく使えるんですけどね。
まぁ問題に書いてあるとおりに、素直にコンピュータが計算するというのも1つの方法です。
僕は基本的にそう解いてます。
しかしどうもちょっと整理してみると、かなりすっきりしてしまう問題もあるようです。
コンピュータに規則を打ち込んで、素直に計算させた後にそういう話題を見ましてね。
まぁ計算を高速にするためには整理した方が確かにいいわな。
そこは思いつかんかったわけですが、コンピュータにとってはどっちでも正解ですね。
人がやるなら、整理して簡単にして解くべきでしょうが。