Divide algorithm?

[ahydra]

Hi,

After being introduced to the 16F887 I'm having good fun with it. I'm now 99% of the way towards a completed digital clock project - the clock can't do a lot, but you can set the time )), view the temperature and set the brightness level.

I needed to code multiplication and division. Multiplication was no problem with the Russian Peasant's method, but I'm still stuck for a decent division algorithm. I currently have this:

; calculates the integer divide and modulus of two numbers
; in: c1, c2
; out: c1 = c1 mod c2, c2 = c1 div c2

  MOVLW 0x01				; division by zero crash code
  MOVF c2, 1
  BTFSC STATUS, Z			; test c2 = 0
  GOTO crash				; division by zero error
  
  MOVF c2, 0				; W holds c2 for repeated subtraction
  CLRF c2				; c2 holds quotient
divideloop
  SUBWF c1, 1
  BTFSS STATUS, C			; carry bit clear if c2 > c1
  GOTO divideend
  INCF c2, 1				; increment quotient
  MOVF c1, 1			
  BTFSC STATUS, Z			; if c1 is exactly zero, need to end here
  GOTO divideend2
  GOTO divideloop

divideend				; at this point quotient is right but modulus is negative
  ADDWF c1, 1
divideend2				; at this point quotient and modulus are right
  RETURN

In short, it keeps subtracting the divisor from the dividend until the result is zero or negative, counting how many times it took to get there. Clearly this is only good when the quotient is small.

I thought of a binary search method - for instance, dividing 60 by 7 might go something like:

make 60 into next highest power of 2: 64
make 7 into next lowest power of 2: 4

therefore result <= 16

make 60 into next lowest power of 2: 32
make 7 into next highest power of 2: 8

therefore result >= 4

so result is between 4 and 16
middle of 4 and 16 is 10, 10 * 7 = 70, so 10 is too high
middle of 4 and 10 is 7, 7 * 7 = 49, so 7 is too low
middle of 7 and 10 is 8, 8 * 7 = 56, so 8 is too low
middle of 8 and 10 is 9, 9 * 7 = 63, so 9 is too high
middle of 8 and 9 is 8, which is equal to one of the boundaries
so result is the lower of the boundaries (8)

finally, calculate the remainder: 60 - (8*7) = 4
so result is 8 with remainder 4

However I'm not certain this would be more efficient. I guess the number of iterations is limited to about n, where n is the lower of the two numbers you get in the first stage (approximating the parameters by powers of two) - but you need to call the multiplication algorithm once per iteration which adds several extra lines of code.

Any thoughts / does somebody know a decent division algorithm using only add/subtract?

On a side note, if you know about voltage regulators etc, could you also please take a look at this thread.

ahydra

p.s. I did think "you need divide to calculate the middle point", but realised one can do that with a RRF:

MOVF low, 0
ADDWF high, 0
MOVWF middle
BCF STATUS, C ; no sneaky bits coming back in the MSB end please
RRF middle, 1 ; same as dividing by two

 

[Pommie]

Have a look at Microchips **broken link removed** routines.

Mike.

 

[ericgibbs]

Also look here:

 

[Nigel Goodwin]

I suggest you consult the PICList, lot's of maths routines and discussion there.

 

[rolls]

Considered writing the code in C? MPLAB with the C compiler works very well and simplifies things like this an awful lot. Whilst you can certainly optimise your code more in asm, the C compiler does a great job of optimisation and I really really doubt you are going to be limited by CPU cycles when writing software for a clock.

 

[atferrari]

Would you like to consider the routines shown here, under "Pics"?:

**broken link removed**

 

[Diver300]

Use a PIC24, with what is effectively built-in divide, as well as multiply.

Otherwise has several good multiply routines.

Why do you need a divide? There are lots of tricks to avoid needing to use a divide. I can't think of any reason why you need to divide by a variable in a clock.

If you want to divide by a constant in a PIC16F887, you can use the multiply routine and multiply by (256 / k), where you calculate (256 / k) with a calculator and program the result onto the PIC.

For example, if you want to divide by 6, multiply by 43 and take the top byte only.

19 / 6 = 3.16666

on the PIC, 19 * 43 = 817, or 0x331. The result is in 2 bytes, 0x03 and 0x31 Just take the top byte, which is 0x03

 

[ahydra]

That multiply/take the higher byte thing is a nice trick. I'll probably use that in future as my multiplication routine is 8x8->16. (It's for working out the characters to display - for instance seconds div 10, seconds mod 10)

Edit: it suffers from rounding errors. For example if I want to divide by 10 I would multiply by 26 and take the top byte, but 99 * 26 = 2574 with a top byte of 10 instead of 9.

So I'm going to go and figure out how the one at ericgibbs' link works.

Thanks all for your help.

ahydra