raíz cuadrada de seguimiento del valor móvil

Question

Tengo un bucle de control ejecutándose a alta frecuencia y necesito calcular una raíz cuadrada en cada ciclo. Las funciones de raíz cuadrada típicas funcionan bien, pero toman un tiempo excesivo. Como el valor que tomo la raíz cuadrada de no cambia demasiado en cada ciclo, me gustaría encontrar una raíz cuadrada iterativa que converja y luego seguir el resultado correcto. De esta forma podría hacer una única iteración en cada paso de tiempo, en lugar de muchas.

El problema es que todos los métodos iterativos de raíz cuadrada que he visto probablemente fallarán cuando la entrada cambie. En particular, parece que habrá problemas cuando la entrada vaya a cero y luego aumente nuevamente; a los métodos no les gusta comenzar con una estimación de cero.

Mi rango de entrada es 0-4.5 y necesito una precisión de alrededor de 0.01, así que usar un incremento/decremento de 0.01 podría llevar demasiado tiempo - Quiero que converja principalmente en 10 ciclos o menos.

FYI Estoy usando un punto fijo de 16/32 bits, la entrada es de 16 bits q12. Está en un microcontrolador, así que no estoy interesado en usar 1K para una tabla de búsqueda. El código también se genera a partir de un modelo simulink y sus funciones de búsqueda de tablas están bastante llenas de sobrecarga.

¿Hay una buena solución para esto?

Answer 1

Puede usar una toma del método Halley. Tiene la convergencia cúbica y por lo tanto debe ser muy precisa si el valor se mueve ligeramente:

x_{n+1} = x_n * (x_n^2 + 3Q)/(3 x_n^2 + Q) 

Esto converge cubcially a sqrt(Q).

Referencia: http://www.mathpath.org/Algor/squareroot/algor.square.root.halley.htm

Answer 2

el rango 0-4.5 es bastante pequeño. Con una precisión de 0.01, solo hay 450 cálculos posibles. Puede calcularlos todos en tiempo de compilación como constantes y solo hacer una búsqueda durante el tiempo de ejecución.

Answer 3

Le sugiero que use una tabla de búsqueda, si conoce de antemano los rangos con los que está tratando. Genere una matriz o una tabla hash (según el idioma en el que esté trabajando) con el nivel de precisión que necesita y consulte esto cuando necesite sus raíces.

Answer 4

que intentaron una segunda expansión de Taylor para el sqrt(x) e ir al siguiente resultado

si y=sqrt(x) y lo sabes y_c = sqrt(x_c) ya continuación:

t = x-3*x_c; 
y = (12*x_c*x_c-t*t)/(8*y_c*y_c*y_c); 

Cuanto más grande es el mejor x la aproximación. En el peor de los casos con x_c=0.01 y x=0.02, el resultado sale 0.1375 frente al resultado real de sqrt(0.02)=0.1414 o una diferencia de 0.0039 que está por debajo de 0.01.

Probé el código con C# y vi una velocidad constante de 33% frente a Math.Sqrt().