Menu
I'm working on a micro-controller without hardware multiply and divide. I need to cook up software algorithms for these basic operations that are a nice balance of compact size and efficiency. My C compiler port will employ these algos, not the the C developers themselves.
My google-fu is so far turning up mostly noise on this topic.
Can anyone point me to something informative? I can use add/sub and shift instructions. Table lookup based algos might also work for me, but I'm a bit worried about cramming so much into the compiler's back-end...um, so to speak.
823
The division algorithm formula is: Dividend = (Divisor × Quotient) + Remainder. This can also be written as: p(x) = q(x) × g(x) + r(x), where, p(x) is the dividend. q(x) is the quotient.
It was first described by Calandri in a 1491 book, and nicknamed "danda" ("giving") by Cataneo in 1546. Cataneo noted that during the division process, after each subtraction of partial products, another figure from the dividend is 'given' to the remainder.
Step 1: Initialize A, Q and M registers to zero, dividend and divisor respectively and counter to n where n is the number of bits in the dividend. Step 2: Shift A, Q left one binary position. Step 3: Subtract M from A placing answer back in A. If sign of A is 1, set Q 0 to zero and add M back to A (restore A).
Division algorithms fall into two main categories: slow division and fast division. Slow division algorithms produce one digit of the final quotient per iteration. Examples of slow division include restoring, non-performing restoring, non-restoring, and SRT division.
Here's a simple multiplication algorithm:
Start with rightmost bit of multiplier.
If bit in multiplier is 1, add multiplicand
Shift multiplicand by 1
Move to next bit in multiplier and go back to step 2.
And here's a division algorithm:
If divisor is larger than dividend, stop.
While divisor register is less than dividend register, shift left.
Shift divisor register right by 1.
Subtract divisor register from dividend register and change the bit to 1 in the result register at the bit that corresponds with the total number of shifts done to the divisor register.
Start over at step 1 with divisor register in original state.
Of course you'll need to put in a check for dividing by 0, but it should work.
These algorithms, of course, are only for integers.
134
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
