On Mon, 9 Jan 2017, Jed Brown wrote: > Satish Balay <[email protected]> writes: > > > On Mon, 9 Jan 2017, Jed Brown wrote: > > > >> Satish Balay <[email protected]> writes: > >> > Sure - I'm using a crappy algorithm [look-up table] to get > >> > "prime_number_close_to(1.4*sz)" - as I don't know how to generate > >> > these numbers automatically. > >> > >> FWIW, it only needs to be coprime with PETSC_HASH_FACT. > > > > Not sure I understand - are you saying coprime requirement is easier > > satisfy than a single prime? > > Yeah, just don't be a multiple of PETSC_HASH_FACT, which is itself > prime. > > > I had switched this code to use double-hasing algorithm - and the > > requirement here is - the table size be a prime number. [so I'm > > attempting to estimate a prime number suitable for the table size] > > Why is it not sufficient to be coprime?
Well whatever was implemented previsously with PETSC_HASH_FACT [a prime number] didn't work well. [there were a couple of reports on it]. Checking double hashing [Intro to algorithms, Coremen et all.]: For a hashtable size 'm' - and using hash functions h1(k), h2(k) - it says: h2(k) must be relatively prime to 'm'. [for all possilbe 'k' values? its not clear. Also any constraints on h1(k)?] And it suggested the following as one way to imlement: choose a prime 'm' h1(k) = k mod m h2(k) = 1 + (k mod m') This was simple enough for me - so I updated ctable to use it. I've added entries up to INT_MAX. If its still lacking (I could potentially add more entries - perhaps for 64bitincides? or) - feel free to change the algorithm for arbirary sizes... Satish
