Using random number generators to solve problems

Nov 4, 2018

I recently came across the following blog post detailing a very nice Ruby solution to the following problem:

you are constantly creating robots, each of which must be given a unique name
this name must follow the pattern letter letter number number number
names need to be assigned at random, e.g. you can’t just call your first robot AA000, your second robot AA001, …
there needs to be a way to reset this name generator

The author came up with a very beautiful Ruby solution that makes clever use of ranges. In essence, it goes a little something like this:

class Generator
  def initialize
    init_rng
  end

  def next
    @names.next
  end

  def reset
    init_rng
  end

  private

  def init_rng
    @names = ('AA000'..'ZZ999').to_a.shuffle.each
  end
end

gen = Generator.new
gen.next # => SX696
gen.next # => VW329

There’s some really good stuff going on here. I had no idea ranges in Ruby where smart enough to deal with ('AA000'..'ZZ999'). The idea of storing @names as an enumerator is very nice as well. The author should feel proud for coming up with it.

Can we make it scale?

Reading through the code, it struck me just how diabolical this problem actually was. Because of the requirement for names to be assigned at random, we need to generate all elements in the range ('AA000'..'ZZ999') during initialization in order for us to be able to shuffle them into a random order. Unfortunately, this doesn’t really scale well for larger ranges. Some computation times for different ranges are shown below.

'AA000'..'ZZ999'     - 0.3 sec
'AAA000'..'ZZZ999'   - 9.8 sec
'AAAA000'..'ZZZZ999' - 133 sec

I started wondering just how hard it would be to solve this problem for arbitrarily large ranges. As it turns out, it’s totally possible, but we need to rephrase our robot naming problem into two completely different subproblems:

Can we come up with a method that takes a number as input and transforms it into the relevant element of the range 'AA000'..'ZZ999' as output? e.g. can we transform the number 0 into the string AA000, the number 1 into the string AA001, … ?
Can we come up with a random number generator that’ll allow us to specify a range and that will then return all elements of this range exactly once in a random order?

If we can solve both of these subproblems, then the original problem can be solved by writing such a random number generator and transforming each random number returned by it into the desired range. The nice thing about this approach is that generating a new name will always take the same amount of time regardless of the size of the range as we now no longer have to compute all elements in the range during initialization.

Designing a transformation function

The transformation function is by far the easier subproblem of the two. There isn’t really much to say about constructing such a function. We’ll start by writing a function that can transform an input into a 5 digit binary number. Once this is done, we’ll just modify this function to transform the input into the range 'AA000'..'ZZ999' instead.

Writing a function that can create 5 digit binary numbers is pretty straightforward. It goes a little something like this:

def transform(number)
  binary = []

  binary << number % 2
  binary = number / 2

  binary << number % 2
  binary = number / 2

  binary << number % 2
  binary = number / 2

  binary << number % 2
  binary = number / 2

  binary << number % 2
  binary = number / 2

  binary.reverse.join
end

transform(17) # => 10001
transform(28) # => 11100

The names we want to generate need to be in the range 'AA000'..'ZZ999'. That is to say, the last three characters need to be 0-9 (base 10), while the first two characters need to be A-Z (base 26). Modifying our function to accommodate this is straightforward enough:

def transform(number)
  name = []

  name << number % 10
  number = number / 10

  name << number % 10
  number = number / 10

  name << number % 10
  number = number / 10

  name << char(number % 26)
  number = number / 26

  name << char(number % 26)
  number = number / 26

  name.reverse.join
end

def char(number)
  (65 + number).chr
end

transform(0) # => AA000
transform(1) # => AA001

If we clean this up a bit, then we end up with the following code:

def generate_name(number)
  name = []

  3.times do
    name << number % 10
    number = number / 10
  end

  2.times do
    name << char(number % 26)
    number = number / 26
  end

  name.reverse.join
end

def char(number)
  (65 + number).chr
end

There we go, that was pretty easy. The first of our subproblems has been solved and we’re now halfway to solving our robot naming problem. Let’s go ahead and take a look at the second subproblem: creating a custom random number generator.

Creating a custom random number generator

Creating a random number generator that returns all numbers in a given range exactly once in a random order is a bit of an unusual programming problem. Thinking back to my CS classes, I can vaguely remember a lecture about generating pseudo-random numbers with a linear congruential generator. So let’s start by having a look at its Wikipedia page.

Linear congruential generators use the following formula to generate random numbers:

next_random_number = (a * current_random_number + c) % m

A generator will have different properties depending on the choice of the a, c, and m parameters. Luckily for us, there is a small section on its wiki page that describes how these parameters should be chosen in order for a generator to return all numbers of a given range exactly once in a random order.

If our range is a power of 2, these parameters need to fulfill the following requirements:

m will be our range, and therefore needs to be a power of 2
a needs to be smaller than m and a - 1 needs to be divisible by 4
c can be any odd number smaller than m

Writing a generator that meets these requirements is a pretty straightforward undertaking:

class Generator
  def initialize(range:)
    @range = range
    init_rng
  end

  def reset
    init_rng
  end

  def next
    @r = ((@a * @r) + @c) % @m
  end

  private

  def init_rng
    random = Random.new

    # m needs to be a power of two for now (we don't support arbitrary ranges yet)]
    # a needs to be smaller than m and (a - 1) needs to be divisible by 4
    # c can be any odd number smaller than m
    @m = @range
    @a = random.rand(@m / 4).to_i * 4 + 1
    @c = random.rand(@m / 2).to_i * 2 + 1

    # a random seed to get our generator started. The value of this seed needs to be
    # smaller than the value of m as well.
    @r = random.rand(@m).to_i
  end
end

# remember that our range needs to be a power of 2 for now
gen = Generator.new(range: 8)
16.times.map { gen.next }
# => [6, 1, 4, 7, 2, 5, 0, 3, 6, 1, 4, 7, 2, 5, 0, 3]

gen.reset
16.times.map { gen.next }
# => [2, 3, 0, 1, 6, 7, 4, 5, 2, 3, 0, 1, 6, 7, 4, 5]

Note that our generator will start repeating itself after having iterated across all elements in its range. We can fix this by having our next method raise an exception when its random numbers start repeating. The code for this can be seen below.

class GeneratorExhausted < StandardError; end

class Generator
  ...

  def next
    @r = ((@a * @r) + @c) % @m
    raise GeneratorExhausted if @r == @first_value
    @first_value ||= @r
    @r
  end

  ...
end

Note that up until now our range has always needed to be a power of two. Luckily we can easily accommodate ranges of arbitrary length. All we need to do is:

calculate the first power of two larger than our arbitrary range
use this power of two for our random number calculations
if our random number generator comes up with a number outside the specified range, then just throw it away and keep generating numbers until we find one that’s inside our range. On average, the very next randomly generated number will be inside the range, so the overhead for this is small. The code for doing so is shown here:

class GeneratorExhausted < StandardError; end

class Generator
  def initialize(range:)
    @range = range
    init_rng
  end

  def reset
    init_rng
  end

  def next
    loop do
      @r = ((@a * @r) + @c) % @m
      raise GeneratorExhausted if @r == @first_value

      if @r < @range
        @first_value ||= @r
        return @r
      end
    end
  end

  private

  def init_rng
    random = Random.new

    # m is the first power of two larger than our range
    # a needs to be smaller than m and (a - 1) needs to be divisible by 4
    # c can be any odd number smaller than m
    @m = 2 ** Math.log(@range + 1, 2).ceil
    @a = random.rand(@m / 4).to_i * 4 + 1
    @c = random.rand(@m / 2).to_i * 2 + 1

    # a random seed to get our generator started. The value of this seed needs to be
    # smaller than the value of m as well.
    @r = random.rand(@m).to_i
  end
end

gen = Generator.new(range: 10)
10.times.map { gen.next }
# => [6, 1, 8, 5, 9, 0, 3, 2, 4, 7]

The above code solves our second subproblem. We have successfully created a random number generator that’ll return all elements in a specified range exactly once in a random order. With both subproblems solved, we can now go ahead and write a solution to the original problem of generating random names for our robots.

Putting it all together

Our final NameGenerator class will end up looking something like shown below. Note that I did not bother to copy the code for the Generator class from the previous section.

class NameGenerator
  RANGE = 10 * 10 * 10 * 26 * 26

  def initialize
    @generator = Generator.new(range: RANGE)
  end

  def reset
    @generator.reset
  end

  def next
    number = @generator.next
    generate_name(number)
  end

  private

  def generate_name(number)
    name = []

    3.times do
      name << number % 10
      number = number / 10
    end

    2.times do
      name << char(number % 26)
      number = number / 26
    end

    name.reverse.join
  end

  def char(number)
    (65 + number).chr
  end
end

name_generator = NameGenerator.new
name_generator.next # => MJ650
name_generator.next # => HK923

The really nice thing about this approach is that by writing our own random number generator we have essentially created a lazily evaluated pseudo-random shuffle. It’s the kind of thing you would never want to use in a library that requires proper random numbers (e.g. encryption), but works great for problems like this.

Because of the lazily evaluated nature of our solution, we can now generate names across arbitrarily large ranges. Remember how it used to take 133 seconds to generate the first random name in the range 'AAAA000'..'ZZZZ999'? We can now do this in just 0.1 seconds! That’s a pretty good speed improvement for generating robot names!

Finishing up, I would just like to mention that this was a bit of a weird article for me to write. I’m not really at home with creating random number generators, so there is a real chance that some bugs might have crept in here or there. As always, if you think I got anything wrong, please feel free to get in touch and let me know.

vaneyckt

Using random number generators to solve problems

Can we make it scale?

Designing a transformation function

Creating a custom random number generator

Putting it all together