antirez 7 days ago

Feistel networks are another way to map your index from linear sequence to a pseudorandom permutation.

Reply View 1 reply
  • brandonasuncion 7 days ago

    I was reading into it and came across your blog post. It's a good followup read.

    It has better avalanching compared to indexing by `(i * prime) % n`, but at the tradeoff of `n` being restricted to powers of 2.

    Reply View 0 replies
teiferer 8 days ago

That's neither random nor O(1). I think everybody reading the link immediately understands what you mean, but I whished this community would use its technical terminology more carefully.

Reply View 1 reply
  • brandonasuncion 7 days ago

    I use "random" in quotation marks because it communicates the topic effectively and is very straight to the point. Colloquially, when people say "random" in the context of algorithms, it's generally understood to mean "pseudorandom" or "quasirandom". The trick is essentially an LCG using coprime numbers.

    The blog post uses "random" in quotations as well in its title.

    I call it O(1) because the ordering is fully determined just by choosing an arbitrary prime number. It's constant time to "reorder" the elements and also constant time to get the i'th element in the permutation. This is in contrast to something like the the Fisher-Yates shuffle which permutes the elements in O(n) time.

    Reply View 0 replies