Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

bitboard 2i mod 67 unique

67 views
Skip to first unread message

Stefan Plenkner

unread,
Aug 6, 1996, 3:00:00 AM8/6/96
to

2i mod 67 (i=0 to 63) is unique!
The operation 'mod' is very expensive !
Is there a way to get the result much cheaper ?

Chris Whittington

unread,
Aug 7, 1996, 3:00:00 AM8/7/96
to


Use a 8086 instead, only $1 each.

Chris Whittington

cma...@ix.netcom.com

unread,
Aug 7, 1996, 3:00:00 AM8/7/96
to

Stefan Plenkner <10133...@CompuServe.COM> wrote:

>2i mod 67 (i=0 to 63) is unique!
>The operation 'mod' is very expensive !
>Is there a way to get the result much cheaper ?

How about a 64 byte lookup table?

Kelly Harrelson

unread,
Aug 8, 1996, 3:00:00 AM8/8/96
to

If you could change it to a mod 64 you could
replace it with & 63. A binary and is a much
cheaper operation.
x mod 64 = x & 63
In fact, you can replace any mod of a power of
2 with a binary and of one less.
x mod (2^y) = x & ((2^y)-1)


Anders Thulin

unread,
Aug 15, 1996, 3:00:00 AM8/15/96
to

In article <4u83h7$2mi$1...@mhade.production.compuserve.com>,

Stefan Plenkner <10133...@CompuServe.COM> wrote:
>2i mod 67 (i=0 to 63) is unique!
>The operation 'mod' is very expensive !
>Is there a way to get the result much cheaper ?

How about table look-up?

--
Anders Thulin Anders...@lejonet.se 013 - 23 55 32
Telia Research AB, Teknikringen 2B, S-583 30 Linkoping, Sweden

Don Fong

unread,
Aug 16, 1996, 3:00:00 AM8/16/96
to

In article <3214A6...@nwlink.com>, brucemo <bru...@nwlink.com> wrote:

>Anders Thulin wrote:
>>
>> In article <4u83h7$2mi$1...@mhade.production.compuserve.com>,
>> Stefan Plenkner <10133...@CompuServe.COM> wrote:
>> >2i mod 67 (i=0 to 63) is unique!
>> >The operation 'mod' is very expensive !
>> >Is there a way to get the result much cheaper ?
>>
>> How about table look-up?
>
>Argh.
>
>1) This "67" number has been picked out of thin air, it has nothing to
>do with reality.
>
>2) If what you want is "i % 64", how you get it is "i & 63", which will
>be faster than a table lookup.

PMFJI. we still don't know "why" the function is so important
in the first place. but as a guess, i would say it might be a
way of computing log2 ? suppose you have an unknown quantity N
which is constrained to be a power of 2,

N = 2^k

but you don't know k. one way to find k would be to do a shift
and compare loop - relatively slow. but since 2^k mod 67 is
unique, another solution is to do a table lookup on N mod 67.
(the table would contain A[2^k mod 67] = k).

essentially "mod 67" is a hash function that maps the domain
X = {1,2,4,...,2^63}
one-to-one into a convenient range.

note that 67 is the smallest prime number greater than or equal to 64.
this trick might be useful for determining the "bit number" of a bit
within a 64 bit word.

--
--- don fong ``i still want the peace dividend''
--

brucemo

unread,
Aug 16, 1996, 3:00:00 AM8/16/96
to

Anders Thulin wrote:
>
> In article <4u83h7$2mi$1...@mhade.production.compuserve.com>,
> Stefan Plenkner <10133...@CompuServe.COM> wrote:
> >2i mod 67 (i=0 to 63) is unique!
> >The operation 'mod' is very expensive !
> >Is there a way to get the result much cheaper ?
>
> How about table look-up?
>
> --
> Anders Thulin Anders...@lejonet.se 013 - 23 55 32
> Telia Research AB, Teknikringen 2B, S-583 30 Linkoping, Sweden

Argh.

1) This "67" number has been picked out of thin air, it has nothing to
do with reality.

2) If what you want is "i % 64", how you get it is "i & 63", which will
be faster than a table lookup.

bruce

Stefan Plenkner

unread,
Aug 19, 1996, 3:00:00 AM8/19/96
to

what do you mean?

Chris Whittington

unread,
Aug 21, 1996, 3:00:00 AM8/21/96
to

Stefan Plenkner <10133...@CompuServe.COM> wrote:
>
> what do you mean?

It was a joke.

80586 v 8086 price comparison.

Sorry if too subtle.

Chris Whittington

Stefan Plenkner

unread,
Aug 22, 1996, 3:00:00 AM8/22/96
to

Do you mean like crafty?
I hope there is a way to get is without three compares
(perhaps with shl and xor愀 or so).

Stefan Plenkner

unread,
Aug 22, 1996, 3:00:00 AM8/22/96
to

what do you mean with "use a 8086 .."?

Chris Whittington

unread,
Aug 22, 1996, 3:00:00 AM8/22/96
to

df...@cse.ucsc.edu (Don Fong) wrote:
>
> In article <3214A6...@nwlink.com>, brucemo <bru...@nwlink.com> wrote:
> >Anders Thulin wrote:
> >>
> >> In article <4u83h7$2mi$1...@mhade.production.compuserve.com>,
> >> Stefan Plenkner <10133...@CompuServe.COM> wrote:
> >> >2i mod 67 (i=0 to 63) is unique!
> >> >The operation 'mod' is very expensive !
> >> >Is there a way to get the result much cheaper ?
> >>
> >> How about table look-up?
> >
> >Argh.
> >
> >1) This "67" number has been picked out of thin air, it has nothing to
> >do with reality.
> >
> >2) If what you want is "i % 64", how you get it is "i & 63", which will
> >be faster than a table lookup.
>
> PMFJI. we still don't know "why" the function is so important
> in the first place. but as a guess, i would say it might be a
> way of computing log2 ? suppose you have an unknown quantity N
> which is constrained to be a power of 2,
>
> N = 2^k
>
> but you don't know k. one way to find k would be to do a shift
> and compare loop - relatively slow. but since 2^k mod 67 is
> unique, another solution is to do a table lookup on N mod 67.
> (the table would contain A[2^k mod 67] = k).
>
> essentially "mod 67" is a hash function that maps the domain
> X = {1,2,4,...,2^63}
> one-to-one into a convenient range.
>
> note that 67 is the smallest prime number greater than or equal to 64.
> this trick might be useful for determining the "bit number" of a bit
> within a 64 bit word.
>
> --
> --- don fong ``i still want the peace dividend''
> --

What I'ld like is a simple function of logical operations to extract
the most significant bit.

Extracting the least significant bit is easy:

ls bit of a = a and -a

ms bit of a = ????????

My eternal gratitude to any solver :)

Chris Whittington

Ilias Kastanas

unread,
Aug 29, 1996, 3:00:00 AM8/29/96
to

In article <84074451...@cpsoft.demon.co.uk>,
Chris Whittington <chr...@cpsoft.demon.co.uk> wrote:


>What I'ld like is a simple function of logical operations to extract
>the most significant bit.
>
>Extracting the least significant bit is easy:
>
>ls bit of a = a and -a
>
ms bit of a = ????????

Why would it be a problem using a 100...0 flag? For 16-bit integers

flag = 0x8000;
msbit = ( (a & flag) == flag);


Or in assembly, most architectures have a Rotate-through-Carry; then
you read the bit, say by Jump-if-Carry-Set. (For Intel, it's RCL and JC).


Much easier is to test a >= 0 (msb = 0) versus < 0 (msb = 1).
But check that 100...0 is handled properly.

Ilias


Marcel van Kervinck

unread,
Aug 29, 1996, 3:00:00 AM8/29/96
to

Ilias Kastanas (ika...@alumnae.caltech.edu) wrote:
> >ls bit of a = a and -a
> >
> ms bit of a = ????????
> Why would it be a problem using a 100...0 flag? For 16-bit integers
> flag = 0x8000;
> msbit = ( (a & flag) == flag);
> Or in assembly, most architectures have a Rotate-through-Carry; then
> you read the bit, say by Jump-if-Carry-Set. (For Intel, it's RCL and JC).
> Much easier is to test a >= 0 (msb = 0) versus < 0 (msb = 1).
> But check that 100...0 is handled properly.

I think you missed the point. But I'm not sure what you mean by
"using a 100...0 flag". The question was how to find the highest
bit set. Somehow the poster used the confusing term 'MSB' for this.

The easiest way, ofcourse, is to put the word into the floating
point unit, let the thing normalize and then examine the exponent
field...

Marcel
-- _ _
_| |_|_|
|_ |_ Marcel van Kervinck
|_| bue...@urc.tue.nl

Chris Whittington

unread,
Aug 29, 1996, 3:00:00 AM8/29/96
to

I was after some fast logic to do it (find the highest bit set).
an *and* and a *negate* is all that's needed for the ls bit;
fp units or looping on a rotate left weren't what I was after.

I know its possible by simple logic because I read the code somewhere
ages ago, but have now forgotten it ....

Chris Whittington

Marcel van Kervinck

unread,
Aug 30, 1996, 3:00:00 AM8/30/96
to

Chris Whittington (chr...@cpsoft.demon.co.uk) wrote:
: I was after some fast logic to do it (find the highest bit set).

: an *and* and a *negate* is all that's needed for the ls bit;
: fp units or looping on a rotate left weren't what I was after.

: I know its possible by simple logic because I read the code somewhere
: ages ago, but have now forgotten it ....

I highly doubt there is a way to do it in less than O(wordsize)
logic operations. Finding LSB works because the negate implies
an increment operation (-a==~a+1), with a carry traveling from
the lowest bit to highest bit. There are no operators that pass
information along the whole word in the opposite direction.
So you need to code it yourself, requiring O(wordsize) instructions.

Btw, I did some investigation to code the %67 function efficiently,
but gave up. Even /67 isn't trivial, but doable. Perhaps we should
be looking for another %n with unique 2^i%n.

Perhaps we should return to programming chess.

Regards,

Marcel van Kervinck

unread,
Aug 30, 1996, 3:00:00 AM8/30/96
to

Marcel van Kervinck (bue...@asterix.urc.tue.nl) wrote:

: I highly doubt there is a way to do it in less than O(wordsize)


: logic operations. Finding LSB works because the negate implies
: an increment operation (-a==~a+1), with a carry traveling from
: the lowest bit to highest bit. There are no operators that pass
: information along the whole word in the opposite direction.
: So you need to code it yourself, requiring O(wordsize) instructions.

Oops, ofcourse I meant O(ln wordsize)...

Chris Whittington

unread,
Aug 31, 1996, 3:00:00 AM8/31/96
to

bue...@asterix.urc.tue.nl (Marcel van Kervinck) wrote:
>
> Chris Whittington (chr...@cpsoft.demon.co.uk) wrote:
> : I was after some fast logic to do it (find the highest bit set).
> : an *and* and a *negate* is all that's needed for the ls bit;
> : fp units or looping on a rotate left weren't what I was after.
>
> : I know its possible by simple logic because I read the code somewhere
> : ages ago, but have now forgotten it ....
>
> I highly doubt there is a way to do it in less than O(wordsize)
> logic operations. Finding LSB works because the negate implies
> an increment operation (-a==~a+1), with a carry traveling from
> the lowest bit to highest bit. There are no operators that pass
> information along the whole word in the opposite direction.
> So you need to code it yourself, requiring O(wordsize) instructions.
>
> Btw, I did some investigation to code the %67 function efficiently,
> but gave up. Even /67 isn't trivial, but doable. Perhaps we should
> be looking for another %n with unique 2^i%n.
>
> Perhaps we should return to programming chess.

This is a chess issue for me. I'ld get 5% extra speed from
a fast way to do this.
>
> Regards,

Ilias Kastanas

unread,
Sep 3, 1996, 3:00:00 AM9/3/96
to

In article <504904$8...@tuegate.tue.nl>,

Marcel van Kervinck <bue...@asterix.urc.tue.nl> wrote:
>Ilias Kastanas (ika...@alumnae.caltech.edu) wrote:
>> >ls bit of a = a and -a
>> >
>> ms bit of a = ????????
>> Why would it be a problem using a 100...0 flag? For 16-bit integers
>> flag = 0x8000;
>> msbit = ( (a & flag) == flag);
>> Or in assembly, most architectures have a Rotate-through-Carry; then
>> you read the bit, say by Jump-if-Carry-Set. (For Intel, it's RCL and JC).
>> Much easier is to test a >= 0 (msb = 0) versus < 0 (msb = 1).
>> But check that 100...0 is handled properly.
>
>I think you missed the point. But I'm not sure what you mean by
>"using a 100...0 flag". The question was how to find the highest
>bit set. Somehow the poster used the confusing term 'MSB' for this.
>
>The easiest way, ofcourse, is to put the word into the floating
>point unit, let the thing normalize and then examine the exponent
>field...


Well, I answered the question I saw; MSB is quite clear in meaning,
most significant bit.

If you have an FPU, great. If not you can RCL until Carry is 1.
If you don't like assembly, repeated integer division by 2, until you
get 0, does it.


Ilias


Marcel Nijman

unread,
Sep 4, 1996, 3:00:00 AM9/4/96
to

...which makes it a programming issue, instead of a chess issue.

MJN

--
____ ____ __ ____ 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

Two Kentuckians were driving a semi down a road when they came to a
viaduct.
The sign said 10 feet zero inches, so they got out to measure their
truck.
Unfortunately, the truck was just over 12 feet high. They didn't know
what
to do, when finally one of them looked both directions and said,
"I don't see any cops, let's go for it!"

Tord Kallqvist Romstad

unread,
Sep 4, 1996, 3:00:00 AM9/4/96
to

Marcel Nijman (mar...@mbfys.kun.nl) wrote:

: Chris Whittington wrote:
: >
: > bue...@asterix.urc.tue.nl (Marcel van Kervinck) wrote:
: > >
: > > Perhaps we should return to programming chess.
: >
: > This is a chess issue for me. I'ld get 5% extra speed from
: > a fast way to do this.

: ...which makes it a programming issue, instead of a chess issue.

It is a programming issue, but it is obviously a programming issue of
great interest to chess programmers. Anyway, I think it would be wise
to discuss this in another newsgroup --- then the probability of getting
an answer would be much higher.

Tord


Don Fong

unread,
Sep 4, 1996, 3:00:00 AM9/4/96
to

In article <322D4481...@mbfys.kun.nl>,

Marcel Nijman <mar...@mbfys.kun.nl> wrote:
>Chris Whittington wrote:
>>
>> bue...@asterix.urc.tue.nl (Marcel van Kervinck) wrote:
>> >
>> > Perhaps we should return to programming chess.
>>
>> This is a chess issue for me. I'ld get 5% extra speed from
>> a fast way to do this.
>
>...which makes it a programming issue, instead of a chess issue.

it's both a chess issue and a programming issue, which makes it
quite appropriate for rgcc. OTOH your observations are relevant
to neither chess nor programming. sheesh, if you're worried about
wasted bandwidth, then trim back your .sig .

[...megalo-signature deleted...]

0 new messages