Tips and Tricks – Fast Divide and Multiply
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.
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.
Struggling to keep your development skills up to date or facing outdated processes that slow down your team, raise costs, and impact product quality?
Here are 4 ways I can help you:
- Embedded Software Academy: Enhance your skills, streamline your processes, and elevate your architecture. Join my academy for on-demand, hands-on workshops and cutting-edge development resources designed to transform your career and keep you ahead of the curve.
- Consulting Services: Get personalized, expert guidance to streamline your development processes, boost efficiency, and achieve your project goals faster. Partner with us to unlock your team's full potential and drive innovation, ensuring your projects success.
- Team Training and Development: Empower your team with the latest best practices in embedded software. Our expert-led training sessions will equip your team with the skills and knowledge to excel, innovate, and drive your projects to success.
- Customized Design Solutions: Get design and development assistance to enhance efficiency, ensure robust testing, and streamline your development pipeline, driving your projects success.
Take action today to upgrade your skills, optimize your team, and achieve success.