Garik Sedrakyan

Mersenne twister-ը հանդիսանում է pseudorandom գեներատորի համարը մշակվել է 1997 թվականին Makoto Matsumoto (ճապ.՝ 松本 眞) և Takuji Nishimura (ճապ.՝ 西村 拓士)-ի կողմից որը հիմնված է matrix գծային կրկնության մի վերջավոր երկուական թվերի ներկայացնելու որեվէ դիսկրետ համակարգի field $F_{2}$. Այն նախատեսում է արագ սերնդի հենց որակյալ pseudorandom թվերի համար, որոնք նախագծվել է, մասնավորապես, շատ հին ալգորիթմների հայտնաբերված թերությունները շտկելու համար. Նրա անունը բխում է նրանով, որ շրջանը երկարությունը ընտրվում է Mersenne prime-ից. Գոյություն ունեն առնվազն ալգորիթմի երկու ընդհանուր տարբերակներ, տարբերվողը միայն Mersenne primes օգտագործված չափի մեջ է . Ավելի ու ավելի հաճախ օգտագործվում է մեկը` Mersenne Twister MT19937-ը, 32-bit երկարությամբ բառի հետ. Կա նաև տարբերակ 64-bit բառի երկարության հետ, MT19937-64, որը առաջացնում է այլ հաջորդականությունը. k-bit երկարությամբ բառի համար, Mersenne Twister generates գրեթե համարների հետ է միասնական բաշխիչ-ում $[0,2^{k}-1]$.

Ծրագրեր

Իսկ ալգորիթմը իր հարազատ ձևով հարմար չէ ծածկագիտության համար (ի տարբերություն Blum Blum Shub-ին). Դիտարկելով բավարար թվով iterates (624 MT19937-ի դեպքում, քանի որ այդ ցուցանիշը պետական վեկտորի չափն է, որից արտադրված են ապագա iterates) թույլ է տալիս կանխատեսել բոլոր ապագա iterates. Մի զույգ cryptographic հոսքը հիմնված է Mersenne twister արտադրանքի վրա, արդեն առաջարկվում Makoto Matsumoto-ի կողմից et al. Հեղինակները պնդում են, որ արագությունը 1,5 - ից 2 անգամ ավելի արագ է, քան Advanced Encryption Standard-ը Հայկական ռեժիմում. Մեկ այլ խնդիր է, որ այն կարող է երկար տևել , դիմել ոչ պատահական սկզբնական պետության , (մասնավորապես շատ զրոների ներկայությունը) թողարկման մեջ, որոնք անցնում ենrandomness թեստեր. Փոքր lagged Fibonacci գեներատորը կամ գծային congruential գեներատորը սկսվել է շատ ավելի արագ և սովորաբար օգտագործվում է Mersenne Twister-ի հետ.

Mersenne twister-ի շատ ծրագրեր են արագ դառնում pseudorandom գեներատոր ընտրության համար. ref>«10.6. random — Generate pseudo-random numbers». {{cite web}}: Unknown parameter |աշխատանք= ignored (օգնություն); Unknown parameter |մուտքի անվանում= ignored (օգնություն)</ref>

Mersenne Twister-ը նախատեսված է Մոնթե Կարլո մոդելավորում-ի և այլ վիճակագրական սիմուլացիոն մտքերի հետ. Հետազոտողները հիմնականում ցանկանում են բարձրակարգ համարներ.

Առավելությունները

Այն սովորաբար օգտագործվում 1 Mersenne Twister MT19937 տարբերակում, որն արտադրում է 32-bit integers հաջորդականություն, ունի հետևյալ ցանկալի հատկությունները:

1. Այն ունի շատ երկար ժամկետ 2¹⁹⁹³⁷ − 1. Չնայած երկար ժամանակ չէ, երաշխիքը մի պատահական համարը է գեներատորի և կարճ ժամանակահատվածներում, (օրինակ 2³² տարածված է մի շարք ծրագրային փաթեթներ) կարող է լինել խնդրահարույց.
2. k-բ աժանվում է 32-bit ճշտության յուրաքանչյուր ը 1 ≤ k ≤ 623 (տես ստորև սահմանումը).
3. Այն անցնում է բազմաթիվ փորձությունների համար վիճակագրական randomness, այդ թվում Diehard tests. Այն անցնում է, բայց ոչ բոլորը, TestU01 Crush randomness tests.

k-բաշխում

pseudorandom հաջորդականությամբx_i w-bit integers ժամանակաշրջանըP լինում էk-բաշխում v-bitքիչ ճշտությունը, և հետևյալն է. .

Թող trunc _ընդդեմ(x) մատնանշում է ձևավորված համարը ընդդեմ x bit-ի, համարում P և kv-bit վեկտորներ

$({\text{trunc}}_{v}(x_{i}),\,{\text{trunc}}_{v}(x_{i+1}),\,...,\,{\text{trunc}}_{v}(x_{i+k-1}))\quad (0\leq i<P)$.

Այնուհետև յուրաքանչյուր 2^kv հնարավոր է տեղի է ունենում միևնույն ժամանակաշրջանում միևնույն քանակը փոխանցել , բացի այդ բոլոր զրոյական համակցության, որ տեղի է ունենում մի քիչ հաճախ.

Այլընտրանք

Mersenne Twister ալգորիթմը չի ստացել որևէ քննադատություն համակարգչային գիտության բնագավառում, հատկապես, ըստ George Marsaglia-ի. Այդ քննադատները պնդում են, որ դա լավ է, որը ոչ շատ էլեգանտ ու չափազանց է, և բարդ է իրականացնել. Marsaglia տրամադրել է պատահական թիվ գեներատորների մի քանի օրինակներ, որոնք պակաս բարդ չեն և ավելի մեծ ժամանակահատվածները պետք է տրամադրվի. Օրինակ, պարզ լրացում բազմապատկել իրականացնելը գեներատոր կարող է ունենալ մի ժամանակաշրջան 10³³⁰⁰⁰ անգամ ավելի երկար, կարող է զգալիորեն ավելի արագ , և պահպանել ավել կամ հավասար randomness.

Այլ հարց է, որ Mersenne Twister շատ զգայուն initialization է և կարող է երկար տևել վերականգնվելը զրոյական նախնական վիճակից. Այլընտրանք, WELL ("Well Equidistributed Long-period Linear"), ունի ավելի արագ ապաքինում և ավելի լավ կատարում և հավասար randomness.

Ալգորիթմական մանրամասներ

Mersenne Twister ալգորիթմը շատ է ընդհանրացված նկատողություններ հերթափոխը ռեգիստում (ՈՒրիշ GFSR, կամ TGFSR) ռացիոնալ նորմալ ձևից (TGFSR(R)), Այն բնութագրվում է հետևյալ քանակներով:

• w: բառի չափը (շատ թվով bit-եր)
• n: կրկնության աստիճանը

• m: Մերձավոր բառը կամ զուգահեռ sequences-ի համարը, 1 ≤ m ≤ n
• r: մեկ բառի, կամ շատ թվով bit-երի տարանջատման կետն է ր ստորին bitmask, 0 ≤ r ≤ w - 1
• a: ռացիոնալ նորմալ ձևի գործակիցները
• b, c: TGFSR(R) կոփում bitmasks
• s, t: TGFSR(R) կոփում բիտ տեղաշարժեր

• u, l: լրացուցիչ Mersenne Twister բիտ տեղաշարժեր

այն սահմանափակման, որ 2^nw − r − 1 Mersenne վարչապետն է. Այս ընտրությունը պարզեցնում է primitivity քննությունը և k- բաշխման փորձարկումը, որոնք փնտրում են անհրաժեշտ պարամետր:

Մի խոսքով ,x –ը w bit լայնությամբ, այն արտահայտվում է որպես վերադարձ հարաբերության

$x_{k+n}:=x_{k+m}\oplus ({x_{k}}^{u}\mid {x_{k+1}}^{l})A\qquad \qquad k=0,1,\ldots$

with | as the bitwise կամ և $\oplus$ as the bitwise բացառիկ կամ (XOR), x^u, x^l being x կիրառվել է վերին և ստորին bitmasks. A սահմանվում է ռացիոնալ նորմալ ձևով

$A=R={\begin{pmatrix}0&I_{w-1}\\a_{w-1}&(a_{w-2},\ldots ,a_{0})\end{pmatrix}}$

with I_n − 1 քանի որ (n − 1) × (n − 1) matrix ինքնությունը (և նորմալ մատրիցով բազմապատկում, bitwise XOR փոխարինում լրացում). Բանական նորմալ ձևը ունի օգուտը, որ կարելի արդյունավետ արտահայտել

${\boldsymbol {x}}A={\begin{cases}{\boldsymbol {x}}\gg 1&x_{0}=0\\({\boldsymbol {x}}\gg 1)\oplus {\boldsymbol {a}}&x_{0}=1\end{cases}}$

որտեղ

${\boldsymbol {x}}:=({x_{k}}^{u}\mid {x_{k+1}}^{l})\qquad \qquad k=0,1,\ldots$

Հասնելու է 2^nw − r − 1 տեսական վերին սահմանը ժամանակաշրջանի մի TGFSR, φ_B(t) պետք է լինի պրիմիտիվ polynomial, φ_B(t) լինելով բնորոշ polynomial-ից

$B={\begin{pmatrix}0&I_{w}&\cdots &0&0\\\vdots &&&&\\I_{w}&\vdots &\ddots &\vdots &\vdots \\\vdots &&&&\\0&0&\cdots &I_{w}&0\\0&0&\cdots &0&I_{w-r}\\S&0&\cdots &0&0\end{pmatrix}}{\begin{matrix}\\\\\leftarrow m{\hbox{-th row}}\\\\\\\\\end{matrix}}$

$S={\begin{pmatrix}0&I_{r}\\I_{w-r}&0\end{pmatrix}}A$

Շրջադարձ վերափոխումը բարելավում է դասական GFSR-ը հետևյալ հիմնական հատկություններով.

• Ժամկետը հասնում է տեսական վերին սահմանին 2^nw − r − 1 (except if initialized with 0)
• Equidistribution in n չափերը (օրինակ, գծային congruential գեներատոր-ի կարող է լավագույնս կառավարել խելամիտ բաշխումն է հինգ հարթություններում)

Ինչպես TGFSR(R), ը, այնպես ել Mersenne Twister-ը i կոփում փոխակերպում է equidistribution-ի համար (քանի որ ընտրելով A գտնվելով ռացիոնալ նորմալ ձևում), որը համարժեք ի փոխակերպման A = R → A = T⁻¹RT, T invertible. Կոփում է սահմանված դեպքում, ինչպես Mersenne Twister -ը

y := x ⊕ (x >> u)

y := :y ⊕ ((y << s) & b)

y := :y ⊕ ((y << t) & c)

z := y ⊕ (y >> l)

ինչպես նաև<<, >> որպես bitwise ձախ և աջ հերթափոխով, ինչպես bitwise և. Առաջին և վերջին transforms ավելացվել են բարելավելու նպատակով bit equidistribution. TGFSR-ից, $s+t\geq \lfloor w/2\rfloor -1$ պահանջվում է հասնել վերին equidistribution-ին վերին bitերի համար.

The coefficients for MT19937 are:

• (w, n, m, r) = (32, 624, 397, 31)
• a = 9908B0DF₁₆
• u = 11
• (s, b) = (7, 9D2C5680₁₆)
• (t, c) = (15, EFC60000₁₆)
• l = 18

Կեղծ կոդը

pseudocode-ի հետևյալ կտորը առաջացնում է uniformly բաժանվող 32-bit integers Լեռնաշղթայի [0, 2³² − 1] MT19937 ալգորիթմի հետ:

 // Create a length 624 array to store the state of the generator
 int[0..623] MT
 int index = 0
 
 // Initialize the generator from a seed
 function initialize_generator(int seed) {
     MT[0] := seed
     for i from 1 to 623 { // loop over each other element
         MT[i] := last 32 bits of(1812433253 * (MT[i-1] xor (right shift by 30 bits(MT[i-1]))) + i) // 0x6c078965
     }
 }
 
 // Extract a tempered pseudorandom number based on the index-th value,
 // calling generate_numbers() every 624 numbers
 function extract_number() {
     if index == 0 {
         generate_numbers()
     }
 
     int y := MT[index]
     y := y xor (right shift by 11 bits(y))
     y := y xor (left shift by 7 bits(y) and (2636928640)) // 0x9d2c5680
     y := y xor (left shift by 15 bits(y) and (4022730752)) // 0xefc60000
     y := y xor (right shift by 18 bits(y))

     index := (index + 1) mod 624
     return y
 }
 
 // Generate an array of 624 untempered numbers
 function generate_numbers() {
     for i from 0 to 623 {
         int y := 32nd bit of(MT[i]) + last 31 bits of(MT[(i+1) mod 624])
         MT[i] := MT[(i + 397) mod 624] xor (right shift by 1 bit(y))
         if (y mod 2) != 0 { // y is odd
             MT[i] := MT[i] xor (2567483615) // 0x9908b0df
         }
     }
 }

SFMT

SFMT, the SIMD-oriented Fast Mersenne Twister, is a variant of Mersenne Twister, introduced in 2006, designed to be fast when it runs on 128-bit SIMD.

• It is roughly twice as fast as Mersenne Twister.
• It has a better equidistribution property of v-bit accuracy than MT but worse than WELL ("Well Equidistributed Long-period Linear").
• It has quicker recovery from zero-excess initial state than MT, but slower than WELL.
• It supports various periods from 2⁶⁰⁷-1 to 2²¹⁶⁰⁹¹-1.

Intel SSE2 և PowerPC AltiVec աջակցում է SFMT. Այն նաև օգտագործվել խաղերի հետ Cell BE PlayStation 3-ում.>

Իրականացման տարբեր լեզուներով

• Pascal/FreePascal/Delphi
• Java
• The GNU Scientific Library (GSL)
• R language
• C++11
• C++
• C and C++
• C++
• C++
• C++
• Excel addin
• VBA
• Microsoft Excel
• Visual Basic
• REALbasic
• Lisp
• Euphoria
• C#
• F#
• Ada
• Fortran 95
• Fortran 95:
• Lua
• Mitrion-C
• Clean
• Perl
• Haskell
• Haskell
• Standard ML
• C++ Sony Cell Broadband Engine
• ActionScript 1
• ActionScript 3.0
• Clojure
• ABAP
• Erlang
• SIMUL8
• Scala

• Այն նաև իրականացվում է ճարտարախոս և ստանդարտ գրադարանները PHP, Python և Ruby. NAG Numerical Library նաև պարունակում է Mersenne Twister իրականացնում.

Արտաքին հղումներ

• The academic paper for MT, and related articles by Makoto Matsumoto
• Mersenne Twister home page, with codes in C, Fortran, Java, Lisp and some other languages
• SIMD-oriented Fast Mersenne Twister (SFMT)