64bit random

Szukam jakiegoś prostego w obsłudze generatora liczb pseudolosowych __int64. Nie musi być jakoś specjalnie mocny, ale warto by było aby był lepszy niż rand(). Jest takie coś?

rozwiązanie na szybko, prawdopodobnie tragicznie niewydajne:

// zwraca liczbę pseudolosową dodatnią z zakresu 0 .. 2^63-1
__int64 rand64()
{
  return (((__int64)rand()&7)<<60) |
             ((__int64)rand()<<45) |
             ((__int64)rand()<<30) |
             ((__int64)rand()<<15) |
              (__int64)rand();
}

To rozwiązanie zmniejsza entropię pięciokrotnie. Ergo: rozwiązanie pięć razy gorsze od rand() (pięciokrotnie mniejszy cykl generatora).

rincewind napisał(a)

To rozwiązanie zmniejsza entropię pięciokrotnie. Ergo: rozwiązanie pięć razy gorsze od rand() (pięciokrotnie mniejszy cykl generatora).

Pięciokrotnie wolniejsze, to na pewno. Ale jeśli długość cyklu rand()a nie jest podzielna przez 5, to nie będzie krótszego cyklu.

Co do entropii — w zastosowaniach, gdzie się naprawdę liczy, stosuje się szum termiczny, rozpad nuklearny lub inne zjawiska, a nie odpala rand() ...

Na 1. rozwiązanie sam wpadłem, chodziło mi o coś lepszego. Ale dlaczego użyłeś 5 randów? 4 by nie wystarczyły?

Czytałem trochę o rejestrach przesuwnych ze sprzężeniem zwrotnym. Czy zaimplementowanie tego w funkcji to dobry pomysł?

to dobry pomysł. Implementacja takiego rejestru jest prosta i przy odpowiednio wybranych parametrach będzie miał okres 2^64 - 1

Ok. Zostaje mi kwestia jak wybrać odpowiedni wielomian, tak żeby ten LFSR miał maksymalny możliwy okres?

zerknij sobie tu http://en.wikipedia.org/wiki/Linear_feedback_shift_register
Jest tam link do pdf-a, w którym znajdują się wielomiany dla rejestrów do długości 168.

__int64 r64state;
__int64 r64mask;

__int64 random64()
{
 r64state = (r64state >> 1) ^ (-(r64state & 1) & r64mask);
 return r64state;
}

void setmask64(__int64 new_mask)
{
 r64mask = new_mask;
}

void setseed64(__int64 seed)
{
 r64state = seed;
}

Wykodziłem na sucho (na tym kompie nie ma kompilatora), przerobiłem trochę przykład z angielskiej wikipedii. Tylko tam było na unsigned, a martwi mnie kod

-(r64state & 1)

To zadziała tak jak jest czy trzeba wszystkie zmienne przerobić na unsigned?

olo16 napisał(a)

Na 1. rozwiązanie sam wpadłem, chodziło mi o coś lepszego. Ale dlaczego użyłeś 5 randów? 4 by nie wystarczyły?

rand() generuje liczbę 15-bitową, więc żeby pokryć nimi 63 bity potrzeba czterech pełnych liczb i jeszcze trzy bity.

Powiedz to rand() z np. glibc, zdziwi się.

Hmm. Według standardu, rand() zwraca liczbę z zakresu 0..MAX_RAND, a MAX_RAND u mnie pod gcc (mingw32) wynosi 32767...

Anata no mirai ga shiawase de arimasu youni.

Doumo arigatou gozaimasu.

Azarien napisał(a)

Hmm. Według standardu, rand() zwraca liczbę z zakresu 0..MAX_RAND, a MAX_RAND u mnie pod gcc (mingw32) wynosi 32767...
MinGW korzysta z microsoftowej biblioteki standardowej, a nie glibc (AFAIR glibc się dosyć mocno nie lubi z Windowsem).

Nie mam Linuksa, ale DJGPP (gcc dosowy ;-)) rzeczywiście zwraca 2147483647.
Ale lipa co do MinGW. To ma się nazywać windowsowy port? Raczej symulator..

Od kiedy glibc jest częścią GCC? Port kompilatora to port kompilatora...

Jeżeli komu zależy na prawdziwej losowości to polecam <url=http://www.idquantique.com/ordering/shop.html<IdQuantique</url>
Ale tysiąc ojro to tysiąc ojro</url>

Jakby mi zależało na prawdziwej losowaości, to niewątpliwie znalazłbym jakieś rozwiązanie, niekoniecznie kartę kwantową za 1000-2000€... Ale mi nie zależy, nawet jestem od tego daleko, więc po co ten post? LFSR mi spokojnie wystarczy.