Expand a random range from 1–5 to 1–7

Question

Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.

Answer 1

/*
  Entropy of 7 calls to rand5() is ceil(log2(5)*7)
  Entropy of 5 calls to rand7() is ceil(log2(7)*5)
  Create an entropy pool of max(ceil(log2(5)*7),ceil(log2(7)*5))
   - this is about 15 bits so int is large enough even on 16-bit systems.
  Fill using rand5, drain using rand7.

  Calculation is simpler if we use the ranges 0..4 and 0..6
  so +/-1 offset is inserted at point of call to rand5
  and at point of returning result of rand7.

  cc -o rand7 -DTEST -Wall rand7.c
 */

extern int rand5(void);
// returns 1..5 with hopefully uniform distribution

int rand7(void) {
  // return 1..7 with equally random distribution.
  // Minimum calls to rand5().
  int i;
  static int entropy_remaining = 0;
  static unsigned int entropy;
  if (entropy_remaining == 0) {  // refill entropy pool.
    entropy = 0U; entropy_remaining = 5;
    for (i = 0; i < 7; i++)
      entropy = entropy * 5U + (unsigned int)rand5()-1;
  }
  i = (int)(entropy % 7U); entropy /= 7U;
  entropy_remaining -= 1;
  return i+1;
}

Answer 2

Python: There's a simple two line answer that uses a combination of spatial algebra and modulus. This is not intuitive. My explanation of it is confusing, but is correct.

Knowing that 5*7=35 and 7/5 = 1 remainder 2. How to guarantee that sum of remainders is always 0? 5*[7/5 = 1 remainder 2] --> 35/5 = 7 remainder 0

Imagine we had a ribbon that was wrapped around a pole with a perimeter=7. The ribbon would need to be 35 units to wrap evenly. Select 7 random ribbon pieces len=[1...5]. The effective length ignoring the wrap around is the same as this method of converting rand5() into rand7().

import numpy as np
import pandas as pd
# display is a notebook function FYI
def rand5(): ## random uniform int [1...5]
    return np.random.randint(1,6)

n_trials = 1000
samples = [rand5() for _ in range(n_trials)]

display(pd.Series(samples).value_counts(normalize=True))
# 4    0.2042
# 5    0.2041
# 2    0.2010
# 1    0.1981
# 3    0.1926
# dtype: float64
    
def rand7(): # magic algebra
    x = sum(rand5() for _ in range(7))
    return x%7 + 1

samples = [rand7() for _ in range(n_trials)]

display(pd.Series(samples).value_counts(normalize=False))
# 6    1475
# 2    1475
# 3    1456
# 1    1423
# 7    1419
# 4    1393
# 5    1359
# dtype: int64
    
df = pd.DataFrame([
    pd.Series([rand7() for _ in range(n_trials)]).value_counts(normalize=True)
    for _ in range(1000)
])
df.describe()
#      1    2   3   4   5   6   7
# count 1000.000000 1000.000000 1000.000000 1000.000000 1000.000000 1000.000000 1000.000000
# mean  0.142885    0.142928    0.142523    0.142266    0.142704    0.143048    0.143646
# std   0.010807    0.011526    0.010966    0.011223    0.011052    0.010983    0.011153
# min   0.112000    0.108000    0.101000    0.110000    0.100000    0.109000    0.110000
# 25%   0.135000    0.135000    0.135000    0.135000    0.135000    0.135000    0.136000
# 50%   0.143000    0.142000    0.143000    0.142000    0.143000    0.142000    0.143000
# 75%   0.151000    0.151000    0.150000    0.150000    0.150000    0.150000    0.151000
# max   0.174000    0.181000    0.175000    0.178000    0.189000    0.176000    0.179000

Answer 3

For the range [1, 5] to [1, 7], this is equivalent to rolling a 7-sided die with a 5-sided one.

However, this can't be done without "wasting" randomness (or running forever in the worst case), since all the prime factors of 7 (namely 7) don't divide 5. Thus, the best that can be done is to use rejection sampling to get arbitrarily close to no "waste" of randomness (such as by batching multiple rolls of the 5-sided die until 5^n is "close enough" to a power of 7). Solutions to this problem were already given in other answers.

More generally, an algorithm to roll a k-sided die with a p-sided die will inevitably "waste" randomness (and run forever in the worst case) unless "every prime number dividing k also divides p", according to Lemma 3 in "Simulating a dice with a dice" by B. Kloeckner. For example, take the much more practical case that p is a power of 2 and k is arbitrary. In this case, this "waste" and indefinite running time are inevitable unless k is also a power of 2.

Answer 4

int rand7() {
    int value = rand5()
              + rand5() * 2
              + rand5() * 3
              + rand5() * 4
              + rand5() * 5
              + rand5() * 6;
    return value%7;
}

Unlike the chosen solution, the algorithm will run in constant time. It does however make 2 more calls to rand5 than the average run time of the chosen solution.

Note that this generator is not perfect (the number 0 has 0.0064% more chance than any other number), but for most practical purposes the guarantee of constant time probably outweighs this inaccuracy.

Explanation

This solution is derived from the fact that the number 15,624 is divisible by 7 and thus if we can randomly and uniformly generate numbers from 0 to 15,624 and then take mod 7 we can get a near-uniform rand7 generator. Numbers from 0 to 15,624 can be uniformly generated by rolling rand5 6 times and using them to form the digits of a base 5 number as follows:

rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5

Properties of mod 7 however allow us to simplify the equation a bit:

5^5 = 3 mod 7
5^4 = 2 mod 7
5^3 = 6 mod 7
5^2 = 4 mod 7
5^1 = 5 mod 7

So

rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5

becomes

rand5 * 3 + rand5 * 2 + rand5 * 6 + rand5 * 4 + rand5 * 5 + rand5

Theory

The number 15,624 was not chosen randomly, but can be discovered using fermat's little theorem, which states that if p is a prime number then

a^(p-1) = 1 mod p

So this gives us,

(5^6)-1 = 0 mod 7

(5^6)-1 is equal to

4 * 5^5 + 4 * 5^4 + 4 * 5^3 + 4 * 5^2 + 4 * 5 + 4

This is a number in base 5 form and thus we can see that this method can be used to go from any random number generator to any other random number generator. Though a small bias towards 0 is always introduced when using the exponent p-1.

To generalize this approach and to be more accurate we can have a function like this:

def getRandomconverted(frm, to):
    s = 0
    for i in range(to):
        s += getRandomUniform(frm)*frm**i
    mx = 0
    for i in range(to):
        mx = (to-1)*frm**i 
    mx = int(mx/to)*to # maximum value till which we can take mod
    if s < mx:
        return s%to
    else:
        return getRandomconverted(frm, to)

Answer 5

Here is a solution that tries to minimize the number of calls to rand5() while keeping the implementation simple and efficient; in particular, it does not require arbitrary large integers unlike Adam Rosenfield’s second answer. It exploits the fact that 23/19 = 1.21052... is a good rational approximation to log(7)/log(5) = 1.20906..., thus we can generate 19 random elements of {1,...,7} out of 23 random elements of {1,...,5} by rejection sampling with only a small rejection probability. On average, the algorithm below takes about 1.266 calls to rand5() for each call to rand7(). If the distribution of rand5() is uniform, so is rand7().

uint_fast64_t pool;

int capacity = 0;

void new_batch (void)
{
  uint_fast64_t r;
  int i;

  do {
    r = 0;
    for (i = 0; i < 23; i++)
      r = 5 * r + (rand5() - 1);
  } while (r >= 11398895185373143ULL);  /* 7**19, a bit less than 5**23 */

  pool = r;
  capacity = 19;
}

int rand7 (void)
{
  int r;

  if (capacity == 0)
    new_batch();

  r = pool % 7;
  pool /= 7;
  capacity--;

  return r + 1;
}

Answer 6

// returns random number between 0-5 with equal probability
function rand5() {
  return Math.floor(Math.random() * 6);
}

// returns random number between 0-7 with equal probability
function rand7() {
  if(rand5() % 2 == 0 && rand5() % 2 == 0) { 
    return 6 + rand5() % 2;
  } else {
    return rand5();
  }
}

console.log(rand7());

Answer 7

Came here from a link from expanding a float range. This one is more fun. Instead of how I got to the conclusion, it occurred to me that for a given random integer generating function f with "base" b (4 in this case,i'll tell why), it can be expanded like below:

(b^0 * f() + b^1 * f() + b^2 * f() .... b^p * f()) / (b^(p+1) - 1) * (b-1)

This will convert a random generator to a FLOAT generator. I will define 2 parameters here the b and the p. Although the "base" here is 4, b can in fact be anything, it can also be an irrational number etc. p, i call precision is a degree of how well grained you want your float generator to be. Think of this as the number of calls made to rand5 for each call of rand7.

But I realized if you set b to base+1 (which is 4+1 = 5 in this case), it's a sweet spot and you'll get a uniform distribution. First get rid of this 1-5 generator, it is in truth rand4() + 1:

function rand4(){
    return Math.random() * 5 | 0;
}

To get there, you can substitute rand4 with rand5()-1

Next is to convert rand4 from an integer generator to a float generator

function toFloat(f,b,p){
    b = b || 2;
    p = p || 3;
    return (Array.apply(null,Array(p))
    .map(function(d,i){return f()})
    .map(function(d,i){return Math.pow(b,i)*d})
    .reduce(function(ac,d,i){return ac += d;}))
    /
    (
        (Math.pow(b,p) - 1)
        /(b-1)
    )
}

This will apply the first function I wrote to a given rand function. Try it:

toFloat(rand4) //1.4285714285714286 base = 2, precision = 3
toFloat(rand4,3,4) //0.75 base = 3, precision = 4
toFloat(rand4,4,5) //3.7507331378299122 base = 4, precision = 5
toFloat(rand4,5,6) //0.2012288786482335 base = 5, precision =6
...

Now you can convert this float range (0-4 INCLUSIVE) to any other float range and then downgrade it to be an integer. Here our base is 4 because we are dealing with rand4, therefore a value b=5 will give you a uniform distribution. As the b grows past 4, you will start introducing periodic gaps in the distribution. I tested for b values ranging from 2 to 8 with 3000 points each and compared to native Math.random of javascript, looks to me even better than the native one itself:

http://jsfiddle.net/ibowankenobi/r57v432t/

For the above link, click on the "bin" button on the top side of the distributions to decrease the binning size. The last graph is native Math.random, the 4th one where d=5 is uniform.

After you get your float range either multiply with 7 and throw the decimal part or multiply with 7, subtract 0.5 and round:

((toFloat(rand4,5,6)/4 * 7) | 0) + 1   ---> occasionally you'll get 8 with 1/4^6 probability.
Math.round((toFloat(rand4,5,6)/4 * 7) - 0.5) + 1 --> between 1 and 7

Answer 8

This is the answer I came up with but these complicated answers are making me think this is completely off/ :))

import random

def rand5():
    return float(random.randint(0,5))

def rand7():
    random_val = rand5()
    return float(random.randint((random_val-random_val),7))

print rand7()

Answer 9

I think I have four answers, two giving exact solutions like that of @Adam Rosenfield but without the infinite loop problem, and other two with almost perfect solution but faster implementation than first one.

The best exact solution requires 7 calls to rand5, but lets proceed in order to understand.

Method 1 - Exact

Strength of Adam's answer is that it gives a perfect uniform distribution, and there is very high probability (21/25) that only two calls to rand5() will be needed. However, worst case is infinite loop.

The first solution below also gives a perfect uniform distribution, but requires a total of 42 calls to rand5. No infinite loops.

Here is an R implementation:

rand5 <- function() sample(1:5,1)

rand7 <- function()  (sum(sapply(0:6, function(i) i + rand5() + rand5()*2 + rand5()*3 + rand5()*4 + rand5()*5 + rand5()*6)) %% 7) + 1

For people not familiar with R, here is a simplified version:

rand7 = function(){
  r = 0 
  for(i in 0:6){
    r = r + i + rand5() + rand5()*2 + rand5()*3 + rand5()*4 + rand5()*5 + rand5()*6
  }
  return r %% 7 + 1
}

The distribution of rand5 will be preserved. If we do the math, each of the 7 iterations of the loop has 5^6 possible combinations, thus total number of possible combinations are (7 * 5^6) %% 7 = 0. Thus we can divide the random numbers generated in equal groups of 7. See method two for more discussion on this.

Here are all the possible combinations:

table(apply(expand.grid(c(outer(1:5,0:6,"+")),(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6),1,sum) %% 7 + 1)

    1     2     3     4     5     6     7 
15625 15625 15625 15625 15625 15625 15625 

I think it's straight forward to show that Adam's method will run much much faster. The probability that there are 42 or more calls to rand5 in Adam's solution is very small ((4/25)^21 ~ 10^(-17)).

Method 2 - Not Exact

Now the second method, which is almost uniform, but requires 6 calls to rand5:

rand7 <- function() (sum(sapply(1:6,function(i) i*rand5())) %% 7) + 1

Here is a simplified version:

rand7 = function(){
  r = 0 
  for(i in 1:6){
    r = r + i*rand5()
  }
  return r %% 7 + 1
}

This is essentially one iteration of method 1. If we generate all possible combinations, here is resulting counts:

table(apply(expand.grid(1:5,(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6),1,sum) %% 7 + 1)

   1    2    3    4    5    6    7 
2233 2232 2232 2232 2232 2232 2232

One number will appear once more in 5^6 = 15625 trials.

Now, in Method 1, by adding 1 to 6, we move the number 2233 to each of the successive point. Thus the total number of combinations will match up. This works because 5^6 %% 7 = 1, and then we do 7 appropriate variations, so (7 * 5^6 %% 7 = 0).

Method 3 - Exact

If the argument of method 1 and 2 is understood, method 3 follows, and requires only 7 calls to rand5. At this point, I feel this is the minimum number of calls needed for an exact solution.

Here is an R implementation:

rand5 <- function() sample(1:5,1)

rand7 <- function()  (sum(sapply(1:7, function(i) i * rand5())) %% 7) + 1

For people not familiar with R, here is a simplified version:

rand7 = function(){
  r = 0 
  for(i in 1:7){
    r = r + i * rand5()
  }
  return r %% 7 + 1
}

The distribution of rand5 will be preserved. If we do the math, each of the 7 iterations of the loop has 5 possible outcomes, thus total number of possible combinations are (7 * 5) %% 7 = 0. Thus we can divide the random numbers generated in equal groups of 7. See method one and two for more discussion on this.

Here are all the possible combinations:

table(apply(expand.grid(0:6,(1:5)),1,sum) %% 7 + 1)

1 2 3 4 5 6 7  
5 5 5 5 5 5 5 

I think it's straight forward to show that Adam's method will still run faster. The probability that there are 7 or more calls to rand5 in Adam's solution is still small ((4/25)^3 ~ 0.004).

Method 4 - Not Exact

This is a minor variation of the the second method. It is almost uniform, but requires 7 calls to rand5, that is one additional to method 2:

rand7 <- function() (rand5() + sum(sapply(1:6,function(i) i*rand5())) %% 7) + 1

Here is a simplified version:

rand7 = function(){
  r = 0 
  for(i in 1:6){
    r = r + i*rand5()
  }
  return (r+rand5()) %% 7 + 1
}

If we generate all possible combinations, here is resulting counts:

table(apply(expand.grid(1:5,(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6,1:5),1,sum) %% 7 + 1)

    1     2     3     4     5     6     7 
11160 11161 11161 11161 11161 11161 11160

Two numbers will appear once less in 5^7 = 78125 trials. For most purposes, I can live with that.

Answer 10

1. What is a simple solution? (rand5() + rand5()) % 7 + 1
   
2. What is an effective solution to reduce memory usage or run on a slower CPU? Yes, this is effective as it calls rand5() only twice and have O(1) space complexity
   

Consider rand5() gives out random numbers from 1 to 5(inclusive).
(1 + 1) % 7 + 1 = 3
(1 + 2) % 7 + 1 = 4
(1 + 3) % 7 + 1 = 5
(1 + 4) % 7 + 1 = 6
(1 + 5) % 7 + 1 = 7

(2 + 1) % 7 + 1 = 4
(2 + 2) % 7 + 1 = 5
(2 + 3) % 7 + 1 = 6
(2 + 4) % 7 + 1 = 7
(2 + 5) % 7 + 1 = 1
...

(5 + 1) % 7 + 1 = 7
(5 + 2) % 7 + 1 = 1
(5 + 3) % 7 + 1 = 2
(5 + 4) % 7 + 1 = 3
(5 + 5) % 7 + 1 = 4
...

and so on

Answer 11

This algorithm reduces the number of calls of rand5 to the theoretical minimum of 7/5. Calling it 7 times by produce the next 5 rand7 numbers.

There are no rejection of any random bit, and there are NO possibility to keep waiting the result for always.

#!/usr/bin/env ruby

# random integer from 1 to 5
def rand5
    STDERR.putc '.'
    1 + rand( 5 )
end

@bucket = 0
@bucket_size = 0

# random integer from 1 to 7
def rand7
    if @bucket_size == 0
        @bucket = 7.times.collect{ |d| rand5 * 5**d }.reduce( &:+ )
        @bucket_size = 5
    end

    next_rand7 = @bucket%7 + 1

    @bucket      /= 7
    @bucket_size -= 1

    return next_rand7
end

35.times.each{ putc rand7.to_s }

Answer 12

Another answer which appears to have not been covered here:

int rand7() {
  int r = 7 / 2;
  for (int i = 0; i < 28; i++)
    r = ((rand5() - 1) * 7 + r) / 5;
  return r + 1;
}

On every iteration r is a random value between 0 and 6 inclusive. This is appended (base 7) to a random value between 0 and 4 inclusive, and the result is divided by 5, giving a new random value in the range of 0 to 6 inclusive. r starts with a substantial bias (r = 3 is very biased!) but each iteration divides that bias by 5.

This method is not perfectly uniform; however, the bias is vanishingly small. Something in the order of 1/(2**64). What's important about this approach is that it has constant execution time (assuming rand5() also has constant execution time). No theoretical concerns that an unlucky call could iterate forever picking bad values.

---

Also, a sarcastic answer for good measure (deliberately or not, it has been covered):

1-5 is already within the range 1-7, therefore the following is a valid implementation:

int rand7() {
  return rand5();
}

Question did not ask for uniform distribution.

Answer 13

Similar to Martin's answer, but resorts to throwing entropy away much less frequently:

int rand7(void) {
  static int m = 1;
  static int r = 0;

  for (;;) {
    while (m <= INT_MAX / 5) {
      r = r + m * (rand5() - 1);
      m = m * 5;
    }
    int q = m / 7;
    if (r < q * 7) {
      int i = r % 7;
      r = r / 7;
      m = q;
      return i + 1;
    }
    r = r - q * 7;
    m = m - q * 7;
  }
}

Here we build up a random value between 0 and m-1, and try to maximise m by adding as much state as will fit without overflow (INT_MAX being the largest value that will fit in an int in C, or you can replace that with any large value that makes sense in your language and architecture).

Then; if r falls within the largest possible interval evenly divisible by 7 then it contains a viable result and we can divide that interval by 7 and take the remainder as our result and return the rest of the value to our entropy pool. Otherwise r is in the other interval which doesn't divide evenly and we have to discard and restart our entropy pool from that ill-fitting interval.

Compared with the popular answers in here, it calls rand5() about half as often on average.

The divides can be factored out into trivial bit-twiddles and LUTs for performance.

Answer 14

def rand5():
    return random.randint(1,5)    #return random integers from 1 to 5

def rand7():
    rand = rand5()+rand5()-1
    if rand > 7:                  #if numbers > 7, call rand7() again
        return rand7()
    print rand%7 + 1

I guess this will the easiest solution but everywhere people have suggested 5*rand5() + rand5() - 5 like in http://www.geeksforgeeks.org/generate-integer-from-1-to-7-with-equal-probability/. Can someone explain what is wrong with rand5()+rand5()-1

Answer 15

the main conception of this problem is about normal distribution, here provided a simple and recursive solution to this problem

presume we already have rand5() in our scope:

def rand7():
    # twoway = 0 or 1 in the same probability
    twoway = None
    while not twoway in (1, 2):
        twoway = rand5()
    twoway -= 1

    ans = rand5() + twoway * 5

    return ans if ans in range(1,8) else rand7()

Explanation

We can divide this program into 2 parts:

1. looping rand5() until we found 1 or 2, that means we have 1/2 probability to have 1 or 2 in the variable twoway
2. composite ans by rand5() + twoway * 5, this is exactly the result of rand10(), if this did not match our need (1~7), then we run rand7 again.

P.S. we cannot directly run a while loop in the second part due to each probability of twoway need to be individual.

But there is a trade-off, because of the while loop in the first section and the recursion in the return statement, this function doesn't guarantee the execution time, it is actually not effective.

Result

I've made a simple test for observing the distribution to my answer.

result = [ rand7() for x in xrange(777777) ]

ans = {
    1: 0,
    2: 0,
    3: 0,
    4: 0,
    5: 0,
    6: 0,
    7: 0,
}

for i in result:
    ans[i] += 1

print ans

It gave

{1: 111170, 2: 110693, 3: 110651, 4: 111260, 5: 111197, 6: 111502, 7: 111304}

Therefore we could know this answer is in a normal distribution.

Simplified Answer

If you don't care about the execution time of this function, here's a simplified answer based on the above answer I gave:

def rand7():
    ans = rand5() + (rand5()-1) * 5
    return ans if ans < 8 else rand7()

This augments the probability of value which is greater than 8 but probably will be the shortest answer to this problem.

Answer 16

Here's mine, this attempts to recreate Math.random() from multiple rand5() function calls, reconstructing a unit interval (the output range of Math.random()) by re-constructing it with "weighted fractions"(?). Then using this random unit interval to produce a random integer between 1 and 7:

function rand5(){
  return Math.floor(Math.random()*5)+1;
}
function rand7(){
  var uiRandom=0;
  var div=1;
  for(var i=0; i<7; i++){
    div*=5;
    var term=(rand5()-1)/div;
    uiRandom+=term;
  }
  //return uiRandom;
  return Math.floor(uiRandom*7)+1; 
}

To paraphrase: We take a random integers between 0-4 (just rand5()-1) and multiply each result with 1/5, 1/25, 1/125, ... and then sum them together. It's similar to how binary weighted fractions work; I suppose instead, we'll call it a quinary (base-5) weighted fraction: Producing a number from 0 -- 0.999999 as a series of (1/5)^n terms.

Modifying the function to take any input/output random integer range should be trivial. And the code above can be optimized when rewritten as a closure.

---

Alternatively, we can also do this:

function rand5(){
  return Math.floor(Math.random()*5)+1;
}
function rand7(){
  var buffer=[];
  var div=1;
  for (var i=0; i<7; i++){
    buffer.push((rand5()-1).toString(5));
    div*=5;
  }
  var n=parseInt(buffer.join(""),5);
  var uiRandom=n/div;
  //return uiRandom;
  return Math.floor(uiRandom*7)+1; 
}

Instead of fiddling with constructing a quinary (base-5) weighted fractions, we'll actually make a quinary number and turn it into a fraction (0--0.9999... as before), then compute our random 1--7 digit from there.

Results for above (code snippet #2: 3 runs of 100,000 calls each):

1: 14263; 2: 14414; 3: 14249; 4: 14109; 5: 14217; 6: 14361; 7: 14387

1: 14205; 2: 14394; 3: 14238; 4: 14187; 5: 14384; 6: 14224; 7: 14368

1: 14425; 2: 14236; 3: 14334; 4: 14232; 5: 14160; 6: 14320; 7: 14293

Answer 17

First, I move ramdom5() on the 1 point 6 times, to get 7 random numbers. Second, I add 7 numbers to obtain common sum. Third, I get remainder of the division at 7. Last, I add 1 to get results from 1 till 7. This method gives an equal probability of getting numbers in the range from 1 to 7, with the exception of 1. 1 has a slightly higher probability.

public int random7(){
    Random random = new Random();
    //function (1 + random.nextInt(5)) is given
    int random1_5 = 1 + random.nextInt(5); // 1,2,3,4,5
    int random2_6 = 2 + random.nextInt(5); // 2,3,4,5,6
    int random3_7 = 3 + random.nextInt(5); // 3,4,5,6,7
    int random4_8 = 4 + random.nextInt(5); // 4,5,6,7,8
    int random5_9 = 5 + random.nextInt(5); // 5,6,7,8,9
    int random6_10 = 6 + random.nextInt(5); //6,7,8,9,10
    int random7_11 = 7 + random.nextInt(5); //7,8,9,10,11

    //sumOfRandoms is between 28 and 56
    int sumOfRandoms = random1_5 + random2_6 + random3_7 + 
                       random4_8 + random5_9 + random6_10 + random7_11;
    //result is number between 0 and 6, and
    //equals 0 if sumOfRandoms = 28 or 35 or 42 or 49 or 56 , 5 options
    //equals 1 if sumOfRandoms = 29 or 36 or 43 or 50, 4 options
    //equals 2 if sumOfRandoms = 30 or 37 or 44 or 51, 4 options
    //equals 3 if sumOfRandoms = 31 or 38 or 45 or 52, 4 options
    //equals 4 if sumOfRandoms = 32 or 39 or 46 or 53, 4 options
    //equals 5 if sumOfRandoms = 33 or 40 or 47 or 54, 4 options
    //equals 6 if sumOfRandoms = 34 or 41 or 48 or 55, 4 options
    //It means that the probabilities of getting numbers between 0 and 6 are almost equal.
    int result = sumOfRandoms % 7;
    //we should add 1 to move the interval [0,6] to the interval [1,7]
    return 1 + result;
}

Answer 18

Would be cool if someone could give me feedback on this one, I used the JUNIT without assert Pattern because it's easy and fast to get it running in Eclipse, I could also have just defined a main method. By the way, I am assuming rand5 gives values 0-4, adding 1 would make it 1-5, same with rand7... So the discussion should be on the solution, it's distribution, not on wether it goes from 0-4 or 1-5...

package random;

import java.util.Random;

import org.junit.Test;

public class RandomTest {


    @Test
    public void testName() throws Exception {
        long times = 100000000;
        int indexes[] = new int[7];
        for(int i = 0; i < times; i++) {
            int rand7 = rand7();
            indexes[rand7]++;
        }

        for(int i = 0; i < 7; i++)
            System.out.println("Value " + i + ": " + indexes[i]);
    }


    public int rand7() {
        return (rand5() + rand5() + rand5() + rand5() + rand5() + rand5() + rand5()) % 7;
    }


    public int rand5() {
        return new Random().nextInt(5);
    }


}

When I run it, I get this result:

Value 0: 14308087
Value 1: 14298303
Value 2: 14279731
Value 3: 14262533
Value 4: 14269749
Value 5: 14277560
Value 6: 14304037

This seems like a very fair distribution, doesn't it?

If I add rand5() less or more times (where the amount of times is not divisible by 7), the distribution clearly shows offsets. For instance, adding rand5() 3 times:

Value 0: 15199685
Value 1: 14402429
Value 2: 12795649
Value 3: 12796957
Value 4: 14402252
Value 5: 15202778
Value 6: 15200250

So, this would lead to the following:

public int rand(int range) {
    int randomValue = 0;
    for(int i = 0; i < range; i++) {
        randomValue += rand5();
    }
    return randomValue % range;

}

And then, I could go further:

public static final int ORIGN_RANGE = 5;
public static final int DEST_RANGE  = 7;

@Test
public void testName() throws Exception {
    long times = 100000000;
    int indexes[] = new int[DEST_RANGE];
    for(int i = 0; i < times; i++) {
        int rand7 = convertRand(DEST_RANGE, ORIGN_RANGE);
        indexes[rand7]++;
    }

    for(int i = 0; i < DEST_RANGE; i++)
        System.out.println("Value " + i + ": " + indexes[i]);
}


public int convertRand(int destRange, int originRange) {
    int randomValue = 0;
    for(int i = 0; i < destRange; i++) {
        randomValue += rand(originRange);
    }
    return randomValue % destRange;

}


public int rand(int range) {
    return new Random().nextInt(range);
}

I tried this replacing the destRange and originRange with various values (even 7 for ORIGIN and 13 for DEST), and I get this distribution:

Value 0: 7713763
Value 1: 7706552
Value 2: 7694697
Value 3: 7695319
Value 4: 7688617
Value 5: 7681691
Value 6: 7674798
Value 7: 7680348
Value 8: 7685286
Value 9: 7683943
Value 10: 7690283
Value 11: 7699142
Value 12: 7705561

What I can conclude from here is that you can change any random to anyother by suming the origin random "destination" times. This will get a kind of gaussian distribution (being the middle values more likely, and the edge values more uncommon). However, the modulus of destination seems to distribute itself evenly across this gaussian distribution... It would be great to have feedback from a mathematician...

What is cool is that the cost is 100% predictable and constant, whereas other solutions cause a small probability of infinite loop...

Answer 19

The simple solution has been well covered: take two random5 samples for one random7 result and do it over if the result is outside the range that generates a uniform distribution. If your goal is to reduce the number of calls to random5 this is extremely wasteful - the average number of calls to random5 for each random7 output is 2.38 rather than 2 due to the number of thrown away samples.

You can do better by using more random5 inputs to generate more than one random7 output at a time. For results calculated with a 31-bit integer, the optimum comes when using 12 calls to random5 to generate 9 random7 outputs, taking an average of 1.34 calls per output. It's efficient because only 2018983 out of 244140625 results need to be scrapped, or less than 1%.

Demo in Python:

def random5():
    return random.randint(1, 5)

def random7gen(n):
    count = 0
    while n > 0:
        samples = 6 * 7**9
        while samples >= 6 * 7**9:
            samples = 0
            for i in range(12):
                samples = samples * 5 + random5() - 1
                count += 1
        samples //= 6
        for outputs in range(9):
            yield samples % 7 + 1, count
            samples //= 7
            count = 0
            n -= 1
            if n == 0: break

>>> from collections import Counter
>>> Counter(x for x,i in random7gen(10000000))
Counter({2: 1430293, 4: 1429298, 1: 1428832, 7: 1428571, 3: 1428204, 5: 1428134, 6: 1426668})
>>> sum(i for x,i in random7gen(10000000)) / 10000000.0
1.344606

Answer 20

Here is an answer taking advantage of features in C++ 11

#include <functional>
#include <iostream>
#include <ostream>
#include <random>

int main()
{
    std::random_device rd;
    unsigned long seed = rd();
    std::cout << "seed = " << seed << std::endl;

    std::mt19937 engine(seed);

    std::uniform_int_distribution<> dist(1, 5);
    auto rand5 = std::bind(dist, engine);

    const int n = 20;
    for (int i = 0; i != n; ++i)
    {
        std::cout << rand5() << " ";
    }
    std::cout << std::endl;

    // Use a lambda expression to define rand7
    auto rand7 = [&rand5]()->int
    {
        for (int result = 0; ; result = 0)
        {
            // Take advantage of the fact that
            // 5**6 = 15625 = 15624 + 1 = 7 * (2232) + 1.
            // So we only have to discard one out of every 15625 numbers generated.

            // Generate a 6-digit number in base 5
            for (int i = 0; i != 6; ++i)
            {
                result = 5 * result + (rand5() - 1);
            }

            // result is in the range [0, 15625)
            if (result == 15625 - 1)
            {
                // Discard this number
                continue;
            }

            // We now know that result is in the range [0, 15624), a range that can
            // be divided evenly into 7 buckets guaranteeing uniformity
            result /= 2232;
            return 1 + result;
        }
    };

    for (int i = 0; i != n; ++i)
    {
        std::cout << rand7() << " ";
    }
    std::cout << std::endl;

    return 0;
}

Answer 21

Given a function which produces a random integer in the range 1 to 5 rand5(), write a function which produces a random integer in the range 1 to 7 rand7()

In my proposed solution, I only call rand5 once only

Real Solution

float rand7()
{
    return (rand5() * 7.0) / 5.0 ;
}

The distribution here is scaled, so it depends directly on the distribution of rand5

Integer Solution

int rand7()
{
    static int prev = 1;

    int cur = rand5();

    int r = cur * prev; // 1-25

    float f = r / 4.0; // 0.25-6.25

    f = f - 0.25; // 0-6

    f = f + 1.0; // 1-7

    prev = cur;

    return (int)f;
}

The distribution here depends on the series rand7(i) ~ rand5(i) * rand5(i-1)

with rand7(0) ~ rand5(0) * 1

Answer 22

I think y'all are overthinking this. Doesn't this simple solution work?

int rand7(void)
{
    static int startpos = 0;
    startpos = (startpos+5) % (5*7);
    return (((startpos + rand5()-1)%7)+1);
}

Answer 23

This solution was inspired by Rob McAfee.
However it doesn't need a loop and the result is a uniform distribution:

// Returns 1-5
var rnd5 = function(){
   return parseInt(Math.random() * 5, 10) + 1;
}
// Helper
var lastEdge = 0;
// Returns 1-7
var rnd7 = function () {
  var map = [
     [ 1, 2, 3, 4, 5 ],
     [ 6, 7, 1, 2, 3 ],
     [ 4, 5, 6, 7, 1 ],
     [ 2, 3, 4, 5, 6 ],
     [ 7, 0, 0, 0, 0 ]
  ];
  var result = map[rnd5() - 1][rnd5() - 1];
  if (result > 0) {
    return result;
  }
  lastEdge++;
  if (lastEdge > 7 ) {
    lastEdge = 1;
  }
  return lastEdge;
};

// Test the a uniform distribution
results = {}; for(i=0; i < 700000;i++) { var rand = rnd7(); results[rand] = results[rand] ? results[rand] + 1 : 1;} 
console.log(results)

Result: [1: 99560, 2: 99932, 3: 100355, 4: 100262, 5: 99603, 6: 100062, 7: 100226]

jsFiddle

Answer 24

There are a lot of solutions here that do not produce a uniform distribution and many comments pointing that out, but the the question does not state that as a requirement. The simplest solution is:

int rand_7() { return rand_5(); }

A random integer in the range 1 - 5 is clearly in the range 1 - 7. Well, technically, the simplest solution is to return a constant, but that's too trivial.

However, I think the existence of the rand_5 function is a red herring. Suppose the question was asked as "produce a uniformly distributed pseudo-random number generator with integer output in the range 1 - 7". That's a simple problem (not technically simple, but already solved, so you can look it up.)

On the other hand, if the question is interpreted to mean that you actually have a truly random number generator for integers in the range 1 - 5 (not pseudo random), then the solution is:

1) examine the rand_5 function
2) understand how it works
3) profit

Answer 25

This solution doesn't waste any entropy and gives the first available truly random number in range. With each iteration the probability of not getting an answer is provably decreased. The probability of getting an answer in N iterations is the probability that a random number between 0 and max (5^N) will be smaller than the largest multiple of seven in that range (max-max%7). Must iterate at least twice. But that's necessarily true for all solutions.

int random7() {
  range = 1;
  remainder = 0;

  while (1) {
    remainder = remainder * 5 + random5() - 1;
    range = range * 5;

    limit = range - (range % 7);
    if (remainder < limit) return (remainder % 7) + 1;

    remainder = remainder % 7;
    range = range % 7;
  }
}

Numerically equivalent to:

r5=5;
num=random5()-1;
while (1) {
   num=num*5+random5()-1;
   r5=r5*5;
   r7=r5-r5%7;
   if (num<r7) return num%7+1;
}

The first code calculates it in modulo form. The second code is just plain math. Or I made a mistake somewhere. :-)

Answer 26

This is similiarly to @RobMcAfee except that I use magic number instead of 2 dimensional array.

int rand7() {
    int m = 1203068;
    int r = (m >> (rand5() - 1) * 5 + rand5() - 1) & 7;

    return (r > 0) ? r : rand7();
}

Answer 27

function rand7() {
    while (true) { //lowest base 5 random number > 7 reduces memory
        int num = (rand5()-1)*5 + rand5()-1;
    if (num < 21)  // improves performance
        return 1 + num%7;
    }
}

Python code:

from random import randint
def rand7():
    while(True):
        num = (randint(1, 5)-1)*5 + randint(1, 5)-1
        if num < 21:
                return 1 + num%7

Test distribution for 100000 runs:

>>> rnums = []
>>> for _ in range(100000):
    rnums.append(rand7())
>>> {n:rnums.count(n) for n in set(rnums)}
{1: 15648, 2: 15741, 3: 15681, 4: 15847, 5: 15642, 6: 15806, 7: 15635}

Answer 28

This expression is sufficient to get random integers between 1 - 7

int j = ( rand5()*2 + 4 ) % 7 + 1;

Answer 29

We are using the convention rand(n) -> [0, n - 1] here

From many of the answer I read, they provide either uniformity or halt guarantee, but not both (adam rosenfeld second answer might).

It is, however, possible to do so. We basically have this distribution:

This leaves us a hole in the distribution over [0-6]: 5 and 6 have no probability of ocurrence. Imagine now we try to fill the hole it by shifting the probability distribution and summing.

Indeed, we can the initial distribution with itself shifted by one, and repeating by summing the obtained distribution with the initial one shifted by two, then three and so on, until 7, not included (we covered the whole range). This is shown on the following figure. The order of the colors, corresponding to the steps, is blue -> green -> cyan -> white -> magenta -> yellow -> red.

Because each slot is covered by 5 of the 7 shifted distributions (shift varies from 0 to 6), and because we assume the random numbers are independent from one ran5() call to another, we obtain

p(x) = 5 / 35 = 1 / 7       for all x in [0, 6]

This means that, given 7 independent random numbers from ran5(), we can compute a random number with uniform probability in the [0-6] range. In fact, the ran5() probability distribution does not even need to be uniform, as long as the samples are independent (so the distribution stays the same from trial to trial). Also, this is valid for other numbers than 5 and 7.

This gives us the following python function:

def rand_range_transform(rands):
    """
    returns a uniform random number in [0, len(rands) - 1]
    if all r in rands are independent random numbers from the same uniform distribution
    """
    return sum((x + i) for i, x in enumerate(rands)) % len(rands) # a single modulo outside the sum is enough in modulo arithmetic

This can be used like this:

rand5 = lambda : random.randrange(5)

def rand7():
    return rand_range_transform([rand5() for _ in range(7)])

If we call rand7() 70000 times, we can get:

max: 6 min: 0 mean: 2.99711428571 std: 2.00194697049
0:  10019
1:  10016
2:  10071
3:  10044
4:  9775
5:  10042
6:  10033

This is good, although far from perfect. The fact is, one of our assumption is most likely false in this implementation: we use a PRNG, and as such, the result of the next call is dependent from the last result.

That said, using a truly random source of numbers, the output should also be truly random. And this algorithm terminates in every case.

But this comes with a cost: we need 7 calls to rand5() for a single rand7() call.

Answer 30

Here's my general implementation, to generate a uniform in the range [0,N-1] given a uniform generator in the range [0,B-1].

public class RandomUnif {

    public static final int BASE_NUMBER = 5;

    private static Random rand = new Random();

    /** given generator, returns uniform integer in the range 0.. BASE_NUMBER-1
    public static int randomBASE() {
        return rand.nextInt(BASE_NUMBER);
    }

    /** returns uniform integer in the range 0..n-1 using randomBASE() */
    public static int randomUnif(int n) {
        int rand, factor;
        if( n <= 1 ) return 0;
        else if( n == BASE_NUMBER ) return randomBASE();
        if( n < BASE_NUMBER ) {
            factor = BASE_NUMBER / n;
            do
                rand = randomBASE() / factor;
            while(rand >= n);
            return rand;
        } else {
            factor = (n - 1) / BASE_NUMBER + 1;
            do {
                rand = factor * randomBASE() + randomUnif(factor);
            } while(rand >= n);
            return rand;
        }
    }
}

Not spectaculary efficient, but general and compact. Mean calls to base generator:

 n  calls
 2  1.250 
 3  1.644 
 4  1.252 
 5  1.000 
 6  3.763 
 7  3.185 
 8  2.821 
 9  2.495 
10  2.250 
11  3.646 
12  3.316 
13  3.060 
14  2.853 
15  2.650 
16  2.814 
17  2.644 
18  2.502 
19  2.361 
20  2.248 
21  2.382 
22  2.277 
23  2.175 
24  2.082 
25  2.000 
26  5.472 
27  5.280 
28  5.119 
29  4.899