Author: Gerd Isenberg
Date: 10:15:50 09/18/03
Go up one level in this thread
On September 17, 2003 at 18:38:36, Dieter Buerssner wrote: >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. hmm, once again x % 65535 = ( x * 65536 / 65535 ) % 65536 sorry Dieter, i can't follow anymore... You are right, "obvious" is propably used to frivolously by me. I mean the 10001 pattern, a two rank difference in pawn bitboads. Isn't it similar to the K&R "lose lose" versus "djb2" or "sdbm" Hash Functions? > >> >> 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. > A good idea. See also: http://www.cs.uiowa.edu/~jones/bcd/divide.html#fixed >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 Thanks again Dieter for all your helpfull hints and suggestions. A very instructive and exciting lesson for me. Cheers, Gerd
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.