Tips and Tricks – Fast Divide and Multiply


RSS
Follow by Email
Facebook
Facebook
Google+
Google+
http://beningo.com/tips-and-tricks-fast-divide-and-multiply/
YouTube
LinkedIn

There are many instances when attempting to perform a mathematical operation on a resource-constrained microcontroller where the use of a simple divide or multiply can drastically affect the speed and efficiency of the system. There is often little that can be done to get around the division or multiplication but there is a neat trick that can be performed to make these operations extremely fast.

speed
Consider how information is stored inside of a computer system. Every object in the system consists of bits that are encoded in 2 to the power of n. For example, the value of 2 raised to 2 is 2*2 = 4. The value of 2 raised to 4 is 2*2*2*2* = 16. What is so interesting about how numbers are stored is that shifting the value of an object to the left behaves like a multiplication and a shift to the right acts like a divide.

Keeping this behavior in mind, algorithms can be developed to take advantage of the bit shift behavior. For example, a commonly performed task in an embedded system is to average values that are being read by an analog-to-digital converter. A developer can keep the 2 to n behavior of values in mind to average the last four adc reads. The pseudo code would look like

AdcTotal = AdcResult1 + AdcResult2 + AdcResult3 + AdcResult4;

AdcAverage = AdcTotal >>2;

The last line is dividing the total result by 2 raised to 2, which results in a division of 4. Rather than using the actual division operator and having a large number of instructions generated, a simple bit shift generates far less.

Below is a simple table that can be used to reference the number of bits shifted and the resulting division or multiplication value.

Bit Shift Value
0 1
1 2
2 4
3 8
4 16
5 32
6 64
7 128

In conclusion, a developer can easily get around the inefficiencies caused by using the multiplication or divisor operator by simply designing their algorithm to take advantage of the 2 to the power of n notation and using bit shifting to perform the operation.

 

RSS
Follow by Email
Facebook
Facebook
Google+
Google+
http://beningo.com/tips-and-tricks-fast-divide-and-multiply/
YouTube
LinkedIn

Leave a Reply

Your email address will not be published. Required fields are marked *