CODEWITHSUNDEEP
algorithmrandomshufflehamming-distancegray-code
Xpector
Xpector

Reputation: 699

low-memory pseudo-random shuffle for fixed arbitrary length array

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"?

Upvotes: 0

Views: 341

Answers (2)

Jim Mischel
Jim Mischel

Reputation: 134045

I'd suggest implementing Xorshift, or something similar. They are fast, require little memory, can be constructed to have a long period, and satisfy many tests of randomness.

Another way to do it would be to uniquely map every number in the range 0..(n-1) to another number within that range. That's easy enough to do using a modular multiplicative inverse, as I describe in this answer.

Upvotes: 2

pjs
pjs

Reputation: 19855

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

Upvotes: 2

Related Questions