8

私は、円と線 ( Constructable Numbers ) を含む 2D ユークリッド幾何学の二次制約を解決し、結果をグラフィカルに表現するためのアプリケーションに取り組んでいます。このような問題を二分木で表すことに関するこの論文を見つけましたが、実装の問題に直面しています。

a + b*sqrt(c)より小さい、より大きい、等しいという標準的な関係演算の形式の数値を比較する必要があります。c私のアプリケーションのの値は、、、、、、、またはに制限さ2れています。例 (C に似た疑似コードは、"to the power of" 演算子です):356101530^

boolean CompareConstructibleNumbers(int a1, b1, c1, a2, b2, c2)
{
    return a1plusb1sqrtc1_is_greater_than_a2plusb2sqrtc2 = 
        4 * ((a1 - a2)^2) * (b1^2) * c1
          > ((b2^2) * c2 - (b1^2) * c1 - (a1 - a2)^2)^2;
        // Not sure if I have the direction right for >
}

この単純な実装では、何度も乗算する必要があるため、32 ビット整数は 64 ビット整数になり、次に 128 ビットなどになります。比較。

また、フロートを使用しないことを好み、フロートとして直接計算しようとする際の丸め誤差のリスクを回避したいと考えていますsqrt(c)。このアプリケーションには正確な計算が必要であり、必ずしも無限の精度ではありませんが、丸め誤差を回避して正しい結果を保証したいと考えています。

a + b * sqrt(c)巨大な中間整数値を必要とせずに、フォームの構成可能な数値を比較するにはどうすればよいですか? aとの初期値bは 32 ビットの範囲です。

****UPDATE**** 返信ありがとうございます。連分数を追求するという提案に続いて、基本再帰式を使用して、平方根の任意の正確な近似値を生成することができました。

また、実数の近似値と固定小数点表現を整数で乗算することによる誤差の累積について説明しているこの論文も見つけました。幸いなことに、私が関心のあるすべての平方根の整数部分は最大で 6 (必要なのは 3 ビットのみ) であるため、近似のために小数部分を表すために使用できるビットがたくさんあります。32 ビット整数による乗算では、乗算後に誤差を 1 ビットに保つために、Q3.32ビットの最小固定小数点近似が必要です。

したがって、53 ビットの精度doubleは平方根の十分に正確な近似値を格納するのに十分ですが、32 ビットの整数を掛けた後の結果を格納するには十分ではありません。エラー。cと 32ビット整数の 64 ビット整数 (Q16.48 など) の固定小数点表現をb使用して、96 ビットまたは 128 ビットの数値でマルチワード演算を使用して、十分なエラーを発生させずに比較を行う予定です。結果。これらの 7 平方根のみを使用する構成可能な数を比較するには、これで十分な精度であると確信していますが、セカンドオピニオンに興味があります。何かご意見は？

4

1 に答える 1

3

値が完全な 32 ビットを使用すると仮定して、正確な比較のために 64 ビット以内にとどまる式はないと思います。私が見た問題は、 a+b*sqrt(c) の形式の数値が実数で密集しているため (c が正方形でないと仮定して)、多くの精度を必要とする非常に微妙な比較が得られることです。したがって、基本的には、3 つの乗算を使用する 2 乗によって平方根を取り除く必要があります。

この場合の BigInt 実装は、実際にはそれほど悪くはありません。実装する必要があるのは、乗算、加算、減算、および比較だけだからです。これらは、ごくわずかなコード行で効率的に実装できます。通常、実装するのが煩わしいのは除算です。さらに、数値が 2 つの 64 ビット セルで配列をオーバーフローすることは決してないことがわかっているので、積のビット数を実際に追跡する必要はありません。

編集: Thomas と Nemo のコメントで提案されている double の使用に関しては、連分数表現を使用して sqrt(2) の 2^{-53} の範囲内で 32 ビットの int を使用して近似を見つけるのは実際には非常に簡単です。

于 2013-01-07T05:37:38.257 に答える