2012-04-12 19 views
7

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.raíz cuadrada de seguimiento del valor móvil

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?

+0

Un disparo del método de Halley (http://www.mathpath.org/Algor/squareroot/algor.square.root.halley.htm) debe hacer bien. Si quiere evitar la división, actualice 1/sqrt (x) en su lugar y use Newton o Halley. –

+0

¿Qué quieres decir con que el valor cambia? ¿Estás diciendo que quieres encontrar 'sqrt (x + epsilon)' conociendo 'x' y' sqrt (x) 'sin tener que calcularlo directamente?¿O está diciendo que el registro que contiene x es volátil y puede cambiar a la mitad del cálculo (!?!)? –

+0

Mira esta función 'FastSqrt' utilizada en los juegos http://www.gamedev.net/topic/278840-fast-sqrt/ – ja72

Respuesta

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

+0

Mis simulaciones muestran que esto funciona mejor. También es lo único que he probado que funciona razonablemente cerca de cero. x_n necesita ser recortado a un valor pequeño al menos en los comentarios para evitar la división por cero. – phkahler

+0

Si es un punto flotante, puede simplemente dividir a la mitad el exponente de la entrada y usar el valor resultante como primera estimación para incluir en este o en cualquier otro algoritmo iterativo de raíz cuadrada. –

+0

@R .. La suposición inicial es el último valor actualizado (ver pregunta). Pero sí, en un entorno más genérico, esto funcionaría muy bien. –

5

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.

+0

Demasiada memoria: editó la pregunta para reflejar esto. – phkahler

+0

¿Ha intentado publicar esta pregunta o algo similar al sitio de intercambio de stack de matemáticas? –

2

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.

2

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().

+0

Voy a ver esto. La división es indeseable pero puede estar bien. ¿Qué hace cuando la entrada es cero por un tiempo? – phkahler

+0

@phkahler: Atajo al cero para devolver '0' duh! si 'y_c' es cero, debe evaluar' sqrt() '. – ja72

+0

@phkahler: necesitarás la división de todos modos si estás computando 'sqrt (x)' (puedes evitarlo si estás computando 1/sqrt (x)). –

Cuestiones relacionadas