魔術師をめざして

魔術師を目指して、相場・数学・プログラム言語を研究しています。

プログラミング言語ごとの多倍長整数の取り扱い 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 などは試していたのだけどね。これが分かるまでちょっと時間がかかってしまった。同じように悩んでいる人のためにと思ったのだけど、まっ、そんな人はいないか。