please dont rip this site

PIC Microcontoller Math Method

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
        ADDWF   Temp+2,F        ; add it to the lsb of 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
        ADDWF   Temp,F  	; handle overflow

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
        goto    Div48by23_add
        
        ; 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

Div48by23_add
        ; result of subtraction was negative restore temp
        ADDWF   Temp+2,F        ; add it to the lsb of 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
        ADDWF   Temp,F          ; handle overflow

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
        goto    Div48by24_add

        ; 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

Div48by24_add
        ; result of subtraction was negative restore temp
        ADDWF   Temp+2,F        ; add it to the lsb of 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
        ADDWF   Temp,F          ; handle overflow

        movlw 1
        skpnc
         addwf   Temp2, f

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

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


See also:


file: /Techref/microchip/math/div/48by24ng.htm, 13KB, , updated: 2004/7/13 00:50, local time: 2018/4/25 11:20, owner: NG--944,
TOP NEW HELP FIND: 
54.198.122.70:LOG IN

 ©2018 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! / 

<A HREF="http://www.piclist.com/techref/microchip/math/div/48by24ng.htm"> PIC Microcontoller Math Method - 48 by 24 bit division</A>

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.


Link? Put it here: 
if you want a response, please enter your email address: 
Attn spammers: All posts are reviewed before being made visible to anyone other than the poster.
Did you find what you needed?

  PICList 2018 contributors:
o List host: MIT, Site host massmind.org, Top posters @20180425 RussellMc, Van Horn, David, Sean Breheny, Isaac M. Bavaresco, Bob Blick, Neil, David C Brown, alan.b.pearce, Brent Brown, John Gardner,
* Page Editors: James Newton, David Cary, and YOU!
* Roman Black of Black Robotics donates from sales of Linistep stepper controller kits.
* Ashley Roll of Digital Nemesis donates from sales of RCL-1 RS232 to TTL converters.
* Monthly Subscribers: Gregg Rew. on-going support is MOST appreciated!
* Contributors: Richard Seriani, Sr.
 

Welcome to www.piclist.com!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  .