Simple hash without obvious periodicities

[jack]

What's the simplest hash function which will take an integer, and return an integer from 0 to N-1, where simple arithmetic cycles in the input don't produce visually obvious cycles in the output? Eg. if the input is 0,2,4,6,8... the output should not all be even. I assumed something simple like "multiply by blah, raise to the something power mod N" would work, but I wasn't sure.

A few caveats:

* Obviously using a non-trivial but non-cryptographic hash (eg. md5) will work, as will seeing a random number generator with the input and using the first number generated. The question is, is there a SIMPLER solution or not.

* I'm happy to contrain N to be prime >2 (or at least, odd), then the trivial hash "output = input % N" works fine.

The use case is, in a tile-based game, many floor types (grass, floorboards, etc) are not drawn with the same image in each tile, because it looks ridiculous to see regemented rows of grass with exactly the same pattern in each square, but rather using a random image from a small set of similar but different tile images.

But when I say "random", it's useful if that's determined by the tile's position, because (a) I don't have to worry about generating the values and caching them (b) each tile on the map uses the same image even if they're generated in a different order, so I don't have to keep rechecking that it looks ok (especially if I expand the concept to include more varied tiles that are still applied randomly).

This seemed like a sensible question, but I tried asking on stack overflow, hoping for "yes, just use X" or "no, I don't think you can do better than the random version", but all I got was:

* I was stupid to even consider it, I should bite the bullet and generate a random value for each tile in the map when it was loaded
* I was stupid to even consider it, I should bite the bullet and make sure I always design prime numbers of tiles whenever I'm designing the art.

OK, yeah, that will work, but once I've separated the parts of code that "draw a tile" from the parts that decide "what's the probability of each tile", I don't want mush them together again (a) wasting MY time in order to save a few cycles doing rand() and (b) meaning a trivial error in designing the art will create giant moire patterns across the whole landscape.

Comments

[jack]

Oh, shiny! Thank you! Yes, it's aimed at python, although the only other likely candidate is C, and I assume I could implement the hash in C if I needed to :)

FWIW, N is going to vary: probably the most common case is 2[*], but there'll probably a bunch of small integer values, so we may choose several p in advance or need to generate it.

[*] Well, ok, the most common case is 1, but that's a special case :)

[simont]

In that case I'd be inclined to think it's simplest just to pick one good fixed prime (my 65267 above is the largest safe prime less than 2^16), compute k as (p+N-2)/N (i.e. ceil rather than floor of the probable-non-integer (p-1)/N), and live with the small imbalance, which will be of the order of N/2^16, i.e. not noticeable.

[jack]

That seems sensible. I'm annoying if the error is 50%, but 10% is fine, and we can safely ignore anything over 2^16 :)