Sobre las curvas de Bezier y la velocidad de Arduino, segunda parte

Pasaremos por - y más allá

En mi publicación anterior, mostré cómo puede mejorar la velocidad de cálculo de puntos en una curva de Bezier (KB) de la siguiente manera:

1. Transformaciones de fórmulas de cálculo: aceleración ~ 3 veces.
2. Casi no hay aceleración de PT a FT, pero permite 3.
3. La operación de reemplazo de la división por multiplicación y cambio es una aceleración de otro 40%.

Al final de la publicación mencionada, dije que los cálculos se pueden hacer aún más rápido, pero lo que "el niño dijo, el niño hizo".

Permítame recordarle una vez más la fórmula obtenida para calcular el punto en el KB

$$

$$P = (A1 * y + B1) * y + C (=> 2 * 2 +)$$

El próximo aumento en la velocidad está relacionado con la peculiaridad del problema: no solo debemos calcular el valor de KB a diferentes valores del parámetro “y”, sino también encontrar una serie de valores al cambiar (en este caso, aumentar) este parámetro por un valor fijo conocido, además. unidad de caso), que le permite utilizar la técnica que se describe a continuación. En mi tiempo, se llamaba el método de cálculo de la diferencia (si la memoria me sirve bien, al menos así era como se llamaba en las conferencias), todo Internet está a su disposición, tal vez (incluso seguro), hay otro nombre.

Consideramos el caso P = A * y (=> 1 *), y supongamos que conocemos el valor de P0 con algún argumento u0. Entonces el valor con el siguiente argumento u0 + 1 puede calcularse como P = A * (u0 + 1) = A * u0 + A = P0 + A (=> 1+). Sin perder ninguna precisión, pudimos reemplazar la operación de multiplicación con la operación de suma, que es mucho más rápida.

Ahora un ejemplo más complejo P = A * y * y (=> 2 *), consideramos por analogía P = A * (y + 1) * (y + 1) = A * (y * y + 2 * y + 1) = A * y * y + 2 * A * y + A = P0 + 2 * A * y + A (=> 2 * 2 +). A primera vista, no ganamos nada, pero si calculamos A '= 2 * A por adelantado, obtenemos (=> 1 * 2 +), una ganancia es bastante posible. Pero no nos detendremos en lo que se ha logrado y en la expresión obtenida A '* y aplicaremos la técnica que ya conocemos, entonces obtendremos dos operaciones en dos variables: P = P + A' + A; A '= A' + A (=> 3+). Si tenemos en cuenta que el valor inicial de A 'puede hacerse más por A, entonces, en general, solo hay dos adiciones en lugar de dos multiplicaciones. Sí, tuvimos que obtener dos variables adicionales, pero este es un intercambio clásico: pagamos con memoria por el momento.

Solo resta calcular los valores iniciales correctos, pero esto se hace solo una vez al comienzo de las iteraciones, y si el valor inicial del parámetro es u = 0, generalmente es trivial P = 0, A '= A. Probaremos nuestro método en varias iteraciones (esto es completamente innecesario, las matemáticas aplicadas correctamente no pueden dar la respuesta incorrecta), pero nos permitirán comprender mejor lo que está sucediendo. Entonces
iteración 0: y = 0; P = 0 (verdadero); A '= A; A '' = 2 * A;
iteración 1: y = 1; P = 0 + A '= 0 + A = A (verdadero); A '= A' + A '' = A + 2 * A = 3 * A;
iteración 2: y = 2; P = A + 3 * A = 4 * A (verdadero); A '= 3 * A + 2 * A = 5 * A;
iteración 3: y = 3; P = 9 * A (verdadero); A '= 7 * A y así sucesivamente.

Observamos la conexión entre las fórmulas obtenidas y el método de Newton para calcular el valor de una función en la vecindad de un punto con un valor conocido. Además, dado que nuestra función es de segundo orden y todas las derivadas, a partir de la tercera, son iguales a cero, podemos reemplazar con seguridad el signo de igualdad aproximado con el exacto. La única diferencia con este método es que constantemente movemos el punto con respecto al cual estamos construyendo un nuevo vecindario para evitar realizar operaciones de multiplicación en la formulación original.

Reescribe nuestra expresión original para KB en forma expandida

$$

$$P = A1 * y * y + B1 * y + C$$

luego, para calcular usando este método, necesitamos 2+ para el primer término (y dos variables), 1+ para el segundo término (y una variable) y 2+ para sumar todo (=> 5+). Se puede esperar que incluso este enfoque (incorrecto) produzca una ganancia en comparación con 2 * 2 +, pero todo es mucho mejor. Obviamente, la operación de suma es aditiva (gracias, capitán), por lo que puede agrupar los términos y reemplazar los términos constantes con nuevas expresiones, lo que da el siguiente algoritmo:

1. Los valores iniciales de P = C; A '= A1 + B1; A '' = 2 * A1;
2. en el siguiente paso P = P + A '; A '= A' + A '' (=> 2+), que sin duda es más rápido que el esquema de Horner.

Implementamos nuestro algoritmo en forma de programa (esto no es tan trivial como podría parecer, ya que por simplicidad olvidé la necesidad de cambios, pero no es demasiado difícil ... durante 20 minutos), obtenemos la complejidad computacional (=> 2 + 1 >>) y medimos velocidad: resultó 140 (aumento de la velocidad en otras 3 veces) ciclos por ciclo, pero este es casi un resultado ideal. Lo que tenemos que hacer para obtener la opción ideal (en cierto sentido) es prestar atención a la dimensión de los operandos en las fórmulas. Ahora llevamos a cabo todas las operaciones en enteros largos (32 bits), y esto puede ser innecesario en algunos lugares. Si reducimos la capacidad de los operandos al mínimo necesario, entonces podemos obtener una ganancia del 20-25 por ciento, pero esto requerirá que cambiemos al ensamblador (C no tiene los medios adecuados para tales operaciones) y analicemos cuidadosamente los datos del problema original. Ya sea que el lector decida si hacer esto o no, ya hemos acelerado los cálculos en más de 1900/140 = 13 veces en comparación con el enfoque "ingenuo".

La última nota sobre la implementación del algoritmo es que todavía excluimos la operación de división cambiándola por multiplicación constante, que tenemos en cuenta al generar los datos iniciales y cambiar por un múltiplo constante de 8. Esto se puede hacer de varias maneras con tiempos de ejecución ligeramente diferentes, dejando tales experimentos a la atención de un lector inquisitivo .

Sin embargo, surgió un problema completamente inesperado: vemos claramente dos operaciones de suma en números de 32 bits, que deberían tomar 4 + 4 = 8 ciclos de reloj, poner otros 8 * 3 * 2 = 48 ciclos de reloj para enviar operandos, 4 ciclos de reloj para recibir el resultado del cambio, 4 un ciclo de reloj para llamar al procedimiento de cálculo y regresar, y 4 ciclos de reloj para organizar el ciclo, desde donde otros 60 ciclos de reloj no están claros. Anteriormente, simplemente no notamos esto en el contexto de cientos de ciclos de reloj, pero ahora puede prestar atención. Se encontraron fácilmente medidas excesivas: en el ciclo hubo operaciones de depuración innecesarias, si limpia todo cuidadosamente, solo quedan 120 medidas y el propósito de cada una es bastante comprensible (bueno, no tan completamente claro, pero aún así). A continuación, descubrimos el tiempo de ejecución del ciclo vacío: 22 medidas, me pregunto qué estarán haciendo allí todo este tiempo, pero bueno, y borramos el tiempo de cálculo real, que será de 98 ciclos. Tenga en cuenta que la estimación de la aceleración de trabajo obtenida cambia: en lugar de 1900/140 = 13 obtenemos (1900-50) / (140-40) = 19 veces, lo que no tiene sentido práctico, ya que el ciclo aún es necesario, pero le permite aumentarlo aún más autoestima

Y el último comentario: como es fácil de ver, comenzamos a buscar y eliminar pulgas solo cuando tratamos con grandes escarabajos ciervos y su existencia (pulgas) se hizo evidente y, además, significativa. Recomiendo exactamente este enfoque (y no estoy solo en esta recomendación) cuando optimizo programas en términos de rendimiento.

Bueno, en conclusión, sobre la nota "en cierto sentido": si estamos hablando de calcular secuencialmente las coordenadas del siguiente punto en la oficina de diseño al cambiar el parámetro (que representa el tiempo), entonces el algoritmo propuesto (después de todas las optimizaciones) ya no es posible mejorar. Pero si reformula la tarea y, por ejemplo, establece el objetivo de simplemente construir una oficina de diseño en la pantalla (sin referencia al tiempo), entonces hay un método muy prometedor, la palabra clave "Brezenheim", pero "esta es una historia completamente diferente", a la que dedicaré una publicación separada (Tal vez algún día si a la hermana mayor no le importa).