lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]




Le mar. 26 mai 2020 à 20:57, Francisco Olarte <folarte@peoplecall.com> a écrit :
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).