PIC Microcontoller Math Method

Divide 24 bits by 16

Andrew David (akdavid at ultronics.co.uk), Software Manager, Ultronics Ltd, Cheltenham says:

This division routine uses the standard binary long-division algorithm. The loop iterates once for each bit in the numerator, so it goes round 24 times. For each loop the numerator (sorry, but I can never remember which is the dividend and the divisor - I guess the divisor is the denominator, but I'd hate to get it wrong) is left shifted 1 bit into the remainder, then the remainder is compared with the denominator. If the remainder is greater than the denominator, the denominator is subtracted from the remainder and a 1 is shifted into the quotient, otherwise a 0 is shifted into the quotient. If you can't see how the routine works, try running through an example on paper, in binary, then think about how you'd write the routine. 
;=============================================================================
; DIV24_16u
;
;       Divides a 24bit number by a 16bit number. Unsigned.
;
;       Inputs: 
;		24-but numerator in ACCcLO:ACCdHI:ACCdLO
;		16-bit denominator in ACCbHI:ACCbLO
;
;       Outputs: 
;		24-bit quotient in ACCcLO:ACCdHI:ACCdLO
;		16-bit rem in ACCaHI:ACCaLO
;
;	Locals used:
;		R5Hi
;
;
; Inputs are not preserved.
; 
; No timing analysis performed.
; Andrew David, Software Manager, Ultronics Ltd, Cheltenham
; akdavid at ultronics.co.uk          http://www.ultronics.com
;
;=============================================================================

DIV24_16u:
        movlw   .24             ; for 24 shifts
        movwf   R5Hi            ;

        clrf    ACCaHI,f        ; clear remainder.
        clrf    ACCaLO,f        ;

d2416lp:rlcf    ACCdLO,f        ; build up remainder.
        rlcf    ACCdHI,f        ;
        rlcf    ACCcLO,f        ;
        rlcf    ACCaLO,f        ;
        rlcf    ACCaHI,f        ;

; remainder is 16-bit, but may have spilled over into carry.

        btfss   ALUSTA,C        ; check for remainder spill into carry.
        goto    d2416s          ;

        movfp   ACCbLO,WREG     ;
        subwfb  ACCaLO,f        ; Carry bit is the 17th bit of this
subtract!
        movfp   ACCbHI,WREG     ;
        subwfb  ACCaHI,f        ;
        bsf     ALUSTA,C        ; bit is known to be zero here.
        goto    d2416ns         ;

d2416s: movfp   ACCbLO,WREG     ; Compare remainder with divisor.
        subwf   ACCaLO,w        ;
        movfp   ACCbHI,WREG     ;
        subwfb  ACCaHI,w        ;
        btfss   ALUSTA,C        ;
        goto    d2416ns         ; (remainder < divisor), shift in a '0'
        movfp   ACCbLO,WREG     ; The remainder is larger, so subtract
the
        subwf   ACCaLO,f        ; ... divisor FROM the remainder and
        movfp   ACCbHI,WREG     ; ... shift a '1' into the quot.
        subwfb  ACCaHI,f        ;

d2416ns:decfsz  R5Hi,f          ; check all bits
        goto    d2416lp         ;
        rlcf    ACCdLO,f        ; shift in final quotient bit.
        rlcf    ACCdHI,f        ;
        rlcf    ACCcLO,f        ;

        return

jaakko-haakana- Says:

This code does not work if the divisor is smaller than 0x100.

Replace the five instructions at d2416s with the following to make it work (converted for 16f84): 

        movf   ACCbHI,W     ; divisor hi
        subwf  ACCaHI,w        ; remainder hi (w = remainder - divisor)
	btfss	STATUS, C
	goto	d2416ns		; (remainder < divisor), shift in a '0'
	movf   ACCbLO,W
        subwf   ACCaLO,w 
        btfss   STATUS,C

Andy David of Ultronics Ltd Says:

The above (anonymous) poster has not convinced me that the original code doesn't work -- my test cases for divisor < 0x100 are all correct.

The original code is for the 17c series pics, hence the use of the subwfb instruction. The purpose of the first 5 lines of code at d2416s is to compare the current remainder with the (constant) divisor. Using a 16-bit subtract abd checking the status of carry is standard, I can't get this code to fail. The carry that is subsequently shifted into the quotient is correct as either remainder => divisor (when remainder - divisor is +ve (>= 0) carry = 1) or remainder < divisor (carry = 0).

I've just tried several test cases with divisor < 0x100, I can't see any problem. As a benchmark I've used BaseCalc.

The alternative code looks like it will work but I don't believe there's a reason for using it; you'd normally need a good reason to replace 5 (working) lines of code with 7.

Note that if you want to use this code for 14-bit core you'll need to change more code than suggested.

Now that I've finished saying that the code works, I refer the reader to the standard disclaimer in that I'm not responsible for your use of this code. Clever people use Dimitry's, Nikolai's or Scott's code, anyway.

-- AD.

Questions:

Interested: