プログラミング言語ごとの多倍長整数の取り扱い Scala 編
現在、ぼくは Haskell のどっぷりハマっている。でも、ちょっと前は Scala に取り組んでいた。なにを隠そう Scala に取り組んだおかげで、Haskell の価値に気付くことができたという次第なのだ。
さてこんかいは以前に書いた「プログラミング言語ごとの多倍長整数の取り扱い」という記事に Scala を追加したい。
Scala の多倍長整数演算については Project Euler Problem 20 を例にとって、紹介したいと思う。 Scala 使いにとっては当たり前の事項かもしれないが、ぼくはわからなかったので試行錯誤したのだ。
------------------------------------------
Problem 20 「各位の数字の和 2」
------------------------------------------
n × (n - 1) × ... × 3 × 2 × 1 を n! と表す.
例えば, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800 となる.
この数の各桁の合計は 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 である.
では, 100! の各位の数字の和を求めよ.
■ 解答 in Scala
//-----------------------------------------------------------------
def fact(n: Int): BigInt = if (n < 2) 1 else n * fact(n - 1)
print(fact(100).toString.split("").map(_.toInt).sum)
//-----------------------------------------------------------------
上の2行が Scala による Problem 20 の解答になっていると思うが、本来は以下のようにできるはずと思っていた。
■ 本来の正解
print((1 to 100).reduce(_*_).toString.split("").map(_.toInt).sum)
↑これで、できると思ったけど、ダメだった。(1 to 10) ならうまく行くけど、(1 to 100) だとオーバーフローしちゃうんだよね。最初の解答のように BigInt を使えばいいと思うけど「本来の正解」でなんとかしたい。だけど、どうしたらいいのかまだわからない。
..ということだった。
■ Scala REPL で
scala> (BigInt(1) to 100).product.toString.split("").map(_.toInt).sum
res1: Int = 648
それが、上のようにすればできることがわかったのだ。どこで知ったのかって? いろいろやってみたらできた(笑)。
■ コンパイル用ソースコード
object PE20 extends APP {
print((BigInt(1) to 100).product.toString.split("").map(_.toInt).sum)
}
■ ついでに 1000の階乗
scala> (BigInt(1) to 1000).product
res0: BigInt = 4023872600770937735437024339230039857193748642107146325
43799910429938512398629020592044208486969404800479988610197196058631
66687299480855890132382966994459099742450408707375991882362772718873
25197795059509952761208749754624970436014182780946464962910563938874
37886487337119181045825783647849977012476632889835955735432513185323
95846307555740911426241747434934755342864657661166779739666882029120
73791438537195882498081268678383745597317461360853795345242215865932
01928090878297308431392844403281231558611036976801357304216168747609
67587134831202547858932076716913244842623613141250878020800026168315
10273418279777047846358681701643650241536913982812648102130927612448
96359928705114964975419909342221566832572080821333186116811553615836
54698404670897560290095053761647584772842188967...
まぁ、わかってしまえば簡単ということだった。
(1.toBigInt to 100).product などは試していたのだけどね。これが分かるまでちょっと時間がかかってしまった。同じように悩んでいる人のためにと思ったのだけど、まっ、そんな人はいないか。