Жалған кездейсоқ сандарды жасау алгоритмі: LCG генераторы, математикалық формула, тұрақтылар (модуль, көбейткіш, арттыру, бастама). Жылдам әрі қарапайым!
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Псевдокезеңдік сандарды жасау алгоритмі
Algorithm for generating pseudo randomized numbers
Сызықтық конгруенциялық генератор (LCG) – үзіліссіз бөліктік сызықтық теңдеу арқылы есептелген псевдокезеңдік сандар тізбегін шығаратын алгоритм. Бұл әдіс ең көне және ең танымал псевдокезеңдік сан генераторларының алгоритмдерінің бірі болып табылады. Оның теориялық негіздерін түсіну салыстырмалы түрде оңай, оларды оңай және жылдам іске асыруға болады, әсіресе модульдік арифметиканы сақтау битін қысқарту арқылы қамтамасыз ете алатын компьютерлік жабдықтарда. Генератор рекурренттік қатынас арқылы анықталады:
A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo randomized numbers calculated with a discontinuous piecewise linear equation. The method represents one of the oldest and best known pseudorandom number generator algorithms. The theory behind them is relatively easy to understand, and they are easily implemented and fast, especially on computer hardware which can provide modular arithmetic by storage bit truncation. The generator is defined by the recurrence relation:
мұнда – псевдокезеңдік мәндердің тізбегі, ал
where is the sequence of pseudo random values, and
— the "modulus"
— the "multiplier"
— the "increment"
— the "seed" or "start value"
генераторды анықтайтын бүтін сан тұрақтылары. Егер c = 0 болса, генератор көбінесе мультипликативтік конгруенциялық генератор (MCG) немесе Лехмер RNG деп аталады. Егер c ≠ 0 болса, әдіс аралас конгруенциялық генератор деп аталады. c ≠ 0 болғанда математик рекурренттік қатынасты сызықтық емес, аффиндік түрлендіру деп атайды, бірақ бұл қате атау компьютерлік ғылымда қалыптасқан.
are integer constants that specify the generator. If c = 0, the generator is often called a multiplicative congruential generator (MCG), or Lehmer RNG. If c ≠ 0, the method is called a mixed congruential generator. When c ≠ 0, a mathematician would call the recurrence an affine transformation, not a linear one, but the misnomer is well established in computer science.
Тарих
Лемер генераторы 1951 жылы, ал сызықтық конгруенциялық генератор 1958 жылы В. Э. Томсон және А. Ротенберг жариялаған.
The Lehmer generator was published in 1951 and the Linear congruential generator was published in 1958 by W. E. Thomson and A. Rotenberg.
m бірінші сан, c = 0
Бұл Lehmer RNG-нің бастапқы құрылымы. Егер a көбейтушісі m модульдік бүтін сандардың түпкілікті элементі ретінде таңдалса, кезеңі m-1 болады. Бастапқы күй 1 мен m-1 аралығында таңдалуы керек. Жақын модульдің бір кемшілігі – модульдік қысқарту екі есе кең өнімді және нақты қысқарту қадамын талап етеді. Көбінесе 2-нің дәрежесінен сәл кем жай сан қолданылады (Мерсеннің 231−1 және 261−1 жай сандары танымал), сондықтан m = 2e − d модулі бойынша азайту (ax mod 2e) + d ретінде есептеледі. Нәтиже тым үлкен болса, оған m-ді шартты түрде азайту қосылуы керек, бірақ азайтулар саны ad/m-мен шектеледі, ал d кішкентай болса, оны оңай бірге шектеуге болады. Егер екі есе кең өнім болмаса және көбейтуші сақтап таңдалса, Шраге әдісін қолдануға болады. Бұл үшін m = qa + r, яғни, және 1 = r = m mod a деп есептеңіз. Содан кейін ax mod m = есептелінеді. x mod q < q ≤ m/a болғандықтан, бірінші мүше am/a = m-ден кіші болады. Егер a таңдалса, онда r ≤ q (сонымен r/q ≤ 1), екінші мүше де m-ден кіші болады: r ≤ rx/q = x(r/q) ≤ x < m. Осылайша, екі өнім де бір кеңдікпен есептелуі мүмкін, ал олардың арасындағы айырмашылық [1−m, m−1] диапазонында жатыр, сондықтан оны бір шартты қосу арқылы [0, m−1] диапазонға дейін қысқартуға болады. Екінші кемшілік – 1 ≤ x < m мәнін біркелкі кездейсоқ биттерге түрлендіру қиын. Егер 2-нің дәрежесінен сәл кем жай сан қолданылса, кейде жоғалған мәндер жай ғана ескерілмейді.
This is the original Lehmer RNG construction. The period is m−1 if the multiplier a is chosen to be a primitive element of the integers modulo m. The initial state must be chosen between 1 and m−1. One disadvantage of a prime modulus is that the modular reduction requires a double width product and an explicit reduction step. Often a prime just less than a power of 2 is used (the Mersenne primes 231−1 and 261−1 are popular), so that the reduction modulo m = 2e − d can be computed as (ax mod 2e) + d This must be followed by a conditional subtraction of m if the result is too large, but the number of subtractions is limited to ad/m, which can be easily limited to one if d is small. If a double width product is unavailable, and the multiplier is chosen carefully, Schrage's method may be used. To do this, factor m = qa+r, i. e. and 1=r = m mod a. Then compute ax mod m = Since x mod q < q ≤ m/a, the first term is strictly less than am/a = m. If a is chosen so that r ≤ q (and thus r/q ≤ 1), then the second term is also less than m: r ≤ rx/q = x(r/q) ≤ x < m. Thus, both products can be computed with a single width product, and the difference between them lies in the range [1−m, m−1], so can be reduced to [0, m−1] with a single conditional add. A second disadvantage is that it is awkward to convert the value 1 ≤ x < m to uniform random bits. If a prime just less than a power of 2 is used, sometimes the missing values are simply ignored.
m a 2 -дің дәрежесі, c = 0
m-ді екінің дәрежесіне тең етіп таңдау, көбінесе m = 232 немесе m = 264, ерекше тиімді LCG-ді қамтамасыз етеді, себебі бұл модульдік амалды бинарлық өрнектің қысқаруы арқылы есептеуге мүмкіндік береді. Шындығында, ең маңызды биттер көбінесе есептелмейді. Дегенмен, кемшіліктері де бар. Бұл форманың максималды периоды m/4-ке тең, егер a ≡ ±3 (mod 8) және бастапқы X0 күйі тақ болса. Тіпті ең жақсы жағдайда, X-тің ең төменгі үш биті екі мәнді кезекпен алмастырады, демек күйге бір ғана бит үлесін қосады. X әрқашан тақ (ең төменгі бит ешқашан өзгермейді), және келесі екі биттің тек біреуі ғана өзгеріп отырады. Егер a ≡ +3 болса, X ±1 ↔ ±3 аралығында ауысады, ал егер a ≡ −3 болса, X ±1 ↔ ∓3 аралығында ауысады (барлығы 8-модуль бойынша). Бұл форманың модулі m/4 және c ≠ 0 болатын генераторға тең екенін көрсетуге болады. Екінің дәрежесін модуль ретінде пайдаланудың маңызды мәселесі – төменгі биттердің жоғары биттерге қарағанда қысқа периодына ие болуы. Оның оңай орындалуының себебі – биттерге жоғары ретті биттер ешқашан әсер етпейді, сондықтан мұндай генератордың төменгі b биті өздігінен 2b модульді LCG құрайды және 2b-2 периодымен қайталанады. Тек X-тің ең маңызды биті ғана толық периодқа жетеді.
Choosing m to be a power of two, most often m = 232 or m = 264, produces a particularly efficient LCG, because this allows the modulus operation to be computed by simply truncating the binary representation. In fact, the most significant bits are usually not computed at all. There are, however, disadvantages. This form has maximal period m/4, achieved if a ≡ ±3 (mod 8) and the initial state X0 is odd. Even in this best case, the low three bits of X alternate between two values and thus only contribute one bit to the state. X is always odd (the lowest order bit never changes), and only one of the next two bits ever changes. If a ≡ +3, X alternates ±1↔±3, while if a ≡ −3, X alternates ±1↔∓3 (all modulo 8). It can be shown that this form is equivalent to a generator with modulus m/4 and c ≠ 0. A more serious issue with the use of a power of two modulus is that the low bits have a shorter period than the high bits. Its simplicity of implementation comes from the fact that bits are never affected by higher order bits, so the low b bits of such a generator form a modulo 2b LCG by themselves, repeating with a period of 2b−2. Only the most significant bit of X achieves the full period.
LCG туындылары
Бірнеше генераторлар бар, олар әртүрлі формадағы сызықтық конгруенциялық генераторлар болып табылады, сондықтан LCG-ді талдауға қолданылатын техникалар оларға да қолданылуы мүмкін. Ұзақ кезеңді қамтамасыз етудің бір жолы – үлкен ең кіші ортақ еселігі бар әртүрлі кезеңдерге ие бірнеше LCG-нің нәтижелерін қосу болып табылады; Вихманн-Хилл генераторы осыған ұқсас мысал. (Олардың толыққанды өзара жай болуын қалаймыз, бірақ жай модуль жұп кезеңді білдіреді, сондықтан кем дегенде 2 ортақ бөлгіші болуы керек.) Бұл компоненттік LCG модульдерінің көбейтіндісіне тең модульге ие бір LCG-ге эквивалентті екенін көрсетуге болады. Марсальяның b=2w сөз өлшемімен және r және s (r > s) лагтарымен «қосып алып жүру» және «азайтып қарыз алу» PRNG-лері br ± bs ± 1 модулі бар LCG-ге баламалы. a көбейтімі бар PRNG-лер abr-1 үлкен жай модулі және 2 дәрежесіндегі b көбейтімі бар LCG-ге тең. Пермутацияланған конгруенциялық генератор 2 дәрежелі модульге ие LCG-ден басталады және төменгі реттік биттердегі қысқа кезең мәселесін жою үшін шығыс түрлендіруін қолданады.
There are several generators which are linear congruential generators in a different form, and thus the techniques used to analyze LCGs can be applied to them. One method of producing a longer period is to sum the outputs of several LCGs of different periods having a large least common multiple; the Wichmann–Hill generator is an example of this form. (We would prefer them to be completely coprime, but a prime modulus implies an even period, so there must be a common factor of 2, at least.) This can be shown to be equivalent to a single LCG with a modulus equal to the product of the component LCG moduli. Marsaglia's add with carry and subtract with borrow PRNGs with a word size of b=2w and lags r and s (r > s) are equivalent to LCGs with a modulus of br ± bs ± 1. Multiply with carry PRNGs with a multiplier of a are equivalent to LCGs with a large prime modulus of abr−1 and a power of 2 multiplier b. A permuted congruential generator begins with a power of 2 modulus LCG and applies an output transformation to eliminate the short period problem in the low order bits.
Басқа PRNG-мен салыстыру
Ұзақ мерзімді псевдокезеңсіз тізбектерді алу үшін тағы бір кеңінен қолданылатын бастауыш құрал – GF(2)[x] арифметикасына негізделген сызықтық кері байланыс тізбектік тіркегінің құрылысы, GF(2)[x] – 2-ден артық сандардың полиномдық сақинасы. Бұлыңғыр сандарды қосу және көбейтудің орнына негізгі амалдар – эксклюзивті немесе және көбейтудің қысқартылған түрі, ол әдетте логикалық ығысулар тізбегі арқылы іске асырылады. Бұлардың артықшылығы – олардың барлық биттері толық кезеңді болады; олар 2k модуліндегі арифметиканың әлсіздігінен зардап шекпейді, бұл төменгі разрядты биттерге зиян келтіреді. Бұл отбасыға xorshift генераторлары және Мерсенн бұралағы жатады. Соңғысы өте ұзақ кезеңді (219937−1) және өзгергіштік біртектілігін қамтамасыз етеді, бірақ кейбір статистикалық тесттерден өте алмайды. Кешіктірілген Фибоначчи генераторлары да осы санатқа жатады; олар арифметикалық қосуды қолданғанымен, олардың кезеңі ең кіші маңызды биттер арасында LFSR арқылы қамтамасыз етіледі. Сызықтық кері байланыс тізбектік тіркегінің құрылымын TestU01 жиынтығында іске асырылған сызықтық күрделілік тесті сияқты тиісті тесттермен анықтау оңай; LFSR-дің тізбекті биттерінен бастау алған бульдік айналмалы матрицаның ранкі полиномның дәрежесінен жоғары болмайды. Сызықтық емес шығыс араластыру функциясын қосу (xoshiro256** және пермутацияланған конгруенциялық генератор құрылымдарындағыдай) статистикалық тесттердегі өнімділіктің айтарлықтай жақсаруына әкелуі мүмкін. PRNG-нің тағы бір құрылымы – қуатты шығыс араластыру функциясымен біріктірілген өте қарапайым рекурсивті функция. Бұған қарсы режимдегі блок шифрлері және SplitMix64 сияқты криптографиялық емес генераторлар кіреді. LCG-ге ұқсас, бірақ эквивалентті емес құрылым – көп рекурсивті генератор: Xn = (a1Xn−1 + a2Xn−2 + ··· + akXn−k) mod m, k ≥ 2 үшін. Бас модульмен бұл mk-1 дейінгі кезеңдерді тудырады, сондықтан LCG құрылымын үлкен кезеңдерге кеңейтудің пайдалы тәсілі. Жоғары сапалы псевдокезеңсіз сандарды жасаудың тиімді әдісі – әртүрлі құрылымдарға ие екі немесе одан да көп PRNG-ді біріктіру; LFSR және LCG-нің қосындысы (KISS немесе xorwow құрылымдарындағыдай) жылдамдықтан кейбір шығынмен жақсы нәтиже бере алады.
The other widely used primitive for obtaining long period pseudorandom sequences is the linear feedback shift register construction, which is based on arithmetic in GF(2)[x], the polynomial ring over GF(2). Rather than integer addition and multiplication, the basic operations are exclusive or and carry less multiplication, which is usually implemented as a sequence of logical shifts. These have the advantage that all of their bits are full period; they do not suffer from the weakness in the low order bits that plagues arithmetic modulo 2k. Examples of this family include xorshift generators and the Mersenne twister. The latter provides a very long period (219937−1) and variate uniformity, but it fails some statistical tests. Lagged Fibonacci generators also fall into this category; although they use arithmetic addition, their period is ensured by an LFSR among the least significant bits. It is easy to detect the structure of a linear feedback shift register with appropriate tests such as the linear complexity test implemented in the TestU01 suite; a boolean circulant matrix initialized from consecutive bits of an LFSR will never have rank greater than the degree of the polynomial. Adding a non linear output mixing function (as in the xoshiro256** and permuted congruential generator constructions) can greatly improve the performance on statistical tests. Another structure for a PRNG is a very simple recurrence function combined with a powerful output mixing function. This includes counter mode block ciphers and non cryptographic generators such as SplitMix64. A structure similar to LCGs, but not equivalent, is the multiple recursive generator: Xn = (a1Xn−1 + a2Xn−2 + ··· + akXn−k) mod m for k ≥ 2. With a prime modulus, this can generate periods up to mk−1, so is a useful extension of the LCG structure to larger periods. A powerful technique for generating high quality pseudorandom numbers is to combine two or more PRNGs of different structure; the sum of an LFSR and an LCG (as in the KISS or xorwow constructions) can do very well at some cost in speed.