Use a 8086 instead, only $1 each.
Chris Whittington
>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?
How about table look-up?
--
Anders Thulin Anders...@lejonet.se 013 - 23 55 32
Telia Research AB, Teknikringen 2B, S-583 30 Linkoping, Sweden
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''
--
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
It was a joke.
80586 v 8086 price comparison.
Sorry if too subtle.
Chris Whittington
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
>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
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
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
: 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,
: 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)...
This is a chess issue for me. I'ld get 5% extra speed from
a fast way to do this.
>
> Regards,
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
...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!"
: ...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
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...]