Q:

Efficient inverse (1/x) for AVR

I'm trying to find an efficient way of calculating an inverse on an AVR (or approximating it).
I'm trying to calculate the pulse period for a stepper motor so that I can vary the speed linearly. The period is proportional to the inverse of the speed (p = K/v), but I can't think of a good way of calculating this on the fly.
My formula is
p = 202/v + 298; // p in us; v varies from 1->100

Testing on the Arduino, the division seems to be ignored completely leaving p fixed at 298 (though perhaps this would be different in avr-gcc). I've also tried summing v in a loop until it exceeds 202, and counting the loops, but this is quite slow.
I could generate a lookup table and store it in flash, but I was wondering if there was another way.
Edit: Maybe the title should be "efficient divide"...
Update: As pingswept points out, my formula for mapping period to velocity is incorrect. But the main problem is the divide operation.
Edit 2: On further investigation, divide is working on the arduino, the problem was due to both the incorrect formula above and an int overflow elsewhere.

A:

One nice thing about division is that more or less everyone is doing it.  It is a pretty core feature of the C language, and compilers like AVR-GCC (called by the Arduino IDE) will choose the best division algorithm available, even when the microcontroller does not have a hardware division instruction.
In other words, you don't need to worry about how division is implemented unless you have a very strange special case.

If you do worry, then you might enjoy reading Atmel's official suggested division algorithms (one optimized for code size, and one optimized for execution speed; neither take any data memory).  They are in:
http://www.atmel.com/dyn/resources/prod_documents/doc0936.pdf
which is the Application Note "AVR200: Multiply and Divide Routines" listed on the Atmel page for its (reasonably big) Atmega processors like the Atmega 168 and Atmega 328 used in the standard Arduinos.  The list of data-sheets and application notes is at:
http://www.atmel.com/dyn/products/product_card.asp?part_id=4720

A:

looks to me like all you need is a 100-entry lookup table. Doesn't get much faster than that.
#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];

EDIT you actually only a 68 value lookup table since values of v greater than 67 always evaluate to 300. 

A:

There are some very good techniques mentioned in the book "Hackers Delight by Henry Warren and on his website hackersdelight.org.  For a technique that works well with smaller microcontrollers when dividing by constants have a look at this file.

