If we want to hash "JAN", "FEB", "MAR", in order to know what day of the week a month this year starts on, we could hash the month string with a magic number and maybe get an index 0-15 after shifting, and have a look-up table with 16 entries, possibly with 12 of them containing values in the range 0-6 or 1-7 for the days of the week. (And the other 4 don't-care locations typically being zero/empty.)
A useful magic number for general purposes would hash the month characters into a value 0-11 so that an array of 'data month by month' would only have 12 elements instead of 16. Hashing into 4 bits, 16 values, there will be (at least) 4 holes in the 16 values used, and there is an advantage in memory usage if the holes are at the end of an array as it allows the array to be shortened, eg using 12 elements instead of 16.
But if we are not trying to hash month strings into month numbers for a general application, but sticking to the original idea of knowing what day of the week a month this year starts on, then that array can contain even less than 12 entries. March and November start on the same day of the week. September and December start on the same day of the week, etc.
So if "MAR" and "NOV" hash to the same values, we get what people sometimes refer to as good collisions. With 4 good collisions, we would be down to using 8 values instead of 12 and so it is conceivable that we can find a useful magic multiplier and shift that generates 3 bits instead of 4.
=
If we wanted to know how many days are in a month this year, the answer would be 29,30 or 31 so to have a look-up table for that, we might be able to hash the month characters into a two-bit value.
=
There is a saying that "it is only safe to eat oysters if there is an R in the month", e.g. avoid the warm summer months when they go off faster. So for the 12 months, and an application like that it might be possible to use magic numbers to hash a month string down to a single bit instead of 4 bits.
Looking for magic numbers, I have been trying to get concepts like this clear in my head, and in doing so, I have developed a sort of personal terminology for things. Maybe there is a more formal mathematical framework somewhere, but I don't remember seeing it - so for the time being at least, I am stuck/sticking to my own words.
I call magics doing what I described above, that can compress (in this example what is essentially in some sense a 4 bit input) into less bits, as skinny magics. If you hash a month string into a 5 bit value for month number then magics like that I call overweight magics. Most people are using just normal sized magics I think. It is most natural to think of them and look for them. A use for overweight magics is when a magic number of the right size cannot be found.
I didn't look for underweight/skinny magics for my chess program, as originally I didn't have any magic stuff at all.
But I assume I have understood you this time: that when you said you have dropped a bit, that you are indexing your data with less bits - you have found some skinny magics.
For a bishop at a1, there are 6 bits {b2, c3, d4, e5, f6, g7} that determine its blocking, and its motion possibilities (8 possibilities {}, {b2}, {b2,c3}, {b2,c3,d4}, ...{b2,..,h8}) can be described by three bits, so the potential is certainly there for some skinny hashing. I didn't really look for them, due to the way magic multiplication works. (Significant occupancy bits need to contribute to the indexing and if two bits are added into the same location, there is no way of knowing which of the two was set, so you can more or less expect each occupancy bit to be sent into the index in a location of its own.) If the numbers created were more random then I think more compression in the tables would be possible. Maybe addition of a constant before multiplication would create better hashing, at the expense of more processor instructions - I base that solely on a gut feeling.
I will look for some skinny magics.
I am happy with the magics I put into my chess program. I went for "small" magics - magics that don't use the remote edge bits as part of the indexing. My rook magics need the remote edge bits to be masked off. My bishop magics are designed so that the remote edge bits are ignored by the magic and that makes the code to use them very slightly simpler.
- Code: Select all
return SmallBishopAttackTable[sq][(SmallBishopMagic[sq]*obstructions)>>SmallBishopShift[sq]];
- Code: Select all
obstructions &= SmallRookSignificantBits[sq];
return SmallRookAttackTable[sq][(SmallRookMagic[sq]*obstructions)>>SmallRookShift[sq]];