[petsc-users] PetscTableCreateHashSize

[Satish Balay]

On Mon, 9 Jan 2017, Jed Brown wrote:

> Satish Balay <balay at mcs.anl.gov> writes:
> 
> > On Mon, 9 Jan 2017, Jed Brown wrote:
> >
> >> Satish Balay <balay at mcs.anl.gov> 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