Inversión eficiente (1 / x) para AVR

12

Estoy tratando de encontrar una manera eficiente de calcular un inverso en un AVR (o aproximarlo).

Estoy tratando de calcular el período de pulso para un motor paso a paso para poder variar la velocidad linealmente. El período es proporcional al inverso de la velocidad ( p = K/v), pero no puedo pensar en una buena forma de calcular esto sobre la marcha.

Mi formula es

p = 202/v + 298; // p in us; v varies from 1->100

Al probar en Arduino, la división parece ignorarse por completo, quedando pfijada en 298(aunque quizás esto sería diferente en avr-gcc). También he intentado sumar ven un bucle hasta que excede 202y contar los bucles, pero esto es bastante lento.

Podría generar una tabla de búsqueda y almacenarla en flash, pero me preguntaba si había otra forma.

Editar : Tal vez el título debería ser "división eficiente" ...

Actualización : como señala pingswept, mi fórmula para asignar el período a la velocidad es incorrecta. Pero el principal problema es la operación de división.

Edición 2 : en una investigación adicional, dividir está trabajando en el arduino, el problema se debió tanto a la fórmula incorrecta anterior como a un desbordamiento int en otra parte.

Peter Gibson
fuente
2
¿Es v un número entero o un punto flotante?
mjh2007
Un número entero, pero como nos da un punto en nosotros, la división de enteros es lo suficientemente precisa aquí.
Peter Gibson
Puede calcular previamente los valores de los 100 enteros y hacer una tabla de búsqueda de preescaladores para multiplicación si realmente le preocupa la velocidad. Por supuesto, hay un intercambio de memoria.
RYS

Respuestas:

7

Una cosa buena de la división es que más o menos todos lo están haciendo. Es una característica básica del lenguaje C, y los compiladores como AVR-GCC (llamado por el IDE de Arduino) elegirán el mejor algoritmo de división disponible, incluso cuando el microcontrolador no tiene una instrucción de división de hardware.

En otras palabras, no necesita preocuparse por cómo se implementa la división a menos que tenga un caso especial muy extraño.


Si te preocupas, entonces podrías disfrutar leyendo los algoritmos de división sugeridos oficiales de Atmel (uno optimizado para el tamaño del código y otro optimizado para la velocidad de ejecución; ninguno de los dos lleva memoria de datos). Ellos están en:

http://www.atmel.com/dyn/resources/prod_documents/doc0936.pdf

que es la Nota de aplicación "AVR200: Rutinas de multiplicación y división" enumeradas en la página de Atmel para sus procesadores Atmega (razonablemente grandes) como Atmega 168 y Atmega 328 utilizados en los Arduinos estándar. La lista de hojas de datos y notas de aplicación se encuentra en:

http://www.atmel.com/dyn/products/product_card.asp?part_id=4720

Jack Schmidt
fuente
4

me parece que todo lo que necesitas es una tabla de búsqueda de 100 entradas. No es mucho más rápido que eso.

#define VALUE_FOR_V_EQUALS_ZERO 0
uint16_t formula_lookup[100] = {VALUE_FOR_V_EQUALS_ZERO, 500, 399, 365, 348, ..., 300};

...

//"calculate" formula
p = formula_lookup[v > 67 ? 67 : v];

EDITE en realidad solo una tabla de búsqueda de 68 valores, ya que los valores de v mayores que 67 siempre se evalúan como 300.

vicatcu
fuente
Como dije en la pregunta, me preguntaba si había otra manera
Peter Gibson, el
3

Hay algunas muy buenas técnicas mencionadas en el libro "Hackers Delight de Henry Warren y en su sitio web hackersdelight.org . Para una técnica que funciona bien con microcontroladores más pequeños cuando se divide por constantes, eche un vistazo a este archivo .

timrorr
fuente
Estos se ven bien para dividir por constantes como usted dice, pero realmente no se aplican a mi problema. Utiliza técnicas como precalcular lo inverso: multiplicar por él y luego cambiar.
Peter Gibson
¡Ese es un libro excelente!
Windell Oskay
3

Su función no parece dar el resultado que desea. Por ejemplo, el valor 50 devuelve aproximadamente 302, mientras que 100 devuelve aproximadamente 300. Esos dos resultados causarán casi ningún cambio en la velocidad del motor.

Si te entiendo correctamente, realmente estás buscando una forma rápida de mapear los números 1-100 al rango 300-500 (aproximadamente), de modo que 1 mapee a 500 y 100 mapee a 300.

Quizás intente: p = 500 - (2 * v)

Pero podría ser un malentendido: ¿está tratando de calcular el tiempo de funcionamiento de una onda cuadrada de frecuencia constante? ¿Qué es el 298?

pingswept
fuente
Sí, gracias, la fórmula está mal. El punto es obtener una aceleración lineal de la salida del paso a paso, variando la velocidad objetivo en una constante cada intervalo de tiempo (velocidad, por ejemplo). Esto debe correlacionarse con el período (frecuencia) en que se envía un borde + ve al controlador del motor paso a paso, de ahí la relación inversa (p = 1 / v).
Peter Gibson
¿Te refieres a una aceleración constante, es decir, una velocidad linealmente creciente?
pingswept
Ah sí, aceleración constante, lo arruiné cuando originalmente escribí la pregunta y recuerdo haberlo arreglado allí también
Peter Gibson,
3

Una forma eficiente de aproximar las divisiones es por turnos. por ejemplo, si x = y / 103; dividir por 103 es lo mismo que multiplicar por 0.0097087, por lo que para aproximar esto primero, seleccione un número de cambio 'bueno' (es decir, un número de base 2, 2,4,8,16,32 y así sucesivamente)

Para este ejemplo, 1024 es un buen ajuste, ya que podemos decir que 10/1024 = 0.009765 Entonces es posible codificar:

x = (y * 10) >> 10;

Recordando, por supuesto, para asegurarse de que la variable y no desborde su tipo cuando se multiplica. No es exacto, pero es rápido.


fuente
Esto es similar a las técnicas en los enlaces que timrorr suministró y funciona bien para dividir por constantes, pero no cuando se divide por un valor que es desconocido en el momento de la compilación.
Peter Gibson
3

En otra nota, si está tratando de dividir en una CPU que no admite la división, hay una forma realmente genial de hacerlo en este artículo de Wiki.

http://en.wikipedia.org/wiki/Multiplicative_inverse

Para aproximar el recíproco de x, usando solo la multiplicación y la resta, se puede adivinar un número y, y luego reemplazar repetidamente y con 2y - xy2. Una vez que el cambio en y se vuelve (y permanece) suficientemente pequeño, y es una aproximación del recíproco de x.

mjh2007
fuente
Interesante, me pregunto cómo se compara esto con los otros métodos mencionados
Peter Gibson,
1

Este proceso aquí parece amigable con mcu, aunque podría necesitar un poco de portabilidad.

Aunque parece que la LUT sería más fácil. Solo necesitaría 100 bytes, menos si usara alguna interpolación, y dado que la LUT está llena de constantes, el compilador podría incluso ubicarla en el área de código en lugar del área de datos.

ajs410
fuente
Intenté algo similar al sumar el divisor hasta que iguala o supera el dividendo, pero descubrí que es bastante lento. Parece que el LUT será el camino a seguir: con avr-gcc necesita macros especiales en <avr / progmem.h> para almacenarlo en flash.
Peter Gibson
1

Compruebe para asegurarse de que la división se realiza como punto flotante. Utilizo Microchip, no AVR, pero cuando utilizo C18 necesita forzar que sus literales sean tratados como coma flotante. P.ej. Intenta cambiar tu fórmula a:

p = 202.0/v + 298.0;

mjh2007
fuente
1

Desea rápido, así que aquí va ... Ya que el AVR no puede normalizar de manera eficiente (desplazándose hacia la izquierda hasta que ya no pueda desplazarse), ignore los algoritmos de pseudo coma flotante. La forma más simple para una división de enteros muy precisa y rápida en un AVR es a través de una tabla de búsqueda recíproca. La tabla almacenará recíprocos escalados por un gran número (digamos 2 ^ 32). Luego implementa una multiplicación unsigned32 x unsigned32 = unsigned 64 en el ensamblador, por lo que answer = (numerator * inverseQ32 [denominator]) >> 32.
Implementé la función de multiplicación usando el ensamblador en línea, (envuelto en la función ac). GCC admite "largos largos" de 64 bits, sin embargo, para obtener el resultado, debe multiplicar 64 bits por 64 bits, no 32x32 = 64 debido a las limitaciones del lenguaje C en la arquitectura de 8 bits ...

La desventaja de este método es que usará 4K x 4 = 16K de flash si desea dividir por enteros del 1 al 4096 ......

Ahora se logra una división sin signo muy precisa en aproximadamente 300 ciclos en C.

Podría considerar usar enteros escalados de 24 o 16 bits para obtener más velocidad y menos precisión.

Mella
fuente
1
p = 202/v + 298; // p in us; v varies from 1->100

El valor de retorno de su ecuación ya se debe a p=298que el compilador se divide primero y luego se agrega, use una resolución muldiv entera que sea:

p = ((202*100)/v + (298*100))/100 

Usar esto es la misma multiplicación a*f, con a = entero f = fracción.

Ese rendimiento r=a*fpero f=b/cluego, r=a*b/cpero aún no funciona porque la posición de los operadores, produce la función final r=(a*b)/co muldiv, una manera de calcular números de fracción usando solo números enteros.

nepermath
fuente