Prev: How to access this package written in C?
Next: integer questia
From: Simon Wright on 24 Apr 2010 07:28
Michael R <michael(a)zanyblue.com> writes:

> On Apr 23, 2:39 pm, Simon Wright <si...(a)pushface.org> wrote:

>> I don't know about 'best', but in ColdFrame
>> (http://coldframe.sourceforge.net/coldframe/) I would generate this hash
>> for use with Booch Maps, where the key components of Instance are
>> {A:Integer, B:Integer, C:Integer}:
>>
>>    function Instance_Hash (I : Instance) return Natural is
>>       type M is mod 2**31;
>>       Result : M := 0;
>>    begin
>>       Result := Result xor M (I.A mod 2**31);
>>       Result := Result * 10019;
>>       Result := Result xor M (I.B mod 2**31);
>>       Result := Result * 10019;
>>       Result := Result xor M (I.C mod 2**31);
>>       Result := Result * 10019;
>>       return Natural (Result);
>>    end Instance_Hash;
>>
>> I believe the 10019 came from Knuth, but can't see a reference.
>
> Thank you for this suggestion. Just fyi, my GNAT 4.4.3 compiler
> generated
>
> xtest.adb:20:40: value not in range of type "Standard.Integer"
> xtest.adb:20:40: static expression fails Constraint_Check
>
> for "M (I.A mod 2**31)" expressions. Rephrasing as
>
> Result := Result xor M'Mod (I.A);
>
> compiled OK.

I looked into this and found that for this specific case I would in fact
generate rather different code -- sorry about that, a bit like posting
untested Ada :-(

Actually it would be

function Instance_Hash (I : Instance) return Natural is
type M is mod 2**31;
Result : M := 0;
begin
Result := Result xor Integer'Pos (I.A);
Result := Result * 10019;
Result := Result xor Integer'Pos (I.B);
Result := Result * 10019;
Result := Result xor Integer'Pos (I.C);
return Natural (Result);
end Instance_Hash;

and, before anyone rushes to check it out, yes, it fails with negative
values and I'm about to file a bug against it.

Thanks for the response.
From: Warren on 26 Apr 2010 11:33
Simon Wright expounded in news:m28w8dyhjr.fsf(a)pushface.org:
...
> for use with Booch Maps, where the key components of Instance are
> {A:Integer, B:Integer, C:Integer}:
>
> function Instance_Hash (I : Instance) return Natural is
> type M is mod 2**31;
> Result : M := 0;
> begin
> Result := Result xor M (I.A mod 2**31);
> Result := Result * 10019;
> Result := Result xor M (I.B mod 2**31);
> Result := Result * 10019;
> Result := Result xor M (I.C mod 2**31);
> Result := Result * 10019;
> return Natural (Result);
> end Instance_Hash;
>
> I believe the 10019 came from Knuth, but can't see a reference.

I think this is just a selected prime number:

http://www.mathematical.com/primes3000kto4000k.html

Probably a compromise between "wideness" and memory
used in the map itself (affects number of buckets perhaps).

Warren.
From: Jeffrey R. Carter on 26 Apr 2010 14:14
Warren wrote:
> Simon Wright expounded in news:m28w8dyhjr.fsf(a)pushface.org:
>>
>> I believe the 10019 came from Knuth, but can't see a reference.
>
> I think this is just a selected prime number:

Except that 10_019 is not a prime number, according to:

http://www.mathematical.com/primes0to1000k.html

9949,9967,9973,10007,10009,10037,10039,10061,10067,10069,10079,10091,10093

--
Jeff Carter
"Ah, go away or I'll kill ya."
Never Give a Sucker an Even Break
100
From: Charmed Snark on 26 Apr 2010 14:32
Jeffrey R. Carter expounded in news:hr4lnl$6m8$1(a)tornado.tornevall.net:

> Warren wrote:
>> Simon Wright expounded in news:m28w8dyhjr.fsf(a)pushface.org:
>>>
>>> I believe the 10019 came from Knuth, but can't see a reference.
>>
>> I think this is just a selected prime number:
>
> Except that 10_019 is not a prime number, according to:
>
> http://www.mathematical.com/primes0to1000k.html
>
> 9949,9967,9973,10007,10009,10037,10039,10061,10067,10069,10079,10091,10
> 093

Oh I see - these numbers start at 3000017-- my haste, my bad.

Warren
From: Robert A Duff on 26 Apr 2010 14:37
Simon Wright <simon(a)pushface.org> writes:

> type M is mod 2**31;
> Result : M := 0;
> begin
> Result := Result xor Integer'Pos (I.A);

> and, before anyone rushes to check it out, yes, it fails with negative
> values and I'm about to file a bug against it.

I don't think that's a compiler bug. Conversion of negative numbers
to modular raises Constraint_Error. I think that's a language
design flaw, but not everyone agrees with me. The 'Mod attribute
works around the problem.

- Bob
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: How to access this package written in C?
Next: integer questia