bitboard 2^i mod 67 is unique

[Stefan Plenkner]

2^i mod 67 is unique
Is there a way to get 'mod' cheaper ?

[Wolfgang Kuechle]

Stefan Plenkner wrote:
>
> 2^i mod 67 is unique
> Is there a way to get 'mod' cheaper ?

Hmmm, would you please enlighten me why the "2^i mod 67" is so important
for chess ?

Thank you,
Wolfgang Kuechle

[Joel Rivat]

Wolfgang Kuechle

Given 2^i, the point is to find i...
As 2^i is unique mod 67, finding i can be done by a table lookup
t[2^i mod 67]...
Such a method works well on 64 bits computers (like the DEC Alpha),
but is poor on 32 bits computers...

Another method that does not use any test is simply bitsum(2^i-1)...
The classical method is a simple dichotomy...

The two last methods work well on both 32 bits and 64 bits computers...

Joel Rivat

[sandy robert garrett jr.]

In article <4umlsp$n...@tempo.univ-lyon1.fr>, ri...@caissa.univ-lyon1.fr
says...

Could someone please supply some actual C source code for the minimum bits
concept. I do not follow whats going on. I do see the practical value of
representing a chess position in 59 or so bits. In the past, there was a post
that gave:

2i mod 67 (i=0 to 63)

How are the pieces on the squares 0 to 63 utilized in the above?

Thanks,

Sandy Garrett

[Marcel Nijman]

Joel Rivat wrote:
>
> Wolfgang Kuechle
> >Stefan Plenkner wrote:
> >>
> >> 2^i mod 67 is unique
> >> Is there a way to get 'mod' cheaper ?
> >
> >Hmmm, would you please enlighten me why the "2^i mod 67" is so important
> >for chess ?
> >
> >Thank you,
> >Wolfgang Kuechle
>
> Given 2^i, the point is to find i...

That doesn't explain why it is important for chess.

Anyone else?

Marcel

--
____ ____ __ ____ ir. Marcel J. Nijman
__/_/_/_/_/_/_ /_/ __/_/_/_ Dept. of Medical Physics
/_/ /_/ /_/ /_/ /_/ /_/ and Biophysics,
/_/ /_/ /_/ __ /_/ /_/ /_/ University of Nijmegen,
/_/ /_/ /_/ /_/___/_/ /_/ /_/ Nijmegen, The Netherlands
/_/ /_/ /_/ /_/_/ /_/ /_/ mar...@mbfys.kun.nl
http://www.mbfys.kun.nl/~marcel

Have you seen the latest Japanese camera? Apparently it is
so fast it can photograph an American with his mouth shut!

[Joost de Heer]

The list of 2^i mod 67:

[1, 2, 4, 8, 16, 32, 64, 61, 55, 43, 19, 38, 9, 18, 36, 5, 10, 20, 40, 13, 26,

52, 37, 7, 14, 28, 56, 45, 23, 46, 25, 50, 33, 66, 65, 63, 59, 51, 35, 3,

6, 12, 24, 48, 29, 58, 49, 31, 62, 57, 47, 27, 54, 41, 15, 30, 60, 53, 39,

11, 22, 44, 21, 42]

Joost
--
Think about all the good in your life - It's only temporary
Think about all the positive sides in life - They never last forever
So drink to forget and drown all your sorrow SENTENCED
Bury your dreams and choose Catharsis NEPENTHE

[Stefan Plenkner]

2î mod 67 (i=0 to 63) is interesting for bitboards.
If you have a 64 bit long(long) N with 1 only 1 bit set you can
get the index i=mod67to0_63[N mod 67] (array init)
(mod 37 32 bit long) but you can also get it with a method like
in CRAFTY.
I think mod 67 is elegant but slow!