s0128x86-64 アセンブリ言語でコード ライブラリを作成して、 、s0256、s0512、s1024符号付き整数型およびf0128、f0256、f0512、f1024浮動小数点型のすべての従来のビット単位、シフト、論理、比較、算術、および数学関数を提供しています。浮動小数点関数は、整数型用に作成された内部ルーチンを呼び出す可能性が高いため、ここまでは符号付き整数型に取り組んでいます。
これまで、さまざまな単項演算子、比較演算子、および加算、減算、乗算の各演算子を実行する関数を作成してテストしてきました。
現在、除算演算子の関数を実装する方法を決定しようとしています。
私の最初の考えは、「ニュートン・ラフソンが最善のアプローチに違いない」というものでした。なんで？適切なシード (最初の推測) が与えられると非常に迅速に収束するため、オペランドでネイティブの 64 ビット除算命令を実行して優れたシード値を取得する方法を理解できるはずです。実際、シード値が 64 ビットまで正確である場合、正しい答えを得るには次のようにする必要があります。
`s0128` : 1~2 iterations : (or 1 iteration plus 1~2 "test subtracts")
`s0256` : 2~3 iterations : (or 2 iterations plus 1~2 "test subtracts")
`s0512` : 3~4 iterations : (or 3 iterations plus 1~2 "test subtracts")
`s1024` : 4~5 iterations : (or 4 iterations plus 1~2 "test subtracts")
しかし、この質問についてもう少し考えてみると、私は疑問に思います。たとえば、すべての大きな整数型に対して乗算演算を実行する、私が書いたコア ルーチンを思い出します。
s0128 : 4 iterations == 4 (128-bit = 64-bit * 64-bit) multiplies + 12 adds
s0256 : 16 iterations == 16 (128-bit = 64-bit * 64-bit) multiplies + 48 adds
s0512 : 64 iterations == 64 (128-bit = 64-bit * 64-bit) multiplies + 192 adds
s1024 : 256 iterations == 256 (128-bit = 64-bit * 64-bit) multiplies + 768 adds
ループがかなり短く効率的 (キャッシュを含む) であるにもかかわらず、より広いデータ型の操作の増加はかなりのものです。このループは、結果の各 64 ビット部分を 1 回だけ書き込み、その後の処理のために結果のどの部分も読み戻すことはありません。
これにより、特に大きな型の場合、従来のシフトと減算型の除算アルゴリズムの方が高速になるのではないかと考えるようになりました。
私の最初の考えはこれでした：
result = dividend / divisor // if I remember my terminology
remainder = dividend - (result * divisor) // or something along these lines
#1: 各ビットを計算するには、通常、除数が被除数以下の場合、被除数から除数を減算します。通常、最も重要な 64 ビット部分を検査するだけで、除数が被除数より確実に小さいか、または大きいかを判断できます。これらの ms64 ビット部分が等しい場合にのみ、ルーチンは次の下位 64 ビット部分をチェックする必要があり、それらが等しい場合にのみさらに下位をチェックする必要があります。したがって、ほぼすべての反復 (結果の各ビットを計算する) で、このテストを計算するために実行される命令を大幅に減らすことができます。
＃2：しかし...平均して、約50％の確率で、被除数から除数を引く必要があることがわかります。とにかく、幅全体を引く必要があります。この場合、実際には従来のアプローチよりも多くの命令を実行しました (最初にそれらを減算し、次にフラグをテストして除数 <= 被除数かどうかを判断します)。したがって、半分の時間は節約を実現し、半分の時間は損失を実現します。s1024(16 ～ 64 ビットのコンポーネントを含む) のような大きな型では、大幅な節約と損失が小さいため、このアプローチは大幅な正味の節約を実現するはずです。(-2- 64 ビット コンポーネントを含む) のような小さな型s0128では、節約はわずかであり、大きな損失ではありませんが、大きなものではありません。
したがって、私の質問は、「最も効率的な除算アルゴリズムは何ですか」ということです。
#1: modern x86-64 CPUs like FX-8350
#2: executing in 64-bit mode only (no 32-bit)
#3: implementation entirely in assembly-language
#4: 128-bit to 1024-bit integer operands (nominally signed, but...)
注: 私の推測では、実際の実装は符号なし整数でのみ動作します。乗算の場合、負のオペランドを正に変換してから符号なし乗算を実行し、元のオペランドが 1 つでも負であれば結果を否定する方が簡単で効率的であることが (おそらく) 判明しました。ただし、効率的である場合は、符号付き整数アルゴリズムを検討します。
注: 浮動小数点型 ( f0128、f0256、f0512、f1024) の最良の答えが異なる場合は、その理由を説明してください。
注: これらすべての整数データ型に対して乗算演算を実行する内部コアの unsigned-multiply ルーチンは、倍幅の結果を生成します。言い換えると：
u0256 = u0128 * u0128 // cannot overflow
u0512 = u0256 * u0256 // cannot overflow
u1024 = u0512 * u0512 // cannot overflow
u2048 = u1024 * u1024 // cannot overflow
私のコード ライブラリには、符号付き整数データ型ごとに 2 つのバージョンの乗算が用意されています。
s0128 = s0128 * s0128 // can overflow (result not fit in s0128)
s0256 = s0256 * s0256 // can overflow (result not fit in s0256)
s0512 = s0512 * s0512 // can overflow (result not fit in s0512)
s1024 = s1024 * s1024 // can overflow (result not fit in s1024)
s0256 = s0128 * s0128 // cannot overflow
s0512 = s0256 * s0256 // cannot overflow
s1024 = s0512 * s0512 // cannot overflow
s2048 = s1024 * s1024 // cannot overflow
これは、「精度を失わない」および「オーバーフローしない」という私のコード ライブラリのポリシーと一致しています (精度の低下またはオーバーフロー/アンダーフローが原因で回答が無効な場合、エラーが返されます)。ただし、倍幅の戻り値関数が呼び出された場合、そのようなエラーは発生しません。