Մասնակից:Garik Sedrakyan

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search

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


Ծրագրեր[խմբագրել | խմբագրել կոդը]

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

Mersenne twister-ի շատ ծրագրեր են արագ դառնում pseudorandom գեներատոր ընտրության համար. ref>«10.6. random — Generate pseudo-random numbers»  </ref>[3]

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


Առավելությունները[խմբագրել | խմբագրել կոդը]

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

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


k-բաշխում[խմբագրել | խմբագրել կոդը]

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

Թող trunc ընդդեմ(x) մատնանշում է ձևավորված համարը ընդդեմ x bit-ի, համարում P և kv-bit վեկտորներ
.
Այնուհետև յուրաքանչյուր 2kv հնարավոր է տեղի է ունենում միևնույն ժամանակաշրջանում միևնույն քանակը փոխանցել , բացի այդ բոլոր զրոյական համակցության, որ տեղի է ունենում մի քիչ հաճախ.


Այլընտրանք[խմբագրել | խմբագրել կոդը]

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

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

Ալգորիթմական մանրամասներ[խմբագրել | խմբագրել կոդը]

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

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

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


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


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


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

որտեղ

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

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

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

Ինչպես TGFSR(R), ը, այնպես ել Mersenne Twister-ը i կոփում փոխակերպում է equidistribution-ի համար (քանի որ ընտրելով A գտնվելով ռացիոնալ նորմալ ձևում), որը համարժեք ի փոխակերպման A = RA = T−1RT, 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-ից, պահանջվում է հասնել վերին equidistribution-ին վերին bitերի համար.

The coefficients for MT19937 are:

  • (w, n, m, r) = (32, 624, 397, 31)
  • a = 9908B0DF16
  • u = 11
  • (s, b) = (7, 9D2C568016)
  • (t, c) = (15, EFC6000016)
  • l = 18

Կեղծ կոդը[խմբագրել | խմբագրել կոդը]

pseudocode-ի հետևյալ կտորը առաջացնում է uniformly բաժանվող 32-bit integers Լեռնաշղթայի [0, 232 − 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,[10] designed to be fast when it runs on 128-bit SIMD.

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

Իրականացման տարբեր լեզուներով[խմբագրել | խմբագրել կոդը]

References[խմբագրել | խմբագրել կոդը]

  1. doi:10.1145/272991.272995
    This citation will be automatically completed in the next few minutes. You can jump the queue or expand by hand
  2. Matsumoto։ http://eprint.iacr.org/2005/165.pdf 
  3. http://www.ruby-doc.org/core/classes/Kernel.html#M005974։ Վերցված է 2010-02-24 
  4. Նշում: 219937 մոտավորապես 4.3 × 106001; սա շատ կարգադրությունների մագնիտուդով ավելի մեծ հաշվարկային քանակի մասնիկներ է observable universe-ի մեջ, որը 1087.
  5. P. L'Ecuyer and R. Simard, TestU01: "A C Library for Empirical Testing of Random Number Generators", ACM Transactions on Mathematical Software, 33, 4, Article 22, August 2007.
  6. Marsaglia on Mersenne Twister 2003
  7. Marsaglia on Mersenne Twister 2005
  8. P. L'Ecuyer, ``Uniform Random Number Generators, in International Encyclopedia of Statistical Science, Lovric, Miodrag (Ed.), Springer-Verlag, 2010.
  9. doi:10.1145/146382.146383
    This citation will be automatically completed in the next few minutes. You can jump the queue or expand by hand
  10. SIMD-oriented Fast Mersenne Twister (SFMT)
  11. SFMT:Comparison of speed
  12. PLAYSTATION 3 License
  13. http://www.nag.co.uk/numeric/fl/nagdoc_fl23/pdf/G05/g05intro.pdf։ Վերցված է 2012-02-09 

Արտաքին հղումներ[խմբագրել | խմբագրել կոդը]