Biorąc pod uwagę funkcję, która generuje losową liczbę całkowitą z zakresu od 1 do 5, napisz funkcję, która generuje losową liczbę całkowitą z zakresu od 1 do 7.
- Jakie jest proste rozwiązanie?
- Jakie jest skuteczne rozwiązanie w celu zmniejszenia zużycia pamięci lub uruchomienia na wolniejszym procesorze?
7 * rand5() / 5
?Odpowiedzi:
Jest to odpowiednik rozwiązania Adama Rosenfielda, ale dla niektórych czytelników może być nieco bardziej jasne. Zakłada, że rand5 () jest funkcją, która zwraca statystycznie losową liczbę całkowitą z zakresu od 1 do 5 włącznie.
Jak to działa? Pomyśl o tym w ten sposób: wyobraź sobie wydrukowanie tej dwuwymiarowej tablicy na papierze, przyczepienie jej do planszy i losowe rzucanie w nią rzutkami. Jeśli osiągniesz wartość niezerową, jest to statystycznie losowa wartość od 1 do 7, ponieważ istnieje taka sama liczba wartości niezerowych do wyboru. Jeśli osiągniesz zero, po prostu rzucaj strzałką, aż osiągniesz wartość niezerową. Tak właśnie działa ten kod: indeksy i i losowo wybierają lokalizację na planszy, a jeśli nie uzyskamy dobrego wyniku, będziemy rzucać rzutkami.
Jak powiedział Adam, może to trwać wiecznie w najgorszym przypadku, ale statystycznie najgorszy przypadek nigdy się nie zdarza. :)
źródło
rand5
jest jednolity, każda komórka wvals
siatce ma jednakowe prawdopodobieństwo pobrania. Siatka zawiera dokładnie trzy kopie każdej liczby całkowitej w przedziale [1, 7] oraz cztery zera. Tak więc „nieprzetworzony” strumień wyników prowadzi do równomiernej mieszanki wartości [1, 7] plus niektórych zer, które występują odrobinę częściej niż jakakolwiek pojedyncza dozwolona wartość. Ale to nie ma znaczenia, ponieważ zera są usuwane, pozostawiając tylko równomierną mieszankę wartości [1, 7].Nie ma (dokładnie poprawnego) rozwiązania, które działałoby w stałym czasie, ponieważ 1/7 to nieskończona liczba dziesiętna w podstawie 5. Jednym prostym rozwiązaniem byłoby użycie próbkowania odrzucenia, np .:
Oczekiwany czas działania wynosi 25/21 = 1,19 iteracji pętli, ale istnieje nieskończenie małe prawdopodobieństwo zapętlenia na zawsze.
źródło
N
połączeńrand5()
. Następnie istnieje 5 ^ N możliwych wyników sekwencji wywołańrand5
, z których każde ma wynik 1-7. Tak więc, jeśli dodasz wszystkie możliwe sekwencje wywołań, których wyjście jestk
dla każdego 1≤k≤7, prawdopodobieństwo, że wyjście będzie wynosiłok
m / 5 ^ N, gdzie m jest liczbą takich sekwencji. Zatem m / 5 ^ N = 1/7, ale nie ma możliwych rozwiązań liczb całkowitych (N, m) dla tej ==> sprzeczności.Chciałbym dodać kolejną odpowiedź, oprócz mojej pierwszej odpowiedzi . Ta odpowiedź próbuje zminimalizować liczbę połączeń do
rand5()
każdego połączeniarand7()
, aby zmaksymalizować wykorzystanie losowości. Oznacza to, że jeśli uważasz przypadkowość za cenny zasób, chcemy wykorzystać jego jak najwięcej, bez wyrzucania losowych elementów. Ta odpowiedź ma również pewne podobieństwa z logiką przedstawioną w odpowiedzi Iwana .Entropia zmiennej losowej jest dobrze określona wielkość. Dla zmiennej losowej, która przyjmuje N stanów z jednakowymi prawdopodobieństwami (rozkład równomierny), entropia wynosi log 2 N. Zatem
rand5()
ma około 2,32193 bitów entropii irand7()
około 2,80735 bitów entropii. Jeśli mamy nadzieję zmaksymalizować wykorzystanie przypadkowości, musimy użyć wszystkich 2,32193 bitów entropii z każdego wywołaniarand5()
i zastosować je do wygenerowania 2.80735 bitów entropii potrzebnych dla każdego wywołania dorand7()
. Podstawowym ograniczeniem jest zatem to, że nie możemy zrobić nic lepszego niż log (7) / log (5) = 1,20906 wywołańrand5()
na połączenie zrand7()
.Dodatkowe uwagi: wszystkie logarytmy w tej odpowiedzi będą podstawą 2, chyba że określono inaczej.
rand5()
zakłada się, że zwracają liczby z zakresu [0, 4] irand7()
przyjmowane są, że zwracają liczby z zakresu [0, 6]. Dostosowanie zakresów odpowiednio do [1, 5] i [1, 7] jest banalne.Więc jak to zrobimy? Generujemy nieskończenie precyzyjną losową liczbę rzeczywistą z przedziału od 0 do 1 (udawajmy, że możemy faktycznie obliczyć i zapisać tak nieskończenie dokładną liczbę - naprawimy to później). Możemy wygenerować taki numer, generując jego cyfry w bazie 5: wybieramy losową liczbę 0.
a
1a
2a
3 ..., gdzie każda cyfra ai
jest wybierana przez wywołanie dorand5()
. Na przykład, jeśli nasz RNG wybrałi
dla wszystkich wartość a = 1i
, to ignorując fakt, że nie jest to zbyt losowe, odpowiadałoby to rzeczywistej liczbie 1/5 + 1/5 2 + 1/5 3 + ... = 1/4 (suma szeregu geometrycznego).Ok, więc wybraliśmy losową liczbę rzeczywistą od 0 do 1. Teraz twierdzę, że taka losowa liczba jest równomiernie rozłożona. Intuicyjnie jest to łatwe do zrozumienia, ponieważ każda cyfra została wybrana jednolicie, a liczba jest nieskończenie dokładna. Jednak formalny dowód na to jest nieco bardziej zaangażowany, ponieważ teraz mamy do czynienia z rozkładem ciągłym zamiast rozkładem dyskretnym, więc musimy udowodnić, że prawdopodobieństwo, że nasza liczba leży w przedziale [
a
,b
] jest równe długości że interwałb - a
. Dowód pozostaje jako ćwiczenie dla czytelnika =).Teraz, gdy mamy losową liczbę rzeczywistą wybraną równomiernie z zakresu [0, 1], musimy przekonwertować ją na serię równomiernie losowych liczb z zakresu [0, 6], aby wygenerować wynik
rand7()
. Jak to robimy? Po prostu odwrotność tego, co właśnie zrobiliśmy - konwertujemy go na nieskończenie dokładny dziesiętny w podstawie 7, a następnie każda podstawowa cyfra 7 odpowiada jednemu wyjściurand7()
.Biorąc przykład z wcześniejszego, jeśli nasz
rand5()
wytworzy nieskończony strumień 1, nasza losowa liczba rzeczywista wyniesie 1/4. Konwertując 1/4 na podstawę 7, otrzymujemy nieskończoną liczbę dziesiętną 0,15151515 ..., więc będziemy produkować jako dane wyjściowe 1, 5, 1, 5, 1, 5 itd.Ok, więc mamy główny pomysł, ale pozostały nam dwa problemy: nie jesteśmy w stanie obliczyć ani zapisać nieskończenie dokładnej liczby rzeczywistej, więc jak sobie z tym poradzić? Po drugie, jak faktycznie przekonwertować go na bazę 7?
Jednym ze sposobów konwersji liczby od 0 do 1 na bazę 7 jest:
Aby poradzić sobie z problemem nieskończonej precyzji, obliczamy wynik częściowy, a także przechowujemy górną granicę możliwego wyniku. To znaczy, załóżmy, że zadzwoniliśmy
rand5()
dwa razy i wrócił 1 razy. Dotychczas wygenerowaliśmy liczbę 0,11 (podstawa 5). Niezależnie od reszty nieskończonej serii wywołań dorand5()
wygenerowania, losowa liczba rzeczywista, którą generujemy, nigdy nie będzie większa niż 0,12: zawsze jest prawdą, że 0,11 ≤ 0,11xyz ... <0,12.Tak więc, śledząc do tej pory bieżącą liczbę i maksymalną wartość, jaką kiedykolwiek mogła przyjąć, konwertujemy obie liczby na bazę 7. Jeśli zgadzają się co do pierwszych
k
cyfr, możemy bezpiecznie wyprowadzić kolejnek
cyfry - niezależnie od tego, co nieskończony strumień podstawowych cyfr 5, nigdy nie wpłyną one na kolejnek
cyfry reprezentacji podstawowej 7!I to jest algorytm - aby wygenerować następny wynik
rand7()
, generujemy tylko tyle cyfr,rand5()
ile potrzebujemy, aby upewnić się, że znamy z pewnością wartość następnej cyfry w przeliczeniu losowej liczby rzeczywistej na bazę 7. Oto implementacja Python z testową wiązką:Zwróć uwagę, że
rand7_gen()
zwraca generator, ponieważ ma stan wewnętrzny polegający na konwersji liczby na bazę 7. Wiązka testowa wywołujenext(r7)
10000 razy w celu wygenerowania 10000 liczb losowych, a następnie mierzy ich rozkład. Używana jest tylko matematyka liczb całkowitych, więc wyniki są dokładnie poprawne.Zauważ też, że liczby tutaj stają się bardzo duże, bardzo szybkie. Moce 5 i 7 rosną szybko. Dlatego wydajność zacznie się zauważalnie obniżać po wygenerowaniu wielu liczb losowych z powodu arytmetyki bignum. Pamiętaj jednak, że moim celem było maksymalne wykorzystanie losowych bitów, a nie maksymalizacja wydajności (chociaż jest to cel drugorzędny).
W jednym z nich wykonałem 12091 wywołań
rand5()
dla 10000 wywołańrand7()
, osiągając minimum wywołań log (7) / log (5) średnio do 4 cyfr znaczących, a wynikowy wynik był jednolity.W celu portu to kod języka, który nie posiada dowolnie duże liczby całkowite wbudowany, musisz cap wartości
pow5
ipow7
maksymalnej wartości swojej rodzimej zintegrowanym typu - jeśli staną się zbyt duże, a następnie zresetować wszystko i zacznij od nowa. Zwiększyrand5()
torand7()
bardzo nieznacznie średnią liczbę wywołań na połączenie , ale mam nadzieję, że nie powinno to zbytnio wzrosnąć nawet dla liczb całkowitych 32- lub 64-bitowych.źródło
(Ukradłem odpowiedź Adama Rosenfelda i sprawiłem, że działa o około 7% szybciej).
Załóżmy, że rand5 () zwraca jeden z {0,1,2,3,4} z jednakowym rozkładem, a celem jest return {0,1,2,3,4,5,6} z jednakowym rozkładem.
Śledzimy największą wartość, jaką pętla może uzyskać w zmiennej
max
. Jeśli dotychczasowy wynik mieści się w przedziale od maks.% 7 do maks. 1, wynik będzie równomiernie rozproszony w tym zakresie. Jeśli nie, używamy reszty, która jest losowa między 0 a maks.% 7-1, oraz innego wywołania funkcji rand () w celu utworzenia nowego numeru i nowego maksimum. Potem zaczynamy od nowa.Edycja: Oczekuj, ile razy wywołanie rand5 () wynosi x w tym równaniu:
źródło
5 * rand5() + rand5()
.Algorytm:
7 można przedstawić w sekwencji 3 bitów
Użyj rand (5), aby losowo wypełnić każdy bit 0 lub 1.
Na przykład: call rand (5) i
jeśli wynik to 1 lub 2, wypełnij bit 0,
jeśli wynik to 4 lub 5, wypełnij bit 1,
jeśli wynik to 3, a następnie zignoruj i zrób to ponownie (odrzucenie)
W ten sposób możemy wypełnić 3 bity losowo 0/1, a tym samym uzyskać liczbę od 1-7.
EDYCJA: To wydaje się być najprostszą i najwydajniejszą odpowiedzią, więc oto dla niej kod:
źródło
źródło
Edycja: To nie do końca działa. Jest wyłączony o około 2 części na 1000 (przy założeniu idealnego rand5). Wiadra otrzymują:
Przełączając na sumę
wydaje się zyskać rząd wielkości na każde 2 dodane
BTW: powyższa tabela błędów nie została wygenerowana przez próbkowanie, ale przez następującą relację powtarzalności:
źródło
źródło
ans += (r < 3) << i
Poniżej przedstawiono rozkład równomierny na {1, 2, 3, 4, 5, 6, 7} przy użyciu generatora liczb losowych, wytwarzając rozkład równomierny na {1, 2, 3, 4, 5}. Kod jest niechlujny, ale logika jest jasna.
źródło
W przeciwieństwie do wybranego rozwiązania algorytm będzie działał w stałym czasie. Wykonuje jednak 2 połączenia z rand5 więcej niż średni czas działania wybranego rozwiązania.
Pamiętaj, że ten generator nie jest doskonały (liczba 0 ma o 0,0064% większą szansę niż jakakolwiek inna liczba), ale dla większości praktycznych celów gwarancja stałego czasu prawdopodobnie przewyższa tę niedokładność.
Wyjaśnienie
To rozwiązanie wywodzi się z faktu, że liczba 15 624 jest podzielna przez 7, a zatem jeśli możemy losowo i jednolicie wygenerować liczby od 0 do 15 624, a następnie wziąć mod 7, możemy uzyskać prawie jednolity generator rand7. Liczby od 0 do 15 624 można równomiernie wygenerować, rzucając 6 razy 6 rand i używając ich do utworzenia cyfr liczby podstawowej 5 w następujący sposób:
Właściwości mod 7 pozwalają jednak nieco uprościć równanie:
Więc
staje się
Teoria
Liczba 15,624 nie została wybrana losowo, ale można ją odkryć za pomocą małego twierdzenia Fermata, które stwierdza, że jeśli p jest liczbą pierwszą, to
To daje nam
(5 ^ 6) -1 jest równe
Jest to liczba w postaci podstawowej 5, dlatego możemy zobaczyć, że ta metoda może być użyta do przejścia z dowolnego generatora liczb losowych do dowolnego innego generatora liczb losowych. Chociaż przy zastosowaniu wykładnika p-1 zawsze pojawia się niewielkie odchylenie w kierunku 0.
Aby uogólnić to podejście i być bardziej dokładnym, możemy mieć taką funkcję:
źródło
Czy dozwolone są tutaj zadania domowe?
Ta funkcja wykonuje surową matematykę „base 5”, aby wygenerować liczbę od 0 do 6.
źródło
Jeśli weźmiemy pod uwagę dodatkowe ograniczenie związane z próbą udzielenia najskuteczniejszej odpowiedzi, tj. Taką, która poda strumień wejściowy
I
, o równomiernie rozłożonych liczbach całkowitych o długościm
od 1-5, wyprowadza strumieńO
, o równomiernie rozłożonych liczbach całkowitych od 1-7 o najdłuższej długości względnej dom
, powiedzmyL(m)
.Najprostszym sposobem na analizę tego jest traktowanie strumieni I i
O
odpowiednio liczb 5-arylowych i 7-arytowych. Osiąga się to dzięki głównej odpowiedzi na pomysł pobrania strumieniaa1, a2, a3,... -> a1+5*a2+5^2*a3+..
i podobnie do strumieniaO
.Jeśli weźmiemy część strumienia wejściowego o długości,
m choose n s.t. 5^m-7^n=c
gdziec>0
i jest tak mała, jak to możliwe. Następnie istnieje jednolita mapa od strumienia wejściowego o długości m do liczb całkowitych od1
do5^m
i kolejna jednolita mapa od liczb całkowitych od 1 do7^n
strumienia wyjściowego o długości n, w którym możemy być zmuszeni stracić kilka przypadków ze strumienia wejściowego, gdy odwzorowana liczba całkowita przekracza7^n
.Daje to wartość
L(m)
około,m (log5/log7)
która jest w przybliżeniu.82m
.Trudność z powyższą analizą stanowi równanie,
5^m-7^n=c
które nie jest łatwe do dokładnego rozwiązania, oraz przypadek, w którym jednorodna wartość od1
do5^m
przekracza7^n
i tracimy wydajność.Pytanie brzmi, jak blisko najlepszej możliwej wartości m (log5 / log7) można osiągnąć. Na przykład, kiedy liczba ta zbliża się do liczby całkowitej, czy możemy znaleźć sposób na osiągnięcie tej dokładnej całkowitej liczby wartości wyjściowych?
Jeśli
5^m-7^n=c
następnie ze strumienia wejściowego skutecznie generujemy jednolitą liczbę losową od0
do(5^m)-1
i nie używamy żadnych wartości wyższych niż7^n
. Wartości te można jednak uratować i wykorzystać ponownie. Skutecznie generują jednolitą sekwencję liczb od 1 do5^m-7^n
. Możemy więc spróbować ich użyć i przekonwertować na liczby 7-arytowe, abyśmy mogli stworzyć więcej wartości wyjściowych.Jeśli pozwolimy
T7(X)
być średnią długością sekwencji wyjściowejrandom(1-7)
liczb całkowitych uzyskanych z jednolitego wejścia wielkościX
, i zakładając, że5^m=7^n0+7^n1+7^n2+...+7^nr+s, s<7
.Zatem,
T7(5^m)=n0x7^n0/5^m + ((5^m-7^n0)/5^m) T7(5^m-7^n0)
ponieważ mamy długość bez sekwencji z prawdopodobieństwem 7 ^ n0 / 5 ^ m z resztą długości5^m-7^n0
z prawdopodobieństwem(5^m-7^n0)/5^m)
.Jeśli po prostu będziemy zastępować, otrzymamy:
W związku z tym
Innym sposobem na przedstawienie tego jest:
Najlepszy możliwy przypadek to mój oryginalny powyżej, gdzie
5^m=7^n+s
, gdzies<7
.Tak
T7(5^m) = nx(7^n)/(7^n+s) = n+o(1) = m (Log5/Log7)+o(1)
jak poprzednio.Najgorszym przypadkiem jest, gdy możemy znaleźć tylko k i st 5 ^ m = kx7 + s.
Inne przypadki są gdzieś pomiędzy. Interesujące byłoby zobaczyć, jak dobrze możemy sobie radzić z bardzo dużym m, tj. Jak dobrze możemy uzyskać warunek błędu:
e(m) = o(1)
Ogólnie wydaje się to niemożliwe, ale mamy nadzieję, że możemy to udowodniće(m)=o(m)
.Całość opiera się na rozkładzie 7-arytowych cyfr
5^m
dla różnych wartościm
.Jestem pewien, że istnieje wiele teorii, które to obejmują. W pewnym momencie mogę się przyjrzeć i zdać relację.
źródło
Oto działająca implementacja odpowiedzi Adama na język Python .
Lubię wrzucać algorytmy, na które patrzę, do Pythona, aby móc się nimi bawić, pomyślałem, że opublikuję to tutaj w nadziei, że przyda się komuś tam, a nie, że zajęło to dużo czasu.
źródło
rand5()
jest przyzwoity PRNG, to pętla nie będzie nieskończona, ponieważ ostatecznie5*(rand5() - 1) + rand5()
będzie na pewno <= 21.)Dlaczego nie zrobić tego prosto?
Szanse na uzyskanie 1 i 7 w tym rozwiązaniu są niższe z powodu modulo, jednak jeśli chcesz tylko szybkiego i czytelnego rozwiązania, jest to dobra droga.
źródło
Zakładając, że rand (n) oznacza tutaj „losową liczbę całkowitą w jednolitym rozkładzie od 0 do n-1 ”, oto przykładowy kod wykorzystujący randinta Pythona, który ma taki efekt. Używa tylko randinta (5) i stałych, aby uzyskać efekt randinta (7) . Właściwie to trochę głupie
źródło
do ... while
. To mogło być1337
, lub12345
, lub dowolną liczbę> 1.Prawidłowa odpowiedź Adama Rosenfielda jest następująca:
Kiedy n jest równe 2, masz 4 możliwości wyrzucenia: y = {22, 23, 24, 25}. Jeśli użyjesz n równa się 6, masz tylko 1 rzut z autu: y = {15625}.
5 ^ 6 = 15625
7 * 2232 = 15624
Dzwonisz do rand5 więcej razy. Masz jednak znacznie mniejszą szansę na uzyskanie wartości wyrzucenia (lub nieskończonej pętli). Jeśli istnieje sposób, aby uzyskać żadną możliwą wartość odrzucenia dla y, jeszcze jej nie znalazłem.
źródło
Oto moja odpowiedź:
Jest to trochę bardziej skomplikowane niż inne, ale uważam, że minimalizuje połączenia z rand5. Podobnie jak w przypadku innych rozwiązań, istnieje małe prawdopodobieństwo, że może zapętlić się przez długi czas.
źródło
Prosty i wydajny:
(Zainspirowany swoją ulubioną kreskówką „programistą”? ).
źródło
Dopóki nie ma już siedmiu możliwości do wyboru, narysuj kolejną liczbę losową, która pomnaża liczbę możliwości przez pięć. W Perlu:
źródło
$possibilities
zawsze musi wzrosnąć do 25, aby wyjść z pętli i powrócić. Zatem twoim pierwszym wynikiem jest[0-124] % 7
, który nie jest równomiernie rozłożony, ponieważ125 % 7 != 0
(w rzeczywistości jest to 6).Nie lubię zakresów zaczynających się od 1, więc zacznę od 0 :-)
źródło
from collections import defaultdict def r7(n): if not n: yield [] else: for i in range(1, 6): for j in r7(n-1): yield [i] + j def test_r7(): d = defaultdict(int) for x in r7(6): s = (((((((((x[5] * 5) + x[4]) * 5) + x[3]) * 5) + x[2]) * 5) + x[1]) * 5) + x[0] if s <= 15623: d[s % 7] += 1 print d
Proszę bardzo, jednolita dystrybucja i zerowe połączenia rand5.
Musisz wcześniej ustawić ziarno.
źródło
Wiem, że odpowiedź została udzielona, ale czy to wydaje się działać poprawnie, ale nie mogę powiedzieć, czy ma tendencyjność. Moje „testowanie” sugeruje, że jest to co najmniej uzasadnione.
Być może Adam Rosenfield byłby na tyle uprzejmy, aby skomentować?
Mój (naiwny?) Pomysł jest taki:
Kumuluj rand5, dopóki nie będzie wystarczającej liczby losowych bitów, aby utworzyć rand7. To zajmuje najwyżej 2 rand5. Aby uzyskać liczbę rand7, używam skumulowanej wartości mod 7.
Aby uniknąć przepełnienia akumulatora, a ponieważ akumulator ma mod 7, biorę mod 7 z akumulatora:
Funkcja rand7 () wygląda następująco:
(Pozwoliłem, aby zakres rand5 wynosił 0-4, a rand7 również 0-6.)
Edycja: Dodano wyniki dla 100 milionów prób.
'Prawdziwe' funkcje randa mod 5 lub 7
rand5: avg = 1.999802 0: 20003944 1: 19999889 2: 20003690 3: 19996938 4: 19995539 rand7: avg = 3.000111 0: 14282851 1: 14282879 2: 14284554 3: 14288546 4: 14292388 5: 14288736 6: 14280046
Mój rand7
Średnia wygląda dobrze, a rozkłady liczb też wyglądają dobrze.
randt: avg = 3.000080 0: 14288793 1: 14280135 2: 14287848 3: 14285277 4: 14286341 5: 14278663 6: 14292943
źródło
Istnieją eleganckie algorytmy cytowane powyżej, ale jest na to jeden sposób, choć może to być rondo. Zakładam wartości wygenerowane z 0.
R2 = generator liczb losowych podający wartości mniejsze niż 2 (przestrzeń próbki = {0, 1})
R8 = generator liczb losowych podający wartości mniejsze niż 8 (przestrzeń próbek = {0, 1, 2, 3, 4, 5, 6, 7 })
Aby wygenerować R8 z R2, uruchomisz R2 trzy razy i użyjesz połączonego wyniku wszystkich 3 przebiegów jako liczby binarnej z 3 cyframi. Oto zakres wartości, gdy R2 jest uruchamiany trzy razy:
0 0 0 -> 0
.
.
1 1 1 -> 7
Teraz, aby wygenerować R7 z R8, po prostu uruchamiamy R7 ponownie, jeśli zwraca 7:
Rozwiązaniem ronda jest wygenerowanie R2 z R5 (tak jak wygenerowaliśmy R7 z R8), następnie R8 z R2, a następnie R7 z R8.
źródło
Oto rozwiązanie, które całkowicie pasuje do liczb całkowitych i zawiera się w granicach około 4% wartości optymalnej (tzn. Używa 1,26 liczb losowych w {0..4} dla każdego w {0..6}). Kod jest w Scali, ale matematyka powinna być dość jasna w każdym języku: wykorzystujesz fakt, że 7 ^ 9 + 7 ^ 8 jest bardzo bliskie 5 ^ 11. Więc wybierasz 11-cyfrową liczbę w bazie 5, a następnie interpretujesz ją jako 9-cyfrową liczbę w bazie 7, jeśli jest ona w zakresie (dając 9 liczb 7 liczb podstawowych), lub jako 8-cyfrową liczbę, jeśli jest powyżej 9-cyfrowej liczby itp. .:
Jeśli wkleisz test do interpretera (faktycznie REPL), otrzymasz:
Rozkład jest ładny i płaski (w granicach około 10k z 1/7 z 10 ^ 8 w każdym przedziale, zgodnie z oczekiwaniami z rozkładu około Gaussa).
źródło
Używając ruchomej sumy , możesz jedno i drugie
Oba te problemy stanowią problem w przypadku uproszczonych
rand(5)+rand(5)...
rozwiązań. Poniższy kod Pythona pokazuje, jak go zaimplementować (większość z nich potwierdza dystrybucję).Ten wynik pokazuje wyniki:
Uproszczenie
rand(5)+rand(5)
, ignorowanie przypadków, w których zwraca więcej niż 6, ma typową wariację 18%, 100 razy większą niż metoda pokazana powyżej:I, za radą Nixuz, wyczyściłem skrypt, abyś mógł po prostu wypakować i użyć tych
rand7...
rzeczy:źródło
Ta odpowiedź jest raczej eksperymentem w uzyskiwaniu jak największej entropii z funkcji Rand5. t jest zatem nieco niejasny i prawie na pewno dużo wolniejszy niż inne implementacje.
Zakładając równomierny rozkład od 0-4 i wynikający z tego równomierny rozkład od 0-6:
Liczba bitów dodanych do bufora na połączenie do Rand5 wynosi obecnie 4/5 * 2, a więc 1,6. Jeśli uwzględniona zostanie wartość prawdopodobieństwa 1/5, to wzrośnie o 0,05, więc 1,65, ale zobacz komentarz w kodzie, w którym musiałem to wyłączyć.
Bity zużywane przez połączenie z Rand7 = 3 + 1/8 * (3 + 1/8 * (3 + 1/8 *) (...
To jest 3 + 3/8 + 3/64 + 3/512 ... więc około 3,42
Wydobywając informacje z siódemek odzyskuję 1/8 * 1/7 bitów na połączenie, czyli około 0,018
Daje to zużycie netto 3,4 bitów na połączenie, co oznacza, że stosunek wynosi 2.125 połączeń do Rand5 dla każdego Rand7. Optymalne powinno być 2.1.
Wyobrażam sobie, że takie podejście jest znacznie wolniejsze niż w przypadku wielu innych tutaj, chyba że koszt połączenia z Rand5 jest wyjątkowo drogi (powiedzmy wywołanie jakiegoś zewnętrznego źródła entropii).
źródło
w php
pętle tworzą losową liczbę między 16 a 127, dzieli przez szesnaście, aby utworzyć liczbę zmiennoprzecinkową między 1 a 7,9375, a następnie zaokrągla w dół, aby uzyskać liczbę całkowitą od 1 do 7. Jeśli się nie mylę, istnieje szansa 16/112 dowolny z 7 wyników.
źródło
źródło
7 = 111b
zp(7) = 8 / 125
Wydaje mi się, że mam cztery odpowiedzi, dwie z dokładnymi rozwiązaniami, takimi jak @Adam Rosenfield, ale bez problemu z nieskończoną pętlą, i dwie z prawie perfekcyjnym rozwiązaniem, ale szybszą implementacją niż pierwsza.
Najlepsze dokładne rozwiązanie wymaga 7 połączeń z
rand5
, ale przejdźmy dalej, aby zrozumieć.Metoda 1 - Dokładnie
Siła odpowiedzi Adama polega na tym, że zapewnia on idealnie równomierny rozkład i istnieje bardzo duże prawdopodobieństwo (21/25), że potrzebne będą tylko dwa wywołania funkcji rand5 (). Jednak najgorszym przypadkiem jest nieskończona pętla.
Pierwsze rozwiązanie poniżej zapewnia również idealną jednolitą dystrybucję, ale wymaga w sumie 42 połączeń z
rand5
. Brak nieskończonych pętli.Oto implementacja R:
Dla osób niezaznajomionych z R dostępna jest uproszczona wersja:
Dystrybucja
rand5
zostanie zachowana. Jeśli wykonamy matematykę, każda z 7 iteracji pętli ma 5 ^ 6 możliwych kombinacji, więc całkowita liczba możliwych kombinacji to(7 * 5^6) %% 7 = 0
. W ten sposób możemy podzielić wygenerowane liczby losowe na równe grupy po 7. Patrz metoda druga, aby uzyskać więcej dyskusji na ten temat.Oto wszystkie możliwe kombinacje:
Myślę, że łatwo jest pokazać, że metoda Adama będzie działać znacznie szybciej. Prawdopodobieństwo, że
rand5
w rozwiązaniu Adama jest 42 lub więcej wywołań , jest bardzo małe ((4/25)^21 ~ 10^(-17)
).Metoda 2 - Nie jest dokładna
Teraz druga metoda, która jest prawie jednolita, ale wymaga 6 wywołań w celu
rand5
:Oto uproszczona wersja:
Jest to w zasadzie jedna iteracja metody 1. Jeśli wygenerujemy wszystkie możliwe kombinacje, oto wynikowe liczby:
Jedna liczba pojawi się ponownie w
5^6 = 15625
próbach.Teraz, w metodzie 1, dodając 1 do 6, przenosimy liczbę 2233 do każdego kolejnego punktu. Tak więc łączna liczba kombinacji będzie się zgadzać. Działa to, ponieważ 5 ^ 6 %% 7 = 1, a następnie robimy 7 odpowiednich odmian, więc (7 * 5 ^ 6 %% 7 = 0).
Metoda 3 - Dokładnie
Jeśli argument metody 1 i 2 jest zrozumiany, następuje metoda 3 i wymaga tylko 7 wywołań do
rand5
. W tym momencie uważam, że jest to minimalna liczba połączeń potrzebnych do uzyskania dokładnego rozwiązania.Oto implementacja R:
Dla osób niezaznajomionych z R dostępna jest uproszczona wersja:
Dystrybucja
rand5
zostanie zachowana. Jeśli wykonamy matematykę, każda z 7 iteracji pętli ma 5 możliwych wyników, więc całkowita liczba możliwych kombinacji to(7 * 5) %% 7 = 0
. W ten sposób możemy podzielić generowane losowo liczby na równe grupy po 7. Patrz metoda pierwsza i druga, aby uzyskać więcej dyskusji na ten temat.Oto wszystkie możliwe kombinacje:
Myślę, że łatwo jest pokazać, że metoda Adama nadal będzie działać szybciej. Prawdopodobieństwo, że
rand5
w rozwiązaniu Adama jest 7 lub więcej wywołań , jest wciąż małe ((4/25)^3 ~ 0.004
).Metoda 4 - Nie jest dokładna
Jest to niewielka odmiana drugiej metody. Jest prawie jednolity, ale wymaga 7 wywołań
rand5
, co stanowi dodatkowe uzupełnienie metody 2:Oto uproszczona wersja:
Jeśli wygenerujemy wszystkie możliwe kombinacje, oto liczby wynikowe:
Dwie liczby pojawią się raz mniej w
5^7 = 78125
próbach. W większości przypadków mogę z tym żyć.źródło
i=7
również nie ma żadnego efektu, ponieważ dodanie7*rand5()
dor
nie zmienia wartościr
mod 7.)Potrzebną funkcją jest rand1_7 () , napisałem rand1_5 (), abyś mógł ją przetestować i wykreślić.
źródło