Gauche:Translation:Devlog:正確なsqrt

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

非整数な有理数を忘れて確定的な整数について考えてみましょう。 私は入力の範囲に応じてみっつの場合を扱うことになりました。

FP sqrt を利用する以外に、これはとても簡単です。 もし、正確整数 sqrt の巧みな方法を知っているなら私に知らせて下さい。

正確な有理数のためには、単純に分母と分子の両方に正確整数 sqrt に適用します。 Gauche の有理数計算は全く最適化されていないため、それは正確な有理数を直接にニュートン・ラプソン法で走らせるよりも高速であると推察しています。

ああ、ところで、 R6RS の exact-integer-sqrt は もし入力が整数の正確な平方数でないならば余りも一緒に返します。 それはエキササイズに別のちょっとした楽しみを加えてくれます。

訳注 : この文章での「正確」「不正確」は近似解か否かを表わすように読めてしまいますが (そして実際に部分的にはそうでもあるのですが) 、 Scheme 用語としての exact/inexact に対応する訳語です。


Last modified : 2013/03/20 21:19:21 UTC