División de caída de manzana

[Paul Curtis] en Segger tiene una serie interesante de publicaciones de blog sobre el cálculo de la división. Este solía ser un tema candente, pero muchas computadoras ahora tienen soporte integrado para multiplicación y división. Pero algunos procesadores carecen de las instrucciones y una biblioteca para hacerlo podría ser menos que ideal. Saber cómo rodar los suyos puede permitirle optimizar la velocidad o el espacio. La parte actual cubre el uso del algoritmo de Newton para hacer una división.

Steve Martin tenía un artículo famoso sobre cómo ser millonario y nunca pagar impuestos. Comenzó diciendo: "Primero ... obtén un millón de dólares. Luego ...". Este método es un poco así, porque primero debes saber cómo multiplicar antes de poder dividir. La premisa básica es doble: el método de Newton te deja refinar una estimación de recíproco por multiplicaciones sucesivas y luego multiplicar un número recíproco es lo mismo que dividir. En otras palabras, si necesitamos dividir 34 entre 6, podrías reescribir 36/6 a 36 * 1/6 y la respuesta es el mismo.

La aproximación de Newton para recíprocos le permite adivinar la respuesta y luego refinarla mediante una serie de multiplicaciones. Cada multiplicación crea una mayor precisión. Puede usar esto para realizar un cambio clásico de velocidad / espacio. Por ejemplo, supongamos que queremos encontrar el recíproco de un byte (presumiblemente un byte de punto fijo). Una tabla de búsqueda de 256 elementos daría una precisión perfecta y sería muy rápida. No más matemáticas. Pero, ¿qué pasa con los 32 bits? Ahora la mesa es demasiado grande. Pero podría buscar, por ejemplo, los primeros 8 bits del número de 32 bits. O más. O menos. Depende de lo que te importe.

Así que ahora tienes una mala calificación de tu reciprocidad. El Sr. Issac puede mejorarlo. Por algún número a, Toma su calificación (X) y multiplicarlos juntos. Reste ese número de 2 y tendrá un factor para multiplicar su calificación anterior para obtener una nueva calificación. En el futuro, está claro que si su estimación fuera correcta, la multiplicación le daría un 1 que no cambiaría la estimación anterior en absoluto. Si la calificación está desactivada, recibirá un factor de escala.

Como fórmula, se ve así:

x=x*(2-a*x);

Entonces, si decides que el recíproco de 22 podría ser .02, el primer paso te dará:

0.02*(2-22*0.02) = .0312

.0312*(2-22*.0312) = .0410

.0410*(2-22*.0410) = 0.0450

La respuesta correcta es un decimal repetido 0.0454545 y si continúa, llegará allí.

Por supuesto, entonces tienes que multiplicar una vez más para hacer la división.

Nos gustó que la publicación tenga una implementación de punto fijo y luego examina el código ensamblador resultante para ARM, RISC-V y dsPIC30. Bien leído.

Nos encantan los trucos matemáticos que podemos usar en lenguaje ensamblador. Si está trabajando en AVR y punto flotante, no se pierda este método.

Gloria Vega
Gloria Vega

Deja una respuesta

Tu dirección de correo electrónico no será publicada.