topic Re: Division...extending bit width in 8-bit Microcontrollers

Division...extending bit width

DustyStew — Thu, 05 Apr 2007 22:45:50 GMT

Hi All

The Freescale Integer Math app note (AN1219) does not use the DIV instruction for extending division to 32 bit dividend/16 bit divisor, the author resorts to shift and subtract. I have not been able to find an algorithm that takes a advantage of a hardware divide instruction.

Does anyone have working code that uses DIV, or is it inherently inefficient and thus pointless?

TIA
Tom

Re: Division...extending bit width

rocco — Fri, 06 Apr 2007 03:03:20 GMT

Hi, Tom:

I don't think it is that extending the DIV instruction to 32 bits is inefficient. I think it is simply not possible.

Unlike multiplying, dividing is non-deterministic. So it can't be broken up into pieces like a multiply can. Hence, the shift/subtract algorithm that operates on the full 32 bits.

Re: Division...extending bit width

CompilerGuru — Fri, 06 Apr 2007 20:25:10 GMT

Reducing multi byte divisions to single byte division is possible.
The basic idea is to use the single byte division for a good estimate of the first bits of the quotient, then subtract the estimate times the dividend from the divisor and restart.
See Donald E. Kunth's "The Art of Computer Programming", Volume 2 for details, but Knuth really shows the concepts. Applying this to a HC08 is another story.

For the HC08 I did not see an actual implementation and I wonder too how it compares to compare, subtract and shift. My estimates are that it is faster, but also larger and more complicated. Also the time it takes to divide would depend on the arguments, but I guess the worst case is still a bit faster.

Daniel

Re: Division...extending bit width

DustyStew — Sat, 07 Apr 2007 05:09:46 GMT

OK...those two answers add up to one answer which make sense. DIV can be used in an extended divide operation, but it is one of those algorithms that converges on an answer given repeated iterations.

My thought had been that I might be able to shift the divisor (and/or dividend) until there was a 1 in the MSB...ie skip the leading zeros to the left of the first 1 bit. And somehow that would lead to an answer. That's about as far as my thinking got on it.

The other algorithm I have become aware of is multiplication by the reciprocal, though I have not read the article yet and so at the moment don't know how to derive the reciprocal.

Thanks very much for your answers, that is very useful in keeping me off of a blind alley!

Re: Division...extending bit width

Wings — Thu, 19 Apr 2007 06:50:49 GMT

I ran across this earlier today in one of my old projects and it jogged my memory ... someone, somewhere was asking about this. I just now remembered where it was so thought I'd stick it up here in case it's found to be helpful. It may not be exactly what the original poster was looking for, but it's at least close. Maybe it can be adapted to fit.

Code:

;
; Divide 5 bytes at M (base page) by AccA, result to M.
;
BIGDIV PSHA  ;SAVE DIVISOR ON STACK.
 LDHX #M ;(M must be on base page)
 PSHH  ;REMAINDER ON STACK (INITIALLY 0).
BIGD040 LDA 0,X ;NEXT BYTE OF DIVIDEND.
 PULH  ;RESTORE REMAINDER.
 PSHX  ;SAVE PTR TO DVDND.
 LDX 2,SP ;THE DIVISOR.
 DIV  ;DIVIDE H:A BY DIVISOR.(H=REMAINDER)
 PULX  ;GET BACK PTR TO DIVIDEND.
 PSHH  ;SAVE REMAINDER.
 CLRH
 STA 0,X ;REPLACE DVDND BYTE WITH QUOTIENT.
 INCX  ;PTR TO NEXT BYTE OF DIVIDEND.
 CPX #M+4 ;ALL DONE?
 BLS BIGD040 ;IF NOT, LOOP.
 AIS #2 ;DISCARD REMAINDER & DIVISOR.
 RTS

Re: Division...extending bit width

bigmac — Thu, 19 Apr 2007 11:44:39 GMT

Hello,

If the divisor is an 8-bit value, it is straight forward to use the DIV instruction, as Wings has shown. Effectively, a "long division" process is used, with a byte value replacing each decimal value. As for normal decimal long division, the process may also be extended to include a fractional value to the right of the binary point.

However, the problem is using DIV when a 16-bit value is required for the divisor, and other, more fundamental methods are used.

An exception could be if the divisor can be factored into two 8-bit values, i.e. (Value / D1) / D2 where D = D1*D2,

or even ((Value / D1)*M) / D2 where D ~= D1*D2 / M, and M is a relatively low integer value. But this is likely applicable only in special cases.

Regards,

Mac

Re: Division...extending bit width

DustyStew — Thu, 19 Apr 2007 22:37:06 GMT

Thanks for that code. Assuming I can work out how to get the remainder (it appears you have it but you are simply discarding it) I would use for it in the conversion of long numbers into ASCII. I am reckoning that the fastest conversion is...

1. divide by 100
2. convert remainder to BCD with the DAA instruction
3. Add '0' to each nybble and put them into the text buffer
4. repeat til dividend is 0

But now I am digressing.

Re: Division...extending bit width

DustyStew — Fri, 20 Apr 2007 00:21:40 GMT

Based on Wing's code, I created a version of the divide by byte routine which uses the stack to pass the dividend and divisor. There is no pointer required, so the remainder can stay in H. No loop counter, it's inline code, so takes a few more bytes.

I tested this, but with a different calling convention. SO I SURE HOPE THIS VERSION WORKS!

;* NAME: divide_by_8bit
;* DESCRIPTION: Divide a 16/24/32 bit number by an 8 bit number
;* Push the dividend and divisor before calling.
;*
;* ARGS: SP+3= 8 bit divisor SP+4= dividend
;* RETURNS: SP+3= 8 bit remainder SP+4= quotient

DIVIDEND_BITS EQU 32

divide_by_8bit:
clrh
lda 4,SP ; get 1st byte of dividend
ldx 3,SP ; get divisor
div ; divide H:A by X (H=remainder)
sta 4,SP ; replace dividend with quotient
; leave remainder in H
lda 5,SP ; same for 2nd byte
ldx 3,SP
div
sta 5,SP

IF DIVIDEND_BITS > 16
lda 6,SP ; same for 3rd byte
ldx 3,SP
div
sta 6,SP

IF DIVIDEND_BITS > 24
lda 7,SP ; same for 4th byte
ldx 3,SP
div
sta 7,SP
ENDIF

ENDIF
pshh
pula
sta 3,SP ; remainder replaces divisor
clrh
rts

Re: Division...extending bit width

bigmac — Fri, 20 Apr 2007 09:21:51 GMT

Hello,

If you actually require to do binary-to-numeric ASCII conversion, the following thread may also be of interest -

http://forums.freescale.com/freescale/board/message?board.id=8BITCOMM&message.id=3288&query.id=8231#M3288

It addresses binary-to-BCD conversion, however a numeric ASCII output is closely related.

Regards,

Mac

Re: Division...extending bit width

DustyStew — Wed, 25 Apr 2007 14:17:56 GMT

Fixing my own code...no need to reload divisor each time, as DIV does not change X.

divide_by_8bit:
clrh
lda 4,SP ; get 1st byte of dividend
ldx 3,SP ; get divisor
div ; divide H:A by X (H=remainder)
sta 4,SP ; replace dividend with quotient
; leave remainder in H
lda 5,SP ; same for 2nd byte
div
sta 5,SP
IF DIVIDEND_BITS > 16
lda 6,SP ; same for 3rd byte
div
sta 6,SP
IF DIVIDEND_BITS > 24
lda 7,SP ; same for 4th byte
div
sta 7,SP
ENDIF
ENDIF
pshh
pula
sta 3,SP ; remainder replaces divisor
clrh
rts