ウィキペディアから:フーリエ除算.
これは同じスクリーンショットです:
(フル解像度で表示)
このアルゴリズムの背後にあるロジックは何ですか?
非常に大きな数の割り算に使用できることは知っていますが、正確にはどのように機能するのでしょうか?
2706 次
2 に答える
5
これは、筆算アルゴリズムの巧妙な変換のようです。賢い部分は、最初の「桁」a1に対してのみ除算演算を使用し、次のステップでそれらを減算して適用することにより、他のa（x）を同じように使用する必要がないことです。中間剰余からの（部分商に対する）積。
これが有効に実行でき、常に機能するのは、おそらく「桁」（この場合は基数100）が実際の桁ではなく、基数より大きい値（つまり、100を超える値）を合法的に想定できるためです。 ）そしてゼロ未満ですら。これにより、たとえば、除数（a（x> 1））の2桁目の適用を、部分商が作成されるまで延期するなど、各「桁」の適用のタイミングをより柔軟に操作できます。前のステップのa（1）による除算。これにより、除算演算ではなく、積の減算として適用できます。
于 2009-09-22T06:24:46.120 に答える
4
非常に巧妙なアルゴリズムです。存在は知っていても再帰関係を見つけるのは非常に難しいため、古いJFがどうやってそれを手に入れたのか想像できません。私の意見では、彼は手書きで除算を行うために使用していた方法を形式化しました。デジタル計算機が登場する前の時代に、彼は膨大な数の計算を手作業で行っていたに違いありません。
確かに、標準的な長除算アルゴリズムの冒頭でメソッドの概要がぼんやりと見えますが、それが唯一の手がかりです。この再発を確認せずに、長く懸命に検索することもできます。非常に多くの数値が関係しているため、関係を見ると混乱します。
標準的な乗算アルゴリズムのデータの流れを調べると、別の直感が得られます。コンピューター ハードウェアで書き出すと、8 ビットの乗法単位の正方配列が、下辺と右辺に沿って配置された 2 つの 32 ビット数値を取り、データを上下に移動し、上端で終了することがわかります。 64 ビットの回答の配列。最上部の左端のユニットは、被乗数の上位桁を使用して、積の上位 2 桁 (8 ビット) を提供し、残りの配列からその右側にキャリーインします。わかった？さて、配列が逆に実行され、上端に沿って 64 ビットの被除数と、配列の右端に沿って 32 ビットの除数が入力として取り込まれることを想像してください。次に、下端に沿って 32 ビットの商を出力します (剰余も生成する必要があります.. ちょっと忘れてしまいます)。
うわー！それは最初の桁の出力のためだけでした。まだ始まったばかりです。フーリエの天才は、入力をわずか 3 桁 (たとえば 8 ビット) に制限し、出力を修正されたすべての単位に対してわずか 2 桁 (たとえば 8 ビット) に制限するために、累積剰余をどのようにフィードできるかを確認したことにありました。逆に実行される乗法配列 (現在、除算配列と呼ぶことができます)。
そしてもちろん、これがコンピューターの ALU で、マイクロコードを必要とせずにハードウェアで除算を行う方法です。
少なくとも、この方法は、数十億個のトランジスタを優先してマイクロコードを避けた場合に使用されると思います。私は最新の CPU の内部に詳しいわけではありませんが、それらには燃焼させるトランジスタがあります。
于 2010-10-02T09:34:41.737 に答える