GNU bug report logs - #50093
djb2 correction

Previous Next

Full log

Message #11 received at 50093 <at> debbugs.gnu.org (full text, mbox):

From: Alex Murray <alex.murray <at> canonical.com>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: Jim Meyering <jim <at> meyering.net>, 50093 <at> debbugs.gnu.org
Subject: Re: bug#50093: djb2 correction
Date: Wed, 18 Aug 2021 12:20:26 +0930

On Tue, 2021-08-17 at 14:04:26 -0700, Paul Eggert wrote:

> On 8/17/21 3:32 AM, Jim Meyering wrote:
>> -  size_t h = 0;
>> +  size_t h = 5381;
>
> I expect DJB chose that number because of the primeth recurrence sequence
> <https://oeis.org/A007097>:
>
> 2 is 1st prime.
> 3 is 2nd prime.
> 5 is 3rd prime.
> 11 is 5th prime.
> 31 is 11th prime.
> 127 is 31st prime.
> 709 is 127th prime.
> 5381 is 709th prime.
> 52711 is 5381st prime.
> ...
>
> Although 5381 is the largest number in this sequence that can fit into
> 'int' in a portable C program, and that's probably why DJB chose 5381,
> we're not limited to such small values here.
>
> How about the attached patch instead?
>

How about letting the compiler choose which prime to use? - something like the following:

#define H15_PRIME (unsigned long long)5381
#define H32_PRIME (unsigned long long)3657500101
#define H64_PRIME (unsigned long long)4123221751654370051
size_t h = H64_PRIME <= SIZE_MAX ? H64_PRIME : H32_PRIME <= SIZE_MAX ? H32_PRIME : H15_PRIME;

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.