ScalaでProject Euler(34)

Problem 16

PythonScala多倍長整数の性能を比較してみます。3を自乗して9、9を自乗して81、という操作を繰り返します。

import time

def test():
    t0 = time.clock()
    n = reduce(lambda x, y: x * x, xrange(N), 3)
    print n % 100
    return time.clock() - t0

N = 20
print [ int(test() * 1000) for k in range(10) ]
import scala.testing.Benchmark

object Test extends Benchmark {
    def run() = {
        val n = (1 to N).foldLeft(BigInt(3))((x, y) => x * x)
        println (n % 100)
    }
}

val N = 20
println (Test.runBenchmark(10))

PythonScalaでは実行時間が全然違います。PythonはNが1増すと3倍時間がかかるので、Karatsuba法を使っているようなのですが、Scalaは4倍です。すなわち、ふつうに計算しているってことですね。基本的にScalaで大きな整数を扱ってはいけないようです。