We’re rewarding the question askers & reputations are being recalculated! Read more.
4 replaced http://scicomp.stackexchange.com/ with https://scicomp.stackexchange.com/
source | link

Say I have a random number generator that generates a number within [0, RAND_MAX], and RAND_MAX < UINT_MAX.

How do I generate a random number within [0, i] such that i>RAND_MAX and i<UINT_MAX, while maintaining an even distribution, and without exceeding UINT_MAX in any calculations?

The first attempt is to split the range into n equal parts such that i mod n == 0 by finding the least denominator of i (using one of the integer factorization sieve algorithms). Each sublist has equal distribution, any can be picked at random. This fails if i is prime:

0 1 2 3 4 5 6
|___| |_____|

The second attempt is to split the range into two parts a = [0, floor(i/2)] and b = [floor(i/2)+1, i], and then to calculate the distribution as the ratio of the length of the two sub-ranges:

g = gcd(length(a), length(b))
if random(0, length(a)/g + length(b)/g - 1) >= length(a)/g
    random(0, floor(i/2))
else
    random(floor(i/2)+1, i)

Given the following range, the right sub-range is selected twice as often as the left sub-range:

0 1 2 3 4 5
|_| |_____|

Unfortunately the first call to random() may recurse forever if gcd() is ever one.

The final attempt is to correct the distribution skew introduced by splitting a range of odd length:

if random(1)
    if random(1)
        random(0, floor(i/2))
    else
        random(floor(i/2) + 1, i)
else
    if random(1)
        random(0, floor(i/2) - 1)
    else
        random(floor(i/2), i)

Which probably doesn't work.

Edit:

For anyone with similar question, the sum of two uniform variables follows a triangular distribution (see Irwin-Hall Distribution). This is invalid:

# triangular distribution:
random(a, floor(b/2)) + random(a, b - floor(b/2))

Edit (on accept):

The two answers I considered are both of high quality. This answerThis answer considers RNGs on a per-digit or per-bit basis. The accepted answersThe accepted answers consider RNGs numerically, without considering digits or bits. In both cases, the comments are important to read.

I've also posted a follow-up question Maintain Uniform Distribution across SubrangesMaintain Uniform Distribution across Subranges.

Say I have a random number generator that generates a number within [0, RAND_MAX], and RAND_MAX < UINT_MAX.

How do I generate a random number within [0, i] such that i>RAND_MAX and i<UINT_MAX, while maintaining an even distribution, and without exceeding UINT_MAX in any calculations?

The first attempt is to split the range into n equal parts such that i mod n == 0 by finding the least denominator of i (using one of the integer factorization sieve algorithms). Each sublist has equal distribution, any can be picked at random. This fails if i is prime:

0 1 2 3 4 5 6
|___| |_____|

The second attempt is to split the range into two parts a = [0, floor(i/2)] and b = [floor(i/2)+1, i], and then to calculate the distribution as the ratio of the length of the two sub-ranges:

g = gcd(length(a), length(b))
if random(0, length(a)/g + length(b)/g - 1) >= length(a)/g
    random(0, floor(i/2))
else
    random(floor(i/2)+1, i)

Given the following range, the right sub-range is selected twice as often as the left sub-range:

0 1 2 3 4 5
|_| |_____|

Unfortunately the first call to random() may recurse forever if gcd() is ever one.

The final attempt is to correct the distribution skew introduced by splitting a range of odd length:

if random(1)
    if random(1)
        random(0, floor(i/2))
    else
        random(floor(i/2) + 1, i)
else
    if random(1)
        random(0, floor(i/2) - 1)
    else
        random(floor(i/2), i)

Which probably doesn't work.

Edit:

For anyone with similar question, the sum of two uniform variables follows a triangular distribution (see Irwin-Hall Distribution). This is invalid:

# triangular distribution:
random(a, floor(b/2)) + random(a, b - floor(b/2))

Edit (on accept):

The two answers I considered are both of high quality. This answer considers RNGs on a per-digit or per-bit basis. The accepted answers consider RNGs numerically, without considering digits or bits. In both cases, the comments are important to read.

I've also posted a follow-up question Maintain Uniform Distribution across Subranges.

Say I have a random number generator that generates a number within [0, RAND_MAX], and RAND_MAX < UINT_MAX.

How do I generate a random number within [0, i] such that i>RAND_MAX and i<UINT_MAX, while maintaining an even distribution, and without exceeding UINT_MAX in any calculations?

The first attempt is to split the range into n equal parts such that i mod n == 0 by finding the least denominator of i (using one of the integer factorization sieve algorithms). Each sublist has equal distribution, any can be picked at random. This fails if i is prime:

0 1 2 3 4 5 6
|___| |_____|

The second attempt is to split the range into two parts a = [0, floor(i/2)] and b = [floor(i/2)+1, i], and then to calculate the distribution as the ratio of the length of the two sub-ranges:

g = gcd(length(a), length(b))
if random(0, length(a)/g + length(b)/g - 1) >= length(a)/g
    random(0, floor(i/2))
else
    random(floor(i/2)+1, i)

Given the following range, the right sub-range is selected twice as often as the left sub-range:

0 1 2 3 4 5
|_| |_____|

Unfortunately the first call to random() may recurse forever if gcd() is ever one.

The final attempt is to correct the distribution skew introduced by splitting a range of odd length:

if random(1)
    if random(1)
        random(0, floor(i/2))
    else
        random(floor(i/2) + 1, i)
else
    if random(1)
        random(0, floor(i/2) - 1)
    else
        random(floor(i/2), i)

Which probably doesn't work.

Edit:

For anyone with similar question, the sum of two uniform variables follows a triangular distribution (see Irwin-Hall Distribution). This is invalid:

# triangular distribution:
random(a, floor(b/2)) + random(a, b - floor(b/2))

Edit (on accept):

The two answers I considered are both of high quality. This answer considers RNGs on a per-digit or per-bit basis. The accepted answers consider RNGs numerically, without considering digits or bits. In both cases, the comments are important to read.

I've also posted a follow-up question Maintain Uniform Distribution across Subranges.

3 summary on accept
source | link

Say I have a random number generator that generates a number within [0, RAND_MAX], and RAND_MAX < UINT_MAX.

How do I generate a random number within [0, i] such that i>RAND_MAX and i<UINT_MAX, while maintaining an even distribution, and without exceeding UINT_MAX in any calculations?

The first attempt is to split the range into n equal parts such that i mod n == 0 by finding the least denominator of i (using one of the integer factorization sieve algorithms). Each sublist has equal distribution, any can be picked at random. This fails if i is prime:

0 1 2 3 4 5 6
|___| |_____|

The second attempt is to split the range into two parts a = [0, floor(i/2)] and b = [floor(i/2)+1, i], and then to calculate the distribution as the ratio of the length of the two sub-ranges:

g = gcd(length(a), length(b))
if random(0, length(a)/g + length(b)/g - 1) >= length(a)/g
    random(0, floor(i/2))
else
    random(floor(i/2)+1, i)

Given the following range, the right sub-range is selected twice as often as the left sub-range:

0 1 2 3 4 5
|_| |_____|

Unfortunately the first call to random() may recurse forever if gcd() is ever one.

The final attempt is to correct the distribution skew introduced by splitting a range of odd length:

if random(1)
    if random(1)
        random(0, floor(i/2))
    else
        random(floor(i/2) + 1, i)
else
    if random(1)
        random(0, floor(i/2) - 1)
    else
        random(floor(i/2), i)

Which probably doesn't work.

Edit:

For anyone with similar question, the sum of two uniform variables follows a triangular distribution (see Irwin-Hall Distribution). This is invalid:

# triangular distribution:
random(a, floor(b/2)) + random(a, b - floor(b/2))

Edit (on accept):

The two answers I considered are both of high quality. This answer considers RNGs on a per-digit or per-bit basis. The accepted answers consider RNGs numerically, without considering digits or bits. In both cases, the comments are important to read.

I've also posted a follow-up question Maintain Uniform Distribution across Subranges.

Say I have a random number generator that generates a number within [0, RAND_MAX], and RAND_MAX < UINT_MAX.

How do I generate a random number within [0, i] such that i>RAND_MAX and i<UINT_MAX, while maintaining an even distribution, and without exceeding UINT_MAX in any calculations?

The first attempt is to split the range into n equal parts such that i mod n == 0 by finding the least denominator of i (using one of the integer factorization sieve algorithms). Each sublist has equal distribution, any can be picked at random. This fails if i is prime:

0 1 2 3 4 5 6
|___| |_____|

The second attempt is to split the range into two parts a = [0, floor(i/2)] and b = [floor(i/2)+1, i], and then to calculate the distribution as the ratio of the length of the two sub-ranges:

g = gcd(length(a), length(b))
if random(0, length(a)/g + length(b)/g - 1) >= length(a)/g
    random(0, floor(i/2))
else
    random(floor(i/2)+1, i)

Given the following range, the right sub-range is selected twice as often as the left sub-range:

0 1 2 3 4 5
|_| |_____|

Unfortunately the first call to random() may recurse forever if gcd() is ever one.

The final attempt is to correct the distribution skew introduced by splitting a range of odd length:

if random(1)
    if random(1)
        random(0, floor(i/2))
    else
        random(floor(i/2) + 1, i)
else
    if random(1)
        random(0, floor(i/2) - 1)
    else
        random(floor(i/2), i)

Which probably doesn't work.

Edit:

For anyone with similar question, the sum of two uniform variables follows a triangular distribution (see Irwin-Hall Distribution). This is invalid:

# triangular distribution:
random(a, floor(b/2)) + random(a, b - floor(b/2))

Say I have a random number generator that generates a number within [0, RAND_MAX], and RAND_MAX < UINT_MAX.

How do I generate a random number within [0, i] such that i>RAND_MAX and i<UINT_MAX, while maintaining an even distribution, and without exceeding UINT_MAX in any calculations?

The first attempt is to split the range into n equal parts such that i mod n == 0 by finding the least denominator of i (using one of the integer factorization sieve algorithms). Each sublist has equal distribution, any can be picked at random. This fails if i is prime:

0 1 2 3 4 5 6
|___| |_____|

The second attempt is to split the range into two parts a = [0, floor(i/2)] and b = [floor(i/2)+1, i], and then to calculate the distribution as the ratio of the length of the two sub-ranges:

g = gcd(length(a), length(b))
if random(0, length(a)/g + length(b)/g - 1) >= length(a)/g
    random(0, floor(i/2))
else
    random(floor(i/2)+1, i)

Given the following range, the right sub-range is selected twice as often as the left sub-range:

0 1 2 3 4 5
|_| |_____|

Unfortunately the first call to random() may recurse forever if gcd() is ever one.

The final attempt is to correct the distribution skew introduced by splitting a range of odd length:

if random(1)
    if random(1)
        random(0, floor(i/2))
    else
        random(floor(i/2) + 1, i)
else
    if random(1)
        random(0, floor(i/2) - 1)
    else
        random(floor(i/2), i)

Which probably doesn't work.

Edit:

For anyone with similar question, the sum of two uniform variables follows a triangular distribution (see Irwin-Hall Distribution). This is invalid:

# triangular distribution:
random(a, floor(b/2)) + random(a, b - floor(b/2))

Edit (on accept):

The two answers I considered are both of high quality. This answer considers RNGs on a per-digit or per-bit basis. The accepted answers consider RNGs numerically, without considering digits or bits. In both cases, the comments are important to read.

I've also posted a follow-up question Maintain Uniform Distribution across Subranges.

    Tweeted twitter.com/StackSciComp/status/679700078580396033
2 improving the quality
source | link

Say I have a random number generator that generates a number within [0, RAND_MAX], and RAND_MAX < UINT_MAX.

How do I generate a random number within [0, i] such that i>RAND_MAX and i<UINT_MAX, while maintaining an even distribution, and without exceeding UINT_MAX in any calculations?

The first attempt is to split the range into n equal parts such that i mod n == 0 by finding the least denominator of i (using one of the integer factorization sieve algorithms). Each sublist has equal distribution, any can be picked at random. This fails if i is prime:

0 1 2 3 4 5 6
|___| |_____|

The second attempt is to split the range into two parts a = [0, floor(i/2)] and b = [floor(i/2)+1, i], and then to calculate the distribution as the ratio of the length of the two sub-ranges:

g = gcd(length(a), length(b))
if random(0, length(a)/g + length(b)/g - 1) >= length(a)/g
    random(0, floor(i/2))
else
    random(floor(i/2)+1, i)

Given the following range, the right sub-range is selected twice as often as the left sub-range:

0 1 2 3 4 5
|_| |_____|

Unfortunately the first call to random() may recurse forever if gcd() is ever one.

The final attempt is to correct the distribution skew introduced by splitting a range of odd length:

if random(1)
    if random(1)
        random(0, floor(i/2))
    else
        random(floor(i/2) + 1, i)
else
    if random(1)
        random(0, floor(i/2) - 1)
    else
        random(floor(i/2), i)

Which probably doesn't work.

Edit:

For anyone with similar question, the sum of two uniform variables follows a triangular distribution (see Irwin-Hall Distribution). This is invalid:

# triangular distribution:
random(a, floor(b/2)) + random(a, b - floor(b/2))

Say I have a random number generator that generates a number within [0, RAND_MAX], and RAND_MAX < UINT_MAX.

How do I generate a random number within [0, i] such that i>RAND_MAX and i<UINT_MAX, while maintaining an even distribution, and without exceeding UINT_MAX in any calculations?

The first attempt is to split the range into n equal parts such that i mod n == 0 by finding the least denominator of i (using one of the integer factorization sieve algorithms). Each sublist has equal distribution, any can be picked at random. This fails if i is prime:

0 1 2 3 4 5 6
|___| |_____|

The second attempt is to split the range into two parts a = [0, floor(i/2)] and b = [floor(i/2)+1, i], and then to calculate the distribution as the ratio of the length of the two sub-ranges:

g = gcd(length(a), length(b))
if random(0, length(a)/g + length(b)/g - 1) >= length(a)/g
    random(0, floor(i/2))
else
    random(floor(i/2)+1, i)

Given the following range, the right sub-range is selected twice as often as the left sub-range:

0 1 2 3 4 5
|_| |_____|

Unfortunately the first call to random() may recurse forever if gcd() is ever one.

The final attempt is to correct the distribution skew introduced by splitting a range of odd length:

if random(1)
    if random(1)
        random(0, floor(i/2))
    else
        random(floor(i/2) + 1, i)
else
    if random(1)
        random(0, floor(i/2) - 1)
    else
        random(floor(i/2), i)

Which probably doesn't work.

Say I have a random number generator that generates a number within [0, RAND_MAX], and RAND_MAX < UINT_MAX.

How do I generate a random number within [0, i] such that i>RAND_MAX and i<UINT_MAX, while maintaining an even distribution, and without exceeding UINT_MAX in any calculations?

The first attempt is to split the range into n equal parts such that i mod n == 0 by finding the least denominator of i (using one of the integer factorization sieve algorithms). Each sublist has equal distribution, any can be picked at random. This fails if i is prime:

0 1 2 3 4 5 6
|___| |_____|

The second attempt is to split the range into two parts a = [0, floor(i/2)] and b = [floor(i/2)+1, i], and then to calculate the distribution as the ratio of the length of the two sub-ranges:

g = gcd(length(a), length(b))
if random(0, length(a)/g + length(b)/g - 1) >= length(a)/g
    random(0, floor(i/2))
else
    random(floor(i/2)+1, i)

Given the following range, the right sub-range is selected twice as often as the left sub-range:

0 1 2 3 4 5
|_| |_____|

Unfortunately the first call to random() may recurse forever if gcd() is ever one.

The final attempt is to correct the distribution skew introduced by splitting a range of odd length:

if random(1)
    if random(1)
        random(0, floor(i/2))
    else
        random(floor(i/2) + 1, i)
else
    if random(1)
        random(0, floor(i/2) - 1)
    else
        random(floor(i/2), i)

Which probably doesn't work.

Edit:

For anyone with similar question, the sum of two uniform variables follows a triangular distribution (see Irwin-Hall Distribution). This is invalid:

# triangular distribution:
random(a, floor(b/2)) + random(a, b - floor(b/2))
1
source | link