フーリエ除算アルゴリズムの背後にあるロジックは何ですか?

Question

ウィキペディアより: フーリエ除算.

以下は同じスクリーンショットです。 (フル解像度で見る)

このアルゴリズムの背後にあるロジックは何ですか?

非常に大きな数を除算するために使用できることは知っていますが、 正確にはどのように機能しますか？

Answer 1

これは、Long Division アルゴリズムを賢く変形したものと思われます。賢い部分は、最初の「数字」 a1 に対してのみ除算演算を使用しており、他の a(x) を次のステップで減算して適用することで同じように使用する必要がないことです。中間剰余からの積（部分商に対する）。

これが有効に実行でき、常に機能するのは、おそらく、「数字」(この場合は基数 100) が実際の数字ではなく、基数より大きい値 (つまり、100 を超える値) を正当に想定できるという事実によるものです。 )、さらにはゼロ未満です。これにより、たとえば、除数の 2 番目の桁 (a(x>1)) の適用を、前のステップの a(1) による除算により、除算演算ではなく積の減算として適用できるようになります。

Answer 2

非常に賢いアルゴリズムです。再発関係が存在することはわかっていても、それを確認するのは非常に難しいため、昔の JF がどうやってそれを把握できたのか想像できません。私の意見では、彼は割り算を手書きで行うために使用していた方法を形式化したものです。デジタル電卓が登場する前の時代に、彼は膨大な数の計算を手で行っていたに違いありません。念のため言っておきますが、計算尺を使うより正確であることを好んだのでしょう。

確かに、標準的な長分割アルゴリズムの冒頭で手法の概要がなんとなく見えますが、それが唯一の手掛かりです。この再発を見つけることなく、長く懸命に検索することもできます。関係する数字が非常に多く、関係を見ると混乱してしまいます。

標準的な乗算アルゴリズムのデータの流れを研究することで得られるもう 1 つの直観があります。これをコンピュータ ハードウェアで書き出すと、8 ビット乗算単位の正方配列が下辺と右辺に沿って配置された 2 つの 32 ビット数値を受け取り、データを上と左に移動して、上端で終了することがわかります。 64 ビットの応答の配列。一番左のユニットは、被乗数の上位の桁を使用して、積の上位 2 桁 (8 ビット) を提供し、配列の残りの部分から右側にキャリーインします。わかりました？さて、配列が逆に実行されて、上端に沿った 64 ビットの除数と、たとえば配列の右端に沿った 32 ビットの除数を入力として受け取ると想像してください。次に、下端に沿って 32 ビットの商を出力します (剰余も生成する必要があります)。しばらく忘れてください）。ここで、配列の一番左のユニットは、配列の先頭から被除数の上位 2 桁を入力し、配列の右側から除数の上位 1 桁を取得し、商の上位 1 桁を下向きに出力します。配列 (および一番下) と残りを右方向に配列します。

ふぅ！これは最初の桁の出力のみでした。それはほんの始まりにすぎません。フーリエの天才は、修正されたユニットごとに入力をわずか 3 (たとえば 8 ビット) 桁に制限し、出力をわずか 2 (たとえば 8 ビット) 桁に制限するために、累積した剰余をどのように入力できるかを考えたことにあります。逆方向に実行される乗算配列 (現在は除算配列と呼ぶことができます)。

そしてもちろん、これにより、マイクロコードを必要とせず、コンピューター ALU でハードウェアで除算を実行できるようになります。

少なくとも、この方法は、さらに数十億個のトランジスタを優先してマイクロコードが使用されない場合に使用されると思います。最新の CPU の内部については詳しくありませんが、CPU には燃焼するトランジスタが搭載されています。