samedi 2 avril 2016

How do I cheaply produce an infinite splittable stream of non-colliding numbers from a single seed?

I need a function split : Word64 -> (Word64, Word64) that takes any Word64 and splits it into two different Word64s in a way that I can keep splitting children and grandchildren in any arbitrary order while avoiding a collision. That is, for any pair sa, sb of consecutive splittings of a seed (such as sa = fst.split.fst.split$ seed), sa must be different from sb with >99.99% odds.

I've thought in using a pairing function, but that makes children exponentially bigger than parents, so, after a few splits there is an integer overflow. I need something that basically sends any value on the space of possible Word64 bits to two other values in a semi randomly fashion. Also, I need it to be as quick and simple as possible. The fewer instructions, the better. It is probably a very stupid calculation that I'm missing.

What can be used here?

Disclaimer: I have asked similar questions before, but now I finally have a better understanding of the problem and know exactly what I need.




Aucun commentaire:

Enregistrer un commentaire