Consider adding another inversible function #23
Comments
FWIW: I spent a little bit of time looking at this function WRT strict avalanche criterion measures (more like a spoonful than a grain of salt for these observations). The constant 'a' doesn't seem to justify itself (adding one to the dependency chain). Continued here: https://twitter.com/marc_b_reynolds/status/1576848952846319616 |
|
Somewhat lagged reply.
This matches my experience trying to use it as a step of a stateless PRNG. Note that I might as well mention (even though it may be obvious), that the inverse may be computed with: template<typename T>
T inverse(T (&fn)(T),T x)
{
T ret=0;
for(T bit=1;bit;bit*=2)
ret^=bit*(((fn(ret)^x)&(2*bit-1))!=0);
return ret;
}(edit: simplified mask) I don't know of any "really O(1)" inverse for this. |
Xorsquare was found (probably?) by fp64 here, skeeto/hash-prospector#23 , and this is a variant that has no fixed points.
|
Oh, whoops, didn't mean to link the issue. But, the |
|
Actually, I also settled on XQO form in my PRNGs. Essentially, once you realize that Arguably, the well-known triangular numbers offer a similar idea. |
|
Another trick with XQO: the constant used with OR can be any odd number, not just 1, and you end up with something on the way to |
|
OK, new finding; this isn't useful for a unary hash, but for the related field of pseudo-random number generation, it might be? state = (state ^ (state * state | o5o7)) * m3;Where (o5o7 & 7) must equal 5 or 7, and (m3 & 3) must equal 3. This appears to change to all states in a random-seeming order for 16-bit states 32-bit states, and probably 64-bit states, for any o5o7 and any m3 I have tested that meet the mentioned criteria. Like an LCG, it alternates even and odd states, and the low 10 or so bits are very predictable. For 64-bit states, XORing the upper 32 bits with the lower 32 bits (but not storing that in
The downside to this is that it's much harder computationally to go backwards than forwards with what we know now, though it should be possible. Skipping around in this sequence seems very challenging. |
|
It's the same isn't it? The final integer product peels off into a second logical step. |
|
The difference is the period; repeatedly calling |
|
Yes. I was just talking about forming the inverse function. That last product is simply reversed by the mod-inverse of m3. |
|
Here's some mixing functions (based on CRC32-C) which are cheapish and strongly mix the bottom 32-bits. https://gist.github.com/Marc-B-Reynolds/7db198a050c422936be4520fb0655a6f |
Well. This also yields much less conspicuous zeroes, e.g.
Interesting. The proof eludes me so far (does anyone know?). I did exhaustively verify that it is both necessary and sufficient up to, and including,
This does fail PractRand at 16GB (2^32 outputs). For comparison, Speaking of PCG, using XQO instead of the first step in uint32_t pxq_hash(uint32_t input)
{
uint32_t state = (input | 1u) ^ (input * input);
uint32_t word = ((state >> ((state >> 28u) + 4u)) ^ state) * 277803737u;
return (word >> 22u) ^ word;
}seems to improve PractRand results (from failing at 4MB to failing at 512MB). Both fail gjrand Doesn't seem better than |
|
The (hand-made) function uint32_t hash(uint32_t x)
{
x ^= x >> 15;
x ^= (x * x) | 1u;
x ^= x >> 17;
x *= 0x9E3779B9u;
x ^= x >> 13;
return x;
}appears to have better avalanche scores than known murmur3-style two-rounders (but weaker than
Avalanche scores use unscaled PractRand is the result of Would be nice if someone double-checks this. Might be worthwhile to prospect around a bit for functions of this form. Update: https://www.shadertoy.com/view/dllSW7 . |
It may be, slightly: https://godbolt.org/z/5jznWeoW5 . So you might be better off writing it as uint32_t hash(uint32_t x)
{
x ^= x >> 15;
x = (x | 1u) ^ (x * x);
x ^= x >> 17;
x *= 0x9E3779B9u;
x ^= x >> 13;
return x;
}which gives identical results. |
|
Might be worth comparing some of these to those on https://mostlymangling.blogspot.com/ which uses a similar PractRand technique |
|
Unless I'm missing something (and I well may), measuring things becomes somewhat harder in 64 bit. E.g. I just spent a number of minutes, running Monte-Carlo (exhaustive is not practical for 64 bit) avalanche calculation, and got... this:
Not very precise (assuming I haven't botched it in the first place)...
Similarly with PractRand. For 32 bit 32GB is enough, but e.g. RRC-64-42-TF2-0.94 is 4TB, and some of the mentioned tests are up to 128TB. Someone with access to more computing power might want to give it a try. |
|
I (Tommy Ettinger) also wonder what's up with ettingerMixer, but I wouldn't be surprised if it's just bad when measured with specific tests. @fp64 , can you post or link the source of the ettingerMixer you used? It might give us some insight into what makes generators fail, since not many seem to do that right now. |
|
From https://mostlymangling.blogspot.com/2019/01/better-stronger-mixer-and-test-procedure.html (except I changed suffixes to uint64_t ettingerMixer(uint64_t v) {
uint64_t z = (v ^ 0xDB4F0B9175AE2165ull) * 0x4823A80B2006E21Bull;
z ^= rol64(z, 52) ^ rol64(z, 21) ^ 0x9E3779B97F4A7C15ull;
z *= 0x81383173ull;
return z ^ z >> 28;
}Update: heatmap (scaled to 0..9): 64x64 |
Some more context on accuracy of Monte Carlo. Show dataLet's take 32-bit function above (so we can actually do exhaustive measurement):
Compare to
And to
As we can see, somewhat good functions look basically indistinguishable with Monte Carlo for fairly sizeable N. But also Monte Carlo can detect more sharp deviations a lot earlier. |
|
Speaking of measuring things exactly, some optimal in their class
|
|
The function uint32_t hash(uint32_t x)
{
x ^= x >> 23;
x = (x | 1u) ^ (x * x);
x ^= x >> 13;
x = (x | 1u) ^ (x * x);
x ^= x >> 9;
x = (x | 1u) ^ (x * x);
x ^= x >> 17;
return x;
}appears to produce better avalanche scores than
The [14,14,14,14] one is easy to memorize. |
|
@tommyettinger, I just noticed something curious. As mentioned before, 32-bit rng uint32_t rng32()
{
uint64_t state=0ull;
state=-(state^(state*state|5ull));
return (uint32_t)(state>>32);
}performs very smoothly in PractRand, up until it abruptly harshly fails at 16GB. Similar for 16-bit rng, which fails at 512KB. This makes sense, since the period of k-th bit is 2^k (tests fail close to the period of lowest bit of output). uint64_t rng64()
{
static __uint128_t state=0ull;
state=-(state^(state*state|5ull));
return (uint64_t)(state>>64);
}seems to fail very fast (but not immediately!). Seeding the state with something like |
The "xorsquare" function (which I briefly describe here) is of the form:
x=((x+a)&-2)^(x*x);for any integer
a.Note: alternative version (
x^=((x+a)*(x+a))&-2;) produces identical results for values ofathat differ in the most significant bit.It is straightforward to show (e.g. by induction on wordsize) that it is inversible.
The text was updated successfully, but these errors were encountered: