Where can I find soft-multiply and divide algorith

Question

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.

Answer 1

One simple and fairly performant multiplication algorithm for integers is Russian Peasant Multiplication.

For rationals, you could try a binary quote notation, for which division is easier than usual.

Answer 2

The Microchip PICmicro 16Fxxx series chips do not have a multiply or divide instruction. Perhaps some of the soft multiply and soft divide routines for it can be ported to your MCU.

PIC Microcontroller Basic Math Multiplication Methods

PIC Microcontroller Basic Math Division Methods

Also check out "Newton's method" for division. I think that method gives the smallest executable size of any division algorithm I've ever seen, although the explanation makes it sound more complicated than it really is. I hear that some early Cray supercomputers used Newton's method for division.

Answer 3

Here's a simple multiplication algorithm:

1. Start with rightmost bit of multiplier.

2. If bit in multiplier is 1, add multiplicand

3. Shift multiplicand by 1

4. Move to next bit in multiplier and go back to step 2.

And here's a division algorithm:

1. If divisor is larger than dividend, stop.

2. While divisor register is less than dividend register, shift left.

3. Shift divisor register right by 1.

4. 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.

5. 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.

Answer 4

Here's a division algorithm: http://www.prasannatech.net/2009/01/division-without-division-operator_24.html

I assume we're talking about ints?

If there's no hardware support, you'll have to implement your own divide-by-zero exception.

(I didn't have much luck quickly finding a multiplication algorithm, but I'll keep looking if someone else doesn't find one).

Answer 5

My favorite reference for things like this, available in book form:

http://www.hackersdelight.org/

Also you can't go wrong with TAoCP: http://www-cs-faculty.stanford.edu/~uno/taocp.html

Answer 6

To multiply, add partial products from the shifted multiplicand to an accumulator iff the corresponding bit in the multiplier is set. Shift multiplicand and multiplier at end of loop, testing multiplier & 1 to see if addition should be done.