17
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ @Optimizer why are you assuming uniform probability? The question doesn't state it. In fact it seems clear from that point that the distribution doesn't have to be uniform as long as at least 50% of it falls outside of [-1 million, 1 million]. \$\endgroup\$ – hobbs Dec 26 '14 at 3:47
  • 10
    \$\begingroup\$ A solution that produces a "uniform distribution across all integers" is impossible. There are infinitely many integers, so each individual integer would appear with a probability of 0. (Or: Outputting a finite number would mean you are neglecting infinitely many others!) Any solution will have to disfavour higher values in order to achieve P(total)=1. \$\endgroup\$ – joeytwiddle Dec 26 '14 at 6:48
  • 2
    \$\begingroup\$ @Ypnypn The computer's RAM isn't a limit, either. You don't have to store your partial output anywhere. \$\endgroup\$ – jimmy23013 Dec 26 '14 at 6:57
  • 4
    \$\begingroup\$ @GiantTree - way too long to fit in an integer - This is only true if you assume that integer means the int datatype on a 32/64 bit arch, which is not necessarily a valid assumption. "Integer" started as a math term, which has no size constraints. \$\endgroup\$ – Fake Name Dec 26 '14 at 9:12
  • 5
    \$\begingroup\$ Anyone using a pseudo random number generator to make their decisions on the output will exclude almost all integers, and place an upper limit on the size of integers that can be produced (assuming that the PRNG has a finite period). Can this be disregarded in answers or does a valid answer require a true random number generator? \$\endgroup\$ – trichoplax Dec 26 '14 at 13:21

20 Answers 20

12
\$\begingroup\$

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 1012) 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*105). 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]:+
\$\endgroup\$
  • \$\begingroup\$ I've added a comment to the question to see if the rules require a true random number generator, but I guessed you would appreciate the pedantry. Is your random source here pseudo random? That would restrict the size of the set of possible outputs to at most the period of your PRNG, right? \$\endgroup\$ – trichoplax Dec 26 '14 at 13:29
  • \$\begingroup\$ (+1 regardless for the simple elegance) \$\endgroup\$ – trichoplax Dec 26 '14 at 13:30
  • \$\begingroup\$ Yes I'm guessing all so far. I'm curious to see if someone posts an answer without that problem though... \$\endgroup\$ – trichoplax Dec 26 '14 at 13:36
  • \$\begingroup\$ I see the OP has stated that you can assume your random number generator is a true random number generator whether it is or not - so this is redundant now... :) \$\endgroup\$ – trichoplax Dec 26 '14 at 13:52
  • \$\begingroup\$ The sum of Kmr in a period is still likely always a big positive number larger than the period. And it can't produce every possible number in that case. \$\endgroup\$ – jimmy23013 Dec 26 '14 at 14:34
11
\$\begingroup\$

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);}
\$\endgroup\$
  • \$\begingroup\$ Both of you are correct but the question states that the probability has to be at least 50% not in the range of +/-1.000.000 \$\endgroup\$ – GiantTree Dec 25 '14 at 22:18
  • \$\begingroup\$ @Optimizer Redone. \$\endgroup\$ – Ypnypn Dec 26 '14 at 17:19
  • \$\begingroup\$ If you use binary literals you don't have to print the -. \$\endgroup\$ – TheNumberOne Dec 27 '14 at 20:21
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ "This will produce an integer between -10^6 and 10^6 with probability 50.4985%." - that's not quite enough. Did you misread the spec? Perhaps you meant to use 10^7 as the variance? \$\endgroup\$ – John Dvorak Dec 26 '14 at 7:29
  • \$\begingroup\$ @JanDvorak Wrong probability, sorry. Now it's the right one. \$\endgroup\$ – swish Dec 26 '14 at 7:40
  • \$\begingroup\$ Does the implementation of this in Mathematica truly cover all integers? I don't have access to the source but I'd guess not... \$\endgroup\$ – trichoplax Dec 26 '14 at 13:34
  • \$\begingroup\$ @githubphagocyte It would depend on current precision. \$\endgroup\$ – swish Dec 26 '14 at 13:37
  • 4
    \$\begingroup\$ What I mean is, specifying any specific precision will exclude numbers bigger than that. The only way it could work is if you could specify unlimited precision. \$\endgroup\$ – trichoplax Dec 26 '14 at 14:34
4
\$\begingroup\$

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


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.

\$\endgroup\$
  • \$\begingroup\$ This won't be able to generate all integers, because the pseudo-random number generator has a finite amount of internal state. According to the documentation Python uses the Mersenne Twister, so the state is quite large. But it is not infinite, so it can only produce a finite subset of all integers. \$\endgroup\$ – starblue Dec 28 '14 at 9:57
  • \$\begingroup\$ @starblue: From the OP: "You can assume that the random number generator of your language is a true random number generator even if it isn't the case." \$\endgroup\$ – kennytm Dec 28 '14 at 11:50
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Yeah I realized I misread the spec. And I imagine it has the same limitations on machine precision with Mathematica \$\endgroup\$ – shadowtalker Dec 26 '14 at 15:23
  • \$\begingroup\$ Hmm in that case I'm not sure. I'll have to look into it; consider this answer "on hold" for now \$\endgroup\$ – shadowtalker Dec 26 '14 at 15:26
  • \$\begingroup\$ @MartinBüttner fixed I think \$\endgroup\$ – shadowtalker Dec 26 '14 at 15:30
  • \$\begingroup\$ Interesting. I don't think you need the whole sample(c(1,-1),1) think though. Just centering at 1e6 should be enough.. \$\endgroup\$ – Martin Ender Dec 26 '14 at 15:32
  • \$\begingroup\$ @MartinBüttner oh it doesn't need to be 50% at both ends? That wasn't clear \$\endgroup\$ – shadowtalker Dec 26 '14 at 15:33
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Doesn't this print "numbers" like -00000000167? That's not really an integer. \$\endgroup\$ – isaacg Dec 26 '14 at 5:09
  • 1
    \$\begingroup\$ @isaacg I don't see why that is not an integer . \$\endgroup\$ – Optimizer Dec 26 '14 at 7:42
  • 2
    \$\begingroup\$ @Optimizer It is, but the OP has explicitly forbidden leading 0. \$\endgroup\$ – Martin Ender Dec 26 '14 at 10:41
  • \$\begingroup\$ You could generate a random non-zero leading digit before the loop, from -9 to +9. print int(rand(20)-10)||1. I need a way to generate 0 as an output, though. Maybe ||die 0, if the trailing garbage after the zero is allowed. Else need a short way to print the zero and exit without further output if int(rand(20)-10)==0. \$\endgroup\$ – Peter Cordes Dec 28 '14 at 1:49
  • \$\begingroup\$ @PeterCordes agreed, that's a decent approach but I don't feel like writing it and I don't think it would be competitive length-wise. Feel free to submit it on your own :) \$\endgroup\$ – hobbs Dec 28 '14 at 1:52
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Didn't we agree that there should not be any upper/lower bounds ? For instance, the integer 2^31 + 1 has 0 probability, breaking rule 2 \$\endgroup\$ – Optimizer Dec 26 '14 at 1:06
  • \$\begingroup\$ @Optimizer for me an integer is defined as in many programming languages: a number within the bounds of -2^31 and +2^31-1 (32bits). You can easily increase the exponents if you'd like to generate larger integers but it may fail depending on the implementation of Perl. \$\endgroup\$ – GiantTree Dec 26 '14 at 1:12
  • \$\begingroup\$ I just saw that that ridiculously big integer has to be generated as well. I'll edit my code quickly. \$\endgroup\$ – GiantTree Dec 26 '14 at 1:14
  • \$\begingroup\$ @MartinBüttner I tried my best to meet the spec of the question. It's just not possible for me (at least not without help) to generate infinitely large integers. Perl's largest integer is about 1.7e308 which is a limit I cannot control. \$\endgroup\$ – GiantTree Dec 26 '14 at 1:46
  • \$\begingroup\$ @MartinBüttner Both are possible but eg. the string would overflow after 2gb of data making it finite again. It's hard to say that a number should be infinitely large if there are issues with memory. I'll come up with a different approach soon using BigInts. Also the integer does not overflow at 1.7e308 it just gets converted to infite (1.#INF to be exact) \$\endgroup\$ – GiantTree Dec 26 '14 at 1:53
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ When using using System;, you don't need System.Random twice, but just Random, right? \$\endgroup\$ – Charlie Dec 26 '14 at 8:57
  • \$\begingroup\$ @Charlie This is a function, so I can't use using statements. It would only save 1 char anyways. \$\endgroup\$ – LegionMammal978 Dec 26 '14 at 12:04
  • 1
    \$\begingroup\$ You can save 1 char by removing the space at -1E6, 1E6+1. \$\endgroup\$ – ProgramFOX Dec 26 '14 at 13:12
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Nice, you squeezed out some things that I wouldn't have thought of :) \$\endgroup\$ – hobbs Dec 28 '14 at 3:32
1
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ The OP has now confirmed that you can assume that your PRNG is truly random, even if it isn't. \$\endgroup\$ – trichoplax Dec 26 '14 at 14:01
1
\$\begingroup\$

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 88−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 / log2(1 − 1/88) ≈ 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 / log2(1 − 1/88) / 4 ≈ 2,907,270, so it still passes the 50% test.

\$\endgroup\$
1
\$\begingroup\$

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(log10n) 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.

\$\endgroup\$
  • \$\begingroup\$ There are a few things that confuse me about this answer. Have you assumed that Math.random() generates a uniform distribution of random numbers, because the spec states that it is implementation dependent. Assuming that it is a uniform distribution, P(Math.random()>0.1)=0.9 so there is a huge probability that it will terminate between each iteration. An implementation of your algorithm run on Firefox 34.0 Ubuntu gives me a probability of ~0.47 (<0.5) every time that I test it: jsfiddle.net/WK_of_Angmar/dh8gq4pb \$\endgroup\$ – Wk_of_Angmar Dec 28 '14 at 4:28
  • \$\begingroup\$ Also, how have you managed to calculate a time complexity for an algorithm without an input? \$\endgroup\$ – Wk_of_Angmar Dec 28 '14 at 4:28
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ But can it generate "2" or "-2"? \$\endgroup\$ – kennytm Dec 26 '14 at 16:31
  • \$\begingroup\$ Yes, obviously. tibasicdev.wikidot.com/randnorm \$\endgroup\$ – Timtech Dec 26 '14 at 16:31
  • 1
    \$\begingroup\$ OK read the code wrongly (thought : means "print" due to how the explanation is presented). But can it generate numbers more than 20 digits? \$\endgroup\$ – kennytm Dec 26 '14 at 16:34
  • \$\begingroup\$ Any arbitrary long integer is possible as an output ? Isn't this limited by the range of randNorm ? \$\endgroup\$ – Optimizer Dec 26 '14 at 16:34
  • \$\begingroup\$ "The distribution is unbounded so in theory this can generate any integer." There is no range. \$\endgroup\$ – Timtech Dec 27 '14 at 1:38
1
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ @Optimizer It is supposed to be slow. That's because it is a real random source. But you can test it with /dev/urandom which is less random. \$\endgroup\$ – jimmy23013 Dec 26 '14 at 16:44
  • \$\begingroup\$ @Optimizer How would that be taking manual input? It's reading a file, but everything's a file. \$\endgroup\$ – Nit Dec 27 '14 at 21:19
  • \$\begingroup\$ @Optimizer I simply don't understand the point you're going for. \$\endgroup\$ – Nit Dec 27 '14 at 22:56
  • \$\begingroup\$ reading from /dev/urandom in a shell script is basically the same as calling rand() in other languages. Although if you're really using bash, not POSIX sh, you can get random numbers from echo $RANDOM. wiki.ubuntu.com/DashAsBinSh gives hexdump /dev/urandom as an equivalent for bare-POSIX-minimum /bin/dash. \$\endgroup\$ – Peter Cordes Dec 28 '14 at 1:58
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ What happened to the online compiler ? \$\endgroup\$ – Optimizer Dec 26 '14 at 7:58
  • \$\begingroup\$ @Optimizer Issues with the website, I'll work on it. \$\endgroup\$ – isaacg Dec 26 '14 at 8:31
  • \$\begingroup\$ Ah.. cool. Wanted to work on the Pyth translation of my CJam answer yesterday and found that it gives 404. \$\endgroup\$ – Optimizer Dec 26 '14 at 8:35
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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