Post by thread:Re[2]: 16bit divide by 10

>> I can save 600bytes in a lookup table if I can figure out a good way >> to divide a 16 bit number by 10. >.... >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 I understand why powers of two are good... And I sort of see how you divide down close to the target before you do too much shifting... 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?

Thomas Coonan <spam_OUTPICLISTTakeThisOuTMITVMA.MIT.EDU> wrote: > So, what's your general problem-solving technique for this class of > problem? In general, my technique goes like this: 1. Call all my friends and ask them how to do it. Invariably, they don't know. 2. Look through Donald Knuth's books for the solution. Invariably, I won't find it. 3. Sit down with a big sheet of paper and the TI-35 calculator I've had since I was in high school (one of these days, I'm gonna get me a calculator with built-in hex/binary/boolean operations), and launch QuickBASIC on my PC. 4. Thrash around for a couple of hours, alternating mad scribbling with blowing smoke rings at the ceiling, until something clicks. 5. Build a model in QuickBASIC, test it, then call all my friends back and gloat. 6. Later that year, while looking through Knuth for something else, find the solution that I "discovered". Sigh. Step 4's kinda vague, I know... > Are you applying some basic number theory tricks about rational > numbers, or is this trial-n-error? Every once in a while, I actually find a use for all the discrete math and number theory I learned in school. Usually, though, it's just a matter of making the right "trial and error" connections. In this case, my divide-by-10 code is just a divide-by-5 with an extra divide-by-2 tacked on at the end. I came up with the original divide-by-5 routine by noticing the following: x 4x x 5x --- = ----, and --- = ----. 5 20 4 20 Therefore, x x x --- = --- - ---- 5 4 20 x x/4 = --- - ------- 4 5 x (x/4) (x/4)/4 = --- - ( ------- - --------- ) 4 4 5 etc... I don't know if that's clear... The point is that you can expand "x/5" into a form that INCLUDES a "/5" element, and THAT element can be further expanded into ANOTHER equation that also includes a "/5" element, etc. This is pretty standard stuff; if you've spent any time at all in advanced math classes, you've probably seen expansions like this. Anyway, the expansion can go on as long as you like. I suppose I COULD have calculated the necessary depth of expansion to give precise answers over the range [0-65535], but I'm lazy, so I just did a little trial-and-error experimentation in QuickBASIC to arrive at the conclusion that only seven iterations were necessary. Sorry this is such an unsatisfying explanation... -Andy Andrew Warren - .....fastfwdKILLspam@spam@ix.netcom.com Fast Forward Engineering, Vista, California http://www.geocities.com/SiliconValley/2499

Thomas Coonan wrote: > > >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 > I understand why powers of two are good... And I sort of see how you > divide down close to the target before you do too much shifting... > > 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? and Andrew Warren wrote: {Quote hidden}> > In this case, my divide-by-10 code is just a divide-by-5 with an > extra divide-by-2 tacked on at the end. I came up with the original > divide-by-5 routine by noticing the following: > > x 4x x 5x > --- = ----, and --- = ----. > 5 20 4 20 > > Therefore, > > x x x > --- = --- - ---- > 5 4 20 > > x x/4 > = --- - ------- > 4 5 > > x (x/4) (x/4)/4 > = --- - ( ------- - --------- ) > 4 4 5 > > etc... > Another way to skin Andy's cat is to return to the binary fraction of x/5 and do some manipulation: x --- = 0.001100110011001100110011... 5 3 3 3 3 = x *( -- + --- + ---- + ... + ------ ) 16 256 4096 2^(4*m) = x * 3 * ( 1>>4 + 1>>8 + 1>>12 + ... + 1>>(4*m) ) (1) Now, x * 3 can be rewritten as x<<2 - x (i.e. x*3 = x*4 - x) x --- = (x<<2 - x) * ( 1>>4 + 1>>8 + 1>>12 + ... + 1>>(4*m) ) 5 = x * ( 1>>2 + 1>>6 + 1>>10 + ... + 1>>(4*m-2) ) - x * ( 1>>4 + 1>>8 + 1>>12 + ... + 1>>(4*m) ) = x * ( 1>>2 - 1>>4 + 1>>6 - 1>>8 + 1>>10 -+ ... -+ 1>>(2*m) ) Now, assuming x is a 16 bit integer we only need to keep terms up to m=7 x --- ~= x * ( 1>>2 - 1>>4 + 1>>6 - 1>>8 + 1>>10 - 1>>12 + 1>>14 ) 5 = x * (1 - (1 - (1 - (1 - (1 - (1 - 1>>2)>>2)>>2)>>2)>>2)>>2)>>2 = (x - (x - (x - (x - (x - (x - x>>2)>>2)>>2)>>2)>>2)>>2)>>2 This is Andy's algorithm unrolled. Just for grins, Pete Brink's cat can be skinned similarly: First note that x * 3 can be rewritten as x<<1 + x. Substitute this into equation (1) from above and you get: x --- = (x<<1 + x) * ( 1>>4 + 1>>8 + 1>>12 + ... + 1>>(4*m) ) 5 = x * (1>>3 + 1>>4 + 1>>7 + 1>>8 + ... ) = (x>>3 + x>>4 + x>>7 + x>>8 + ...) = (x + x>>1 + x>>4 + x>>5 + ...) >> 3 or, x --- = (x + x>>1 + x>>4 + x>>5 + ...) >> 4 10 Everyone knows a cat has 9 lives. We have used three on this problem, so there are probably six more solutions lurking out there. Scott