# PICMicrocontollerMathMethod

## 48 by 24 bit division from Nikolai Golovchenko, Scott Dattalo and Tony Kübek

Tony posted

```;
***********************************************************************
; DIVIDE_48by24 - Routine to divide a 48 bit number with a 24 bit number

; result upto 48 bits !
;
; Formula:      Dividend = Dividend/Divisor
;
; Format:       Little endian, Ram = msb, Ram+x = lsb ( where
x=bytesize-1)
; Ram used:     Dividend 6 bytes ( 48 bits )
;               Divisor 3 bytes ( 24 bits )
;               Temp 3 bytes
;               BitCount 1 byte for loop counting ( and temp. saving of
carry )
;
; Divisor is preserved
; Dividend holds result
; Returns with zero in W if failed ( division with zero )
; Else returns with one in w
;
; Based on pseudo-code from Nikolai Golovchenko [golovchenko@mail.ru]
;
;
DIVIDE_48by24

; Test for zero division
MOVF    Divisor,W
IORWF   Divisor+1,W
IORWF   Divisor+2,W
BTFSC   STATUS,Z
RETLW   0x00    ; divisor = zero, not possible to calculate return with zero in w

; prepare used variables
CLRF    Temp
CLRF    Temp+1
CLRF    Temp+2

MOVLW   D'48'           ; initialize bit counter
MOVWF   BitCount

CLRC    ; clear carry at entry

DIVIDE_LOOP_48by24
; a) first time carry cleared
; b) every other bit carry contains the result of
;    last subtraction ( division ).
; shift in carry as lowest bit
RLF     Dividend+5,F
RLF     Dividend+4,F
RLF     Dividend+3,F
RLF     Dividend+2,F
RLF     Dividend+1,F
RLF     Dividend,F
; shift in highest bit from dividend through carry in temp
RLF     Temp+2,F
RLF     Temp+1,F
RLF     Temp,F
; save carry status in bitcounter temporarily ( possible overflow from temp msb )
BTFSC   STATUS,C
BSF     BitCount,7      ; set bit ( carry was set, temp>24bit)

; subtract 24 bit divisor from 24 bit temp
MOVF    Divisor+2,W     ; get lsb
SUBWF   Temp+2,F        ; subtract

MOVF    Divisor+1,W     ; get middle byte
SKPC                    ;  if overflow ( from prev. subtraction )
INCFSZ       Divisor+1,W ; incresase source
SUBWF   Temp+1,F ; and subtract from dest.

MOVF    Divisor,W               ; get top byte
SKPC                    ;  if overflow ( from prev. subtraction )
INCFSZ       Divisor,W ; increase source
SUBWF   Temp,F  ; and subtract from dest.

;        BTFSC   STATUS,C        ; save carry status again to use for negative check
;        BSF     BitCount,7      ; yes carry was set.

; if was carry set ( saved in top bit of bitcount ):
; a) Temp overflowed ( i.e. temp > divisor )
; b) Result was positive from subtraction ( i.e. temp > divisor )
; if carry was cleared:
; a) temp < divisor

;        BTFSC   BitCount,7
;        GOTO    DIVIDE_SKIP_48by24 ; carry was set, subtraction ok, continue with next bit
;Scott Dattalo says:
;...[the lines above which are commented out can be] reduced to:

skpc
btfsc  BitCount,7
goto  DIVIDE_SKIP_48by24

; result of subtraction was negative restore temp
MOVF    Divisor+2,W     ; get LSB of divisor

MOVF    Divisor+1,W     ; middle byte
BTFSC   STATUS,C        ; check carry for overflow from previous addition
INCFSZ  Divisor+1,W     ; if carry set we add 1 to the source
ADDWF   Temp+1,F        ; and add it if not zero in that case Product+Multipland=Product

MOVF    Divisor,W       ; MSB byte
BTFSC   STATUS,C        ; check carry for overflow from previous addition
INCFSZ  Divisor,W

DIVIDE_SKIP_48by24
;        CLRC    ; clear carry
; carry should now reflect if divison was possible ( i.e. temp > divisor )
; so if it was set, set carry to be shifted in as lowest bit of Dividend
;        BTFSC   BitCount,7
;        BSF     STATUS,C        ; restore carry
;        BCF     BitCount,7      ; clear bit used for saving carry
;        DECFSZ  BitCount,F      ; decrement loop counter
;        GOTO    DIVIDE_LOOP_48by24      ; another run
;Scott Dattalo says:
;...[the lines above which are commented out can be] reduced to:

rlf     BitCount,W             ;Restore the carry
bcf     BitCount,7             ;clear temporary carry
decfsz  BitCount,F
goto   DIVIDE_LOOP_48by24

; finally shift in the last carry
RLF     Dividend+5,F
RLF     Dividend+4,F
RLF     Dividend+3,F
RLF     Dividend+2,F
RLF     Dividend+1,F
RLF     Dividend,F
NOP
NOP
RETLW   0x01    ; done

```

Nik commented:

Some ideas to improve it:
1. ) Saving carry in counter can be made like at 24by16

to save carry in counter:

```        rlf BitCount, f

```

to check carry and BitCount.0 after subtraction:

```        SKPNC                   ;if no borrow
BSF BitCount, 0        ;set bit 0 of counter (saved carry)
BTFSC BitCount, 0       ;if no borrow
GOTO DIVIDE_SKIP_48by24 ;jump

```

to restore carry and counter:

```        CLRC                    ;copy bit 0 to carry
RRF BitCount, F         ;and restore counter

```

Total: 7 instructions instead of 10 (same savings as in Scott's proposal though) It's hard to beat Scott :)

2. ) Clearing carry not necessary before loop.
3. ) Using slightly different method can improve speed a lot with small code increase. That can be achieved if you don't restore the remainder in the same iteration. You can do just one subtraction/addition in each iteration. Subtract from remainder if remainder is positive or zero and add to remainder if remainder is negative.

For example let's divide 10101100 (172) by 1001 (9) using this nonrestoring method:

```  C Temp Dividend
= ==== ========
0 0001 0101100x  (x - garbage after initial shift)
-   1001
----------------
0 1000 0101100x -> borrow, first bit of result is 0

next iteration (2nd),
1 0000 101100x0
+   1001
-----------------
0 1001 101100x0 -> no carry, next bit of result is 0

next iteration (3rd),
1 0011 01100x00
+   1001
------------------
0 1100 01100x00 -> no carry, next bit of result is 0
```

It actually works!

Because the remainder can be negative as well as positive in the non-restoring division method, the sign must be kept somewhere. The easiest case is division of 48 by 23 bits. In that case the remainder (Temp) MSbit is free and can be used for sign bit.

But when divisor is 24 bit, Temp should be extended to hold sign. That consumes one more byte of RAM but saves 9 cycles per loop (original was 42 minus 3 optimized vs 30 in the non-restoring routine). That makes about 48*9=432 cycles total savings!

Probably BitCount can be used as additional space for sign storage, but I don't know how to do that as efficiently for speed.

See both versions below.

Nikolai

```;****************************************************
;max time in loop: 26 cycles
DIVIDE_48by23

; Test for zero division
MOVF    Divisor,W
IORWF   Divisor+1,W
IORWF   Divisor+2,W
BTFSC   STATUS,Z
RETLW   0x00    ; divisor = zero, not possible to calculate return with zero in w

; prepare used variables
CLRF    Temp
CLRF    Temp+1
CLRF    Temp+2

MOVLW   D'48'           ; initialize bit counter
MOVWF   BitCount

setc
DIVIDE_LOOP_48by23
RLF     Dividend+5,F
RLF     Dividend+4,F
RLF     Dividend+3,F
RLF     Dividend+2,F
RLF     Dividend+1,F
RLF     Dividend,F
; shift in highest bit from dividend through carry in temp
RLF     Temp+2,F
RLF     Temp+1,F
RLF     Temp,F

MOVF    Divisor+2,W     ; get LSB of divisor
btfss   Dividend+5, 0

; subtract 23 bit divisor from 24 bit temp
SUBWF   Temp+2,F        ; subtract

MOVF    Divisor+1,W     ; get middle byte
SKPC                    ;  if overflow ( from prev. subtraction )
INCFSZ  Divisor+1,W     ; incresase source
SUBWF   Temp+1,F        ; and subtract from dest.

MOVF    Divisor,W       ; get top byte
SKPC                    ;  if overflow ( from prev. subtraction )
INCFSZ  Divisor,W       ; increase source
SUBWF   Temp,F          ; and subtract from dest.
GOTO    DIVIDE_SKIP_48by23 ; carry was set, subtraction ok, continue with next bit

; result of subtraction was negative restore temp

MOVF    Divisor+1,W     ; middle byte
BTFSC   STATUS,C        ; check carry for overflow from previous addition
INCFSZ  Divisor+1,W     ; if carry set we add 1 to the source
ADDWF   Temp+1,F        ; and add it if not zero in that case Product+Multipland=Product

MOVF    Divisor,W       ; MSB byte
BTFSC   STATUS,C        ; check carry for overflow from previous addition
INCFSZ  Divisor,W

DIVIDE_SKIP_48by23
DECFSZ  BitCount,F      ; decrement loop counter
GOTO    DIVIDE_LOOP_48by23      ; another run
; finally shift in the last carry
RLF     Dividend+5,F
RLF     Dividend+4,F
RLF     Dividend+3,F
RLF     Dividend+2,F
RLF     Dividend+1,F
RLF     Dividend,F
RETLW   0x01    ; done

;****************************************************
;max time in loop: 30 cycles
DIVIDE_48by24

; Test for zero division
MOVF    Divisor,W
IORWF   Divisor+1,W
IORWF   Divisor+2,W
BTFSC   STATUS,Z
RETLW   0x00    ; divisor = zero, not possible to calculate return with zero in w

; prepare used variables
CLRF    Temp
CLRF    Temp+1
CLRF    Temp+2

clrf    Temp2

MOVLW   D'48'           ; initialize bit counter
MOVWF   BitCount

DIVIDE_LOOP_48by24
RLF     Dividend+5,F
RLF     Dividend+4,F
RLF     Dividend+3,F
RLF     Dividend+2,F
RLF     Dividend+1,F
RLF     Dividend,F
; shift in highest bit from dividend through carry in temp
RLF     Temp+2,F
RLF     Temp+1,F
RLF     Temp,F

rlf     Temp2, f

MOVF    Divisor+2,W     ; get LSB of divisor
btfsc   Temp2, 7

; subtract 24 bit divisor from 24 bit temp
SUBWF   Temp+2,F        ; subtract

MOVF    Divisor+1,W     ; get middle byte
SKPC                    ;  if overflow ( from prev.
subtraction )
INCFSZ  Divisor+1,W     ; incresase source
SUBWF   Temp+1,F        ; and subtract from dest.

MOVF    Divisor,W       ; get top byte
SKPC                    ;  if overflow ( from prev.
subtraction )
INCFSZ  Divisor,W       ; increase source
SUBWF   Temp,F          ; and subtract from dest.

movlw 1
skpc
subwf   Temp2, f
GOTO    DIVIDE_SKIP_48by24 ; carry was set, subtraction ok, continue with next bit

; result of subtraction was negative restore temp

MOVF    Divisor+1,W     ; middle byte
BTFSC   STATUS,C        ; check carry for overflow from previous addition
INCFSZ  Divisor+1,W     ; if carry set we add 1 to the source
ADDWF   Temp+1,F        ; and add it if not zero in that case Product+Multipland=Product

MOVF    Divisor,W       ; MSB byte
BTFSC   STATUS,C        ; check carry for overflow from previous addition
INCFSZ  Divisor,W

movlw 1
skpnc

DIVIDE_SKIP_48by24
DECFSZ  BitCount,F      ; decrement loop counter
GOTO    DIVIDE_LOOP_48by24      ; another run
; finally shift in the last carry
RLF     Dividend+5,F
RLF     Dividend+4,F
RLF     Dividend+3,F
RLF     Dividend+2,F
RLF     Dividend+1,F
RLF     Dividend,F
RETLW   0x01    ; done

;****************************************************

```

 file: /Techref/microchip/math/div/48by24ng.htm, 13KB, , updated: 2004/7/12 23:50, local time: 2020/2/20 22:08, owner: NG--944, TOP NEW HELP FIND:  35.173.57.84:LOG IN

 ©2020 These pages are served without commercial sponsorship. (No popup ads, etc...).Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE. Questions?Please DO link to this page! Digg it! / MAKE! PIC Microcontoller Math Method - 48 by 24 bit division

After you find an appropriate page, you are invited to your to this massmind site! (posts will be visible only to you before review) Just type in the box and press the Post button. (HTML welcomed, but not the <A tag: Instead, use the link box to link to another page. A tutorial is available Members can login to post directly, become page editors, and be credited for their posts.

Attn spammers: All posts are reviewed before being made visible to anyone other than the poster.
 Did you find what you needed? "No. I'm looking for: " "No. Take me to the search page." "No. Take me to the top so I can drill down by catagory" "No. I'm willing to pay for help, please refer me to a qualified consultant" "No. But I'm interested. me at when this page is expanded."

.