В този пост ще обсъдим прилагането на линеен congruential метод за псевдослучайни числа битова дълбочина от 64 бита, и 128, като обясни принципа на работа и подбор на параметри.
Ако са в тежест за използване на RNG на стандартната библиотека, ще трябва да го нестандартни изисквания, или просто лов за контрол на целия процес на генериране на случайни числа в молбата Ви, заповядайте при среза.
Долу стандартен генератор!
Доста общи програмни езици имат функция за генериране на случайни (или, за да бъдем изключително прецизни, псевдослучайни числа). Въпреки това, понякога е необходимо да се приложи свой собствен генератор на случайни числа (RNG). Въпреки RNG "извън кутията" обикновено е достатъчно добър, за да се използва в повечето случаи, но също така се случва, че не е необходимо твърде стръмен генератор като него, но вградената RNG все още не ми харесва.
Причините могат да бъдат различни, а не очевидни на пръв поглед. На първо място, следва да се отбележи, че проблемът за генериране на случайни числа, често включва намирането на баланс между скорост и качество на резултатите. Понякога трябва да се направи малко по-бързо, или малко по-сложно.
На второ място, RNG - не само бъркотия на аритметични операции, както и строго детерминиран алгоритъм, характеристиките на които могат да се различават значително. Някои научни експерименти, необходими за пълното описват условията на тестове, за да се гарантира възможността за да ги възпроизвежда. Това включва алгоритъм и параметри на RNG. В този случай е по-добре да си изпълнение.
Възможно е да има проблем, при който се изисква едновременното действие на различни RNG. Тя е различна, както и вграден генератор обикновено е един. Вие със сигурност може да работи на множество копия на различните първоначална зърно, но в този случай, генераторът ще даде членове на една и съща последователност (която се повтаря циклично) просто като се започне от различни места. Дължина на цикъл е огромен, но теоретично това може да създаде проблеми.
В моя случай, че е необходимо да се генерира номер на 128-битово. В C ++ има функция, която извежда поне 64-битова версия. След продължително gugleniya открих объркване ранд () и RAND_MAX различни компилатори, патерици, определени за генериране на 64 бита, и реши да се откаже от построен RNG. Писане вашия генератор изглежда елементарна задача - за няколко повторения на линеен генератор еднакви, за да получите два 64-битови числа, а след това да ги залепите заедно. Не беше толкова лесно. Но първо първите неща.
Така че, ние се пристъпи към създаването на RNG. Като основа се вземе най-простият и най-популярната линеен congruential генератора, който оперира в съответствие с формулата:
където XI. XI + 1 - ток и следващите случайни числа; а. с и м - константи; Министерството на отбраната - оператор намери остатъка от деление.
Постоянният м често се приема, че е 2 32, или 2 64 за да се избегне разделението в изпълнение на софтуера. Това са получени в резултат на 64-битови остатъци, използвах m = 2 64. Но къде да се получи постоянен, и в. В Wikipedia, е установено следното двойка: а = С = 6364136223846793005 и 1442695040888963407. Без да се замисля, аз написах генератор с помощта на тези параметри, и започнала да тества своя генетичен алгоритъм. Въпреки това, той бързо се фиксирам. Подозрението падна на RNG. Оказва се, че няколко LSBs в получената последователност на 64-битови "случайни" номера не показват случаен поведение. Стойностите на някои части от последователни числа са показани като монохромни изображения:
Стойности, 5-ия, 15-ия и 20-бита (номерирани от нула)
Приблизително 20-24 LSB не са подходящи за използване. С увеличаване на броя на заустване увеличава шанса си. По този начин, за да се получи една 64-битова случайни числа, са необходими две линейни генератори congruential повторения. Резултатът е конкатенацията на два 32-битови фрагменти:
Например, в java.util.Random използва същия принцип, но поради факта, че м = 48. 2 има изхвърлят LSBs 16 само в дългосрочен Int и поколение. Това, разбира се, се отразява негативно на качеството на случайни числа.
Ето един пример на номера 64-битова последователност, която се получава, когато а = 6364136223846793005, с = 1442695040888963407, т = 2 64. x0 = 0, както е описано на фигура начин:
1442695037175000593
11166244415259155177
7076646891078057782
1459328390042580878
8905969149530007863
11682375496967736740
897247724006084730
Как случаен тези номера? Приблизително на нивото на RNG на стандартната Java библиотека, може би дори малко по-добре. Изчисляването на всеки номер изисква само две умножения.
Ако имате нужда от няколко различни осцилатори, трябва да изберете други стойности на константите А и с. изчислено за М = 2 64. Изделие от тази справка показва примери на три константи с "добро качество":
в - е нечетен, т = 2 64
Свързани статии