Gauche:Translation:Devlog:正確なsqrt
(原文: Exact sqrt)
数ヶ月前、ユーザのひとりが私に尋ねました。 何故 (sqrt 4) が 2.0 になるのか、引数が正確な平方数なら結果は正確な数値であるべきではと。
はい、そうなるべきですが、結果を不正確数に変換することは R5RS では許されていると私は信じています。 それはただ単に私が怠け者で、「問題が起こったときに修正しよう」と考えていたからです。 時が来たようです。
入力が正確な値の平方であった場合に正確な値を返す「適切な」 sqrt の実装は興味深い小さなエクササイズになることがわかりました。 それは有理数を含みます。 たぶん、それはコンピューターサイエンス新入生のための良いクイズでしょう。 もし、実装したことがないなら、考えてみて下さい。
ここに現在の Gauche での結果です。 (長い桁の値は折り返されています。)
gosh> (sqrt 144) 12 gosh> (sqrt 169/81) 13/9 gosh> (sqrt 340282366920938463463374607431768211456) 18446744073709551616 gosh> (sqrt 32317006071311007300714876688669951960444102669 71548403213034542752465513886789089319720141152291346368871 79609218980194941195591504909210950881523864482831206308773 67300996091750197750389652106796057638384067568276792218642 61975616183809433847617047058164585203630504288757589154106 58086075523991239303855219143333896683424206849747865645694 94856176035326322058077805659331026192708460314150258592864 17711672594360371846185735759835115230164590440369761323328 72312271256847108202097251571017269313234696785425806566979 35045997268352998638215525166389437335543602135433229604645 318478604952148193555853611059596230656) 17976931348623159077293051907890247336179769789423065727343 00811577326758055009631327084773224075360211201138798713933 57658789768814416622492847430639474124377767893424865485276 30221960124609411945308295208500576883815068234246288147391 31105408272371633505106845862982399472459384797163048353563 29624224137216
非整数な有理数を忘れて確定的な整数について考えてみましょう。 私は入力の範囲に応じてみっつの場合を扱うことになりました。
- 入力の範囲が 2^52 以下である場合、整数は IEEE 倍精度浮動小数点数で確定的に表すことができ、 FP sqrt は我々が知るような整数を生成すればそれが結果です。 現代的なハードウェアで高速な FP sqrt です。(編集:この部分は、2013年3月20日午前2時14分15秒UTC、マーク·H·ウィーバーのおかげで修正されています。このエントリを参照してください。)
- そうでなければ正確な演算でニュートン・ラプソン法を実行します
- 入力が IEEE 倍精度で表現可能な場合 (例えば 2.0^1024 付近の場合) FP sqrt によって近似結果を得られ、最初の近似値としてそれに近い整数を使います。
- そうでなければ 2^floor((log2(input)+1)/2) を最初の近似値として使います。 log2(input) は高速に計算できるからです。
FP sqrt を利用する以外に、これはとても簡単です。 もし、正確整数 sqrt の巧みな方法を知っているなら私に知らせて下さい。
正確な有理数のためには、単純に分母と分子の両方に正確整数 sqrt に適用します。 Gauche の有理数計算は全く最適化されていないため、それは正確な有理数を直接にニュートン・ラプソン法で走らせるよりも高速であると推察しています。
ああ、ところで、 R6RS の exact-integer-sqrt は もし入力が整数の正確な平方数でないならば余りも一緒に返します。 それはエキササイズに別のちょっとした楽しみを加えてくれます。
訳注 : この文章での「正確」「不正確」は近似解か否かを表わすように読めてしまいますが (そして実際に部分的にはそうでもあるのですが) 、 Scheme 用語としての exact/inexact に対応する訳語です。