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]:+
Apart from noticing that your last example is way too long to fit in an integer, I think you should clarify that the program/function should have 50% probability of creating an integer within the bounds of -1.000.000 and +1.000.000 and outside as well. – GiantTree – 2014-12-25T21:42:30.783
I think the second rule should stop you from just outputting integers outside the range of +/-1.000.000 (100% > 50% so at least 50% is met) – GiantTree – 2014-12-25T22:27:34.010
@Optimizer I don't think so. The third rule makes it a real challenge as you need to define the probability for the integers on your own. If I generate 1000 integers, at least 500 of them have to be outside the range of +/-1.000.000. Normal implementations of random define all integers to have equal probability which is not asked for in the question. – GiantTree – 2014-12-25T22:32:45.503
@Optimizer Thats true the set is very small <strike>but the question asks for a change in probability</strike>. After thinking about the question it's obvious that the probability of generating an integer outside the range of +/-1.000.000 is more than 50%. Even more it's way more than 50% because the range of 2.000.000 integers in a set of 2^32 is about 0,04656612873077392578125% (checked with calculator). So the rest is the probability of integers outside that range, covering all the rules. (Shame on me noticing that so late) – GiantTree – 2014-12-25T22:44:55.100
Are we allowed to print leading zeros? – Martin Ender – 2014-12-25T23:56:04.500
2@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]. – hobbs – 2014-12-26T03:47:27.943
10A 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. – joeytwiddle – 2014-12-26T06:48:58.037
2@Ypnypn The computer's RAM isn't a limit, either. You don't have to store your partial output anywhere. – jimmy23013 – 2014-12-26T06:57:57.557
Many answers output leading zeros sometimes. Is that allowed? – jimmy23013 – 2014-12-26T07:07:48.100
4
@GiantTree -
– Fake Name – 2014-12-26T09:12:03.823way too long to fit in an integer
- This is only true if you assume thatinteger
means theint
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.@user23013 Leading zeros aren't allowed.
-0
is permitted. – randomra – 2014-12-26T09:16:13.957@FakeName I know. My answer uses BigInt so I don't have that problem. In the beginning I haven't thought about that. – GiantTree – 2014-12-26T11:57:06.477
5Anyone 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? – trichoplax – 2014-12-26T13:21:13.190
2@githubphagocyte You can assume that the random number generator of your language is a true random number generator even if it isn't the case. – randomra – 2014-12-26T13:38:16.687
People have touched on this point before, but can you clarify the "any integer" rule? Some integers in mathematics are too large for any computer that will ever exist to output digit by digit. What is "any integer"? – Muqo – 2014-12-27T16:15:42.147
@Muqo You're allowed to take infinite time to output infinite length answers. You don't have to count the digits you output, or anything, so finite RAM and infinite time will suffice, as long as every possible integer could in theory be the output of your program, with the right sequence of return values from
rand()
. – Peter Cordes – 2014-12-30T01:59:08.330@Peter Cordes Ah, so integers are simply what the output looks like. Really, this challenge is to output random digits on one line, not starting with 0, randomly stopping at some point while staying within the probability constraint. Since RAM is finite, I would think any entry storing the whole output would be invalid. – Muqo – 2014-12-30T05:18:32.867
1@Muqo, yeah I'd agree that everyone who went with arbitrary precision instead of outputting a stream picked wrong, with exceptions for things like JavaScript where there isn't really an output destination that can accept a stream of unknown length. And I guess it's interesting to see what people can do with toy languages for code-golfing, as long as the probability that they actually will use 4GB or something is vanishingly small. A theoretical turing machine has an infinitely long tape, so just run it on that. (if you can find an RNG on a turing machine :P) – Peter Cordes – 2014-12-30T12:28:30.823
function random() return 7; does this count? – Mark Knol – 2014-12-30T20:07:07.947