Twój program / funkcja powinna

• wypisuje dokładnie jedną liczbę całkowitą
• wyprowadza dowolną liczbę całkowitą z prawdopodobieństwem dodatnim
• wyprowadza liczbę całkowitą większą niż 1.000.000 lub mniejszą niż -1.000.000 z prawdopodobieństwem co najmniej 50%.

Przykładowe dane wyjściowe (wszystkie muszą być możliwe):

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

Wyjaśnienia:

• Dopuszczalne jest przerywanie linii końcowej.
• Zera wiodące są niedozwolone.
• -0 jest dozwolone.

Najkrótszy kod wygrywa.

CJam, 16 14 13 bajtów

0{Kmr(+esmr}g

Będzie to działało przez bardzo długi czas, ponieważ wykorzystuje bieżący znacznik czasu (rzędu 10 ¹² ), aby ustalić, czy pętla powinna się zakończyć. Używam tego jako przesłania, ponieważ jest najkrótszy, ale istnieją dwie 14-bajtowe alternatywy, które mają swoje zalety:

0{esmr(+esmr}g

Ten jest nie ograniczony przez okres PRNG, ponieważ zakres wszystkich liczb losowych zależy od aktualnej datownik. Dlatego powinno to być w stanie wygenerować dowolną liczbę, chociaż prawdopodobieństwo dla liczb ujemnych, a nawet małych liczb dodatnich, jest znikomo małe.

Poniżej znajduje się równoważna wersja, która używa 3e5zamiast znacznika czasu. I 20dla pierwszego zakresu (jako przesłanie 13-bajtowe). Jest znacznie szybszy i spełnia wszystkie zasady. Jest to rodzaj ograniczającego przypadku, aby uzyskać 50% prawdopodobieństwa dla liczb powyżej 1 000 000, przy zachowaniu rozsądnego czasu działania i małego rozmiaru kodu. Wyjaśnienie i matematyczne uzasadnienie odnoszą się do tej wersji:

0{Kmr(+3e5mr}g

Uruchomienie zajmuje zwykle kilka sekund. Można wymienić 5z 2aby go uruchomić nawet szybciej. Ale wtedy wymóg 50% prawdopodobieństwa zostanie spełniony tylko dla 1000 zamiast 1 000 000.

Zaczynam od 0. Potem mam pętlę, z której zerwałam z prawdopodobieństwem 1 / (3 * 10 ⁵ ). W tej pętli dodam losową liczbę całkowitą od -1 do 18 (włącznie) do mojej sumy bieżącej. Istnieje skończone (aczkolwiek małe) prawdopodobieństwo, że każda liczba całkowita zostanie wyprowadzona, przy czym liczby całkowite dodatnie są znacznie bardziej prawdopodobne niż wartości ujemne (nie sądzę, byś widział wartość ujemną w swoim życiu). Wybicie z tak małym prawdopodobieństwem i zwiększenie czasu (i dodanie znacznie więcej niż odejmowanie) gwarantuje, że zwykle przekroczymy 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.";

Niektóre matematyczne uzasadnienie:

• Na każdym kroku dodajemy średnio 8,5.
• Aby dostać się do 1 000 000, potrzebujemy 117 647 tych kroków.

• Prawdopodobieństwo, że zrobimy mniej niż ta liczba kroków, jest

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

  co ocenia na 0.324402. Dlatego w około dwóch trzecich przypadków podejmiemy więcej 117 647 kroków, a każdy z nich z łatwością 1 000 000.

• (Należy pamiętać, że nie jest to dokładne prawdopodobieństwo, ponieważ wystąpią pewne wahania dotyczące tych średnich 8,5, ale aby uzyskać 50%, musimy znacznie przekroczyć 117 646 do około 210 000 kroków).
• W razie wątpliwości możemy łatwo wysadzić mianownik prawdopodobieństwa zakończenia, nawet 9e9bez dodawania bajtów (ale lat pracy).

... lub 11 bajtów?

Wreszcie istnieje 11-bajtowa wersja, która nie jest również ograniczona przez okres PRNG, ale której zabraknie pamięci za każdym razem. Generuje tylko jedną liczbę losową (na podstawie znacznika czasu) podczas każdej iteracji i używa jej zarówno do zwiększania, jak i kończenia. Wyniki każdej iteracji pozostają na stosie i są sumowane tylko na końcu. Podziękowania dla Dennisa za ten pomysł:

{esmr(}h]:+

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

Przykładowe dane wyjściowe

-8288612864831065123773
0
660850844164689214
-92190983694570102879284616600593698307556468079819964903404819
3264

Bez golfa

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

Stara odpowiedź (przed zmianą reguły)

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

Mathematica - 47

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

Zasadniczo wystarczy wygenerować liczbę losową przy użyciu rozkładu normalnego z wariancją równą 1500000. To da liczbę całkowitą między -10 ^ 6 a 10 ^ 6 z prawdopodobieństwem 49,5015%.

Python 2, 75 69 bajtów

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

Trywialne jest sprawdzenie, czy pętla while w środku może generować wszystkie liczby całkowite (choć tendencyjne w kierunku zera). „12” wybiera się w taki sposób, że z grubsza połowa liczb przekracza ± 10 ⁶ .

Starsze rozwiązanie:

Python 2, 44 bajty

Na podstawie rozwiązania Mathematica .

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

Naprawdę nie działa, ponieważ Python floatma tylko skończoną precyzję.

Ruby, 70

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

Aby generowanie bardzo dużych liczb było możliwe, zwracam liczbę jako Stringz lambda. Jeśli nie jest to dozwolone, policz 8 dodatkowych znaków (for puts f[]), aby uczynić go programem zamiast funkcji.

Wyjaśnienie

Wygeneruj liczbę pomiędzy -1,000,000a 1,000,000. Jeśli liczba jest równa 1lub wyższa, liczba jest zwracana jako String.

Jeśli liczba jest niższa niż 1, funkcja jest wywoływana rekurencyjnie, aby zwrócić liczbę spoza zakresu liczb. Aby mieć pewność, że można również wygenerować liczby ujemne, -do wyniku powstaje a, Stringjeśli liczba początkowa jest większa niż -500,000.

Mam nadzieję, że poprawnie zrozumiałem wyzwanie!

R, 38

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

Dobiera z rozkładu Gaussa ze średnią 2 000 000 losowo dobranymi odchyleniami standardowymi 1 000 000, tak że około 2/3 losowań będzie mieścić się w przedziale od 1 000 000 do 3 000 000. Rozkład jest nieograniczony, więc teoretycznie może to generować dowolną liczbę całkowitą. Pakiet Rmpfr zastępuje wbudowane podwójne pływaki R z dowolną precyzją.

Perl, 53 znaki

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

Na pewno nie widzę powodu, aby pracować z liczbami całkowitymi podczas drukowania jednego :)

Ma równe prawdopodobieństwo wydrukowania liczby z wiodącym „-” lub bez niego.

Drukuje 1-cyfrową liczbę 10% czasu, 2-cyfrową liczbę 9% czasu, 3-cyfrową liczbę 8,1% czasu, 4-cyfrową liczbę 7,29% czasu, 5-cyfrową liczbę 6,56% czasu, 6-cyfrowa liczba 5,9% czasu itp. Możliwa jest dowolna długość ze zmniejszającym się prawdopodobieństwem. Liczby od jednego do pięciu cyfr stanowią około 41,5% przypadków wyjściowych, a liczba 1 000 000 (lub 1 000 000) tylko 6 milionów części procentowych, więc liczba wyjściowa będzie poza zakresem od 1 000 000 do 1 000 000 około 54,6 % czasu.

Zarówno „0”, jak i „-0” są możliwymi wyjściami, które, mam nadzieję, nie stanowią problemu.

Perl, 114 znaków

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

Awaria:

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

Prawdopodobieństwo uzyskania wartości od -1 000 000 do 1 000 000 zmierza w kierunku zera, ALE jest to możliwe.

Uwaga: ten podprogram może być uruchamiany przez długi czas i powodować błąd „Brak pamięci!” błąd, ale to technicznie generowania dowolnego liczbę całkowitą, jak podano w pytaniu.

Perl, 25

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

Generuje losową liczbę całkowitą w zakresie +/- 2 ^ 99.

Awaria

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

Testowany z 1 milionem próbek:

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

Spełnia to wszystkie zasady:

• 1 liczba całkowita
• dowolna liczba całkowita jest możliwa
• co najmniej 50% (w moim przypadku 99,99%) wszystkich wygenerowanych liczb całkowitych jest poza zakresem +/- 1.000.000.

Działa to, ponieważ leżący u podstaw generator liczb losowych określa równe prawdopodobieństwo dla każdego generowanego bitu, tym samym również na generowanych liczbach całkowitych.
Każda liczba całkowita ma prawdopodobieństwo wygenerowania 1/2 ^ 99.

Edytować:

Musiałem zwiększyć wykładnik, aby generowane były większe liczby całkowite. Wybrałem 99, ponieważ kod jest tak krótki, jak to możliwe.

DO#, 126 107 bajtów

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

Nie golfowany:

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

Szansa na wygenerowanie liczby n cyfr wynosi 1/2 (n-10), co jest większe niż 0 dla wszystkich dodatnich n, a 1/2 dla n = 11.Tworzy również wiodące zera, które nie wydają się być niedozwolone w pierwotnym pytaniu ani w żadnym z jego komentarzy.

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.

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

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⁸) ≈ 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 ≈ 2,907,270, so it still passes the 50% test.

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.

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

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

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.

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.

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

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.

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!