views:

354

answers:

7

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.

Thanks!

+1  A: 

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

Seth
Carl Norum
Yes integers. And thanks Carl, I'll check the wiki.
srking
+1  A: 

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.

outis
I thought that algorithm was for people, not machines.
Steve314
Algorithms are processor-agnostic.
outis
Not necessarily - one algorithm may perform better or worse than others depending on whether the hardware it runs on supports the right basic operations. The human brain supports different basic operations to a CPU. My personal brains 32 bit integer addition is at least a few billion times slower than an x86, for example, whereas I have hardware-accelerated vision algorithms that are far superior to any current PC.
Steve314
Well, since "divide by 2 and throw away remainder" is just "shift right", and "test for odd" is "logical and with 1 and test against 0", it seems to map pretty well on to basic CPU ops. It's essentially the same algorithm described by Justin's answer.
caf
@Steve314: you're right that algorithm efficiency depends on the efficiency of basic operations, which are processor dependent, but algorithm correctness is processor agnostic. In this sense peasant multiplication isn't for any particular processor. As caf points out, peasant multiplication is efficient on CPUs.
outis
@caf: yup. All the specific multiplication algorithms posted as answers here are essentially the same.
outis
+6  A: 

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.

Justin Peel
What happens in step 3 of the division algorithm if you divide (1<<n)+1 by (1<<x), where n is the register width-1?
jbcreix
@jbcreix, I'm not sure that I understand what you are asking. Can you elaborate?
Justin Peel
@Justin Peel, if you shift the divisor left while the dividend is larger, the highest bit will be shifted out in very large dividends. So, when you shift right you will get a different number in the case of a power of 2 divisor, 0.
jbcreix
@jbcreix, yes, of course you have to be careful to avoid overflow problems.
Justin Peel
A: 

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.

Arthur Kalliokoski
+1  A: 

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

kotlinski
+1 for Hacker's Delight. Has all kinds of tricks.
rmk
A: 

It turns out that I still have some old 68000 assembler code for long multiplication and long division. 68000 code is pretty clean and simple, so should be easy to translate for your chip.

The 68000 had multiply and divide instructions IIRC - I think these were written as a learning exercise.

Decided to just put the code here. Added comments and, in the process, fixed a problem.

;
; Purpose  : division of longword by longword to give longword
;          : all values signed.
; Requires : d0.L == Value to divide
;          : d1.L == Value to divide by
; Changes  : d0.L == Remainder
;          : d2.L == Result
;          : corrupts d1, d3, d4
;

        section text

ldiv:   move    #0,d3     ; Convert d0 -ve to +ve - d3 records original sign
        tst.l   d0
        bpl.s   lib5a
        neg.l   d0
        not     d3
lib5a:  tst.l   d1        ; Convert d1 -ve to +ve - d3 records result sign
        bpl.s   lib5b
        neg.l   d1
        not     d3
lib5b:  tst.l   d1        ; Detect division by zero (not really handled well)
        bne.s   lib3a
        rts
lib3a:  moveq.l #0,d2     ; Init working result d2
        moveq.l #1,d4     ; Init d4
lib3b:  cmp.l   d0,d1     ; while d0 < d1 {
        bhi.s   lib3c
        asl.l   #1,d1     ; double d1 and d4
        asl.l   #1,d4
        bra.s   lib3b     ; }
lib3c:  asr.l   #1,d1     ; halve d1 and d4
        asr.l   #1,d4
        bcs.s   lib3d     ; stop when d4 reaches zero
        cmp.l   d0,d1     ; do subtraction if appropriate
        bhi.s   lib3c
        or.l    d4,d2     ; update result
        sub.l   d1,d0
        bne.s   lib3c
lib3d:                    ; fix the result and remainder signs
;       and.l   #$7fffffff,d2  ; don't know why this is here
        tst     d3
        beq.s   lib3e
        neg.l   d2
        neg.l   d0
lib3e:  rts

;
; Purpose  : Multiply long by long to give long
; Requires : D0.L == Input 1
;          : D1.L == Input 2
; Changes  : D2.L == Result
;          : D3.L is corrupted
;

lmul:   move    #0,d3       ; d0 -ve to +ve, original sign in d3
        tst.l   d0
        bpl.s   lib4c
        neg.l   d0
        not     d3
lib4c:  tst.l   d1          ; d1 -ve to +ve, result sign in d3
        bpl.s   lib4d
        neg.l   d1
        not     d3
lib4d:  moveq.l #0,d2       ; init d2 as working result
lib4a:  asr.l   #1,d0       ; shift d0 right
        bcs.s   lib4b       ; if a bit fell off, update result
        asl.l   #1,d1       ; either way, shift left d1
        tst.l   d0
        bne.s   lib4a       ; if d0 non-zero, continue
        tst.l   d3          ; basically done - apply sign?
        beq.s   lib4e       ; was broken! now fixed
        neg.l   d2
lib4e:  rts
lib4b:  add.l   d1,d2      ; main loop body - update result
        asl.l   #1,d1
        bra.s   lib4a

By the way - I never did figure out whether it was necessary to convert everything to positive at the start. If you're careful with the shift operations, that may be avoidable overhead.

Steve314
A: 

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.

David Cary