Re: Hashing on System.Address

[Marius Amado Alves <amado.alves@netcabo.pt>]

On 14 Jun 2005, at 11:14, Duncan Sands wrote:

> On Tuesday 14 June 2005 12:03, Marius Amado Alves wrote:
>>> ... The other thing I haven't really figured out is what to do
>>> if you have a 64-bit address, and Hash_Type is only 32...
>>
>> I gave a general solution to this class of cases before:
>>
>> <<
>> Treat both the input and output values as bit strings X (1 .. M) and Y
>> (1 .. N) respectively. (Use representation clauses, packed arrays, and
>> unchecked conversion for this.) Make N small, say 16. Set Y bits to 
>> the
>> value of X bits as follows:
>>
>> if M > N, Y (J) = X (1 + (J - 1) * M / N), for J in 1 .. N
>>
>> if M = N, Y = X
>>
>> if M < N, initialize Y to all zeros,
>>   then let Y (1 + (I - 1) * N / M) = X (I), for I in 1 .. M
>>>>
>
> Hi Marius, thanks for the suggestion.  A few comments though:
> if M > N (say M = 2*N) then you're skipping every second bit
> in X.  Why not use them - mix them in somehow?

Yes, I thought of that, namely picking every slice of M / N bits of the 
input and convert it to 1 bit. Example for M = 2 * N: 00 => 0, 01 => 0, 
10 => 1, 11 => 1. But see below.

>   If M < N then
> you are trying to spread the bits of X evenly throughout Y.  Are
> there any theoretical reasons to think this is a good strategy?

Intuition + experimentation. "Guess first, prove later" (Poincaré) I 
tested my function against GNAT's. Dispersion was equivalent. Speed 
also I if I remember correctly. That's proof enough for me. That's why 
I didn't advance to the slice variant just above.