On Tue, May 26, 2020 at 3:46 AM Philippe Verdy <verdyp@gmail.com> wrote:
> A table size for 16 elements: 2^4-1=15 is Mersenne, but is a multiple of 3 and 5, so collisions occur for objects whose differences of addresses is frequently a multiple of 3 or 5 (e.g. allocating many objects with size 10, or 12 or 20).
> A table size for 32 elements: 2^5-1=31 is Mersenne, but is prime (no problem here).
> A table size for 64 elements: 2^6-1=63 is Mersenne, but is a multiple of 3, so collisions occur for objects whose differences of addresses is frequently a multiple of 3 (e.g. allocating many objects with size 12)
> A table size for 128 elements: 2^7-1=127 is Mersenne, but is prime (no problem here).
> A table size for 512 elements: 2^9-1=511 is Mersenne, but is a multiple of 3.
> A table size with 256 elements: 2^8-1=255 is Mersennen but is a multiple of 5
4,6,9,8 are not primes and are even, their mersennes must all be divisible by 3.
That's what I said, but there are some missing words at end of the sentence.
4 is 2*2, so 2^4-1 must be multiple of 2^2-1 = 3, same for 8 ( the 5
factor is easy to spot in decimal, but 255 = 3*5*17.
In fact any 2^p-1 where p is even is trivially proven to be equal to
(2^(p/2)-1)*(2^(p/2)+1) as (x-1)*(x+1)=x^2-1 ), as can be seen in
3*5=15, 7*9=63, 15*17=255
The interesting odd 9 must be a multiple of 7 ( 2^3-1), in fact, it
is NOT A MULTIPLE OF 3 (5+1+1=7!). It is in fact seven times seventy
three ( try factor 511 )
This message and the previous one makes me suspicious on the soundness
of all your hash table collisions/primes/sizes dissertation. Do you
have ay measurements/simulations of your various assertions?
You are misreading what I wrote. I've *explicitly* said 4,6,9,7 are not primes, so they are eliminated as multipliers for Knuth's hashing. I listed them jsut to show that the searh for good primes will not be long for an 8-bit multiplier. There are not a lot of primes in 1..255, they are known. As well I saif thay Mersenne numbers (like 127 or 129) are not good multipliers even if they are primes (like 127).
