ScalaでProject Euler（125）

Scala

Problem 85

前々回の方法だと計算量はだいたいO(N1/4)になります。だから、1032くらいが視野に入ってきます。ScalaはBigIntを使うと遅くなるので、型を決めるのは重要です。mはIntで十分です。nはLongが必要です。

それから、sqrtですが、これは引数が大きくなるとDoubleでの計算では不十分になります。例えば、

scala> sqrt((BigInt(1e16.toLong) - 1).toDouble).toInt
res3: Int = 100000000

間違ってますね。これは、Doubleのsqrtの結果を初期値にしていつもの繰り返し計算をすると速いでしょう。

def int_sqrt(n :BigInt) :Long = {
    def f(m :Long) :Long = {
        val m1 = (m + (n / m).toLong) / 2
        if(m1 >= m) m else f(m1)
    }
    
    val m = sqrt(n.toDouble).toLong
    f((m + (n / m).toLong) / 2)
}

繰り返し計算は1、2回しかしないはずですが、その前が遅いはずです。一方、前回の方法はmとnが近いところでは速いです（mが小さいところでは非常に遅い）。ですから、2つの方法のいいとこ取りをすると速くなるはずです。

2*1029で59秒、前々回の方法では77秒でした。意外と速くなりませんね。フォーラム用に書いたPythonではもうちょっと違ったんですが。それから、Pythonの2倍しか速くありませんでした。どこが悪いんでしょうね。