Dlaczego rand () w języku C ++ wydaje się generować tylko liczby tego samego rzędu wielkości?

146

W małej aplikacji napisanej w C / C ++ mam problem z randfunkcją i być może zalążkiem:

Chcę utworzyć sekwencję liczb losowych, które mają różne rzędy, tj. Mają różne wartości logarytmu (podstawa 2). Wydaje się jednak, że wszystkie uzyskane liczby są tego samego rzędu, wahając się między 2 ^ 25 a 2 ^ 30.

Czy to dlatego, że rand()jest zasiane czasem uniksowym, który jest obecnie stosunkowo dużą liczbą? O czym ja zapominam? Rozsiewam rand()tylko raz na początku main().

c++ c math random

— Tallaron Mathias
źródło

7

FWIW, czy to C czy C ++? Jeśli przez C / C ++ masz na myśli, że faktycznie możesz używać C ++, a wzmianka o C była po prostu przypadkowa, może to en.cppreference.com/w/cpp/numeric/random/binomial_distribution może pomóc.

— R. Martinho Fernandes

9

Niestety obstawiłeś niewłaściwego konia. Nasiona nie powinny być twoim problemem. Twoim problemem była nieprawidłowa oczekiwana dystrybucja. Ponieważ bezstronny programista spodziewałby rand()się zwrócić równomiernie rozłożone liczby (dokumentacja z wysokim rankingiem Google wyraźnie tak mówi), nie sądzę, aby to pytanie było przydatne dla przyszłych czytelników. Dlatego głosuj negatywnie, ale nie zniechęcaj się do używania SO.

— Cesarz Orionii

12

@ doug65536 "... gdzie żadna liczba się nie powtarza" - to nie jest przypadkowe! Mógłbym sfinansować swoją emeryturę przy stole do gry w kości, gdyby moje kości rand () nigdy nie zwracały tej samej liczby dwa razy, dopóki wszystkie możliwe liczby nie zostały zwrócone.

— Chris Gregg,

6

@GalacticCowboy Nie myl okresowości z powtórzeniami poszczególnych liczb. Z cytowanego artykułu w Wikipedii: „powtarzający się wynik nie oznacza, że został osiągnięty koniec okresu, ponieważ jego stan wewnętrzny może być większy niż wynik”. Byłoby bardzo, bardzo źle, gdyby PRNG wytwarzał wartość, a następnie miał gwarancję, że nie wytworzy tej wartości ponownie, dopóki wszystkie wartości nie zostaną zwrócone.

— Chris Gregg

12

Doug65536, nikt nie wybiera walk. Po prostu poprawnie stwierdzają, że się mylisz. PRNG mógłby całkiem szczęśliwie wypuścić następujące rzeczy, gdybym chciał RAND między 1 a 10: 2 4 7 2 8 1 5 9 7 3 To byłoby całkowicie poprawne, pomimo wielu 2 i 7. Myślę, że mylisz PRNG z funkcją tasowania na iPhonie.

— Relaks na Cyprze

479

Jest tylko 3% liczb od 1 do 2 ^30, które NIE są między 2 ²⁵ a 2 ³⁰ . Więc to brzmi całkiem normalnie :)

Ponieważ 2 ²⁵ /2 ³⁰ = 2 ^-5 = 1/32 = 0,03125 = 3,125%

— C4stor
źródło

36

Tak, słuszna uwaga! Jest 31 razy więcej liczb między 2 ^ 25 a 2 ^ 30 niż między 1 a 2 ^ 25 :) dzięki za szybką odpowiedź. Muszę więc przemyśleć program. Pytanie odpowiedział.

— Tallaron Mathias

1

@TallaronMathias Rozważ skrócenie liczby poprzez >>przesunięcie bitów - to da ci mniejsze liczby. (Lub biorąc moduł z %.)

— Sean Allred

13

Spodziewam się, że jest to oczywiste dla większości programistów: Każda liczba całkowita bez znaku mniej niż 2 ^ 25 musi mieć swoje pierwsze 7 bitów równa się 0- i jeśli każdy bit jest przypadkowy ...

— BlueRaja - Danny Pflughoeft

118

@ BlueRaja-DannyPflughoeft - gdyby prawdopodobieństwa były oczywiste, kasyna wypadłyby z biznesu.

— Brett Hale

26

@BrettHale - nie sądzę jednak, że programiści są docelową grupą demograficzną kasyna.

— EkoostikMartin

272

Jaśniejszy zielony to region między 0 a 2 ²⁵ ; ciemniejsza zieleń to obszar między 2 ²⁵ a 2 ³⁰ . Tiki mają moc 2.

dystrybucja

— Casey Chu
źródło

42

Musisz być bardziej precyzyjny: chcesz różnych wartości logarytmu o podstawie 2, ale jaki rozkład chcesz dla tego? Standardowe funkcje rand () generują równomierną dystrybucję, będziesz musiał przekształcić te dane wyjściowe za pomocą funkcji kwantyli związanej z żądaną dystrybucją.

Jeśli podasz nam dystrybucję, możemy Ci powiedzieć, jakiej quantilefunkcji potrzebujesz.

— Batszeba
źródło

13

+1, dystrybucja to kluczowy termin. Nie ma sensu mówić o liczbach losowych, kiedy nic nie wiadomo o rozkładzie. Mundur to tylko szczególny przypadek, aczkolwiek ważny. Może być dobrym miejscem na wskazanie różnych dystrybucji ze standardowej biblioteki C ++ 11.

— leftaround około

18

Jeśli chcesz różnych rzędów wielkości, dlaczego po prostu nie spróbować pow(2, rand())? A może wybierz kolejność bezpośrednio jako rand (), jak zasugerował Harold?

— aspiring_sarge
źródło

3

dobry pomysł, ale powinieneś poprawić swoją odpowiedź używając pow zamiast ^ (co jest logicznym operatorem xor, a nie potęgą, w języku C).

— kriss

6

Ponieważ rand()może wzrosnąć do RAND_MAX, naprawdę musisz przeskalować liczbę losową, aby wynik się nie przepełnił ...

— Floris

@Floris: ale jeśli wyskalujesz mały policzalny zakres w bardzo dużym zakresie, będziesz miał DUŻO dziur, co prawdopodobnie nie jest tym, czego oczekuje OP.

— André Caron

13

@ C4stor zrobił świetną uwagę. Ale dla bardziej ogólnego przypadku i łatwiejszego do zrozumienia dla człowieka (podstawa 10): dla zakresu od 1 do 10 ^ n ~ 90% liczb mieści się w przedziale od 10 ^ (n-1) do 10 ^ n, zatem ~ 99% liczb waha się od 10 ^ (n-2) do 10 ^ n. Dodawaj tyle miejsc po przecinku, ile chcesz.

Zabawna matematyka, jeśli będziesz to robić dla n, zobaczysz, że od 1 do 10 ^ n, 99,9999 ...% = 100% liczb to od 10 ^ 0 do 10 ^ n tą metodą.

Teraz o kodzie, jeśli chcesz losową liczbę o losowych rzędach wielkości, od 0 do 10 ^ n, możesz zrobić:

Wygeneruj małą liczbę losową od 0 do n
Jeśli znasz zakres, który ma n, wygeneruj dużą liczbę losową rzędu 10 ^ k, gdzie k> max {n}.
Wytnij dłuższą liczbę losową, aby uzyskać n cyfr tej dużej liczby losowej.

— Francisco Presencia
źródło

46

Masz całkowitą rację, ale aby uzyskać NAPRAWDĘ łatwą do zrozumienia odpowiedź, OP powinien zadać sobie pytanie, dlaczego 90% liczb losowych od 1 do 100 to dwie cyfry.

— Zapytaj o Monikę,

13

Podstawowa (i poprawna) odpowiedź została już podana i zaakceptowana powyżej: jest 10 liczb od 0 do 9, 90 liczb od 10 do 99, 900 od 100 do 999 itd.

Aby uzyskać wydajny obliczeniowo sposób uzyskania rozkładu o rozkładzie w przybliżeniu logarytmicznym, należy przesunąć w prawo liczbę losową o liczbę losową:

s = rand() & 31; // a random number between 0 and 31 inclusive, assuming RAND_MAX = 2^32-1
r = rand() >> s; // right shift

Nie jest doskonały, ale jest znacznie szybszy niż komputer pow(2, rand()*scalefactor) . Będzie „grudkowaty” w tym sensie, że rozkład będzie jednorodny dla liczb w ramach współczynnika 2 (jednolity dla 128 do 255, połowa gęstości dla 256 do 1023 itd.).

Oto histogram częstotliwości liczb od 0 do 31 (w próbkach 1M):

wprowadź opis obrazu tutaj

— Floris
źródło

czepianie się: to zachęca do bardzo małych liczb bardziej, niż można by się spodziewać. Prawdopodobieństwo uzyskania zera jest znacznie wyższe niż 10.

— Mooing Duck,

Cóż - chodzi o to, aby zachęcić małe liczby, więc cieszę się, że działa! Przeprowadziłem symulację Monte Carlo i daje mi to dwukrotny spadek prawdopodobieństwa, gdy liczby się podwajają - podobnie jak rozkład logów. Zaktualizowana odpowiedź ze zdjęciem.

— Floris

nie, mam na myśli, rand()>>(rand()&31);intuicyjnie można by oczekiwać, że 1/32 liczby będzie miała 32 bity, a 1/32 liczby miała 31 bitów, a 1/32 liczby miała 30 bitów itd. nie wyniki, które otrzymujesz, tylko około 1/64 liczby daje 32 bity, podczas gdy prawie połowa powinna wynosić 0. Ponieważ moja psychiczna matematyka nie zgadza się z twoimi pomiarami, będę musiał wykonać własne pomiary, aby obliczyć to na zewnątrz.

— Mooing Duck

2

Nie chcę powiedzieć, że twój kod jest zły. Prawdopodobnie to bym zrobił. Po prostu zasługuje na ostrzeżenie, że nie ma wyników tak rozłożone, jak można by się spodziewać.

— Mooing Duck,

1

Myślę, że problem wynika z myślenia o 0 jako liczbie 1-bitowej ... to rodzaj zagadki, na którą natrafisz, gdy mieszasz liczby całkowite i logarytmy. Ale to było dobre ćwiczenie i dałeś mi coś do przemyślenia. „Przetestuj ograniczenia swojego algorytmu” - nigdy się nie zestarzeje.

— Floris,

5

Jest dokładnie taka sama liczba liczb od 0 do 2 ^ 29 i 2 ^ 29 i 2 ^ 30.

Inny sposób spojrzenia na problem: rozważ binarną reprezentację generowanej liczby losowej, prawdopodobieństwo, że najwyższy bit to 1, równa się 1/2, a zatem otrzymujesz rząd 29 w połowie przypadków. Chcesz zobaczyć liczbę, która byłaby poniżej 2 ^ 25, ale to oznacza, że 5 najwyższych bitów to zero, co zdarza się z niskim prawdopodobieństwem 1/32. Są szanse, że nawet jeśli uruchomisz go przez długi czas, w ogóle nie zobaczysz zamówienia poniżej 15 (prawdopodobieństwo jest takie, jak wyrzucenie 6 6 razy z rzędu).

A teraz część twojego pytania o ziarno. Nie, ziarno prawdopodobnie nie może określić zakresu, z którego generowane są liczby, po prostu określa pierwszy, początkowy element. Pomyśl o rand () jako sekwencji wszystkich możliwych liczb w zakresie (z góry określona permutacja). Ziarno określa, gdzie zaczniesz rysować liczby z sekwencji. Dlatego jeśli chcesz (pseudo) losowości, do inicjalizacji sekwencji używasz bieżącego czasu: nie obchodzi cię, że pozycja, od której zaczynasz, nie jest równomiernie rozłożona, liczy się tylko to, że nigdy nie zaczynasz z tej samej pozycji.

— Vadim
źródło

2

jego użycie pow(2,rand()) da odpowiedzi w kolejności pożądanej wielkości !!

— Shivendra
źródło

2

Jeśli chcesz użyć liczb losowych z usługi online, możesz użyć do tego wget, możesz również zobaczyć, że możesz również użyć usług takich jak random.org do generowania liczb losowych, możesz je złapać za pomocą wget, a następnie odczytać liczby z pobrany plik

wget -q https://www.random.org/integers/?num=100&min=1&max=100&col=5&base=10&format=html&rnd=new -O new.txt

http://programmingconsole.blogspot.in/2013/11/a-better-and-different-way-to-generate.html

— Namit Sinha
źródło

Witamy w SO. proszę powstrzymać się od publikowania linków jako odpowiedzi. Możesz podać szczegółowy szkic odpowiedzi, pozostawiając szczegóły do przeczytania za pomocą linków.

— Shai