Fast Division and Square Root Algorithms for AVR 8 Bit Flight Control Applications

I have an digital board intended for a Flight control system on RC aircraft, with grand plans for a home built UAV. I have been doing a lot of study of the math and algorithms that go into such systems. Some of the discussions cover efficiency of the algorithms, in terms of how many multiply operations and addition operations are required for each update time. The AVR 8 bit devices have a built in hardware multiply operation, in 8 bit. 16 bit operations require a couple of cycles. What they do NOT have is a divide operation. A divide is the same a multiplication by the reciprocal.. but how do you get the reciprocal? The other operation that is not represented is the square root.

The avr-libc library includes divide and sqrt functions, but they are fairly costly according to the documentation. The __divsf3 function, which I assume is the divide (but documentation is limited here), takes 465 clock cycles. That is about 24us at 20Mhz, with 1 cycle per clock (I think that is correct).. That seems like an awfully long time to perform a division.. especially if a mul operation is 1 cycle! sqrt takes 492 cycles, which is also pretty high. For some reason, I would expect sqrt to take more.

I'm sure I can dig into the details of these routines, but if anyone has some insight, that would be great. Perhaps if I knew a bit more about how these particular routines work, I might be able to optimize a version specifically for my task. I'm sure that the avr-libc versions are somewhat generic, so, making one that is specific to a single purpose might save some of those cycles. Anyone have any experience in this area?

The folks on the forum at http://www.avrfreaks.net might have a good answer.

Let us know what you find out...

AVR Freaks might help, but I was thinking my question was more of a general microprocessor question. The question is more what types of shortcuts can one make with a small micro.

I was discussing transcendental functions (sin, cos, tran) with a friend recently. The processor I am using takes 1600+ clock cycles for a sin or cos calculation. The calculations are done in floating point.

For small angles, a taylor series expansion can be used instead. This expansion requires only multiplication and addition, which have direct hardware support. While this isn't a full sin/cos function, for some applications it might work quite well (small angles), and the performance will be significantly better.

Those are the types of optimization I am looking for.

Thanks for the update. A Taylor Series does sound like the way to go.

Ed, I'm going to suggest HACKMEM as a note you might enjoy.

Its a bit dated MIT paper (1972), but lots of mathematical gems in there.

Just plain interesting reading, too!

Here's a link to the paper Randy is talking about. Thanks Randy.

http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html

The internal multiply instruction you talk about is for 8 bit integers, while the divsf3 and sqrt functions are for 32bit FLOATING POINT numbers, which is a lot different.

For high speed math as you might need in a flight control system, you probably want to look for a library of high-speed FIXED POINT FRACTIONAL math functions. This is nicely searchable. While I don't have any direct experience, there is this: https://sourceforge.net/projects/avrfix/

Hi Ed, I have a book titled "Math Toolkit for Real-Time Programming" by Jack Crenshaw. It may not be everything you're looking for, but it's interesting to read anyway. The author did the 'Programmer's Toolbox' column for Embedded Systems Programming magazine for many years, and his columns are the main reason I've kept most of the back issues.

I'm sure we'll be seeing each other this week, so I'll bring it along.

I wrote some 16 bit fixed point routines for AVRGCC. The format is 8:8. Multiply speed is about 40 cycles, divide speed is about 360 cycles worst case. Code is at
http://people.ece.cornell.edu/land/courses/ece4760/Math/index.html

I wrote a simple 16-bit reciprocal and sqrt for Mega644 in GCC.
http://people.ece.cornell.edu/land/courses/ece4760/Math/index.html

As a rule in realtime applications:
Find out how precise you will have to be.
eight bit gives you a 1.4% error in sinus or cosinus.
Is that not enough try 16 bits and so on.
You can also do calculations beforehand and put in a table. Exchange memory for speed.

Hi Edward,

Let me add one more item to this discussion. In Microcontrollers there always is a tradeoff of speed verses use of memory. At the most basic level you can write the routine and have the low speed microcontroller attempt to do the calculations as fast as an algorithm can be coded. The other solution is to code all or part of the routine using lookup tables where the calculations have been previously performed and placed into the table. The only negative will be your resolution. If this is a simple 8 bit result that is passed an 8 bit value this uses 256 bytes of EEPROM, else if it is a 12 bit result from a 12 bit parameter that can use 1536 bytes. The key is to attempt to only use the resolution that you need. Further, with tables they can be used along with the algorithm for key sections so the solution can be a hybrid.

Just some ideas to consider when using low precessing power micros.

Good points.

Another thing I have done to avoid consuming memory space with a 1:1 table is to use piecewise linear approximations to the function. Select the table entries so that interpolation between two entries still gives the resolution needed. The table size can sometimes be reduced dramatically for a small increase in processing of the value.