Post by thread:16bit divide by 10

David E. Queen <spam_OUTPICLISTTakeThisOuTMITVMA.MIT.EDU> wrote: > I can save 600bytes in a lookup table if I can figure out a good way > to divide a 16 bit number by 10. > > I have the app notes with the general 16 math, but I need a smaller > and faster routine. David: Didn't I just post a divide-by-5 routine here? Oh, well... Must have been that other PIC list. Here's a 16-bit divide-by-10 algorithm (y = x/10): y = x/4 for i = 1 to 7 y = x - y y = y/4 next i y = y/2 This works for both signed and unsigned x; if you can deal with a very slight rounding error, you can speed the routine up by iterating only 5 times, rather than 7. -Andy Andrew Warren - .....fastfwdKILLspam@spam@ix.netcom.com Fast Forward Engineering, Vista, California http://www.geocities.com/SiliconValley/2499

David E. Queen wrote: > > I can save 600bytes in a lookup table if I can figure out a good way to > divide a 16 bit number by 10. > > I have the app notes with the general 16 math, but I need a smaller and > faster routine. David, I don't have a routine, but I do have an algorithm. In general, when you find that you need to divide by a constant, it is often easier to multiply by the reciprocal of that constant. For example, to divide by some X, we can find the closest Y that satisfies the equation: 1/X = Y/ (2^n) Then division by X is transformed to multiplication by Y followed by a shift of n bits. Note that this is actually converting the fraction 1/X into a binary fraction. When X is an integer, then either Y will be an integer or will be a repeating pattern (somewhat analogous to how 1/3 = .333333). If it is a repeating pattern, then pray to the god of numbers that it is a simple one. Fortunately, 1/10 is a very simple pattern: 1/10 = 0.00011001100110011001100110011001100 ..... (base 2) This can be rewritten to emphasize the optimization: 1/10 = 2 * (3/16 + 3/256 + 3/4096 + ... + 3/(2^(4*m)) ) where m is an integer corresponding to how many terms you wish to keep. Or more compactly: i->infinity ___ \ 1/10 = 6*/__ 2^(-4*i) i=1 This can be checked by using the formula for the sum of a geometric series: i=k-1 ___ 1 - r^k \ ---------- /__ r^i = 1 - r i=0 In our case, r = 1/16. Taking into account the fact that our summation begins at 1 and not zero and also that k is infinity, we get 1/10 = 6* [1/ (1 -1/16) - 1] = 6 ( 16/15 - 1) = 1/10 (The check is good!) We can also express the multiplications and divisions by shifting X / 10 = 3 * (X>>4 + X>>8 + X>>12 + X>>16 + ...) << 2 Since you are only interested in 16 bit integers divided by 10 then all you need are the first four terms. To reduce roundoff, you will want to re-arrange this slightly, X / 10 ~ 3 * ((X<<12 + X<<8 + X<<4 + X) >> 17) The following (untested) psuedo code implements the formula int divby10(int X) { long Y; int i; Y = 0; for(i=0; i<4; i++) { Y = Y + X; X = X << 4; } Y = (Y + Y<<1) >> 17; /* i.e. Y*3/(2^17) */ return(Y); } Scott

James Musselman <PICLISTKILLspamMITVMA.MIT.EDU> wrote: > Scott Dattalo wrote: > > > 1/10 = 0.00011001100110011001100110011001100 ..... (base 2) > > > > This can be rewritten to emphasize the optimization: > > 1/10 = 2 * (3/16 + 3/256 + 3/4096 + ... + 3/(2^(4*m)) ) > > Isn't the above line wrong? Isn't 2 * 3/16 greater than 1/10? Or > am I missing something? You're not missing anything, James. Scott's explanation (and ASCII-art equations) were all excellent, but he screwed up slightly in that last line; it should be: 1/10 = 3 + 3/16 + 3/256 + 3/4096 + ... + 3/(2^(4*m)) --------------------------------------------- 32 -Andy Andrew Warren - .....fastfwdKILLspam.....ix.netcom.com Fast Forward Engineering, Vista, California http://www.geocities.com/SiliconValley/2499

Steve Hardy wrote: {Quote hidden}> > > From: James Musselman <jamesspam_OUTRADIXGROUP.COM> > > > > Scott Dattalo wrote: > > > > > 1/10 = 0.00011001100110011001100110011001100 ..... (base 2) > > > > > > This can be rewritten to emphasize the optimization: > > > 1/10 = 2 * (3/16 + 3/256 + 3/4096 + ... + 3/(2^(4*m)) ) > > > > Isn't the above line wrong? Isn't 2 * 3/16 greater than 1/10? Or am I > missing > > something? > > James > > > > Scott meant the initial coefficient to be 1/2 not 2. Scott > must have had an April 1 calculator since he also claimed that > > > > 1/10 = 6* [1/ (1 -1/16) - 1] = 6 ( 16/15 - 1) = 1/10 (The check is good!) The Derivative of r cubed divided by three. With egg dripping off his face he confesses, "I inadvertantly propogated an error." 8^( If you're really interested, here are the corrections for Rev 1.0001: This line is correct: 1/10 = 0.00011001100110011001100110011001100 ..... (base 2) This line was incorrect: > 1/10 = 2 * (3/16 + 3/256 + 3/4096 + ... + 3/(2^(4*m)) ) and should have been 1/10 = (3/16 + 3/256 + 3/4096 + ... + 3/(2^(4*m)) ) / 2 The summation is incorrect: > i->infinity > ___ > \ > 1/10 = 6*/__ 2^(-4*i) > i=1 And should have been i->infinity ___ 3 \ 1/10 = --- * /__ 2^(-4*i) 2 i=1 The **check** was incorrect: > 1/10 = 6* [1/ (1 -1/16) - 1] = 6 ( 16/15 - 1) = 1/10 (The check is good!) and should have been 1/10 = 3* [1/ (1 -1/16) - 1]/2 = 3 ( 16/15 - 1)/2 = 1/10 (The check is good!) ((I think)) Sorry folks... I guess people do read this stuff. So, as Steve points out, I inadvertantly was multiplying by two when I should have been dividing by two (thanks Steve). However the theory is sound. BTW Thomas Coonan wrote: (in Response to Andy's posting) > > So, what's your general problem-solving technique for this class of > problem? Are you applying some basic number theory tricks about rational > numbers, or is this trial-n-error? Yes. Scott PS The answer is: r * dr * r. Get it? Hardy-har-har. Sorry Steve, it's something I stole from the Simpsons.

>I can save 600bytes in a lookup table if I can figure out a good way to >divide a 16 bit number by 10. > >I have the app notes with the general 16 math, but I need a smaller and >faster routine. > > As everybody was probably expecting, I have to put in my two cents worth and drop in some code... Here is a 16 bit unsigned division algorithm that I have used in the past. Initially, it shifts the Divisor until bit 14 is set and then begins shifting down. If the divisor can be taken from the dividend, it is. Next, the divisor is shifted down until you get the initial divisor. The results (quotient and remainder) are all 16 bits long and an additional 8 bit register is used in the example code below. Here is the psuedo-code: Count = 0 - Count keeps track of where the Divisor is Quotient = 0 - Quotient is actually a 16 bit sum while ( Divisor & 0x04000 ) != 0 - Find where to shift the Divisor up to Count = Count + 1 - Record How Many Bits Shifted Divisor = Divisor << 1 - Shift up the Divisor while Count != 0 - Now, do the Shifting Subtraction (Division) if Dividend >= Divisor - Can Subtract from the Result Quotient = Quotient + ( 2 ^ Count ) Divident = Divident - Divisor Count = Count - 1 Divisor = Divisor >> 1 That's it. Divident contains the remainder and Quotient contains the quotient of the value. Note that this algorithm will go into an endless loop if the divisor is equal to zero. I stop the shifting up with bit 14 of the Divisor so that signed values can be supported (even though this algorithm won't work with negative values). The PIC code for doing this is below. Note, that I have changed the code in two places. The first is with regards to Count. Rather than using a counter, I shift a "1" up and down (ending the division when the "1" ends up in the Carry Flag). This means that I can add Count to the Quotient directly. The second area that I have changed is in regard to the comparison of the Dividend to the Divisor, note that I save the contents of the subtraction (compare) and use it later, rather than subtracting twice. clrf Quotient ; Initialize the Variables clrf Quotient + 1 movlw 1 ; Instead of a Counter, Count is a shifted movwf Count ; Value for adding to the Quotient clrf Count + 1 StartLoop ; Find the Top Value for the Divisor btfsc Dividend, 6 ; If Bit 14 Set, then we have the value goto DivLoop bcf STATUS, C ; Shift over the Carry and the Divisor rlf Count rlf Count + 1 rlf Divisor ; Note, Carry will be Zero from Count rlf Divisor + 1 goto StartLoop ; Now, see if we can shift again DivLoop ; Do the Shifted Subtraction movf Divisor + 1, w ; Compare Values, High First subwf Dividend + 1, w movwf Temp ; Save Result for later (just in case) movf Divisor, w subwf Dividend btfss STATUS, C ; Make Sure Carry is accounted for decf Temp btfsc Temp, 7 ; Do we have a Negative Number from Subtract? goto DivSkip ; Yes, Don't Subtract this value movwf Dividend ; Else, save the result for the Next movf Temp, w ; Subtract movwf Dividend movf Count + 1, w ; Add the Bit Offset to the Quotient addwf Quotient + 1 movf Count, w addwf Quotient ; Don't have to worry about Carry DivSkip ; Now, Shift the Values Down bcf STATUS, C ; Shift down the Divisor rrf Divisor + 1 rrf Divisor rrf Count + 1 ; Now see if the Count is finished rrf Count btfss STATUS, C ; Finished if Carry is Set goto DivLoop Note that with this code, "Dividend" now contains the Remainder and "Divisor" is the original "Divisor" >> 1. In terms of space and execution speed, I think you'll find this to be a pretty good improvement from the code in the ECBK (although not as good as some of the algorithms other people have put in for a direct divide by 10). Myke Myke "We're Starfleet officers, weird is part of the job." Capt. Catherine Janeway

David E. Queen wrote: (a few weeks ago) > > I can save 600bytes in a lookup table if I can figure out a good way to > divide a 16 bit number by 10. > David, Did you ever code a 16 bit divide by 10 routine? If so what did you end up with? Out of curiosity, I wrote a few versions. Here are some approximate cycle and word counts: Version 1: 50 cycles 50 words Version 2: 90 cycles 40 words Version 3: 136 cycles 14 words Version 1 is an implementation of the solution I had originally posted. Version 2 is an implementation of a variation of Andy Warren's solution. Version 3 is an old-fashioned shift and subtract routine. The first two versions exist only on paper. The third has been tested over several, but not all 2^16 possible dividends. N_hi equ 0x20 N_lo equ 0x21 count equ 0x22 R_hi equ 0x23 R_lo equ 0x24 ;---------------------------------- ;divby10 ; Divides the unsigned integer N_hi:N_lo by the constant 10. ; ;Input ; N_lo - Low byte of the 16 bit dividend ; N_hi - High " " ;Output ; R_lo - Low byte of the result ; R_hi - High " " ; ; 14 words ; 149 cycles divby10_ver3 CLRF R_lo ;Only need to clear R_lo. R_hi is cleared by shifting(below) MOVLW 13 MOVWF count ; v3_1 MOVLW 0xa0 ;If the high byte is greater than or equal to 0xa0, SUBWF N_hi,W ;then this subtraction causes no borrow (i.e. C=1) SKPNC MOVWF N_hi ;Replace N_hi with N_hi - 0xa0 if RLF R_lo,F ;Shift result left one bit and RLF R_hi,F ; pick up the carry bit in the process. RLF N_lo,F ;Adjust N for the next iteration. RLF N_hi,F DECFSZ count,F goto v3_1 RETURN

Tom Van Baak wrote: (note: Tom did not send this to the PIC list) > > Is it me or does your divby10_ver3 fail on 16? > > No, it's me! I didn't take (==have) the time to test the routine thoroughly enough during lunch. The problem was that under certain conditions, a borrow was not occuring during the subtraction (when I was expecting one to occur). To fix the problem, I shifted the input right one bit and divided by 0x50 instead of 0xa0. I tested this version over more but still not all of the possible values. (16 was the first value I tested). N_hi equ 0x20 N_lo equ 0x21 count equ 0x22 R_hi equ 0x23 R_lo equ 0x24 ;---------------------------------- ;divby10 ; Divides the unsigned integer N_hi:N_lo by the constant 10. ; ;Input ; N_lo - Low byte of the 16 bit dividend ; N_hi - High " " ;Output ; R_lo - Low byte of the result ; R_hi - High " " ; ; 17 words ; 152 cycles divby10_ver3 CLRC RRF N_hi,F RRF N_lo,F CLRF R_lo ;Only need to clear R_lo. R_hi is cleared by shifting(below) MOVLW 13 MOVWF count ; v3_1 MOVLW 0x50 ;If the high byte is greater than or equal to 0xa0, SUBWF N_hi,W ;then this subtraction causes no borrow (i.e. C=1) SKPNC MOVWF N_hi ;Replace N_hi with N_hi - 0xa0 if RLF R_lo,F ;Shift result left one bit and RLF R_hi,F ; pick up the carry bit in the process. RLF N_lo,F ;Adjust N for the next iteration. RLF N_hi,F DECFSZ count,F goto v3_1 RETURN Thanks Tom for catching this one. Scott PS. Next time, I'll make my butthead project manager insist I go to lunch. Oops, sorry E. S., I meant that other butthead project manager.