Was ist die Logik hinter dem Fourier-Divisionsalgorithmus?

Question

von Wikipedia: fourier division. Hier

ist ein Screenshot von der gleichen: (view in full-resolution)

Was ist die Logik hinter diesem Algorithmus?

Ich weiß, es kann verwendet werden, um sehr große Zahlen zu teilen, aber wie genau funktioniert es?

Answer 1

Dies scheint eine clevere Transformation des Long Division-Algorithmus zu sein. Die schlauen Teile scheinen zu sein, dass sie nur die Divisionsoperation für die erste "Ziffer" a1 verwenden und vermeiden, dass sie die anderen a (x) auf die gleiche Weise verwenden müssen, indem sie sie im nächsten Schritt anwenden, indem sie ihre subtrahieren Produkt (gegen den Teilquotienten) aus dem Zwischenrest.

Dass dies gültig gemacht werden kann und dass es immer funktioniert, liegt wahrscheinlich daran, dass die "Ziffern" (Basis 100, in diesem Fall) keine echten Ziffern sind und berechtigterweise Werte annehmen können, die größer sind als ihre Basis (dh über 100) und sogar weniger als Null. Dies erlaubt eine grßere Flexibilität bei der Zeitgabe der Anwendung jeder "Ziffer" auf die Operation, wie beispielsweise das Aufschieben der Anwendung der sekundären Ziffern des Divisors (a (x> 1)), bis nach dem Erzeugen eines partiellen Quotienten aus der Teilung des vorherigen Schritts durch a (1), was wiederum zulässt, dass sie als Produktsubtraktion und nicht als Teilungsoperation angewendet werden.

Answer 2

Es ist ein extrem cleverer Algorithmus. Ich kann mir nicht vorstellen, wie sehr es JF gelungen ist, davon zu profitieren, da die Rückkehrbeziehung extrem schwer zu erkennen ist, selbst wenn man weiß, dass sie existiert. Meiner Meinung nach hat er eine Methode formalisiert, mit der er lange Zeit Divisionen machte - er musste im Zeitalter vor den digitalen Taschenrechnern sehr viele Berechnungen von Hand gemacht haben, und wahrscheinlich zog er es vor, genau zu sein, um einen Rechenschieber zu benutzen.

Es ist wahr, dass man den Umriss der Methode am Anfang des Standard-Langdivisionsalgorithmus vage sehen kann, aber das ist der einzige Anhaltspunkt. Sie könnten lange und intensiv nach dieser Wiederholung suchen, ohne sie zu sehen. Es gibt so viele Zahlen - es wird verwirrend, wenn man die Beziehungen betrachtet.

Es gibt eine andere Intuition, die man aus der Untersuchung des Datenflusses im Standard-Multiplikationsalgorithmus gewinnen kann. Wenn Sie es in Computerhardware schreiben, können Sie sehen, dass ein quadratisches Array von 8-Bit-multiplikativen Einheiten zwei 32-Bit-Zahlen entlang ihrer unteren und rechten Seite nimmt und die Daten nach oben und links bewegt, wobei sie an der oberen Kante des Array in einer 64-Bit-Antwort. Die oberste Einheit ganz links liefert die oberen ZWEI (8-Bit) -Ziffern des Produkts, wobei die obersten Ziffern der Multiplikanden verwendet werden und vom Rest des Arrays nach rechts geführt werden. OK? Nun, stell dir vor, dass das Array rückwärts läuft, um den 64-Bit-Divident entlang der oberen Kante und einen 32-Bit-Divisor, etwa entlang der rechten Kante des Arrays, als Eingabe zu nehmen. Dann gibt es den 32-Bit-Quotienten entlang der unteren Kante aus (ein Rest muss ebenfalls erzeugt werden. Vergessen Sie ihn für die MO). Jetzt nimmt die oberste linke Einheit im Array die obersten zwei Ziffern des Dividenden vom oberen Teil des Arrays, die oberste Ziffer des Divisors von der rechten Seite des Arrays, und gibt die oberste Ziffer des Quotienten DOWNWARDS in die Array (und aus dem unteren) und ein Rest RIGHTWARDS in das Array.

Puh! Das war nur für die erste Ziffernausgabe. Es ist nur der Anfang. Fouriers Genialität bestand darin, zu sehen, wie man die sich anhäufenden Reste einspeisen kann, um die Eingaben auf nur drei (z. B. 8-Bit) Ziffern zu begrenzen, und das outut auf nur zwei (z. B. 8-Bit) Ziffern für jede Einheit in der modifizierten multiplikatives Array, das rückwärts läuft (das können wir jetzt ein Division-Array nennen).

Und natürlich, so können wir Division in Hardware, keine Mikrocode erforderlich, in einem Computer ALU.

Zumindest nehme ich an, dass diese Methode dort verwendet wird, wo Microcode zugunsten einiger weniger Milliarden Transistoren vermieden wurde. Ich bin nicht in das Innere der neuesten CPUs eingeweiht, aber sie haben Transistoren zu brennen.