Fri
20
Jun 2008

Wczorajszy wieczór spędziłem na zajmowaniu się liczbami pseudolosowymi. Ogólne wnioski: Są różne algorytmy. Do kryptografii potrzebne są wyjątkowo dobre i istnieją różne hardcore'owe metody ich badania, ale w zwykłym programowaniu nie trzeba aż tak kombinować.

Popularnym algorytmem jest Linear congruential generator, który działa wg wzoru: x[i] = (x[i-1] * a + c) mod m. Z niego korzystają biblioteki standardowe w popularnych kompilatorach C, C++, Delphi. Działa szybko, ale ma słabo losowe młodsze bity.

Napisałem sobie program pozwalający oceniać generatory liczb pseudolosowych metodą organoleptyczną ;) czyli wizualizując wyniki - wartości, rozkład wartości oraz poszczególne bity generowanych liczb. (Przy okazji przekonałem się, jak beznadziejną i pełną błędów biblioteką jest DevIL.) Oto wyniki:

• CommonLib - prosty Linear congruential generator, którego używałem dotychczas w moim CommonLib. Młodsze bity są beznadziejne.
• Biblioteka standardowa C - młodsze bity mają pewne regularności, ale generalnie jest OK.
• Linuksowy /dev/urandom - losowość jest świetna.

Rozwiązaniem jest po prostu branie tylko starszych bitów z liczb generowanych przez Linear congruential generator. Tak z resztą robią biblioteki standardowe w różnych środowiskach. Można też użyć innego algorytmu - dobry i szybki jest podobno Mersenne twister.

Przy okazji ciekawostki: Na Random.org można sobie wygenerować prawdziwie losowe liczby, łańcuchy, bitmapy, a także rzuty kośćmi czy monetą (w tym polskimi złotymi! :) Po wyczerpaniu limitu liczb losowych na adres IP można sobie dokupić więcej. Są też w sprzedaży generatory liczb prawdziwie losowych pod USB :)

Comments | #math Share

Comments