Generate any random integer

Question

Your program/function should

• output exactly one integer
• output any integer with positive probability
• output an integer greater than 1.000.000 or less than -1.000.000 with at least with 50% probability.

Example outputs (all must be possible):

59875669123
12
-42
-4640055890
0
2014
12
24
-7190464664658648640055894646646586486400558904644646646586486400558904646649001

Clarifications:

• A trailing line break is permitted.
• Leading zeros aren't allowed.
• -0 is permitted.

Shortest code wins.

Answer 1

CJam, 16 14 13 bytes

0{Kmr(+esmr}g

This will run for a very long time, because it uses the current timestamp (on the order of 10¹²) to determine if the loop should terminate. I'm using this as the submission, as it is the shortest, but there are two 14-byte alternatives, which have their own merits:

0{esmr(+esmr}g

This one is not limited by the period of the PRNG, since the range of all random numbers depends on the current timestamp. Therefore, this should be able to produce any number whatsoever, although the probability for negative, or even small positive numbers vanishingly small.

Below is an equivalent version that uses 3e5 instead of the timestamp. And 20 for the first range (as the 13-byte submission). It's much faster and also complies with all the rules. It is sort of the limiting case to get the 50% probability for numbers beyond 1,000,000 while keeping a reasonable runtime and small code-size. The explanation and mathematical justification refer to this version:

0{Kmr(+3e5mr}g

This usually takes a few seconds to run. You can replace the 5 with a 2 to make it run even faster. But then the requirement on the 50% probability will only be met for 1,000 instead of 1,000,000.

I'm starting at 0. Then I've got a loop, which I break out of with probability 1/(3*10⁵). Within that loop I add a random integer between -1 and 18 (inclusive) to my running total. There is a finite (albeit small) probability that each integer will be output, with positive integers being much more likely than negative ones (I don't think you'll see a negative one in your lifetime). Breaking out with such a small probability, and incrementing most of the time (and adding much more than subtracting) ensures that we'll usually go beyond 1,000,000.

0              "Push a 0.";
 {          }g "Do while...";
  Kmr          "Get a random integer in 0..19.";
     (         "Decrement to give -1..18.";
      +        "Add.";
       3e5mr   "Get a random integer in 0..299,999. Aborts if this is 0.";

Some mathematical justification:

• In each step we add 8.5 on average.
• To get to 1,000,000 we need 117,647 of these steps.

• The probability that we'll do less than this number of steps is

  sum(n=0..117,646) (299,999/300,000)^n * 1/300,000
  

  which evaluates to 0.324402. Hence, in about two thirds of the cases, we'll take more 117,647 steps, and easily each 1,000,000.

• (Note that this is not the exact probability, because there will be some fluctuation about those average 8.5, but to get to 50%, we need to go well beyond 117,646 to about 210,000 steps.)
• If in doubt, we can easily blow up the denominator of the termination probability, up to 9e9 without adding any bytes (but years of runtime).

...or 11 bytes?

Finally, there's an 11 byte version, which is also not limited by the period of the PRNG, but which will run out of memory pretty much every time. It only generates one random number (based on the timestamp) each iteration, and uses it both for incrementing and terminating. The results from each iteration remain on the stack and are only summed up at the end. Thanks to Dennis for this idea:

{esmr(}h]:+

Answer 2

Java, 133 149

void f(){String s=x(2)<1?"-":"";for(s+=x(9)+1;x(50)>0;s+=x(10));System.out.print(x(9)<1?0:s);}int x(int i){return new java.util.Random().nextInt(i);}

Example outputs

-8288612864831065123773
0
660850844164689214
-92190983694570102879284616600593698307556468079819964903404819
3264

Ungolfed

void f() {
    String s = x(2)<1 ? "-" : "";       // start with optional negative sign
    s+=x(9)+1;                          // add a random non-zero digit
    for(; x(50)>0; )                    // with a 98% probability...
        s+=x(10)                        // append a random digit
    System.out.print(x(9)<1 ? 0 : s);   // 10% chance of printing 0 instead
}

int x(int i) {
    return new java.util.Random().nextInt(i);
}

Old answer (before rule change)

void f(){if(Math.random()<.5)System.out.print('-');do System.out.print(new java.util.Random().nextInt(10));while(Math.random()>.02);}

Answer 3

Mathematica - 47

Round@RandomVariate@NormalDistribution[0,15*^5]

Basically just generate random number using normal distribution with variance equal to 1500000. This will produce an integer between -10^6 and 10^6 with probability 49.5015%.

Answer 4

Python 2, 75 69 bytes

from random import*;s=0;j=randrange
while j(12):s=s*9+j(-8,9)
print s

It is trivial to check that the while loop in the middle can generate all integers (albeit biased towards zero). "12" is chosen such that there are roughly half of numbers exceeding ±10⁶.

---

Older solution:

Python 2, 44 bytes

Based on the Mathematica solution.

from random import*;print int(gauss(0,8**7))

Doesn't really work because Python's float has only finite precision.

Answer 5

Ruby, 70

f=->{m=10**6
r=rand -m..m
r<1?(r>-5e5??-:'')+r.to_s+f[][/\d+/]:r.to_s}

To make generating very large numbers possible, I'm returning the number as a String from a lambda. If that's not allowed, count 8 characters extra (for puts f[]) to make it a program instead of a function.

Explanation

Generate a number between -1,000,000 and 1,000,000. If the number is 1 or higher, the number is returned as a String.

If the number is lower than 1, the function is called recursively to return number outside the number range. To make sure negative numbers can also be generated, a - is prefixed to the resulting String if the initial number is greater than -500,000.

I hope I understood the challenge correctly!

Answer 6

R, 38

library(Rmpfr)
round(rnorm(1,2e6,1e6))

Draws from the Gaussian distribution with mean 2,000,000, chosen randomly, and standard deviation 1,000,000, so that about 2/3 of the draws will lie within 1,000,000 and 3,000,000. The distribution is unbounded so in theory this can generate any integer. The Rmpfr package replaces R's built in double floats with arbitrary precision.

Answer 7

Perl, 114 Chars

use Math::BigInt;sub r{$x=Math::BigInt->new(0);while(rand(99)!=0){$x->badd(rand(2**99)-2**98);}print($x->bstr());}

Breakdown:

use Math::BigInt;               -- include BigIntegers
  sub r{                        -- Define subroutine "r"
    $x=Math::BigInt->new(0);    -- Create BigInteger $x with initial value "0"
      while(rand(99)!=0){       -- Loop around until rand(99) equals "0" (may be a long time)
        $x->badd(               -- Add a value to that BigInt
          rand(2**99)-2**98);   -- Generate a random number between -2^98 and +2^98-1
        }print($x->bstr());}    -- print the value of the BigInt

The probability of getting a value between -1.000.000 and 1.000.000 are tending towards zero BUT it is possible.

Note: This subroutine may run for a long time and error out with an "Out of Memory!" error but it's technically generating any integer as stated in the question.

Perl, 25

sub r{rand(2**99)-2**98;}

Generates a random integer within the range of +/-2^99.

Breakdown

sub r{                    -- Define subroutine "r"
     rand(2**99)          -- Generate a random integer between 0 and 2^99
                -2**98;}  -- Subtract 2^98 to get negative values as well

Tested with 1 million samples:

~5 are inside the range of +/-1.000.000
~999.995 are outside that range
= a probability of ~99,99% of generating an integer outside that range.
Compare that number to the probability of 2.000.000 in 2^99: It is approx. the same.

This meets all rules:

• 1 integer
• any integer is possible
• at least 50% (in my case 99,99%) of all generated integers are outside the range of +/-1.000.000.

This works because the underlying random number generator defines equal probability to every bit that is generated, thus doing that on generated integers as well.
Every integer has a probability of 1/2^99 to be generated.

Edit:

I had to increase the exponent so that larger integers are being generated. I have chosen 99 because it keeps the code as short as possible.

Answer 8

C#, 126 107 bytes

string F(){var a=new System.Random();var b=a.Next(-1E6,1E6+1)+"";while(a.Next(1)>0)b+=a.Next(10);return b;}

Ungolfed:

string F()
{
    System.Random rand = new System.Random();
    string rtn = rand.Next(-1E6, 1E6 + 1) + "";
    while (rand.Next(1) > 0)
         rtn += a.Next(10);
    return rtn;
}

Chance to generate a number of n digits is 1/2^(n-10), which is greater than 0 for all positive n, and 1/2 for n=11. Also creates leading zeros, which do not seem to be disallowed in the original question or any of its comments.

Answer 9

Perl, 53 characters

print"-"if rand>.5;do{print int rand 10}while rand>.1

I certainly don't see any reason to work with integers when printing one :)

Has equal probability of printing a number with or without a leading "-".

Prints a 1-digit number 10% of the time, a 2-digit number 9% of the time, a 3-digit number 8.1% of the time, a 4-digit number 7.29% of the time, a 5-digit number 6.56% of the time, a 6-digit number 5.9% of the time, etc. Any length is possible, with decreasing probability. The one-through-five digit numbers account for about 41.5% of output cases, and the number 1,000,000 (or -1,000,000) only 6-millionths of a percent, so the output number will be outside of the range -1,000,000 through 1,000,000 about 54.6% of the time.

Both "0" and "-0" are possible outputs, which I hope is not a problem.

Answer 10

Perl, 62 bytes

print $n=int rand(20)-10;while($n&&rand>.1){print int rand 10}

I had the same idea as @Hobbs, of generating a digit at a time, but his code didn't satisfy the added no-leading-zeros requirement. Generating the first digit instead of just the sign solved that. And unless there's a shorter way to exit if we printed a zero, or a shorter way to generate the leading -9 to 9, this should do it for size.

In a shell loop: while perl -e '...'; do echo;done |less

I think this is one of the shortest that doesn't require infinite RAM to satisfy the problem. As a bonus, the output is isn't strongly biased towards anything, and runtime is very fast.

I tried using bitwise and to save a character in the while condition, but I think this ends up being true more often, so the loop ends sooner. Would need more chars to adjust other things to counter that, to maintain the probability of generating abs(output) > 1M.

Answer 11

Bash, 42 bytes

printf "%d\n" 0x$(xxd -p -l5 /dev/random)
/dev/random on OSX is just random bytes, and xxd -p -l5 converts 5 of the ascii characters to hex, and printf turns it into decimal format.

Answer 12

Javascript (73)

This solution uses that you can construct a number with base n by multiplying the previous number with n and adding a digit in base n. We have an additional ..?..:.. in there to be able to create all negative integers. The following code should be tested in a browser console.

b=Math.round;c=Math.random;x=0;while(b(c()*99)){x*=b(c())?2:-2;x+=b(c())}

The probability to get an integer >= 2^1 (or <= -(2^1)) is equal to the chance that the loop is ran 2 times. The chance of that happening is (98/99)^2. The chance of getting a number that is greater than 2^20 (or <= -(2^20)) is therefore (98/99)^21 = 0.808 or 81%. This is all in theory though, and assuming that Math.random is truely random. It obviously isn't.

---

Snippet testing this code. Also in a more readable fashion.

var interval = 0;
var epic_unicorns = 0;
var unicorns = 0;

function gimmerandom() {
  var b = Math.round;
  var c = Math.random;
  var x = 0;
  while( b(c()*99) ) {
    x *= b(c()) ? 2 : -2;
    x += b(c());
  }
  return x;
}

function randomcount() {
  var a = gimmerandom();
  if( a <= -1000000 || a >= 1000000 ) {
    epic_unicorns++;
  }
  unicorns++;
  updatedisplay();
}

function updatedisplay() {
  $('#num_of_epicunicorns').text( epic_unicorns );
  $('#num_of_unicorns').text( unicorns );
  var perc = unicorns > 0 ? Math.round( (epic_unicorns / unicorns) * 1000 ) / 10 : 0;
  $('#perc_of_unicorns').text( perc );
}

$('#a').on( 'click', function() {
  clearInterval( interval );
  interval = setInterval( randomcount, 10 );
} );

$('#b').on( 'click', function() {
  clearInterval( interval );
} );

$('#c').on( 'click', function() {
  epic_unicorns = 0;
  unicorns = 0;
  updatedisplay();
} );

updatedisplay();
  

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<span id="num_of_epicunicorns"></span> / <span id="num_of_unicorns"></span> (<span id="perc_of_unicorns"></span>%) were larger than 1.000.000 or less than 1.000.000.

<br><br>
<input type="button" id="a" value="Start"> 
<input type="button" id="b" value="Stop"> 
<input type="button" id="c" value="Reset">

Answer 13

GolfScript, 20 bytes

0{)8.?rand}do.2&(*4/

Yeah, this one is also kind of slow.

Compared to languages like CJam and Pyth, GolfScript suffers from a verbose random number generation keyword (rand). To overcome this handicap, I needed to find a way to use it only once.

This code works by repeatedly picking a random number between 0 and 8⁸−1 = 16,777,215 inclusive, and incrementing a counter until the random number happens to be 0. The resulting counter value has a geometric distribution with a median approximately -1 / log₂(1 − 1/8⁸) &approx; 11,629,080, so it meets the "over 1,000,000 at least 50% of the time" test.

Alas, the random number thus generated is always strictly positive. Thus, the extra .2&(*4/ part is needed to let it become negative or zero. It works by extracting the second-lowest bit of the number (which is thus either 0 or 2), decrementing it to make it -1 or 1, multiplying it with the original number, and dividing the result by 4 (to get rid of the lowest two bits, which are now correlated with the sign, and also to allow the result to become zero). Even after the division by 4, the absolute value of the random number still has a median of -1 / log₂(1 − 1/8⁸) / 4 &approx; 2,907,270, so it still passes the 50% test.

Answer 14

JavaScript, 81 bytes

This code fulfills all the rules:

• Output any integer with positive probability
• Output integers outside the range of +/-1000000 with at least 50% probability
• No leading 0 in the output

As a bonus, the algorithm runs with a time complexity of O(log₁₀n) so it returns the integer almost instantly.

for(s="",r=Math.random;r()>.1;s+=10*r()|0);r(s=s.replace(/^0*/,"")||0)<.5?"-"+s:s

This assumes an REPL environment. Try running the above code in your browser's console, or use the stack snippet below:

D.onclick = function() {
  for(s="", r=Math.random;r()>.1; s+=10*r()|0);
  P.innerHTML += (r(s=s.replace(/^0*/,"") || 0) <.5 ?"-" + s : s) + "<br>"
}

<button id=D>Generate a random number</button><pre id=P></pre>

Algorithm:

• Keep appending random digits to string s until a Math.random() > 0.1.
• Based on Math.random() > 0.5, make the number negative (by prepending the string s with -).

This algorithm does not have a uniform distribution across all integers. Integers with higher digit count are less probable than the lower ones. In each for loop iteration, there is a 10% chance that I will stop at the current digit. I just have to make sure that I stop after 6 digits more than 50% of the time.

This equation by @nutki explains the maximum value of stopping chance percentage based on the above condition:

1 - 50%^(1/6) ≈ 0.11

Thus 0.1 is well within range to satisfy all the three rules of the question.

Answer 15

TI-BASIC, 14 bytes

1-2int(2rand:randNorm(AnsE6,9

Similar to @ssdecontrol's R answer, this draws from the Gaussian distribution with mean -1,000,000 or 1,000,000, chosen randomly, and standard deviation 9. The distribution is unbounded so in theory this can generate any integer.

Explanation:

1-2int(2rand     - get a random integer 0 or 1, then multiply by 2 and subtract 1
:                - this gives the number 1 or -1 (with equal probability) to Ans
randNorm(AnsE6,9 - displays Gaussian distribution with mean (Ans * 1,000,000) and std. dev. 9

Answer 16

Bash, 66

LANG=C sed -r '/^-?(0|[1-9][0-9]*)$/q;s/.*/5000000/;q'</dev/random

It almost always prints 5000000. But if it found a valid number in /dev/random, it will print that number instead.

And this one is faster:

LANG=C sed -r '/^-?(0|[1-9][0-9]*)$/q;s/.*/5000000/;q'</dev/urandom

Answer 17

C++, 95 bytes

void f(){int d=-18,s=-1;while(s<9){d=(rand()%19+d+9)%10;cout<<d;s=9-rand()%10*min(d*d+s+1,1);}}

Expanded:

void f() {
    int d=-18,s=-1;
    while(s<9) {
        d=(rand()%19+d+9)%10;
        cout<<d;
        s=9-rand()%10*min(d*d+s+1,1);
    }
}

Explanation:

The function keeps on printing consecutive random digits until a random valued switch takes the required value to stop the function. d is the variable that keeps the value of the next digit to be printed. s is the switch variable that takes random integer values in the interval [0, 9], if s == 9 then no more digits are printed and the funtion ends.

The variables d and s are initialized in order to give special treatment to the first digit (taking it from the interval [-9, 9] and if the first digit is zero then the function must end to avoid leading zeroes). The value of d could be assigned as d=rand()%10 but then the first digit couldn't be negative. d is assigned instead as d=(rand()%19+d+9)%10 and initialized at -18 so the first value of d will range from [-9, 9] and the next values will always range from [0, 9].

The variable s ranges randomly from [0, 9], and if s equals 9, the function ends, so after printing the first digit the next one will be printed with a probability of 90% (assuming rand() is truly random, and in order to satisfy the third condition). s could be easily assigned as s=rand()%10, however, there is an exception, if the first digit is zero, the function must end. In order to handle such exception, s has been assigned as s=9-rand()%10*min(d*d+s+1,1) and initialized as -1. If the first digit is zero, the min will return 0 and s will equal to 9-0=9. s variable's assignment will always range from [0, 9], so the exception can only occur at the first digit.

Characteristics (assuming rand() is truly random)

• The integer is printed digit by digit, with a fixed probability of 90% of printing another digit after printing the last one.

• 0 is the integer with highest chance of being printed, with a probability of aproximately 5.2%.

• The probability of printing an integer on the interval [-10^6, 10^6] is aproximately 44% (the calculation is not written here).

• Positive and negative integers are printed with the same probability (~47.4%).

• Not all digits are printed with the same probability. For example: in the middle of printing the integer, if the last digit was 5, the digit 3 will have a slightly lower chance of being printed next. In general, if the last digit was d, the digit (d+18)%10 will have a slightly lower chance of being printed next.

Example outputs (10 executions)

-548856139437
7358950092214
507
912709491283845942316784
-68
-6
-87614261
0
-5139524
7

Process returned 0 (0x0)   execution time : 0.928 s
Press any key to continue.

Answer 18

Java (JDK), 140 127 bytes

()->{int i;var o=System.out;for(o.print(i=(int)(19*Math.random())-10);i!=0&Math.random()<.9;)o.print((int)(11*Math.random()));}

-13 bytes by sneaking more logic into the loop header - thanks to @ceilingcat

Try it online!

Answer 19

Pyth, 11 bytes

WOyG~ZtOT)Z

Note: this program will probably crash with a memory error on any real computer. To test it, try replacing G with a shorter string, such as in this code, which generates numbers averaging around 28000:

pyth -c 'WOy"abcdefghijklm"~ZtOUT)Z'

This code loops, adding a random number from -1 to 8 to Z, with a 2^-26 probability of exiting the loop on each repetition. The 2^-26 probability is attained by selecting a random element (O) of the set of all subsets (y) of the alphabet (G).

Technical details & justification:

The probability 2^-26 is derived from two facts: y, when called on sequences, is the power-set function, an constructs the list of all subsets of the input. Since the input, G, is 26 characters long, this power-set, yG has 2^26 entries. OyG selects a random element from those 2^26 entries. Exactly one of those entries, the empty string, will evaluate as falsy when passed to W, the while loop. Therefore, there is a 2^-26 probability of exiting the loop each time.

In any fixed number of loop cycles K, the probability of getting the number K*3.5 + m and getting K*3.5 - m are equal, because each sequences of addends that achieves one total can be inverted, -1 -> 8, 0 -> 7, etc., to achieve the other. Additionally, numbers closer to K*3.5 are clearly more likely than numbers farther away. Thus, if K > 2000000/3.5 = 571428.5 the probability of getting a number over 1000000 is greater than 75%, because some of the results above that number can be put into a one-to-one correspondence with all of the results below that number, and the upper less-than-half, can be put into a one-to-one correspondence with those under 1000000. The probability of getting at least 571429 loops is (1-2^-26)^571429, which is no less than (1-2^-26 * 571429), the expected number of times leaving the loop over the first 571429 tries, which is 99.1%. Thus, on 99.1% or more of trials, there is a 75% or more chance of getting at least 1000000, so there is more than a 50% chance of getting over 1000000.

This code relies on a behavior of O where a bug was accidentally introduced 3 days ago and was fixed today. It should work on any version of Pyth 3 from before Dec 22nd, or after today. The following code is equivalent, and has always worked:

WOyG~ZtOUT)Z

Answer 20

Java, 113 bytes

void g(){String a=Math.random()>0?"10":"01";for(;Math.random()>0;)a+=(int)(Math.random()*2);System.out.print(a);}

This program prints a binary number to standard output stream. You might have to wait a while because the probability of it ending the number (or it being positive) is approximately 0. The idea that the absolute value of a number generated is less than 1 million is amusing, yet possible.

Ungolfed:

void g(){
    String a=Math.random()>0?"10":"01";             //Make sure there are no trailing zeroes.
    for(;Math.random()>0;)a+=(int)(Math.random()*2);//Add digits
    System.out.print(a);                            //Print
}

Sample output: Will post when a number is done being generated.