Fast Owen-scrambling of Arrays
Different ways to randomly permute implicit trees in O(n) time

Say you have an array whose length is a power of some base b. For most of this post we’ll be using powers of two, but we’ll discuss other bases as well. Imagine that there is a b-ary tree over the array. We want to shuffle the array in the following way: randomly shuffle the b sub-trees of the root. Then, recurse into each subtree, and do the same, until we get to the bottom.

Read More
August 9, 2021

Andrew Kensler's permute()
A function for stateless, constant-time pseudorandom-order array iteration

That subtitle is a little bit of a mouthful, but I’ve been wanting to talk about Andrew Kensler’s permute() function for a while and I wanted to make it clear right off the bat why it’s useful. permute() is used some in the graphics community, especially in offline rendering, and the techniques are more widely known in cryptography*, but it’s applicable to so much more than graphics and cryptography.

Read More
March 22, 2021