Konwersja losowego ciągu bitów na liczby całkowite z określonego przedziału

Witam Wszystkich

Mam pewną ilość danych (załóżmy 10MB) pochodzących z sprzętowego generatora liczb losowych. Chciałbym to teraz przerobić na losowe liczby całkowite ale z określonego przedziału. Poszukuję algorytmu który by :

1. generował liczbę całkowitą z jak najmniejszej ilości bitów
2. nie zmniejszał entropii nowo wygenerowanych liczb

do dolnej granicy dodajesz wartosc reprezentowana przez X bitow losowych
jesli suma wyjdzie poza gorna granice to musisz wziasc kolene X bitow ( az do skutku )

ewentualnie mozesz sie bawic w przeskalowywanie wartosci zapisanej w bitach losowych na wartosc z zadanego zakresu

pojawiają się pewne cienkości, ciekawe...
może nawet trzeba by losować ile bitów wziąć?
bo powiedzmy w ciągu bitów mamy trochę zer, ile ich wziąć? nie więcej niż log_2(N)
ciekawe
<image>podyc</image>

dla przedzialu <0;17>
potrzebne 5 bitow
przeskalowanie 32 na 17 -> to przemnozenie przez 17/32
powiedzmy losowe bity tworza wartosc 22
22*17/32
generujesz liczbe uzywajac random i w ten sposob okreslasz czy czesc liczby po przecinku zaokraglisz w gore czy w dol

jakisnick napisał(a)

generujesz liczbe uzywajac random i w ten sposob okreslasz czy czesc liczby po przecinku zaokraglisz w gore czy w dol
A nie lepiej po prostu zaokrąglić do najbliższej?

//EDIT
Oczywiście zrobić to w taki sposób, aby pierwsza i ostatnia liczba była tak samo prawdopodobna jak pozostałe... kurcze może to nie być takie proste...

Niestety sposób z przeskalowanie kompletnie odpada bo na 5 bitach można wygenerować 32 liczby całkowite:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 - prawdopodobieństwo każdej jest jednakowe

po przeskalowaniu mamy odpowiednio:

0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 - prawdopodobieństwo dla zera i ósemki to 1/32, dla pozostałych pozostałych 1/16.
Liczby po przeskalowaniu nie będą prawdziwie losowe.

adam12 napisał(a)

Niestety sposób z przeskalowanie kompletnie odpada bo na 5 bitach można wygenerować 32 liczby całkowite:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 - prawdopodobieństwo każdej jest jednakowe

po przeskalowaniu mamy odpowiednio:

0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 - prawdopodobieństwo dla zera i ósemki to 1/32, dla pozostałych pozostałych 1/16.
Liczby po przeskalowaniu nie będą prawdziwie losowe.

nie przeczytales dokladnie tego co napisalem :-)

jesli zakres bedzie staly a ilosc liczb wygenerowanych bardzo duza to mozesz po prostu skorzystac z przesuniecia o zakres w razie wyjscia poza niego

Możesz jaśniej bo za bardzo nie rozumieniem Twojego toku myślenia ?

Teraz się trochę zastanowiłem nad tematem i faktycznie sposób ze skalowaniem przedziału nie sprawdzi się (chyba, że też czegoś nie zrozumiałem). Wylosowana, przeskalowana wartość może wypaść gdzieś pomiędzy dwoma kolejnymi liczbami. Ale między niektórymi parami losowana i skalowana wartość będzie mogła wypadać w tylko jednym przypadku, a pomiędzy innymi parami takich przypadków będą dwa.

Wpadł mi jeszcze inny pomysł. Bierzemy minimalną ilość bitów. Jeśli wartość nie mieści się w zakresie - negujemy bity.

Z negacją jest tak samo jak z przeskalowaniem tu na przykład analiza dla przedziału <0,10> :