Context: I'm writing an external SRAM tester for a microcontroller-based embedded system. No security, no cryptography involved. For reproducible access to "as-non-consecutive-as-possible" memory locations, I'm looking for an implementation of
y = shuffle(x), taking and returning an integer between 0 and a fixed N = 2^16 - 1
It may not use a lot of RAM itself, as e.g. a naive shuffled array of addresses would. On the upside, it is allowed to be slow. No strict definition of non-consecutive - it's about bumping address lines up and down, hunting for soldering and other faults of the printed circuit board. Suggestions?
I found so far Knuth shuffle a.k.a. Fisher-Yates shuffle.
A late EDIT: I think I'm looking to maximize the Hamming distance. "Anti-Grey code"?
I agree with Jim Mischel that xorshift is a good candidate for a fast non-crypto PRNG. Coefficients need to be carefully chosen to achieve full cycle, which includes all values except 0.
Since you wired the problem to 16 bits in your question, here's a 16 bit implementation written in Ruby, but easily ported to anything else you like:
# << is shift left, >> is shift right, ^ is bitwise XOR, & is bitwise AND
MASK_16 = (1 << 16) - 1
def xorshift(x)
x ^= x << 7 & MASK_16
x ^= x >> 9
x ^= x << 8 & MASK_16
return x
end
counter = 0
x = 1
y = 1
# Floyd's "Tortoise and Hare" cycle-finding algorithm shows
# the generator to be full cycle for 16 bits, excluding zero.
loop do
counter += 1
x = xorshift(x)
y = xorshift(xorshift(y))
break if x == y
end
puts counter # => 65535