¿Cuál es la lógica detrás del algoritmo de división de Fourier?

Question

de Wikipedia: fourier division.

Aquí está una captura de pantalla de la misma: (view in full-resolution)

¿Cuál es la lógica detrás de este algoritmo?

Sé que se puede utilizar para dividir números muy grandes, pero ¿cómo funciona exactamente?

Answer 1

esto parece ser una transformación inteligente del algoritmo de Long Division. Las partes inteligentes parecen ser que solo están usando la operación de división para el primer "dígito", a1, y evitan tener que usar las otras a (x) de la misma manera, aplicándolas en el siguiente paso restando sus producto (contra el cociente parcial) del resto provisional.

Que esto puede hacerse válidamente y que siempre funciona es probablemente debido a que los "dígitos" (base 100, en este caso) no son dígitos reales y legítimamente pueden asumir valores mayores que su base (es decir, más de 100) e incluso menos de cero. Esto permite una mayor flexibilidad en el tiempo de aplicación de cada "dígito" a la operación como, por ejemplo, difiriendo la aplicación de los dígitos secundarios del divisor (a (x> 1)) hasta que se crea un cociente parcial desde el la división del paso anterior por un (1), que a su vez permite que se apliquen como una resta de producto, en lugar de una operación de división.

Answer 2

Es un algoritmo extremadamente inteligente. No me puedo imaginar cómo el viejo JF logró hacerlo, ya que la relación de recurrencia es extremadamente difícil de ver incluso cuando sabes que existe. En mi opinión, formalizó un método que estaba usando para hacer divisiones a mano: debe haber hecho un gran número de cálculos a mano en la era anterior a las calculadoras digitales, y probablemente prefirió ser más exacto que usar una regla de cálculo, solo para estar seguro.

Es cierto que uno puede ver vagamente el esquema del método en el inicio del algoritmo de división larga estándar, pero esa es la única pista. Podrías buscar mucho y más tiempo para esta recurrencia sin verlo. Hay tantos números involucrados que se confunde al mirar las relaciones.

Hay otra intuición que se obtiene al estudiar el flujo de datos en el algoritmo de multiplicación estándar. Si lo escribe en hardware, puede ver que una matriz cuadrada de unidades multiplicativas de 8 bits toma dos números de 32 bits dispuestos a lo largo de su lado inferior y derecho y mueve los datos hacia arriba y hacia la izquierda, saliendo en el borde superior del matriz en una respuesta de 64 bits. La unidad situada más a la izquierda entrega los dos dígitos superiores (8 bits) del producto, usando los dígitos superiores de los multiplicandos y los lleva desde el resto de la matriz a la derecha. ¿OKAY? Bueno, imagine que la matriz se ejecuta en reversa para tomar como entrada el divisor de 64 bits a lo largo del borde superior y un divisor de 32 bits, por ejemplo a lo largo del borde derecho de la matriz. Luego, emite el cociente de 32 bits a lo largo del borde inferior (también se debe generar un resto ... olvídate del mo). Ahora la unidad superior izquierda de la matriz toma IN los dos dígitos superiores del dividendo desde la parte superior de la matriz, el dígito superior del divisor desde el lado derecho de la matriz, y emite el dígito superior del cociente ABAJO en el array (y la parte inferior) y un resto RIGHTWARDS en la matriz.

Whew! Eso fue solo para la primera salida de dígitos. Es solo el comienzo. El genio de Fourier fue ver cómo uno puede alimentar los residuos acumulados para mantener las entradas limitadas a solo tres dígitos (digamos 8 bits), y el resultado a solo dos dígitos (digamos 8 bits) para cada unidad en el modificado matriz multiplicativa que se ejecuta en reversa (que ahora podemos llamar una matriz de división).

Y, por supuesto, así es como podemos hacer la división en hardware, no se requiere microcódigo, en una ALU de computadora.

Al menos, supongo que este método se utiliza cuando se ha evitado el microcódigo en favor de unos pocos miles de millones de transistores. No conozco el interior de las últimas CPU, pero tienen transistores para grabar.