How can I transform a random integer to a uniform real [0,1[ distribution

Question

On Wikipedia, I found the following random number generator:

#include <stdint.h>

/* The state must be seeded so that it is not everywhere zero. */

uint64_t s[ 2 ];

uint64_t next(void) { 
    uint64_t s1 = s[ 0 ];
    const uint64_t s0 = s[ 1 ];
    s[ 0 ] = s0;
    s1 ^= s1 << 23;
    return ( s[ 1 ] = ( s1 ^ s0 ^ ( s1 >> 17 ) ^ ( s0 >> 26 ) ) ) + s0;
}

Now, when implemented, (using a random seed for s[0] and s1), this works nicely, but outputs numbers like:

2318509732609079156, 5455176535758408500, 14446583927462861784, 3420274542024626201, etc.

My question now is: How can I transform these numbers to a uniform real distribution [0,1[, i.e. with 0 included and 1 excluded?

there's a whole library for that in C++11: [](http://en.cppreference.com/w/cpp/numeric/random). Do you have a reason for doing that yourself? — Dmitry Ledentsov, May 27 '14 at 07:42
I'd recommend this talk about random generators in C++11: http://channel9.msdn.com/Events/GoingNative/2013/rand-Considered-harmful ; getting random numbers right is hard. — Mat, May 27 '14 at 07:46
Yes @DmitryLedentsov, speed. I selected this algorithm in particular because it is known to be one of the fastest random number engines around. I am writing a program where the main speed bottleneck is random number generation, so as fast as the Mersenne Twister or Lagged Fibonnaci generators are, they are still slower than this one. — Mark Anderson, May 27 '14 at 07:46
@PeterG. Thank you very much, that seems to have done the trick! (At least, at first glance). But may I ask: How did you know that this was the number to divide by? — Mark Anderson, May 27 '14 at 07:49
@MarkAnderson The maximum 64bit unsigned value is 2^64, so that's the maximum possible value of your generator. Assuming that `next` can return that value, dividing by this value can never be larger than 1. — anderas, May 27 '14 at 07:59
@MarkAnderson thanks for the answer. It seems like a valid reason, however, it all then depends on the other properties that you expect of that generator, and at least [one answer](http://stackoverflow.com/questions/1046714/what-is-a-good-random-number-generator-for-a-game) has an alternative — Dmitry Ledentsov, May 27 '14 at 08:11

score 3 · Answer 1 · answered May 27 '14 at 07:43

3

In C++11 there's a way to produce uniformly distributed numbers over an interval with std::uniform_real_distribution:

// uniform_real_distribution
#include <iostream>
#include <random>

int main()
{
  std::default_random_engine generator;
  std::uniform_real_distribution<double> distribution(0.0,1.0);
  double random_number_in_01 = distribution(generator);

  return 0;
}

answered May 27 '14 at 07:43

101010

41,839
11
94
168

Thank you very much for your comment! I am quite aware of the standard library's random number generators, but in my case, speed is paramount. The generators in the standard library are fast, but I compared them to this simple algorithm, and they are significantly slower. – Mark Anderson May 27 '14 at 07:49
2

With regards to the C++11 random numbers model, your algorithm is a `random_engine`. Maybe you should try to blend into the C++11 random numbers by converting your algorithm to a custom `random_engine`, that you can then use with `std::uniform_real_distribution`. – Laurent LA RIZZA May 27 '14 at 07:57

score 1 · Accepted Answer · answered May 27 '14 at 07:50

Assuming that you want a double result, simply cast the result of your random generator to double and divide by the maximum value (i.e. 2^64):

double result = next() / (double) std::numeric_limits<uint64_t>::max();

Note that some precision might be lost when converting to 64bit real values, so the values might not be exactly uniformly distributed. If this matters for your application, you shouldn't use this code...

edit: Sorry, this could also result in the value 1. A simple workaround would be to repeat this until the value is not 1, or making sure that next() never returns std::numeric_limits<uint64_t>::max().

edit: Even simpler, as inspired by 40two's answer: Call std::uniform_real_distribution with your random generator:

std::uniform_real_distribution<double> distribution(0.0,1.0);
double random_number_in_01 = distribution(next);

Your original answer is misleading. If you divide by 2^64-1 in double precision you get non-uniformly distributed numbers since floating point numbers do not have uniform density in all intervals. For more information: https://crypto.stackexchange.com/questions/31657/uniformly-distributed-secure-floating-point-numbers-in-0-1 — lightxbulb, Feb 23 '18 at 21:15

How can I transform a random integer to a uniform real [0,1[ distribution

2 Answers2