バッチファイルでProject Euler（50）

整数の範囲で平方根を求める、すなわち整数Nに対して[√N]を求めます。これは簡単なアルゴリズムで求められます。Nを初期値として、x -> [([N / x] + x) / 2]を繰り返し、値が減少しなくなったら、その前の値が平方根です。例えば、10 -> [(10 / 10 + 10) / 2] = 5 -> [(10 / 5 + 5) / 2] = 3 -> [(10 / 3 + 3) / 2] = 3で、3となります。さて、この繰り返し計算の回数は何回必要でしょうか。
コードを書いて確認しましょう。

@echo off

setlocal enabledelayedexpansion
for /L %%k in (1, 1, 100) do (
    call :num_sqrt_iteration %%k
    echo %%k,!ERRORLEVEL!
)
exit /b 0

:num_sqrt_iteration
    setlocal
    set /a r = %1
    set /a counter = 0
    :loop_sqrt
        set /a r1 = (%r% + %1 / %r%) / 2
        set /a counter += 1
        if %r1% GEQ %r% exit /b %counter%
        set /a r = %r1%
        goto :loop_sqrt

結果を見ればわかるのですが、だいたい回数は多くなっていきます。ただし、平方数のときだけ1下がります。平方数では平方根まで辿りつくのが速くて、それより少し小さいと遅いのです。とにかく最大の数で回数を数えて1回余分にやっておけば確実に収束していることになります。数学的な証明も難しくありません。

:sqrt
    setlocal
    set /a r = %1
    for /L %%k in (1, 1, %num_iter%) do (
        set /a r1 = !r! + %1 / !r!
        set /a r1 /= 2
        if !r1! GEQ !r! exit /b !r!
        set /a r = !r1!
    )

繰り返しの回数が決まれば、このようにforで回すことが可能になります。上の回数を数えたときと同じようにgotoで回したときに比べて、1〜10000まで繰り返したところ4倍くらい速くなりました。意外と速くならないですね。