MDP@su-score.arpa (03/29/83)
From: Mike Peeler <MDP@su-score.arpa> T. W., I doubt that anybody is going to do better than Windsor. That is to say, no other approach will give better results faster than his. Don, your algorithm is not perverse. You could have explained it quite easily. Start with a clearer representation: (1 - (3/16) * (1+1/16) * (1+1/256)) * x / 8 This calculates (1-.2)x/8. 3/16 is .1875 and the rest hones the approximation. This works out to .1999967, but integer arithmetic loses something in the translation. Don is correct that his quotient is never off by more than one. I wish I could end the story here. To be honest, I have very little occasion to divide integers by ten without exact precision. I am as often as not more interested in the remainder than in the quotient. If the quotient is off by one, how heavily should I rely on the remainder? I have written a routine that shares some of the characteristics of Don's. It is fast: around 235 8080 cycles, compared to 213 Z80 cycles for his--I do not have Z80 timing figures, nor do I have an 8080 on which to test my routine. It runs in just about constant time, like his. Finally, I will probably have about as much need for it as for Don's. Its one virtue is that its result is exact. Its major drawback is how heavily it trades space for time. The way I wrote it, it uses about 1K of memory for constants storage: four tables of 256 bytes each. I could cut this almost in half by adding one index calculation, not too heavy a price to pay, to reduce two of the tables from 256 to 10. I could cut this again almost in half by figuring out the remainder instead of looking it up, which would not be as expensive as it sounds: it would use one multiply, one subtraction, and a little juggling, for a total of about 40 cycles, since multiplying by 10 is five fast instructions. I am sure you can take this idea and find a trade-off between lookup and computation to satisfy your needs. Cheers, Mike Peeler -------
twhgbo (04/01/83)
It seems to me that a method of using Winsor's algorithm for divide by 10 if you want the exact remainder is the following: Multiply the "quotient" (which may be in error by one) by 0AH (which is easy, as you point out) and subtract the result from the original dividend. Then reduce the remainder modulo 0AH until it is in the range 0 <= R <= 9. A single addition or subtraction will suffice. It would sure save memory for you! An alternative way of looking at Winsor's procedure is that 0.1 (decimal) is the binary fraction 0.0001100110011001 and that the procedure produces the product of this fraction with the original dividend (with the requisite rounding). You can see that this is the case if you assume that the dividend is the (17-bit) integer 10000H. T. W. Hildebrandt UNC-Greensboro