Author: Eugene Nalimov
Date: 15:14:58 08/21/99
Go up one level in this thread
On August 21, 1999 at 17:54:16, David Franklin wrote: > >>On August 19, 1999 at 18:12:35, Johannes Buchner wrote: >> >>>Hi there ! >>> >>>I just wanted to know if anybody out there knows a different way how to do this >>>than using table-lookups like crafty. Is really no other mathematical >>>possibility ? > >On August 19, 1999 at 20:59:28, Robert Hyatt replied: > >>There's no mathematical method to compute this that anyone knows of, although >>that doesn't mean no such method exists. > >I'm sure Bob already knows this one, but a 'mathematical' approach is to >note that 2 is a primitive root of F_67; In particular this means >2^N % 67 is unique for N = 0,...,63. > >So something like: > >which_bit = LUT[M % 67]; // M must have only one bit set > // of course can enforce this with > // M &= ~(M & (M-1)) or something similar > >only requires a 67 entry lookup table. Unfortunately that % 67 evaluation >is going to be a lot slower than the standard approaches... > >Dave Not sure that it is so slower. It does not need non-cacheable memory access, nor branch that can be mispredicted. As it is division by a constant, it can be replaced by multiplication 64x64-->128, of which only high word will be used, plus maybe some shifts and additions - don't remember exactly, have to cosult some papers (there is well-known algorithm "how to replace division by a constant by multiplication" that was published some years ago in SigPlan PLDI proceedings). It looks that it can be reasonable approach to determine bit # of last set bit, at least at Alpha and maybe at IA-64. Eugene Eugene
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.