Adrian Adkison
Adrian Adkison

Reputation: 3757

Write a truly inclusive random method for javascript

Javascript's MATH object has a random method that returns from the set [0,1) 0 inclusive, 1 exclusive. Is there a way to return a truly random method that includes 1.

e.g.

var rand = MATH.random()*2;

if(rand > 1)
{
   rand = MATH.floor(rand);
}

return rand; 

While this always returns a number from the set [0,1] it is not truly random.

Upvotes: 24

Views: 8452

Answers (12)

EnterChaos
EnterChaos

Reputation: 1

This is my first post on stackoverflow woo hoo! I would have commented on @Guffa's answer but don't have enough reputation! To use that answer for this particular question, I would recommend picking a precision, say for example you are willing to settle for a random number between 0 and 1 inclusive with 6 digits of precision, then you could:

double precision = 1000000.0;
return (Math.random()*(precision+1))/precision;

Upvotes: -1

user5924708
user5924708

Reputation:

What about this:

var randomFloatInclusive = Math.random();
if (randomFloatInclusive + Number.EPSILON >= 1) {
  randomFloatInclusive = 1;
}
console.log(randomFloatInclusive);

Upvotes: 0

Will Vousden
Will Vousden

Reputation: 33358

To put it bluntly, what you're trying to do doesn't make sense.

Remember that under a continuous probability distribution, the probability of getting a specific value is infinitesimal, so mathematically speaking you will never see the exact value of 1.

Of course, in the world of computers, the distribution of an RNG isn't truly continuous, so it's "possible" that you'll encounter a specific value (as silly as that sounds), but the probability will be so vanishingly small that in practice you will never observe it.

To make the point a bit more clearly: if you did manage to write such a function in terms of double-precision floats, the probability of getting exactly 1 would be approximately 2-64. If you called the function 1 million times per second, you would have to wait around 600,000 years before you got a 1.

Upvotes: 14

tevemadar
tevemadar

Reputation: 13195

If you do need generating [0-1] inclusive, it can be achieved via specifying a precision, like when generating an integer number with an inclusive limit, and divide it back afterwards.
Because we are in the world of computers, I suggest a using a precision which is a power of 2 so the division at the end will not actually touch the digits.
The upper limit is not specified other than by Number itself being a 64-bit double-precision number, which means 53 significant digits. But the generator itself is implementation-dependent, and in reality it may or may not be capable of generating every single floating point number between 0 and 1.

To actually see 0 and 1 generated, typically a far lower precision is needed, like 20-something bits. This time-limited (stops after 30 seconds) snippet succeeds for me up to 25-bits, sometimes even 26. The default is 23, that's really expected to finish fast.

const precision=1<<parseInt(prompt("Bits (23)?") || "23");
console.log("hex:",precision.toString(16),"dec:",precision);
const limit=precision+1;
function next0to1() {
  return Math.floor(Math.random()*limit)/precision;
}

let start=Date.now();
let stop=start+30000;
let count=0;
while(Date.now()<stop){
  count++;
  if(next0to1()===0){
    console.log("0",count,Date.now()-start);
    break;
  }
}
while(Date.now()<stop){
  count++;
  if(next0to1()===1){
    console.log("1",count,Date.now()-start);
    break;
  }
}
console.log("attempts:",count);

Upvotes: 0

Sjieke
Sjieke

Reputation: 412

The solution I found was to use trigonometric equations.

Because sine oscillates from Math.sin(0) = 0 and Math.sin(90) = 1. This repeats until 360 degrees which is equal to 0. However, 360 is still not highly precise so use radians which is 2 * Math.PI. You only need to take the absolute value to get rid of the negative values.

So,

double angle = 2 * Math.PI * Math.random() 
double inclusive = Math.abs(Math.sin(angle)) // Math.cos(angle) also works.

Upvotes: 1

blakkwater
blakkwater

Reputation: 1181

This should work properly.

function random_inclusive () {
    while (true) {
        var value = Math.random() + (Math.random() < 0.5? 0: 1);
        if (value <= 1) {
            return value;
        }
    }
}

What we do here is generate additional single random bit to expand PRNG range to [0, 2). Then we simply discard values in (1, 2) and retry until our value hits in [0, 1].

Notice that this method calls Math.random() 4 times on average.

Alternatively, we can speed up things twice by the cost of 1 bit of precision:

var value = Math.random() * 2;

For those who want to test, here is the way. Just assume that Math.random() only has 1 bit of precision and generates either 0 or 0.5. So on the output we should have uniform distribution among values 0, 0.5, and 1.

function random_inclusive_test (samples) {
    var hits = {};
    for (var i=0; i<samples; i++) {
        while (true) {
            var value =
                (Math.random() < 0.5? 0: 0.5) +
                (Math.random() < 0.5? 0: 1);
            if (value <= 1) {
                break;
            }
        }
        if (!hits[value]) {
            hits[value] = 1;
        }
        else {
            hits[value]++;
        }
    }
    console.log(hits);
}
random_inclusive_test(300000);

Upvotes: 1

Thomas
Thomas

Reputation: 12637

Since this question has been asked again, and I didn't read this approach here I'll add another answer.

IMO the best you can do, without too much hassle would be:

exclusive:

//simply ignore the 0
for(var rand=0; !rand;rand = Math.random());

//or simpler:
var rand = Math.random() || Math.random();
//because the probability for two consecutive `0` is pretty much non existant.

this doesn't even introduce an error, since we just excluded the possibility of returning 0, every other value between 0 and 1 has the same probability

inclusive:

var rand = Math.random() * 2;
if(rand > 1) rand-=1;
//so the 0 shares it's probability with the 1.

just to be clear about how tiny the "error" is:

  • the probability for a 0 or a 1 is
    1 / Math.pow(2, 54) or about 5.55e-17
  • the probability for any other value between 0 and 1 is
    1 / Math.pow(2, 53) or about 11.1e-17

and the whole random-function would be:

function random(min, max, inclusive){
    var r = Math.random();
    if(inclusive)
        r = r>0.5? 2*r-1: 2*r;
    else 
        while(!r) r = Math.random();

    return r * (max - min) + min;
}

Edit: I'm not sure wether I make a mistake, but shouldn't the probability be fixed on the inclusive approach, if I add another bit to the zeroes and ones, and therefore duplicate their probability:

var rand = Math.random() * 4;
rand = (rand % 1) || (rand & 1);

Upvotes: 1

thdoan
thdoan

Reputation: 19097

From what I can see from the JavaScript console in Chrome, Math.random() generates a number from 0 up to 0.9999999999999999. Taking this into account, you can get what you want by adding a modifier. For example, here's a function that will give you quasi-random float between 0 and 1, with 1 being inclusive:

function randFloat() {
  // Assume random() returns 0 up to 0.9999999999999999
  return Math.random()*(1+2.5e-16);
}

You can try this in the console by enter 0.9999999999999999*(1+2.5e-16) -- it will return exactly 1. You can take this further and return a float between 0 and 1024 (inclusive) with this function:

function randFloat(nMax) {
  // Assume random() returns 0 up to 0.9999999999999999
  // nMax should be a float in the range 1-1024
  var nMod;
  if (nMax<4) nMod = 2.5e-16;
  else if (nMax<16) nMod = 1e-15;
  else if (nMax<32) nMod = 3.5e-15;
  else if (nMax<128) nMod = 1e-14;
  else if (nMax<512) nMod = 3.5e-14;
  else if (nMax<1024) nMod = 1e-13;
  return Math.random()*(nMax+nMod);
}

There's probably a more efficient algorithm to be had somewhere.

Upvotes: 2

David Tonhofer
David Tonhofer

Reputation: 15316

Addendum:

Taking a look at the java.util.Random source code included with the distribution of Oracle JDK 7 ("Copyright (c) 1995, 2010, Oracle and/or its affiliates. All rights reserved. ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms") shows this simple code:

class Random {

    public float nextFloat() {
        return next(24) / ((float)(1 << 24));
    }

    protected int next(int bits) {
        long oldseed, nextseed;
        AtomicLong seed = this.seed;
        do {
            oldseed = seed.get();
            nextseed = (oldseed * multiplier + addend) & mask;
        } while (!seed.compareAndSet(oldseed, nextseed));
        return (int)(nextseed >>> (48 - bits));
    }
}

Thus, for nextFloat():

  1. Take a "random integer value" between 0 and 2^24-1 (or rather, a random 24-bit bitpattern interpreted as an integer value),
  2. Convert it to float (in Java, "float" is mandated to be an IEEE 724 32-bit floating point, which can represent up to 2^24 with no loss of precision, and this will thus be a value between 0 and 1.6777215E7)
  3. Then divide it by the float representation of 2^24, again just representable with no loss of precision as 1.6777216E7. 2^24+1 = 16777217 would drop down to 1.6777216E7 when forced to be float. In the code, this should really be a constant. Hey Sun, cycles don't grow on trees!!
  4. Division results in a float in [0.0 .. 0.99999994] (the correct division result would be around 0.999999940395355224609375), with, I think, all the possible IEEE 724 floating point values in between 'equally possible'.

See also IEEE floating point and Floating-Point Arithmetic on the JVM.

The Javadoc comments for `next() is:

/**
 * Generates the next pseudorandom number. Subclasses should
 * override this, as this is used by all other methods.
 *
 * <p>The general contract of {@code next} is that it returns an
 * {@code int} value and if the argument {@code bits} is between
 * {@code 1} and {@code 32} (inclusive), then that many low-order
 * bits of the returned value will be (approximately) independently
 * chosen bit values, each of which is (approximately) equally
 * likely to be {@code 0} or {@code 1}. The method {@code next} is
 * implemented by class {@code Random} by atomically updating the seed to
 *  <pre>{@code (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)}</pre>
 * and returning
 *  <pre>{@code (int)(seed >>> (48 - bits))}.</pre>
 *
 * This is a linear congruential pseudorandom number generator, as
 * defined by D. H. Lehmer and described by Donald E. Knuth in
 * <i>The Art of Computer Programming,</i> Volume 3:
 * <i>Seminumerical Algorithms</i>, section 3.2.1.
 *
 * @param  bits random bits
 * @return the next pseudorandom value from this random number
 *         generator's sequence
 * @since  1.1
 */

The Javadoc comments for nextFloat() is:

/**
 * Returns the next pseudorandom, uniformly distributed {@code float}
 * value between {@code 0.0} and {@code 1.0} from this random
 * number generator's sequence.
 *
 * <p>The general contract of {@code nextFloat} is that one
 * {@code float} value, chosen (approximately) uniformly from the
 * range {@code 0.0f} (inclusive) to {@code 1.0f} (exclusive), is
 * pseudorandomly generated and returned. All 2<font
 * size="-1"><sup>24</sup></font> possible {@code float} values
 * of the form <i>m&nbsp;x&nbsp</i>2<font
 * size="-1"><sup>-24</sup></font>, where <i>m</i> is a positive
 * integer less than 2<font size="-1"><sup>24</sup> </font>, are
 * produced with (approximately) equal probability.
 *
 * <p>The method {@code nextFloat} is implemented by class {@code Random}
 * as if by:
 *  <pre> {@code
 * public float nextFloat() {
 *   return next(24) / ((float)(1 << 24));
 * }}</pre>
 *
 * <p>The hedge "approximately" is used in the foregoing description only
 * because the next method is only approximately an unbiased source of
 * independently chosen bits. If it were a perfect source of randomly
 * chosen bits, then the algorithm shown would choose {@code float}
 * values from the stated range with perfect uniformity.<p>
 * [In early versions of Java, the result was incorrectly calculated as:
 *  <pre> {@code
 *   return next(30) / ((float)(1 << 30));}</pre>
 * This might seem to be equivalent, if not better, but in fact it
 * introduced a slight nonuniformity because of the bias in the rounding
 * of floating-point numbers: it was slightly more likely that the
 * low-order bit of the significand would be 0 than that it would be 1.]
 *
 * @return the next pseudorandom, uniformly distributed {@code float}
 *         value between {@code 0.0} and {@code 1.0} from this
 *         random number generator's sequence
 */

Upvotes: 1

Guffa
Guffa

Reputation: 700362

The Math.random function returns a random number between 0 and 1, where 0 is inclusive and 1 is exclusive. This means that the only way to properly distribute the random numbers as integers in an interval is to use an exclusive upper limit.

To specify an inclusive upper limit, you just add one to it to make it exclusive in the calculation. This will distribute the random numbers correctly between 7 and 12, inclusive:

var min = 7;
var max = 12;
var rnd = min + Math.floor(Math.random() * (max - min + 1));

Upvotes: 9

Trevor
Trevor

Reputation: 6689

This will return [0,1] inclusive:

if(MATH.random() == 0)
    return 1;
else
    return MATH.random();

Explanation: If the first call to random() returns 0, return 1. Otherwise, call random again, which will be [0,1). Therefore, it will return [0,1] all inclusive.

Upvotes: 19

nickf
nickf

Reputation: 546055

You want it to include 1?

return 1 - Math.random();

However, I think this is one of those questions which hints at other problems. Why do you need to include 1? There's probably a better way to do it.

Upvotes: 2

Related Questions