Xoroshiro128 + - Xoroshiro128+

xoroshiro128 + (operatsiyalari nomi bilan nomlangan: XOR, aylantiring, siljiting, aylantiring) bu a pseudorandom tasodifiy generator uchun voris sifatida mo'ljallangan xorshift +. Marsalya an'anasini davom ettirish o'rniga xorshift asosiy operatsiya sifatida, xoroshiro128 + tomonidan ishlab chiqilgan siljish / aylantirish asosida chiziqli transformatsiyadan foydalaniladi Sebastiano Vigna Devid Blekman bilan hamkorlikda. Natijada tezlikning sezilarli yaxshilanishi va statistik sifatning sezilarli yaxshilanishi.[1]

Statistik sifat

Tomonidan ishlab chiqarilgan mahsulotning eng past bitlari xoroshiro128 + past sifatga ega. Mualliflari xoroshiro128 + barcha statistik testlardan o'tolmasligini bildiradi

Bu xoroshiro128 + 1.0, bizning suzuvchi nuqta raqamlari uchun eng yaxshi va eng tezkor kichik holatli generator. Uning yuqori bitlarini suzuvchi nuqta hosil qilish uchun ishlatishni taklif qilamiz, chunki u xoroshiro128 ** dan biroz tezroq. To'rt pastki bitdan tashqari, biz biladigan barcha sinovlardan o'tadi, bu chiziqli sinovlarda muvaffaqiyatsiz bo'lishi mumkin (va faqat o'sha), shuning uchun agar past chiziqli murakkablik muammo deb hisoblanmasa (odatdagidek), uni yaratish uchun ishlatilishi mumkin 64-bitli chiqishlar ham; Bundan tashqari, ushbu generator juda yumshoq Hamming-vaznga bog'liqlikka ega bo'lib, bizning sinovimizni amalga oshiradi (http://prng.di.unimi.it/hwd.php ) 5 TB chiqqandan keyin ishlamay qolishi; biz ishonamizki, bu biroz noaniqlik hech qanday dasturga ta'sir qilmaydi. Agar xavotirda bo'lsangiz, xoroshiro128 ** yoki xoshiro256 + dan foydalaning.

Mantiqiy tasodifiy qiymatni chiqarish uchun imo-ishora testini va bitlarning pastki to'plamlarini ajratish uchun o'ng siljishlardan foydalanishni taklif qilamiz.

Davlat hamma joyda nol bo'lmasligi uchun urug'lantirilishi kerak. Agar sizda 64-bitli urug 'bo'lsa, biz splitmix64 generatorini ekishni taklif qilamiz va uning natijasini s ni to'ldirish uchun ishlatamiz.

Izoh: ushbu versiyaning parametrlari (a = 24, b = 16, b = 37) biroz beradi

bizning testimizdagi 2016 yilgi versiyadan yaxshiroq natijalar (a = 55, b = 14, c = 36).[2]

Sinovlardan o'tmaslik haqidagi ushbu da'volarni PractRand-ni ishga tushirish orqali tasdiqlash mumkin, natijada quyida ko'rsatilgan natijaga erishiladi:

RNG_test PractRand versiyasidan foydalanib 0.93RNG = RNG_stdin64, seed = 0xfac83126test set = normal, folding = standard (64 bit) rng = RNG_stdin64, seed = 0xfac83126length = 128 megabayt (2 ^ 27 bayt), vaqt = 2,1 soniya Sinov nomi Xom qayta ishlangan baholash [ Low1 / 64] BRank (12): 256 (2) R = +3748 p ~ = 3e-1129 FAIL !!!!!!!! [Low1 / 64] BRank (12): 384 (1) R = +5405 p ~ = 3e-1628 FAIL !!!!!!!! ... va anomaliyalarsiz 146 ta test natijalari

Zaif buyurtma bitini tan olgan holda, mualliflar quyidagilarni aytadilar:

Biz tasodifiy mantiqiy qiymatni chiqarish uchun imo-ishora testidan foydalanishni taklif qilamiz[2]

Shunday qilib, dasturchilar eng yuqori bitlarni afzal ko'rishlari kerak (masalan, yozish orqali bosh / quyruq yasash) tasodifiy_nomera <0 dan ko'ra tasodifiy_sonlar va 1). Shuni ta'kidlash kerakki, xuddi shu test ba'zi bir holatlarda muvaffaqiyatsiz tugadi Mersen Tvister va Xo'sh.

Izohlarda aytib o'tilganidek, generator Blekman va Vigna tomonidan ishlab chiqarilgan Hamming vazniga bog'liqlik testini bajarolmaydi[3] 5 TB ma'lumotdan keyin. Taqqoslash uchun ba'zi parametrlarni tanlash uchun Mersen Tvister 607 bitda bir gigabaytdan kam ma'lumotdan so'ng bir xil sinovdan o'tmaydi.

Iqtiboslar

Buni amalga oshirgan Devid Mayster Klojure, bir nechta qimmatli bayonotlarni berdi:

"Bu tavsiflangan xoroshiro128 + PRNG-ni amalga oshirish http://xoroshiro.di.unimi.it. Algoritm tezkorligi va Java, shu jumladan tillar bilan jo'natilgan ko'plab PRNG-larga nisbatan yuqori statistik natijalarni ko'rsatishi ko'rsatilgan. Statistik natijalar PractRand va TestU01 da mualliflar tomonidan tasdiqlangan. xoroshiro128 + hozirda Chrome, Firefox va Safari-ning JavaScript dvigatellarida ishlatiladigan xorshift128 + ning vorisi sifatida ishlab chiqilgan. Ikkala xorshift128 + va xoroshiro128 + ning davri 2 ga teng128 lekin xoroshiro128 + mualliflar tomonidan 20% tezroq va BigCrush-da 20% kamroq muvaffaqiyatsizlikka uchraganligi bilan taqqoslangan. "[4]

Mett Gallager, Sviftda tasodifiy sonlar generatorlari bo'yicha olib borgan tadqiqotida quyidagi xulosaga keldi:

Xoroshiro hozirda mavjud bo'lgan eng yaxshi umumiy maqsadli algoritmga o'xshaydi. Kam xotira (bor-yo'g'i 128 bit xotira), juda yuqori mahsuldorlik (asosiy xarajatlarni olib tashlaganingizdan so'ng, 64 bitli raqamga 1,2 nanosekundiya) va juda yaxshi taqsimlangan (bir qator avtomatlashtirilgan testlarda boshqa algoritmlarni urib). Mersenne Tvister bunday yangi algoritmga o'tishni istamaydigan yuqori konservativ loyihalar uchun hali ham yaxshi tanlov bo'lishi mumkin, ammo statistik tekshirilgan algoritmlarning hozirgi avlodi avvalgi avlodlar etishmayotganidanoq ishonchning asosini keltirib chiqaradi.[5]

Tegishli generatorlar

  • xoroshiro128 ** past bitlardagi chiziqli artefaktlarning oldini oladi
  • xoshiro256 + 256 bit holatiga ega bo'lib, ko'proq parallellikka imkon beradi
  • xoshiro256 ** - "bizning barcha maqsadlarimiz uchun mo'ljallangan, qattiq generator"

+ Bilan tugaydigan generatorlar kuchsiz past bitlarga ega, shuning uchun ular faqat eng muhim 53 bitdan foydalanib, suzuvchi nuqta sonini yaratish uchun tavsiya etiladi.

Shuningdek qarang

Adabiyotlar

  1. ^ Blekman, Devid; Vigna, Sebastiano. "Scrambled Line Pseudorandom Generator". arXiv:1805.01407 [cs.DS ].
  2. ^ a b Blekman, Devid; Vigna, Sebastiano (2018). "Xoroshiro128 + ning asl C manba kodini amalga oshirish". Olingan 4-may, 2018.
  3. ^ "Hamming vazniga bog'liqlikni tekshirish". 2018 yil 3-may. Olingan 3-may, 2018.
  4. ^ Mayster, Devid (2016 yil 1-avgust). "Xoroshiro.di.unimi.it veb-saytida tavsiflangan xoroshiro128 + PRNG dasturlarini amalga oshirish". github.com. Olingan 2-noyabr, 2016.
  5. ^ Gallagher, Mett (2016 yil 19-may). "Swift-da tasodifiy raqamlar generatorlari". www.cocoawithlove.com. Olingan 2-noyabr, 2016.

Tashqi havolalar