Help with assembly language divide.

mynet43 · 2013-03-23 19:55

I need to divide a 32 bit unsigned number by a constant. The constant is either 72 or 10 (1001000 or 1010).

Would someone please help me with an optimized way to divide a 32 bit number by these two constants.

Thank you for your help.

Jim

Kye · 2013-03-23 20:46

' /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
'                       Unsigned Divide
' /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


LNDivide                mov     LNDivideQuotient,       #0                           ' Setup to divide.
                        mov     LNDivideBuffer,         #0                           '
                        mov     LNDivideCounter,        #32                          '


                        tjz     LNDivideDivsor,         #LNDivide_ret                ' Clear if dividing by zero.


LNDivideLoopPre         shr     LNDivideDivsor,         #1 wc, wz                    ' Align divisor MSB and count size.
                        rcr     LNDivideBuffer,         #1                           '
if_nz                   djnz    LNDivideCounter,        #LNDivideLoopPre             '


LNDivideLoopPost        cmpsub  LNDivideDividend,       LNDivideBuffer wc            ' Preform division.
                        rcl     LNDivideQuotient,       #1                           '
                        shr     LNDivideBuffer,         #1                           '
                        djnz    LNDivideCounter,        #LNDivideLoopPost            '


LNDivide_ret            ret                                                          ' Return. Remainder in dividend on exit.


' /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
'                       Unsigned Multiply
' /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


LNMultiply              mov     LNMultiplyProduct,      #0                           ' Clear product.


LNMultiplyLoop          shr     LNMultiplyMultiplicand, #1 wc                        ' Preform multiplication.
if_c                    add     LNMultiplyProduct,      LNMultiplyMultiplier         '
                        shl     LNMultiplyMultiplier,   #1                           '
                        tjnz    LNMultiplyMultiplicand, #LNMultiplyLoop              '


LNMultiply_ret          ret                                                          ' Return.

LNDivideDividend        res     1
LNDivideDivsor          res     1
LNDivideQuotient        res     1
LNMultiplyMultiplicand  res     1
LNMultiplyMultiplier    res     1
LNMultiplyProduct       res     1

Usage

mov LNMultiplyMultiplicand, #10
mov LNMultiplyMultiplier, #100
call #LNMultiply
' LNMultiplyProduct now equals 1000

mov LNDivideDividend, #100
mov LNDivideDivisor, #10
call #LNDivide
' LNDivideQuotient now equals 10
' LNDividend now equals the remainder

mynet43 · 2013-03-23 20:58

Hi Kye,

Thank you for the sample code. I'll take a look at it. I think this should help. It looks like your pre loop may be the trick.

Regards,

Jim

Mark_T · 2013-03-24 05:13

If you don't need full accuracy you can do much better by shifts/add/subs - rather than divide by 10, you'd multiply by 0.1, and this
is a repeating binary expansion that can be computed by various tricks is a few shifts and adds.

mynet43 · 2013-03-24 07:31

Questions for Mark and Kye

Mark. I need about 4 digits decimal accuracy from a dividend ranging from 1_600_000 to 1_600_000_000. Can you give me an example of your coding suggestion for divide by 10. If it works, I'm happy to have a dedicated routine just for this.

Kye. In your code, it looks like the initial values of LNDivideBuffer and LNDivideCounter depend ONLY on the value of LNDivideDivsor. If this divisor is a constant, then I should be able to precalculate these values, use them as constants, and greatly reduce the initialization and the number of loops required to get the answer. Does this seem right?

Thanks for all your help!

Jim

tonyp12 · 2013-03-24 07:48

>ranging from 1_600_000 to 1_600_000_000
Are the values in +1 steps or +512 steps?, as I try to see if the lower 9bits are always unused.

some info on how to use shr to help out.
http://www.tofla.iconbar.com/tofla/arm/arm02/index.htm

Kye · 2013-03-24 08:23

Yes mynet43, you can do that.

Mike G · 2013-03-24 08:32

There's also Appendix B: Math Samples and Function Tables in the propeller manual...

mynet43 · 2013-03-24 09:36

Tony,

The value comes from cnt. It's the time it takes an engine distributor to make one revolution, based on the input from a hall-effect sensor.

I have twelve events I have to process during each revolution, so time is critical at 6000 RPM.

For this application, I'm not sure the last 9 bits matter. So what did you have in mind?

All these ideas are really great!

Thanks for your help.

Jim

tonyp12 · 2013-03-24 11:27

>I'm not sure the last 9 bits matter. So what did you have in mind?

Add #256 to value to round it, andn #511 to mask out the lower 9bits.
Divide by 10 or 72
Remember, your value now have a decimal point at 9th bit (you just divided it by 512)
so cmpsub with #5120 to see how many times you can subtract #10.0 from your main value.
But as I have not tested it, you have to look up correct ways to div

The lower 9bits will be reserved for your decimal point value.
Of course this decimal point is all simulated.
and it's up to you to make sure and data added/subtracted also have a simulated 9bits of decimals.

Tracy Allen · 2013-03-24 11:49

Pointing back to this thread.

As noted, 1/10 is a repeating binary fraction:
%.000_1100_1100_1100_1100_1100_1100_1100_1
and can probably ignore the lsb 1.
So multiplication starts with * %.1100,
sar x, #1
mov t1, x
sar t1, #1
add x, t1 ' now have %.1100 in x
followed by 6 repetitions of shifting that 4 bits right and adding to the accumulator, then a final right shift by three. Or shorten code by using intermediate results 1100_1100 or 1100_1100_1100.

Mark_T · 2013-03-24 15:11

Tracy Allen wrote: »

Pointing back to this thread.

As noted, 1/10 is a repeating binary fraction:
%.000_1100_1100_1100_1100_1100_1100_1100_1
and can probably ignore the lsb 1.
So multiplication starts with * %.1100,
sar x, #1
mov t1, x
sar t1, #1
add x, t1 ' now have %.1100 in x
followed by 6 repetitions of shifting that 4 bits right and adding to the accumulator, then a final right shift by three. Or shorten code by using intermediate results 1100_1100 or 1100_1100_1100.

Ah, yes but there is a cleverer trick than iterating, original a trick in HAKMEM I think:

OK, you've got the value x .00011, so you shift right 4 and add back, gives x.000110011, then you shift right 8, addback, gives x.00011001100110011,
shift right 16, add back and you have all 32 bits...

Fortunately 1/72 is also a simple repeating form: x .000000111000111000111000111000111....
so you shift right 3 and subtract from original, gives x.111, then shift right 6, then take this value and apply a similar procedure with shifts of 6, 12 and 24

[ if you like you can think of the divide by 10 example as first multiplying by 3/32, then by 17/16, then by 257/256, then by 65537/65536,
and 3 / 32 * 17 / 16 * 257 / 256 * 65537 / 65536 = 0.09999999995 ]

Help with assembly language divide.

Comments