• AVR Freaks

16 bit divided by constant 5

Page: 12 > Showing page 1 of 2
Author
Post
Essentials Only Full Version
piccandies
Super Member
  • Total Posts : 222
  • Reward points : 0
  • Joined: 2008/08/12 23:12:23
  • Location: 0
  • Status: offline
2009/03/12 23:56:17 (permalink)
0

16 bit divided by constant 5

Does anyone have a quick/slick 18F asm method to divide 16 bits by the value 5? 
(ex:  120/5=>24, 12345/5=>2469, 12349==>2469) I don't want/need the remainder.
 
Might try dumb repeated subtraction (uggh), but thought there might be something quick & simple.
 
 
#1

28 Replies Related Threads
    BobK
    Super Member
    • Total Posts : 1404
    • Reward points : 0
    • Joined: 2008/04/16 12:13:38
    • Location: Worcester, MA
    • Status: offline
    RE: 16 bit divided by constant 5 2009/03/13 02:13:20 (permalink)
    0
    Multiply by 65536/5 = 13107 then keep the upper 16 bits.
     
    Bob
    #2
    dchisholm
    Super Member
    • Total Posts : 3805
    • Reward points : 0
    • Joined: 2003/12/14 15:30:12
    • Location: St Louis Mo
    • Status: offline
    RE: 16 bit divided by constant 5 2009/03/13 08:10:36 (permalink)
    0
    ORIGINAL: BobK

    Multiply by 65536/5 = 13107 then keep the upper 16 bits.

    Bob
    That is the "Reciprocal Multiplication" algorithm, described at "Jones on reciprocal multiplication".

    Dale
    #3
    piccandies
    Super Member
    • Total Posts : 222
    • Reward points : 0
    • Joined: 2008/08/12 23:12:23
    • Location: 0
    • Status: offline
    RE: 16 bit divided by constant 5 2009/03/13 08:46:11 (permalink)
    0
    Thanks---I was looking for some thing a bit simpler than a 16x16 multiply...was hoping for a few shifts, adds, subtracts type thing.
     
     
    #4
    dchisholm
    Super Member
    • Total Posts : 3805
    • Reward points : 0
    • Joined: 2003/12/14 15:30:12
    • Location: St Louis Mo
    • Status: offline
    RE: 16 bit divided by constant 5 2009/03/13 08:58:17 (permalink)
    0
    ORIGINAL: piccandies

    Thanks---I was looking for some thing a bit simpler than a 16x16 multiply...was hoping for a few shifts, adds, subtracts type thing.
    Well, Jones' article presents some algorithms based on shift-and-add.  But doesn't your processor have a built-in hardware multiplier?

    Dale
    #5
    piccandies
    Super Member
    • Total Posts : 222
    • Reward points : 0
    • Joined: 2008/08/12 23:12:23
    • Location: 0
    • Status: offline
    RE: 16 bit divided by constant 5 2009/03/13 15:08:01 (permalink)
    0
    No I need an exact answer when the number is  a mutiple of 5...these methods tend to give something like 2000/5=399.86, which finally gives 399 which is horrible for my needs.  I suppose I could do round-up. 
     
    How about a straight integer division (16 bits divided by 8 bits (or even only  4 bits))  where is one for the 18F series?
     
     
     
     
    #6
    Stefan Uhlemayr
    Super Member
    • Total Posts : 4292
    • Reward points : 0
    • Joined: 2005/05/12 12:25:46
    • Location: Germany
    • Status: offline
    RE: 16 bit divided by constant 5 2009/03/13 16:11:07 (permalink)
    0
    ORIGINAL: piccandies

    No I need an exact answer when the number is  a mutiple of 5...these methods tend to give something like 000/5=399.86, which finally gives 399 which is horrible for my needs.
    Hm, aren't you contradicting yourself, as you've given this example as your need in your first post:
    ORIGINAL: piccandies

    Does anyone have a quick/slick 18F asm method to divide 16 bits by the value 5? 
    (ex:  120/5=>24, 12345/5=>2469, 12349==>2469)
    The result of the marked example is 2469,8 and was given as ok...[8|]

    ORIGINAL: piccandies

      I suppose I could do round-up. 
    One good possibility...wink

    ORIGINAL: piccandies

    How about a straight integer division (16 bits divided by 8 bits (or even only  4 bits))  where is one for the 18F series?
    I doubt, that you can realize a routine, which will need less then 24 instruction-cycles for this calculation. Have a look to example 6-3: 16 x 16 Unsigned Multiply Routine in this reference-manual:
    ORIGINAL: Flying with HardWare Favorites Gallery List

    -------------------------------------------------------------------
    [ Reference-manuals:                                                                ]
    -------------------------------------------------------------------

    PICmicro 18C MCU Family Reference Manual: from Microchip

    Hope this helps,Smile
    Stefan

    Software / Hardware / Explorer 16
    #7
    piccandies
    Super Member
    • Total Posts : 222
    • Reward points : 0
    • Joined: 2008/08/12 23:12:23
    • Location: 0
    • Status: offline
    RE: 16 bit divided by constant 5 2009/03/13 18:42:24 (permalink)
    0
    Thanks---I was hoping to avoid 16x16 multiply & needing a whole slew of >eight registers (32 bit results)  for what seems a simple need.
     
    I did not mention before, but ALL of my numbers I want to divide by 5 are, in fact, exact multiples of 5 & I need an exact answer :
    ex 125/5==>25, 34210/5==>6842, 17885/5==>3577, etc.  Seems like there would be a short/sweet way to do this.
     
     
    May be I'll have to throw n the towel, do a16x16 mult, and also take care of the fact that the result will need rounded as well.
     
    #8
    Guest
    Super Member
    • Total Posts : 80503
    • Reward points : 0
    • Joined: 2003/01/01 00:00:00
    • Location: 0
    • Status: online
    RE: 16 bit divided by constant 5 2009/03/15 11:46:40 (permalink)
    0
    I've played a minute with Windows calculator:
     
    125    *2 =    250
    17885 *2 = 35570
    34210 *2 = 68420
     
    so in decimal, you'd just have to shift by one digit after that.
     
    I admit it is a crude exploit. However HEX to DEC conversion routine is generic,
    and easy to do.
     
    You could remove it via string arithmetic, and convert back to number.

    aspforum.mchp.guest
    #9
    Stefan Uhlemayr
    Super Member
    • Total Posts : 4292
    • Reward points : 0
    • Joined: 2005/05/12 12:25:46
    • Location: Germany
    • Status: offline
    RE: 16 bit divided by constant 5 2009/03/15 13:39:52 (permalink)
    0
    ORIGINAL: hybridpic

    I've played a minute with Windows calculator:

    125    *2 =    250
    17885 *2 = 35570
    34210 *2 = 68420

    so in decimal, you'd just have to shift by one digit after that.
    This would result in a /10 -division, which has no benefit to a /5 -division on a digital controller...

    Greetings,
    Stefan

    Software / Hardware / Explorer 16
    #10
    piccandies
    Super Member
    • Total Posts : 222
    • Reward points : 0
    • Joined: 2008/08/12 23:12:23
    • Location: 0
    • Status: offline
    RE: 16 bit divided by constant 5 2009/03/15 19:18:50 (permalink)
    0
    I've found that if I mult by 13108 (rather than the suggested 13107) & keep the upper 16 bits I'll get an answer which does not need rounded up.  This will work all the way up to 65535  (65535/5=13107) & actually fails at about 81920 .
     
    I guess a 16x16 multiply is the way to go, though I was hoping for something more clever for divide by 5.
     
     
    #11
    m_singer
    Super Member
    • Total Posts : 433
    • Reward points : 0
    • Joined: 2004/06/10 15:08:18
    • Status: offline
    RE: 16 bit divided by constant 5 2009/03/17 08:14:34 (permalink)
    0

    ORIGINAL: Stefan Uhlemayr
    ORIGINAL: hybridpic
    I've played a minute with Windows calculator:
    125    *2 =    250
    17885 *2 = 35570
    34210 *2 = 68420
    so in decimal, you'd just have to shift by one digit after that.

    This would result in a /10 -division, which has no benefit to a /5 -division on a digital controller...

    Perhaps he meant to multiply by two by shifting one bit left, then convert to decimal and divide by 10 by removing one digit, then convert back to binary.
    ---
    "Flowers for Algeron" must be his favorite novel, I'm starting to think :-)
    #12
    Stefan Uhlemayr
    Super Member
    • Total Posts : 4292
    • Reward points : 0
    • Joined: 2005/05/12 12:25:46
    • Location: Germany
    • Status: offline
    RE: 16 bit divided by constant 5 2009/03/17 11:56:53 (permalink)
    0
    ORIGINAL: m_singer

    ORIGINAL: Stefan Uhlemayr
    ORIGINAL: hybridpic
    I've played a minute with Windows calculator:
    125    *2 =    250
    17885 *2 = 35570
    34210 *2 = 68420
    so in decimal, you'd just have to shift by one digit after that.

    This would result in a /10 -division, which has no benefit to a /5 -division on a digital controller...

    Perhaps he meant to multiply by two by shifting one bit left, then convert to decimal and divide by 10 by removing one digit, then convert back to binary.
    Yes, perhaps you're right, but I really doubt, that all this could be realized in less then 24 instruction-cycles as the 16x16 unsigned multiply on a PIC18 would need.[8|]

    If someone knows a shorter/faster solution for the 16-bit-value divide by 5, I would be very interested, too...Smile

    Greetings,
    Stefan

    Software / Hardware / Explorer 16
    #13
    BitWise
    Super Member
    • Total Posts : 1238
    • Reward points : 0
    • Joined: 2004/11/09 13:24:20
    • Location: UK
    • Status: offline
    RE: 16 bit divided by constant 5 2009/03/17 13:11:35 (permalink)
    0
    This seems to do it in ~37 cycles per calculation.

                     include P18F4620.inc
     
                     udata_acs
     
     VALUE           res     .2
     TEMP            res     .1
     RESULT          res     .2
     
     
                     code    h'0000'
     
                     clrf    VALUE+.0        ; Test 0/5
                     clrf    VALUE+.1
                     rcall   Div5
                     nop                     ; should be 0
     
                     movlw   low .2009       ; Test 2009/5
                     movwf   VALUE+.0
                     movlw   high .2009
                     movwf   VALUE+.1
                     rcall   Div5
                     nop                     ; Should be 401 (191)
             
                     movlw   low .36890      ; Test 36890/5
                     movwf   VALUE+.0
                     movlw   high .36890
                     movwf   VALUE+.1
                     rcall   Div5
                     nop                     ; Should be 7378 (1cd2)
     
                     bra     $
     
     ; Calculate RESULT = VALUE /5. Takes 37 instruction cycles.
     
     Div5:
                     clrf    RESULT+.0       ; Clear result area
                     clrf    RESULT+.1
                     movf    VALUE+.0,W      ; Multiply by h'cccd' and keep high 24-bits
                     mullw   h'cd'
                     movff   PRODH,TEMP
                     mullw   h'cc'
                     movf    PRODL,W
                     addwf   TEMP,F
                     movf    PRODH,W
                     addwfc  RESULT+.0,F
                     btfsc   STATUS,C
                     incf    RESULT+.1,F
                     movf    VALUE+.1,W
                     mullw   h'cd'
                     movf    PRODL,W
                     addwf   TEMP,F
                     movf    PRODH,W
                     addwfc  RESULT+.0,F
                     btfsc   STATUS,C
                     incf    RESULT+.1,F
                     movf    VALUE+.1,W
                     mullw   h'cc'
                     movf    PRODL,W
                     addwf   RESULT+.0,F
                     movf    PRODH,W
                     addwfc  RESULT+.1,F
                     bcf     STATUS,C        ; Shift back two bits
                     rrcf    RESULT+.1,F
                     rrcf    RESULT+.0,F
                     bcf     STATUS,C
                     rrcf    RESULT+.1,F
                     rrcf    RESULT+.0,F
                     return
     
                     end

    Could probably squeeze 1 or 2 instructions out.

    Throughout your life advance daily, becoming more skillful than yesterday, more skillful than today. This is never-ending.

    Yamamoto Tsunetomo (1659-1719)
    #14
    Stefan Uhlemayr
    Super Member
    • Total Posts : 4292
    • Reward points : 0
    • Joined: 2005/05/12 12:25:46
    • Location: Germany
    • Status: offline
    RE: 16 bit divided by constant 5 2009/03/17 13:44:26 (permalink)
    0
    ORIGINAL: BitWise

    This seems to do it in ~37 cycles per calculation.

                     include P18F4620.inc
     
                     udata_acs
     
     VALUE           res     .2
     TEMP            res     .1
     RESULT          res     .2
     
     
                     code    h'0000'
     
                     clrf    VALUE+.0        ; Test 0/5
                     clrf    VALUE+.1
                     rcall   Div5
                     nop                     ; should be 0
     
                     movlw   low .2009       ; Test 2009/5
                     movwf   VALUE+.0
                     movlw   high .2009
                     movwf   VALUE+.1
                     rcall   Div5
                     nop                     ; Should be 401 (191)
             
                     movlw   low .36890      ; Test 36890/5
                     movwf   VALUE+.0
                     movlw   high .36890
                     movwf   VALUE+.1
                     rcall   Div5
                     nop                     ; Should be 7378 (1cd2)
     
                     bra     $
     
     ; Calculate RESULT = VALUE /5. Takes 37 instruction cycles.
     
     Div5:
                     clrf    RESULT+.0       ; Clear result area
                     clrf    RESULT+.1
                     movf    VALUE+.0,W      ; Multiply by h'cccd' and keep high 24-bits
                     mullw   h'cd'
                     movff   PRODH,TEMP
                     mullw   h'cc'
                     movf    PRODL,W
                     addwf   TEMP,F
                     movf    PRODH,W
                     addwfc  RESULT+.0,F
                     btfsc   STATUS,C
                     incf    RESULT+.1,F
                     movf    VALUE+.1,W
                     mullw   h'cd'
                     movf    PRODL,W
                     addwf   TEMP,F
                     movf    PRODH,W
                     addwfc  RESULT+.0,F
                     btfsc   STATUS,C
                     incf    RESULT+.1,F
                     movf    VALUE+.1,W
                     mullw   h'cc'
                     movf    PRODL,W
                     addwf   RESULT+.0,F
                     movf    PRODH,W
                     addwfc  RESULT+.1,F
                     bcf     STATUS,C        ; Shift back two bits
                     rrcf    RESULT+.1,F
                     rrcf    RESULT+.0,F
                     bcf     STATUS,C
                     rrcf    RESULT+.1,F
                     rrcf    RESULT+.0,F
                     return
     
                     end

    Could probably squeeze 1 or 2 instructions out.

    Well, nice work, Andrew.Smile

    BUT: instead of multiplying with 13107 you're multiplying with 52429 and then you do shift your result 2 times right (= /4). The advantage of your way is the higher precision, but this you get only with the additional required instructions. [8|]

    A very simple (including higher error), but shorter and quicker method is a multiply of the 16-bit-value with 51, and throw out the lowest 8 bit of the 24-bit-result...

    Greetings,
    Stefan

    Software / Hardware / Explorer 16
    #15
    BitWise
    Super Member
    • Total Posts : 1238
    • Reward points : 0
    • Joined: 2004/11/09 13:24:20
    • Location: UK
    • Status: offline
    RE: 16 bit divided by constant 5 2009/03/17 13:49:42 (permalink)
    0
    ORIGINAL: Stefan Uhlemayr

    A very simple (including higher error), but shorter and quicker method is a multiply of the 16-bit-value with 51, and throw out the lowest 8 bit of the 24-bit-result...

    I tried that approach first but the error is considerable (1 in 5 results is out by one) and difficult to correct. This method (Alverson) yields the right answer in all cases but takes a bit more code.

    It all depends on how important accuracy is to the end solution.
    post edited by BitWise - 2009/03/17 14:06:14

    Throughout your life advance daily, becoming more skillful than yesterday, more skillful than today. This is never-ending.

    Yamamoto Tsunetomo (1659-1719)
    #16
    Stefan Uhlemayr
    Super Member
    • Total Posts : 4292
    • Reward points : 0
    • Joined: 2005/05/12 12:25:46
    • Location: Germany
    • Status: offline
    RE: 16 bit divided by constant 5 2009/03/17 14:53:52 (permalink)
    0
    ORIGINAL: BitWise

    I tried that approach first but the error is considerable (1 in 5 results is out by one) and difficult to correct.
    Yes, the better the correction is done, the more instructions will be needed - finally this method would not have any advantage over the 16x16-multiplication, if the accuracy is necessary.
    ORIGINAL: BitWise

    This method (Alverson) yields the right answer in all cases but takes a bit more code.
    Well, good to know (I've placed it already in my routines-bibliography, as well as I will add it into the software-gallery here, too).Smile
    ORIGINAL: BitWise

    It all depends on how important accuracy is to the end solution.
    Exactly.Smile

    Thanks,
    Stefan

    Software / Hardware / Explorer 16
    #17
    DSchabel
    Super Member
    • Total Posts : 1714
    • Reward points : 0
    • Joined: 2005/05/24 14:00:34
    • Location: Western NY State
    • Status: offline
    RE: 16 bit divided by constant 5 2009/03/17 15:32:08 (permalink)
    0
    ORIGINAL: piccandies

    I've found that if I mult by 13108 (rather than the suggested 13107) & keep the upper 16 bits I'll get an answer which does not need rounded up.  This will work all the way up to 65535  (65535/5=13107) & actually fails at about 81920 .

    I guess a 16x16 multiply is the way to go, though I was hoping for something more clever for divide by 5.

    Remember, you're truncating the number when you want to round. 

    A good rounding technique is to pre-add 1/2 to the number.  Since you can't do this in integer math, this can be done by adding 32768 after doing your multiply by 13107, and THEN truncate the least significant word. 

    I believe this should always work. 
    post edited by DSchabel - 2009/03/17 15:39:33
    #18
    m_singer
    Super Member
    • Total Posts : 433
    • Reward points : 0
    • Joined: 2004/06/10 15:08:18
    • Status: offline
    RE: 16 bit divided by constant 5 2009/03/17 15:35:34 (permalink)
    0
    ORIGINAL: piccandies
    Does anyone have a quick/slick 18F asm method to divide 16 bits by the value 5? 
    (ex:  120/5=>24, 12345/5=>2469, 12349==>2469) I don't want/need the remainder.
    Might try dumb repeated subtraction (uggh), but thought there might be something quick & simple.

    Yes, the simplest and quickest, as for me, is using sort of PIC24FJ256GA106 (256 kByte, 64/TQFP). It's priced about US$5 and you can just store the result in a look-up table.
    #19
    piccandies
    Super Member
    • Total Posts : 222
    • Reward points : 0
    • Joined: 2008/08/12 23:12:23
    • Location: 0
    • Status: offline
    RE: 16 bit divided by constant 5 2009/03/17 23:20:54 (permalink)
    0
    my solution for divide by 5, (division by 5) using inversion/inverting multiplication

    ;the number to convert is supplied in ARG2H:ARG2L
    ;the result is in BIN2H:BIN2L
    MCONST EQU .13108  ;constant for inverse multiply by five
      MOVLW LOW(MCONST)
      MULWF ARG2L
      MOVFF PRODH, RES1  ;another temp register that is needed
      MOVLW HIGH(MCONST)
      MULWF ARG2H
      MOVFF PRODH, BIN2H 
      MOVFF PRODL, BIN2L
      MOVLW LOW(MCONST)
      MULWF ARG2H
      MOVF PRODL, W 
      ADDWF RES1, F 
      MOVF PRODH, W  
      ADDWFC BIN2L, F 
      CLRF WREG 
      ADDWFC BIN2H, F 
      MOVLW HIGH(MCONST) 
      MULWF ARG2L
      MOVF PRODL, W 
      ADDWF RES1, F
      MOVF PRODH, W
      ADDWFC BIN2L, F
      CLRF WREG
      ADDWFC BIN2H, F  ;final result in BIN2H:BIN2L
      RETURN
    post edited by piccandies - 2009/03/18 22:35:43
    #20
    Page: 12 > Showing page 1 of 2
    Jump to:
    © 2021 APG vNext Commercial Version 4.5