[Paul Curtis] sobre Segerger tiene una serie interesante de publicaciones de blog sobre el cálculo de la división. Esto solía ser un tema más caliente, pero hoy en día, muchas computadoras o idiomas de computadora tienen soporte para la multiplicación y la división incorporada. Pero algunos procesadores carecen de las instrucciones y una biblioteca para hacerlo podría ser menos que ideal. Saber cómo rodar el suyo podría permitirle optimizar la velocidad o el espacio. La cubre la a plazos actuales utiliza el algoritmo de Newton para hacer la división.
Steve Martin tuvo un poco de cómo ser millonario y nunca pagar impuestos. Comenzó diciendo: “Primero … obtener un millón de dólares. Entonces … “Este método es un poco así, ya que primero tiene que saber cómo multiplicarse antes de que pueda dividir. La premisa básica es doble: el método de Newton le permite refinar una estimación de un recíproco por multiplicaciones sucesivas y luego multiplicar a un número un reciprocal es el mismo que dividir. En otras palabras, si necesitamos dividir 34 a 6, puede reescribir 34/6 a 34 * 1/6 y la respuesta es la misma.
La aproximación de Newton para reciprocales le permite adivinar la respuesta y luego refinarla a través de una serie de multiplicaciones. Cada multiplicación crea mejor precisión. Puede usar esto para realizar una velocidad clásica 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 proporcionaría una precisión perfecta y sería muy rápido. No hay más matemáticas necesarias. Pero, ¿qué pasa con 32 bits? Ahora la mesa es demasiado grande. Pero usted podría mirar hacia arriba, digamos, los primeros 8 bits del número de 32 bits. O más. O menos. Depende de lo que sea importante para usted.
Así que ahora tienes una mala estimación de tu reciprocal. Sir Issac puede hacerlo mejor. Para algunos números A, usted toma su estimación (x) y multiplíquelos juntos. Resta ese número de 2 y tiene un factor para multiplicar su antigua estimación para obtener una nueva estimación. Saltando, está claro si su estimación tenía razón, la multiplicación le daría 1, lo que no cambiaría la antigua estimación en absoluto. Si la estimación está apagada, obtendrá un factor de escala.
Como una fórmula se ve así:
x = x * (2-a * x);
Entonces, si decide que el recíproco de 22 podría ser .02, la primera pasada le 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 de repetición 0.0454545 y si sigues yendo, llegarás 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 puntos fijos y luego examina el código de ensamblaje resultante para el brazo, RISC-V y DSPIC30. Bien vale la pena leer.
Amamos los trucos de matemáticas que podemos usar en el lenguaje de montaje. Si está trabajando en AVR y punto flotante, no se pierda este método.