平方根のアルゴリズムを改善、2*10^2000の平方根が1秒台になりました。 これを使って、円周率を約600桁求めるデモを追加しました。
平方根は依然として通常の（平方根の逆数でなく平方根自身を求める）ニュートン法ですが、 逐次近似の各ステップでその段階で有効でない数字はすべて無視すること、 最終的に必要な精度ぎりぎりでゴールインするように意図的に有効桁数を落とし必要最小限の計算しか行わないことで計算量を節約、 約10秒かかった2*10^2000の平方根が1秒台 2*10^4000が約10秒、^6000が約20～30秒です。 100桁であれば一瞬であり、任意の数の平方根が、有効数字100桁の高精度で、一瞬で求まることに相当します。
Mathematical Information Technology の 平方根のアルゴリズムでは、Javaを使った標準的な実装で平方根の計算が「102000でも40秒かかっていない」とありますが、こっちはそれが1秒台。 リンク先のコードはどこも悪いところはなく、Java自身の実装です。 アグレッシブにチューンアップされたJavaScriptは、Javaのお上品なBigIntegerより、何十倍も速く走ることができます。
例示: JavaScriptの浮動小数点演算は15桁程度の有効数字がある。そしてニュートン法では1回ごとに有効桁が倍になる。 単純に考えると、初期値「有効数字15桁」から30、60、90、180、360、720、1440と7回ループして1000桁の精度に至る。 しかし、実際には有効数字8桁から始めれば、同じ7回で16、32、64、128、256、512、1024となって、これでも1000桁の精度が出る。 しかも各ステップでほぼ半分の桁数の計算で済むので、 計算量がざっと半分になる。 つまり、何桁の精度が必要か自動認識して、 その桁数をぎりぎり超過できる必要最小限の条件を内部的に自動設定することで、 トータルの計算量を最適化できる。
円周率の計算はガウス・ルジャンドルでとりあえずやってみました。 所要時間は手元では8～9秒程度です。
[index]