[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#50093: djb2 correction
From: |
Alex Murray |
Subject: |
bug#50093: djb2 correction |
Date: |
Wed, 18 Aug 2021 12:20:26 +0930 |
User-agent: |
mu4e 1.6.3; emacs 28.0.50 |
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;