718

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.

6
  • It proved to be an unexpectedly interesting problem, I still think how to 1) do it in fixed time and 2) not spoil the uniform distribution (if there was)
    – eugensk
    Sep 27, 2008 at 5:20
  • We had the similar problem while choosing one player out of 5 with a dice. We threw the dice in turns, one who gets the max score is choosen. The uniformity was achived, but not time constantness :)
    – eugensk
    Sep 27, 2008 at 5:29
  • Would I get downvoted if I posted an answer saying that the problem doesn't mandate you have to use the given function and just write one that returns 1-7 randomly? Jan 18, 2011 at 2:45
  • What about 7 * rand5() / 5 ?
    – kiwixz
    Feb 19, 2015 at 0:43
  • @kiwixz, that will produce "between 1 and 7", but you won't get 3 or 6: {1: 19.96, 2: 20.02, 4: 20.01, 5: 19.99, 7: 20.02} rough percentages testing manually. 7*.2, 7*.4, 7*.6, 7*.8, 7*1. Apr 18, 2016 at 20:40

79 Answers 79

2

The function you need is rand1_7(), I wrote rand1_5() so that you can test it and plot it.

import numpy
def rand1_5():
    return numpy.random.randint(5)+1

def rand1_7():
    q = 0
    for i in xrange(7):  q+= rand1_5()
    return q%7 + 1
2
function Rand7
   put 200 into x
   repeat while x > 118
      put ((random(5)-1) * 25) + ((random(5)-1) * 5) + (random(5)-1) into x
   end repeat
   return (x mod 7) + 1
end Rand7

Three calls to Rand5, which only repeats 6 times out of 125, on average.

Think of it as a 3D array, 5x5x5, filled with 1 to 7 over and over, and 6 blanks. Re-roll on the blanks. The rand5 calls create a three digit base-5 index into that array.

There would be fewer repeats with a 4D, or higher N-dimensional arrays, but this means more calls to the rand5 function become standard. You'll start to get diminishing efficiency returns at higher dimensions. Three seems to me to be a good compromise, but I haven't tested them against each other to be sure. And it would be rand5-implementation specific.

2
int getOneToSeven(){
    int added = 0;
    for(int i = 1; i<=7; i++){
        added += getOneToFive();
    }
    return (added)%7+1;
}
1
  • 2
    This can't be right because there are 5**7 possible outcomes (78125) but 78125%7 = 5 -- meaning that there is an uneven distribution of the seven desired outcomes.
    – hughdbrown
    Dec 1, 2010 at 18:27
2

This is the simplest answer I could create after reviewing others' answers:

def r5tor7():
    while True:
        cand = (5 * r5()) + r5()
        if cand < 27:
            return cand

cand is in the range [6, 27] and the possible outcomes are evenly distributed if the possible outcomes from r5() are evenly distributed. You can test my answer with this code:

from collections import defaultdict

def r5_outcome(n):
    if not n:
        yield []
    else:
        for i in range(1, 6):
            for j in r5_outcome(n-1):
                yield [i] + j

def test_r7():
    d = defaultdict(int)
    for x in r5_outcome(2):
        s = sum([x[i] * 5**i for i in range(len(x))])
        if s < 27:
            d[s] += 1
    print len(d), d

r5_outcome(2) generates all possible combinations of r5() results. I use the same filter to test as in my solution code. You can see that all of the outcomes are equally probably because they have the same value.

2
package CareerCup;

public class RangeTransform {
 static int counter = (int)(Math.random() * 5 + 1);

 private int func() {
  return (int) (Math.random() * 5 + 1);
 }

 private int getMultiplier() {
  return counter % 5 + 1;
 }

 public int rangeTransform() {
  counter++;
  int count = getMultiplier();
  int mult = func() + 5 * count;
  System.out.println("Mult is : " + 5 * count);
  return (mult) % 7 + 1;
 }

 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  RangeTransform rangeTransform = new RangeTransform();
  for (int i = 0; i < 35; i++)
   System.out.println("Val is : " + rangeTransform.rangeTransform());
 }
}
2

For values 0-7 you have the following:

0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

From bitwise from left to right Rand5() has p(1) = {2/5, 2/5, 3/5}. So if we complement those probability distributions (~Rand5()) we should be able to use that to produce our number. I'll try to report back later with a solution. Anyone have any thoughts?

R

2
rand25() =5*(rand5()-1) + rand5()

rand7() { 
   while(true) {
       int r = rand25();
       if (r < 21) return r%3;         
   }
}

Why this works: probability that the loop will run forever is 0.

2

Here's what I've found:

  1. Random5 produces a range from 1~5, randomly distributed
  2. If we run it 3 times and add them together we'll get a range of 3~15, randomly distributed
  3. Perform arithmetic on the 3~15 range
    1. (3~15) - 1 = (2~14)
    2. (2~14)/2 = (1~7)

Then we get a range of 1~7, which is the Random7 we're looking for.

2
  • 2
    Random7 is not uniformally distributed. Take step 2. What are the odds of 3 being generated? 1/125. How about 4? 3/125. Assuming integer division in step 3, these are the only 2 ways of generating 1 in Random7. That only happens 4/125 of the time. Now maybe my mistake is using the word uniformally.
    – demongolem
    Jun 8, 2012 at 17:09
  • The 3~15 probability distribution is not uniform, it is a bell curve, therefore this is incorrect.
    – Muhd
    Aug 21, 2012 at 0:48
2

Assuming rand gives equal weighting to all bits, then masks with the upper bound.

int i = rand(5) ^ (rand(5) & 2);

rand(5) can only return: 1b, 10b, 11b, 100b, 101b. You only need to concern yourself with sometimes setting the 2 bit.

2

Why won't this work? Other then the one extra call to rand5()?

i = rand5() + rand5() + (rand5() - 1) //Random number between 1 and 14

i = i % 7 + 1;
1
  • 1
    First, the comment is wrong - rand5() + rand5() + rand5() - 1 will always be at least 2. Regardless, though, your solution is not uniform; 6's are about 20% more likely than 3's.
    – Mark Reed
    Mar 28, 2012 at 1:07
2

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:

rand5_proba.png

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.

fig_moving_average_proba.png

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.

2

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. :-)

2

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.

1

how about this

rand5()%2+rand5()%2+rand5()%2+rand5()%2+rand5()%2+rand5()%2

Not sure this is uniform distributed. Any suggestions?

1
  • 1
    It's not uniform because rand5()%2 is not uniform. 5 possible answers can't be split evenly into two categories - the 0/1 split will be 60/40 instead of 50/50 (60% 0's if rand5 returns 0..4, 60% 1's if it returns 1..5).
    – Mark Reed
    Mar 28, 2012 at 1:09
1

I thought of an interesting solution to this problem and wanted to share it.

function rand7() {

    var returnVal = 4;

    for (var n=0; n<3; n++) {
        var rand = rand5();

        if (rand==1||rand==2){
            returnVal+=1;
        }
        else if (rand==3||rand==4) {
            returnVal-=1;
        }
    }

    return returnVal;
}

I built a test function that loops through rand7() 10,000 times, sums up all of the return values, and divides it by 10,000. If rand7() is working correctly, our calculated average should be 4 - for example, (1+2+3+4+5+6+7 / 7) = 4. After doing multiple tests, the average is indeed right at 4 :)

3
  • 3
    if you got all ones and sevens the average could be 4. Apr 1, 2011 at 15:10
  • dqhendricks is right. You need to show that the distribution of the values 1-7 that your solution gives, is the isomorphic to the original distribution. (In other words, that changing the range didn't make the odds "less random".) Jan 11, 2012 at 9:49
  • Your mean is 4, but the distribution isn't uniform. I don't think you can produce a uniform distribution using less than 7 calls of rand5(), both 5 and 7 being primes. Nov 25, 2012 at 21:54
1

First thing came on my mind is this. But i have no idea whether its uniformly distributed. Implemented in python

import random

def rand5():

return random.randint(1,5)

def rand7():

return ( ( (rand5() -1) * rand5() ) %7 )+1

1

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 
1
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}
1

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();
}
1

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
1

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

1
  • It is a uniform distribution, but it is not totally random, because in the first call, you are more likely to get the 1, in the second call the 2, and so on. This would only make sense if the consumer of the function has no way to know if it's the Nth call. Else you have 7/25 chance of guessing the number against 3/25...
    – Martin
    Oct 16, 2014 at 12:25
1

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);
}
1

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

1

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;
}
1

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...

1
+100

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.

1

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 }
1
  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

4
  • What do you do at (7+5)% 7 +1 = ??, Does this add a bias or require a re roll, what issues are there with your first answer?
    – daniel
    Apr 24, 2017 at 13:44
  • @daniel, this won't be the case. rand5() will not generate a random number 7. Thus at max, it can be (5 + 5) % 7 + 1 = 4. Apr 24, 2017 at 14:37
  • So its not uniform, you are allowing 1,2,3,4 to be picked more often. If you look at the most up voted answer your solution is like his except instead of 0,0,0,0 you have 1,2,3,4
    – daniel
    Apr 24, 2017 at 15:03
  • 1
    Why is this answer not correct ? The problem statement does not require the result to be unifromly distributed.
    – RBF06
    Dec 29, 2017 at 14:32
1

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
0

Why don't you just divide by 5 and multiply by 7, and then round? (Granted, you would have to use floating-point no.s)

It's much easier and more reliable (really?) than the other solutions. E.g. in Python:

def ranndomNo7():
    import random
    rand5 = random.randint(4)    # Produces range: [0, 4]
    rand7 = int(rand5 / 5 * 7)   # /5, *7, +0.5 and floor()
    return rand7

Wasn't that easy?

1
  • 3
    You still only end up with 5 distinct integers, not 7. You just have changed the 5 integers that are generated
    – demongolem
    Jun 8, 2012 at 16:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.