lua-users home
lua-l archive

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


And this is not a personal "essay" or "disertation". All is proven in wellknown Knuth's papers and books !
Still not convinced ? You need documentation about wellknown fast hashing algorithms. But not knowing Knuth's algo means that you don't know the subject at all and just used personal (wrong) assumptions in your code.

Le mar. 26 mai 2020 à 21:14, Philippe Verdy <verdyp@gmail.com> a écrit :


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).