20151014_MSU_rnd (Лекции), страница 2

Marsaglia 1968]Для RANDU(IBM 360/370) a=216+3, m=231, c=0a  32 0 mod mНе более 16-ти плоскостей [Richard P.Brent, 1992]U n 2  6U n1  9U n  0 mod mПсевдослучайные числа для расчетов на многопроцессорных системах© Якобовский М.В.39Случайные точкиПоследовательностьxn1  845xn  2625 mod 8192все точки90001024 точки вида9000x2i , x2i 1 80007000600080005000700040006000300050004000200030001000200000200040006000800010000100000200040006000800010000Псевдослучайные числа для расчетов на многопроцессорных системах© Якобовский М.В.40Разумная альтернативаМ – последовательностиМ-последовательностиГенератор на сдвиговомрегистре [П.Хоровиц,У.Хилл, 1983]М-последовательности[И.М.

Соболь, 1973]123…20…33XOR i   i  20   i 33  0 nr r 1   ek  n  k  mod 2 k 0Псевдослучайные числа для расчетов на многопроцессорных системах© Якобовский М.В.42Генерация псевдослучайных чиселAABCDF=(A+D)mod2D=CC=BB=AA=FBCD(A+D)mod21151111021401111313101104100101155101016111101076011008120011199100101020100011400100128000111311000114311001157111011615111101234XOR43Генерация псевдослучайных чиселAABCDF=(A+D)mod2D=CC=BB=AA=FBCD(A+D)mod21151111021401111313101104100101155101016111101076011008120011199100101020100011400100128000111311000114311001157111011615111101234XOR44Генерация псевдослучайных чиселAABCDF=(A+D)mod2D=CC=BB=AA=FBCD(A+D)mod2115111102140111131310110410010115510101611110107601100812001119910010102010001140010012800011131100011431100115711101161511110010 = 2110 = 6010 = 2001 = 1111 = 745ntСвязь между mod Gt  и фрагментом MпоследовательностиЕслиr 1t   an , j t mod 2, Gt njj 0тоr 1xn   an , j x j mod 2j 0Richard P.

BrentOn the period of generalized Fibonacci recurrences, 1992Псевдослучайные числа для расчетов на многопроцессорныхсистемах © Якобовский М.В.46 из 51Генерация элемента с произвольнымномером kf k  x mod Gkn 1k    i 2 i ,  i  0,1i 0n 1 mod Gx  xki 02iif k  x k mod x 4  x1  1Псевдослучайные числа для расчетов на многопроцессорныхсистемах © Якобовский М.В.47 из 51Проверка примитивности полиномаhi простые делители2  1   hiriПсевдослучайные числа для расчетов на многопроцессорныхсистемах © Якобовский М.В.48 из 51Вычислить x^n за O(logn) операций перемноженияполиномов2*log(n) операций153x xx2*76  x x xxxx222*92*38 2x x22   x  x xx 82222*192 2Псевдослучайные числа для расчетов на многопроцессорных системах© Якобовский М.В.49mod xmod xmod xmod x x  1  x x  1  x x  1  x x  1  xx mod x  x  1  10x1x2x3x44444433323334x 4  x3  1  x3  1x 5  ( x 3  1) x  x 4  x  x 4  x  x 4  x 3  1  x 3  x  1x6  x4  x2  x x 4  x3  1  x3  x 2  x  1x7  x 4  x3  x 2  x x 4  x3  1  x 2  x  1x8  x3  x 2  xx9  x 4  x3  x 2 x10  x 3  xx 4  x3  1  x 2  1x 5  ( x 3  1) x  x 4  x  x 4  x  x 4  x 3  1  x 3  x  1x6  x4  x2  x x 4  x3  1  x3  x 2  x  1x7  x 4  x3  x 2  x x 4  x3  1  x 2  x  1x8  x3  x 2  xx9  x 4  x3  x 2 x 4  x3  1  x 2  1x10  x 3  xx11  x 4  x 2 x 4  x3  1  x3  x 2  1x12  x 4  x 3  x x 4  x3  1  x  1x13  x 2  xx14  x 3  x 2x15  x 4  x 3 x16  xx 4  x3  1  1mod xmod xmod xmod x x  1  x x  1  x x  1  x x  1  xmod x  x  1mod x  0mod x  x  1mod x  0mod x  x  1mod x  0mod x  x  1mod x  1mod x  x  1mod x  1mod x  x  1mod x  1mod x  x  1mod x  1mod x  x  1mod x  0mod x  x  1mod x  1mod x  x  1mod x  0mod x  x  1mod x  1mod x  x  1mod x  1mod x  x  1mod x  0mod x  x  1mod x  0x 0 mod x 4  x 3  1  1x 0 mod x 4  x 3  1 mod x  1x1x1x2x3x44444332x233x334x 4  x3  1  x3  1x4x 5  ( x 3  1) x  x 4  x  x 4  x  x 4  x 3  1  x 3  x  1x5x6  x4  x2  x x6x 4  x3  1  x3  x 2  x  1x7  x 4  x3  x 2  x x 4  x3  1  x 2  x  1x8  x3  x 2  xx7x8x9  x 4  x3  x 2 x 4  x3  1  x 2  1x10  x 3  xx9434343434343434343x1043x1143x1243x13  x 2  xx1343x14  x 3  x 2x1443x11  x 4  x 2 x 4  x3  1  x3  x 2  1x12  x 4  x 3  x x 4  x3  1  x  1Генерация псевдослучайных чиселAABCDF=(A+D)mod2D=CC=BB=AA=FBCD(A+D)mod211511110214011113131011041001011551010161111010760110081200111991001010201000114001001280001113110001143110011571110153Генерация псевдослучайных чиселABCD(A+D)mod2x1x2ABCDF=(A+D)mod2D=CC=BB=AA=Fmod x  x  1mod x  0mod x  x  1mod x  0mod x  x  1mod x  0mod x  x  1mod x  1mod x  x  1mod x  1mod x  x  1mod x  1mod x  x  1mod x  1mod x  x  1mod x  0mod x  x  1mod x  1mod x  x  1mod x  0mod x  x  1mod x  1mod x  x  1mod x  1mod x  x  1mod x  0mod x  x  1mod x  0x 0 mod x 4  x 3  1 mod x  143434343434343434311511110214011113131011041001011x55510101x661111010x7760110081200111991001010201000x104311400100x1143128000114313110001x124314311001x1315711101x1443x3x4x8x954mod xmod xmod xmod x 1  x 1  x 1  x 1  xx 0 mod x 4  x 2  1  1x1x2x3x44 x24 x24 x24 x2234x4  x2 1  x2 1x 5  ( x 2  1) x  x 3  xx6  x4  x2 x4  x2 1  1x7  xx8  x 2x9  x3x10  x 3  xx11  1x x12x13  x 2x14  x 3x15  x 3  xx16  1hi простые делители2  1   hiriВычислить x^n за O(logn) операций перемноженияполиномов2*log(n) операций228 2x mod x  x  1  x  xxx    mod x 4  x 3  1 x 8 mod x 4  x 3  1  x 3  x 2  x153432x153 mod x 4  x 3  1  x 3Псевдослучайные числа для расчетов на многопроцессорных системах© Якобовский М.В.56f k  x mod x  x  x  x  1k19157512 десятиразрядных двоичных чиселx xkk 1r 1x mod Gi 0ix mod x  x  12i31 fk  x   xk3i2ir 1mod G,j 0x mod x  x  12i3128k    j 2 j ,  j  0,1r 1G x     i x 2 1 ,  j  0,1ii 0012345678910111213141516171819xx^2x^4x^8x^16x^4+xx^8+x^2x^16+x^4x^8+x^4+xx^16+x^8+x^2x^16+xx^4+x^2+xx^8+x^4+x^2x^16+x^8+x^4x^16+x^8+x^4+xx^16+x^8+x^4+x^2+xx^16+x^8+x^2+xx^16+x^2+xx^2+xx^4+x^2202122232425262728293031x^8+x^4x^16+x^8x^16+x^4+xx^8+x^4+x^2+xx^16+x^8+x^4+x^2x^16+x^8+xx^16+x^4+x^2+xx^8+x^2+xx^16+x^4+x^2x^8+xx^16+x^2xxx^2x^4x^8x^16x^29+xx^28+x^27+x^24+x^21+x^18+x^15+x^12+x^9+x^6+x^3+x^2+1x^30+x^29+x^25+x^24+x^23+x^22+x^20+x^19+x^18+x^16+x^13+x^12x^11+x^10+x^8+x^7+x^6+x+1x^30+x^29+x^28+x^27+x^23+x^22+x^21+x^19+x^18+x^14+x^12+x^9+x^7+x^6+x^5+x^4+x^3x^28+x^27+x^26+x^25+x^22+x^21+x^19+x^16+x^14+x^12+x^11+x^10+x^7+x^6+x^4+xx^29+x^25+x^24+x^23+x^21+x^18+x^17+x^15+x^13+x^10+x^9+x^8+x^6+x^3+x^2+x+1x^29+x^28+x^27+x^26+x^24+x^21+x^20+x^19+x^17+x^14+x^13+x^12+x^10+x^7+x^6+x^5+x^3+xx^30+x^28+x^27+x^26+x^25+x^23+x^22+x^19+x^16+x^14+x^13+x^12+x^11+x^9+x^8+x^5x^28+x^25+x^24+x^21+x^16+x^13+xx^29+x^26+x^25+x^22+x^17+x^14+x^2+xx^27+x^24+x^19+x^16+x^4+x^3+x^2+1x^23+x^20+x^8+x^7+x^6+1x^16+x^15+x^14+1x^30+x^29+x^28+x+1x^30+x^28+x^27+x^26+x^25+x^24+x^23+x^22+x^21+x^20+x^19+x^18+x^17+x^16+x^15+x^14+x^13+x^12+x^11+x^10+x^9+x^8+x^7+x^6+x^5+x^4+x^3+xx^28+x^25+x^24+x^21+x^20+x^17+x^16+x^13+x^12+x^9+x^8+x^5+xx^29+x^26+x^25+x^24+x^22+x^18+x^17+x^16+x^14+x^10+x^9+x^6+x^2+xx^29+x^27+x^24+x^20+x^19+x^18+x^17+x^16+x^14+x^12+x^11+x^8+x^4+x^3+x^2+x+1x^30+x^27+x^23+x^22+x^21+x^20+x^18+x^16+x^15+x^12+x^8+x^7+x^6+x^5+x^3x^30+x^29+x^26+x^24+x^16+x^15+x^14+x^13+x^11+x^8+x^7+x^6+x^4x^30+x^28+x^27+x^24+x^23+x^22+x^20+x^16+x^14+x^12+x^8+xx^30+x^28+x^26+x^25+x^24+x^22+x^19+x^17+x^15+x^14+x^12+x^11+x^8+x^5+xx^30+x^29+x^28+x^26+x^25+x^24+x^23+x^21+x^20+x^18+x^16+x^15+x^13+x^12+x^9+x^6+x^2x^30+x^27+x^25+x^23+x^22+x^20+x^18+x^15+x^11+x^8+x^4+xx^29+x^26+x^22+x^19+x^15+x^12+x^8+x^5Псевдослучайные числа для расчетов наx^30+x^27+x^16+x^13многопроцессорных системах © Якобовский М.В.x58x mod Gx  2iразреженные полиномыx^31+x^3+1x^31+x^7+1x^31+x^7+x^3+x+1 x^31+x^15+x^3+x+1x^127+x^1+1x^127+x^63+1x^127+x^7+x^3+x+1x^127+x^63+x^15+x+151115G x  x  x 1•x^255+x^15+x^7+x^3+1••x^255+x^31+x^7+x+1x^255+x^31+x^7+x^3+1••x^255+x^63+x^7+x^3+1x^255+x^63+x^31+x^15+1•••x^255+x^127+x^7+x^3+1x^255+x^127+x^3+x+1x^255+x^127+x^31+x^7+110237G x x x 12 255 - 1  7  31 103 151  2143 11119 106591 131071  949111 9520972806333758431  57024515776397755458386431512511 - 1  127  439  2298041  9361973132609 15212471 144780974187086260903935034761413745643636578290924150417 253759974502551913415676116426759191352183553552922472559253865815359Проверка примитивности полиномаhi простые делители2  1   hiriПсевдослучайные числа для расчетов на многопроцессорныхсистемах © Якобовский М.В.60 из 51Publication Date: 2002Number of Pages: 236pp.Publisher: AMShttp://www.mersenneforum.org/attachment.php?attachmentid=7727&d=133055598061Перколяционный кластерПсевдослучайные числа для расчетов на многопроцессорныхсистемах © Якобовский М.В.62 из 51Перколяционный кластерПсевдослучайные числа для расчетов на многопроцессорныхсистемах © Якобовский М.В.63 из 51Перколяционный кластерПсевдослучайные числа для расчетов на многопроцессорныхсистемах © Якобовский М.В.64 из 51Перколяционный кластерПсевдослучайные числа для расчетов на многопроцессорныхсистемах © Якобовский М.В.65 из 51размер максимального кластераПорог перколяции100%80%размер сетки800 х 800 х 8001 000 х 1 000 х 1 0001 100 х 1 100 х 1 100[ Ю.Ю.Тарасевич, 2002]60%40%размер сетки1 000 х 1 00010 000 х 10 000Точное значение0.2488126(5)Точное значение 0.520%0%00.1 0.20.3 0.40.50.6 0.7доля открытых ребер0.8 0.9Ю.Ю.ТарасевичН.Н.Медведев1Gx   x 255  x31  x7  x3  1Батарея тестов DiehardLRND320123456123456712345678123456789SWBMWCMWCMIXRNDXMIXRNDXYBRNDRANDP=0P <0.00001P <0.001P <0.01a0000000121274146bcd0130100.01≤ P ≤0.99P >0.99P >0.999P >0.99999P=1DCB309510431220006309400015312100002311600004312300105307600885263391110552624714521318721118A0000000007117003222218Псевдослучайные числа для расчетов на многопроцессорных системах© Якобовский М.В.67Парковочный тестПсевдослучайные числа для расчетов на многопроцессорных системах© Якобовский М.В.68Тестируемые последовательностиxn1  3141592653xn  2718281829 mod 235 , x0  0BRNDMIXRNDрандомизация перемешиваниемMWCгенератор на основе метода умножения с переносом MWC,период 4*10^18SWBMWCкомбинированный генератор на основе методов умножения спереносом MWC и Фибоначчи с запаздыванием SWBG, период4*10^364Псевдослучайные числа для расчетов на многопроцессорных системах© Якобовский М.В.69Gx   x 255  x31  x7  x3  1Батарея тестов DiehardLRND320123456123456712345678123456789SWBMWCMWCMIXRNDXMIXRNDXYBRNDRANDP=0P <0.00001P <0.001P <0.01a0000000121274146bcd0130100.01≤ P ≤0.99P >0.99P >0.999P >0.99999P=1DCB309510431220006309400015312100002311600004312300105307600885263391110552624714521318721118A0000000007117003222218Псевдослучайные числа для расчетов на многопроцессорных системах© Якобовский М.В.70Gx   x 255  x31  x7  x3  1РезюмеЕсть возможность вычисления за время O(log(k))числа с произвольным номером k с помощьюбинарного возведения в степеньf k  x mod GkПри наличии числа с номером k естьвозможность быстрого вычисления числа сномером k+1 с помощьюf k 1  x f k mod GПсевдослучайные числа для расчетов на многопроцессорных системах© Якобовский М.В.71Сравнение различных библиотек генерации ПСЧТипПери-одВозм.перехода(skip-ahead)G(x) r 255M-посл-ть2255-1+20,438,5G(x) r 1023M-посл-ть21023-1+18,512,3ЛКГ m=31231-1–204,1--MCG31m1ЛКГ m=31231- 1+R250M-посл-ть2250–MRG32k3a2 ген-ра Фибоначчи2191+105,321,3MCG59ЛКГ m=59257+WH273 ЛКГ280+MT19937Mersenne-Twister (MT)219937-1–MT22031024 MT22203-1–Библио-тека/ГенераторV перехода,103 шт/с106V,ПСЧ/сPRANDANSIrandIntel MKLПсевдослучайные числа для расчетов намногопроцессорных системах © Якобовский М.В.72Доступные реализации генераторов ПСЧ для GPUCURAND (Nvidia)Библиотека для генерации псевдослучайных иквазислучайных чисел на GPU / CPUГенераторы случайных чисел (СЧ)••••XORWOWMRG32k3aMTGP32 (Mersenne Twister)Генераторы квазислучайных чисел Соболя (Sobol’)Распределения:равномерное, нормальное, логнормальное, ПуассонаПсевдослучайные числа для расчетов на многопроцессорных системах© Якобовский М.В.73Библиотека LRND32-GPUГенератор j 1023   j 511   j 127   j  7   jТо же для 32-битных словwj 8  wj  1  wj 1  31  wj  8  wj 1  24  wj  4  w j 16Период: 21023-1Скорость: 2,6 ∙ 107 ПСЧ/с на NVidia Tesla C2050Исходные коды библиотеки LRND32-GPU:http://apos.imamod.ru/Programms/GK_07_514_11_4002_rng.tar.gzМ.Н.