![]() We are going to work in fixed-point arithmetic using scaled integers. Let’s take a 16/16 unsigned division as a way to pare down the problem to something that is tractable. So let’s do it! Calculating a reciprocal by looking it up That is entirely true, but it turns out that we can tolerate not-entirely-accurate reciprocals, use some software artistry and calculate an entirely accurate quotient. It would seem that even if we can calculate a reciprocal 1/3, the endeavor to find a quotient is still futile because the inaccurate reciprocal, when multiplied by 3, will result in a number that is not 2. The reason for this is clear, 1/3 is a recuring decimal and the calculator truncates the true value of 1/3 (which is 0.333333…) after 8 or 10 decimal places, working with limited precision. But from calculators of days long-gone, we intuitively know that entering the algebraically-identical “ 1 ÷ 3 × 6 =” does not display “ 2“. On any calculator, if you enter “ 6 ÷ 3 =” you would expect to see “ 2“. Let’s take, by way of example, a division of 6 by 3. On the face of it, this really doesn’t look like progress, there’s still a division in there, 1 / v. We start by rewriting the division u / v as a multiplication, u × (1 / v). To improve division speed our aim is to produce more than “one bit per step”. This fact is the foundation of many complex numerical algorithms in emFloat, and is leveraged in emRun to provide fast integer division on processors that don’t have division instructions. Multiplication in hardware is cheap compared to division, and most multipliers are fast, delivering their result in a few cycles, or even a single cycle. Besides, all this complexity can be offloaded to software to sort out! This die space and complexity isn’t included for many microcontrollers simply because division is infrequently used and doesn’t justify the cost to include it. This type of implementation really does exist which might be a deal-breaker for some applications.ĭivision in hardware can also be complex, requiring significant die space dedicated to efficient algorithms which require a lot of computation. And a multi-cycle uninterruptible divide increases interrupt latency. Why is that?ĭivision in hardware can be slow, using the shift-subtract algorithms we’ve seen. What’s the problem with dividing?Ĭheap low-end microcontrollers typically offer some form of multiplication ability (by instruction or by a peripheral), but don’t offer a complementary divide capability. Now it’s time to change up a couple of gears and turbocharge division for speed!įor those of you just interested in the code, and not the background or explanation, jump right to the end and take what you need. We’ve explored simple algorithms that develop a quotient one digit at a time: reliable, understandable, but ultimately quite slow.
0 Comments
Leave a Reply. |