Author: Dieter Buerssner
Date: 15:38:36 09/17/03
Go up one level in this thread
On September 17, 2003 at 18:08:17, Gerd Isenberg wrote: >>> 65535 1000100010002 > >this sucks for obvious pawn pattern reasons The reasons may not be totally obvious. I think x % 2**16-1 = (x * 2**16/(2**16-1))%2**16. > > K = (2**64 + i - 1) / i > >is a ceil (1 / i) fixed point division, rounding the fixed point quotient K to >the nearest integers greater than or equal to K Thanks! I actually figured it out, while watching soccer tonight. >But for some a's and i's i got numbers up to 3 greater "i"! >E.g. for i = 49981 with K = 0x00014FAC00053EB1 >and a = 26182082926361 or 0x000017cffdc09719 >i got a result of 49984! I think, this will be avoided, when you give the divisor more precision. There are 15 leading zero bits in the fixed point devisor. So you can use a much better approximation, by calculating the divisor as (2**(64+15)+i)/i and use the shift 32+15 for the fixed point arithmetics. Of course, this will make the code a bit slower. I think, this method (use all bits in the fixed point arithmetics) will guarantee a max error of one in the result (and that should occure very rarely). If you search for numbers where the floating point result is really close to the integer, it will probably guarantee no error at all. I would search for prime numbers in the range you want, and use the one with the smallest difference between the integer and the real result. With a bit of effort, one might be able to find an exact condition, that guarantees no errors. At least, when you make your table one larger than the modulus, and correct the rounding step a bit (so that the error in the most unfortunate case will mean that your approximation of x/d will be one too small - and this case will only happen, when the result is almost exact. It will leave you then with a one too big mod). Regards, Dieter
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.