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

Question

de Wikipedia:. división de Fourier

Esta es una captura de pantalla de la misma: ( vista en resolución completa )

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

Sé que puede ser usado para dividir un número muy grande, pero ¿Cómo funciona exactamente?

Answer 1

esto parece ser una transformación inteligente del algoritmo de la división larga. Las partes inteligentes parece ser que sólo están utilizando la operación de división para la primera "dígito", a1, y evitar tener que utilizar el otro a (x) 's de la misma manera mediante la aplicación de ellos en la siguiente etapa restando su producto (contra el cociente parcial) del resto provisional.

Que esto se puede hacer de forma válida y que siempre funciona es probablemente debido al hecho de que los "dígitos" (base 100, en este caso) no son cifras reales y legítimamente pueden asumir valores mayores que tanto su base (es decir, , más de 100) e incluso menor que cero. Esto permite una mayor flexibilidad en la temporización de la 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 después de un cociente parcial se crea a partir de la división del paso previo de un (1), que a su vez les permite ser aplicados como una resta producto, en lugar de una operación de división.

Answer 2

Es un algoritmo muy inteligente. No me puedo imaginar cómo ol' JF consiguió hld de ella desde therecurrence relación es extremadamente difícil de ver, incluso cuando kknow existe. En mi opinión se formaliza un método que utilizaba para hacer longhand división - debe haber hecho un gran número de cálculos a mano en la era antes de calculadoras digitales, y lo más probable es preferido ser exacta sobre el uso de una regla de cálculo, sólo para estar seguro.

Es cierto que uno puede ver vagamente el contorno del método en el inicio del algoritmo de división de tiempo estándar, pero esa es la única pista. Se podría buscar mucho para esta recurrencia sin verlo. Hay tantos números implicados - se vuelve confuso mirando las relaciones

.

Hay otra intuición que se derivan de estudiar el flujo de datos en el algoritmo de multiplicación estándar. Si usted lo escribe en hardware, se puede ver que una matriz cuadrada de unidades multiplicativos de 8 bits tiene dos números de 32 bits dispuestos a lo largo de su parte inferior y los lados derecho e mueve los datos arriba ya la izquierda, saliendo en el borde superior de la matriz en una respuesta de 64 bits. La unidad más a la izquierda superior ofrece los mejores dos dígitos (8 bits) del producto, el uso de los dígitos superiores de los multiplicandos y llevar desde el resto de la matriz a su derecha. ¿De acuerdo? Bueno, imagina la matriz por el reverso de tomar como entrada la divident 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. A continuación, se da salida al cociente de 32 bits a lo largo del borde inferior (un resto necesita ser generada también .. olvidar aboutit para el mo). Ahora la unidad superior izquierda de la matriz de toma entre los dos primeros dígitos del dividendo de la parte superior de la matriz, el dígito superior del divisor de la parte derecha de la matriz, y emite el dígito superior del cociente hacia abajo en el array (y fuera de la parte inferior) y un resto hacia la derecha en la matriz.

¡Menos mal! Eso fue sólo para la primera salida dígitos. Es sólo el comienzo. El genio de Fourier estaba en ver cómo se puede alimentar en los desechos que se acumulan con el fin de mantener a los insumos limitados a sólo tres dígitos (por ejemplo de 8 bits), y la outut a tan sólo dos dígitos (por ejemplo 8 bits) para cada unidad de la modificación array multiplicativo que se ejecuta en inversa (que podemos llamar una matriz de división de ahora).

Y, por supuesto, eso es lo que podemos hacer una división en hardware, no requiere de microcódigo, en una ALU ordenador.

Al menos, supongo que este método se utiliza cuando microcódigo se ha dejado de lado a favor de un poco más de mil millones de transistores. No estoy al tanto al interior de las últimas CPUs, pero tienen transistores para quemar.