El nuevo find-first-set La instrucción de CPU "ffs" de bits que se encuentra en las extensiones multimedia (MMX) 4 aparentemente hizo posible comenzar a hacer División Newton-Raphson (según Wikipedia).
¿Alguien sabe si ya se ha intentado utilizar Matrices de acompañamiento para el mismo propósito?
Explicación:
La ecuación polinómica $ax-b=0$ no es el más complicado, pero sigue siendo muy interesante ya que su solución $x = b/a$ es precisamente la división entre el número $a$ y $b$ que sigue siendo, a día de hoy, vergonzosamente lento incluso en las modernas CPUs de sobremesa que tienen latencias de 10 o 20 ciclos de reloj.
Como toda ecuación polinómica está relacionada con una matriz
Si consideramos: $${\bf M} = \begin{bmatrix}0&a\\1&b\end{bmatrix}$$ Lo que representaría $x^2-ax-b$ . Esto no es lo que queremos encontrar un cero, pero podemos con la continuidad alterar para hacer la $x^2$ menos impactante para las raíces. Por ejemplo, multiplicando $-ax-b$ con una constante grande, o lo que sería lo mismo en este caso, alterar el 1 de la diagonal de salida a algún $\epsilon>0$ por ejemplo, podemos elegir $\epsilon = 2^{k}$ que podría implementarse con un simple desplazamiento de bits. Aquí hay un gráfico sobre la forma de cuánto se aleja la raíz en función del número de bits $k$ que podemos permitirnos por iteración: Supongo que esto también podría ser pre-almacenado en una tabla en caché si los bits extra cuestan demasiado para los registros de la CPU. Este ejemplo particular 3/2.
Un segundo enfoque sería ampliar $(x-b/a)^2$ o $(x+b/a)(x-b/a)$ o alguna otra en la que sepamos que las raíces estarán estrechamente relacionadas con la fracción que buscamos y entonces modificamos la matriz en consecuencia, multiplicando con el mayor común divisor escalar.
Concluyamos que hay muchos enfoques, ¿de acuerdo? En fin, al grano:
Con propiedades para que ${\bf M}^k {\bf v}$ para casi cualquier inicial $\bf v$ cociente entre el primer y el último índice se acercará a una raíz del polinomio como $k$ crece.
¿Podría haber algún beneficio de las matrices compañeras u otros enfoques basados en matrices-vectores en combinación con este nuevo ffs ¿Instrucción?
