1780:
793: > 1, conditional subtraction can also be avoided, but the procedure is more intricate. The fundamental challenge of a modulus like 2 − 5 lies in ensuring that we produce only one representation for values such as 1 ≡ 2 − 4. The solution is to temporarily add
217:
Given the dynamic nature of the area, it is difficult for nonspecialists to make decisions about what generator to use. "Give me something I can understand, implement and port... it needn't be state-of-the-art, just make sure it's reasonably good and efficient." Our article and the associated minimal
2069:
This function can be called repeatedly to generate pseudorandom numbers, as long as the caller is careful to initialize the state to any number greater than zero and less than the modulus. In this implementation, 64-bit arithmetic is required; otherwise, the product of two 32-bit integers may
1521:
1561:
313:
will do). This produces the best-quality output, but introduces some implementation complexity, and the range of the output is unlikely to match the desired application; converting to the desired range requires an additional multiplication.
3709:(Note that the ZX81 manual incorrectly states that 65537 is a Mersenne prime that equals 2 − 1. The ZX Spectrum manual fixed that and correctly states that it is a Fermat prime that equals 2 + 1.)
340:
are always odd (bit 0 never changes), bits 2 and 1 alternate (the lower 3 bits repeat with a period of 2), the lower 4 bits repeat with a period of 4, and so on. Therefore, the application using these random numbers
1357:
398:; combining (e.g. by summing their outputs) several generators is equivalent to the output of a single generator whose modulus is the product of the component generators' moduli. and whose period is the
1775:{\displaystyle {\begin{aligned}ax&=a(x{\bmod {q}})+aq\lfloor x/q\rfloor \\&=a(x{\bmod {q}})+(m-r)\lfloor x/q\rfloor \\&\equiv a(x{\bmod {q}})-r\lfloor x/q\rfloor {\pmod {m}}\\\end{aligned}}}
3086:
Many other Lehmer generators have good properties. The following modulo-2 Lehmer generator requires 128-bit support from the compiler and uses a multiplier computed by L'Ecuyer. It has a period of 2:
1566:
1362:
3276:
The following core routine improves upon the speed of the above code for integer workloads (if the constant declaration is allowed to be optimized out of a calculation loop by the compiler):
102:
3269:. That test has been designed to catch exactly the defect of this type of generator: since the modulus is a power of 2, the period of the lowest bit in the output is only 2, rather than 2.
543:
1227:
is usually implemented using double-width multiplication, so this technique should be avoided if efficiency is a concern. Even in high-level languages, if the multiplier
575:
218:
standard generator was an attempt to respond to this request. Five years later, we see no need to alter our response other than to suggest the use of the multiplier
3791:
3394:
However, because the multiplication is deferred, it is not suitable for hashing, since the first call simply returns the upper 64 bits of the seed state.
585:
A prime modulus requires the computation of a double-width product and an explicit reduction step. If a modulus just less than a power of 2 is used (the
1134: < 2, the first reduction will produce a value in the range required for the preceding case of two reduction steps to apply.
345:
use the most significant bits; reducing to a smaller range using a modulo operation with an even modulus will produce disastrous results.
1516:{\displaystyle {\begin{aligned}aq&=a\cdot (m-r)/a\\&=(a/a)\cdot (m-r)\\&=(m-r)\\&\equiv -r{\pmod {m}}\\\end{aligned}}}
33:
1025: − 1 will work just the same, if that is more convenient. This reduces the offset to 0 in the Mersenne prime case, when
4137:
1945:, and may be implemented by the same technique. Because each step, on average, halves the size of the multiplier (0 ≤
4034:
395:
455:, it is a special case that implies certain restrictions and properties. In particular, for the Lehmer RNG, the initial seed
3855:
L'Ecuyer, Pierre; Tezuka, Shu (October 1991). "Structural
Properties for Two Classes of Combined Random Number Generators".
4084:
1957:−1)/2), this would appear to require one step per bit and be spectacularly inefficient. However, each step also divides
704:
subtraction can be replaced by an unconditional shift and addition. To see this, note that the algorithm guarantees that
3802:, ... The CRAY RANF function only rolls three of the six possible outcomes (which three sides depends on the seed)!
391: = 6700417 (which divides 2 + 1) or any multiple would lead to an output with a period of only 640.
3719:
3684:
701:
42:
201:. Although MINSTD was later criticized by Marsaglia and Sullivan (1993), it is still in use today (in particular, in
3755:
333:
bits form a modulo-2 generator all by themselves; the higher-order bits never affect lower-order bits. The values
3776:
4078:
589:
2 − 1 and 2 − 1 are popular, as are 2 − 5 and 2 − 59), reduction modulo
302:
Most commonly, the modulus is chosen as a prime number, making the choice of a coprime seed trivial (any 0 <
1224:
3270:
478:
is also more restrictive for the Lehmer RNG. In contrast to LCG, the maximum period of the Lehmer RNG equals
440:
29:
782:. Thus whether the high bit is 1 or 0, a second reduction step (addition of the halves) will never overflow
3793:
Fast
Generation of High-Quality Pseudorandom Numbers and Permutations Using MPI and OpenMP on the Cray XD1
1244:
can be computed using two single-width multiplications, and reduced using the techniques described above.
4142:
325:
makes for a particularly convenient computer implementation, but comes at a cost: the period is at most
4042:
1920:
by applying it recursively. Of the two terms subtracted to produce the final result, only the second (
286:
includes several random number generators of the Lehmer form, including MINSTD, RANF, and the infamous
519:
3649:
3605:
3561:
3514:
3470:
3419:
3911:
4056:
3688:
750: − 1 ≤ m − 2. Thus the first reduction step produces a value at most
377:= 2 + 1 might seem attractive, as the outputs can be easily mapped to a 32-bit word 0 ≤
551:
132:
3641:
3597:
1898:. Thus, the difference lies in the range and can be reduced to with a single conditional add.
731:-bit representations of the state; only values where the high bits are non-zero need reduction.
4051:
4013:
3943:
3906:
3462:
1075: − 1)2, and one reduction step converts this to at most 2 − 1 + (
406:
of 2, the moduli can be chosen so that is the only common divisor and the resultant period is (
283:
1981:, and quickly a point is reached where the argument is 0 and the recursion may be terminated.
3723:
399:
3891:
4092:
1122:, which is too large for the final reduction step. (It also requires the multiplication by
124:
8:
3554:"Technical correspondence: Remarks on Choosing and Implementing Random Number Generators"
3553:
1220:
4035:"Tables of linear congruential generators of different sizes and good lattice structure"
4002:
This explores several different implementations of modular multiplication by a constant.
3692:
689:
is a single-width product; if it is violated, a double-width product must be computed.)
599:
can be implemented more cheaply than a general double-width division using the identity
3993:
3924:
3872:
3837:
3779:. Vol. 2 (2nd ed.). Reading, MA: Addison-Wesley Professional. pp. 12–14.
3666:
3622:
3578:
3531:
3487:
3436:
498:
3506:
3535:
3411:
696: = 1), the procedure is particularly simple. Not only is multiplication by
428:
3997:
3928:
3841:
3670:
3626:
3582:
4061:
3983:
3916:
3864:
3827:
3658:
3614:
3570:
3549:
3523:
3491:
3479:
3440:
3428:
1939:
4065:
1114:, then it is possible for the first reduction step to produce a sum greater than 2
329:/4, and the lower bits have periods shorter than that. This is because the lowest
4088:
4117:
1161:
586:
403:
177:
4080:
Proceedings of a Second
Symposium on Large-Scale Digital Calculating Machinery
4131:
4077:
Lehmer, D. H. (1949). "Mathematical methods in large-scale computing units".
3727:
546:
371:
3944:"Computer Systems Performance Analysis Chapter 26: Random-Number Generation"
1913: < 0), changing the final reduction to a conditional subtract.
1013:(For the case of a Lehmer generator specifically, a zero state or its image
828:. In this case, a single offset subtraction step will produce 0 ≤
3768:
3258:
The generator computes an odd 128-bit value and returns its upper 64 bits.
322:
246:
172:
In 1988, Park and Miller suggested a Lehmer RNG with particular parameters
112:
21:
4105:
3988:
3971:
3920:
3832:
3815:
3662:
3618:
3574:
3432:
213:). Park, Miller and Stockmeyer responded to the criticism (1993), saying:
4121:
116:
3527:
3483:
3876:
2940:// The multiply result fits into 32 bits, but the sum might be 33 bits.
1146:, also called the approximate factoring method, may be used to compute
809:. Finally subtracting the temporary offset produces the desired value.
648:
until the result is in range. The number of subtractions is limited to
470:, which is not required for LCGs in general. The choice of the modulus
3741:
The ZX Spectrum uses p=65537 and a=75, and stores some bi-1 in memory.
202:
3868:
2934:// product = (product & 0xffffffff) + 5 * (product >> 32);
1938:) risks overflow. But this is itself a modular multiplication by a
28:(after Stephen K. Park and Keith W. Miller), is a type of
3266:
2937:// A multiplier larger than 0x33333333 = 858,993,459 would need it.
2931:// Not required because 5 * 279470273 = 0x5349e3c5 fits in 32 bits.
370:, or the period will be greatly reduced. For example, a modulus of
3409:
3262:
1785:
The reason it does not overflow is that both terms are less than
727:
are both impossible. This avoids the need to consider equivalent
463:
227:
206:
146:
3972:"Implementing a random number package with splitting facilities"
3640:
Park, Stephen K.; Miller, Keith W.; Stockmeyer, Paul K. (1988).
1219:
While this technique is popular for portable implementations in
439:
While the Lehmer RNG can be viewed as a particular case of the
1044:
can be done by one or more reduction steps without an offset.
3320:// GCC cannot write 128-bit literals, so we use an expression
3178:// GCC cannot write 128-bit literals, so we use an expression
2784:
Another popular Lehmer generator uses the prime modulus 2−5:
1990:
1717:
1650:
1592:
805:
bits in a way that never generates representations less than
291:
82:
774:
set), but the high half is at most 1, and if it is, the low
402:
of the component periods. Although the periods will share a
267:
238:
4099:
Annals of the
Computation Laboratory of Harvard University
3463:"Efficient and Portable Combined Random Number Generators"
3445:
812:
Begin by assuming that we have a partially reduced value
746:, and the high bits will never hold a value greater than
362:
Using a composite modulus is possible, but the generator
287:
2073:
To avoid the 64-bit division, do the reduction by hand:
1844: ≤ 1), then the second term is also less than
1223:
which lack double-width operations, on modern computers
1215:
One division (with remainder) per iteration is required.
3598:"Technical correspondence: Another test for randomness"
801:
through 2 − 1, and reduce values larger than
3798:
The die is determined using modular arithmetic, e.g.,
3756:
GNU Scientific
Library: Other random number generators
3507:"Random Number Generators: Good Ones Are Hard To Find"
766: + 1)-bit number, which can be greater than
614:
The basic reduction step divides the product into two
241:
and its successors use the Lehmer RNG with parameters
3732:(2nd ed.). Sinclair Research Ltd. pp. 73–75
2719:// max: 0x5e46c371 + 0x7fff8000 + 0xbc8e = 0xde46ffff
2239:
To use only 32-bit arithmetic, use
Schrage's method:
1993:
code, the Park-Miller RNG can be written as follows:
1564:
1360:
1055:, then one additional reduction step suffices. Since
554:
522:
394:
A more popular implementation for large periods is a
45:
3639:
2860:
This can also be written without a 64-bit division:
2659:// max: 65,535 * 48,271 = 3,163,439,985 = 0xbc8e4371
2620:// max: 32,767 * 48,271 = 1,581,695,857 = 0x5e46c371
2436:// max: 44,487 * 48,271 = 2,147,431,977 = 0x7fff3629
1009:, and subtracting the offset never causes underflow.
545:
represent a linear congruential sequence modulo the
348:
To achieve this period, the multiplier must satisfy
3273:with a power-of-2 modulus have a similar behavior.
1916:The technique may also be extended to allow larger
1901:This technique may be extended to allow a negative
158:
multiplicative linear congruential generator (MLCG)
3854:
3412:"Coding the Lehmer pseudo-random number generator"
2268:// Precomputed parameters for Schrage's method
1774:
1515:
1001:, as desired. Because the multiplied high part is
569:
537:
96:
3892:"A More Portable Fortran Random Number Generator"
3595:
3106:/* The state must be seeded with an odd value. */
1821:and may be computed with a single-width product.
4129:
3969:
97:{\displaystyle X_{k+1}=a\cdot X_{k}{\bmod {m}},}
3816:"Notes on a New Pseudo-Random Number Generator"
3410:W. H. Payne; J. R. Rabung; T. P. Bogyo (1969).
1164:; arithmetic operations must allow a range of ±
1130:bits, as mentioned above.) However, as long as
3790:Bique, Stephen; Rosenberg, Robert (May 2009).
3789:
762: − 2 = 2 − 4. This is an (
427: − 1)/2. One example of this is the
274:is a Lehmer RNG with the power-of-two modulus
1091: − 1. This is within the limit of 2
786:bits, and the sum will be the desired value.
674:is chosen. (This condition also ensures that
4120:may be useful for choosing moduli. Part of
3970:L'Ecuyer, Pierre; Côté, Serge (March 1991).
3460:
1749:
1735:
1694:
1680:
1627:
1613:
1142:If a double-width product is not available,
3813:
3505:Park, Stephen K.; Miller, Keith W. (1988).
352: ≡ ±3 (mod 8), and the seed
167:
162:multiplicative congruential generator (MCG)
3504:
1261:, i.e. precompute the auxiliary constants
797:, so that the range of possible values is
384: − 1 < 2. However, a seed of
4055:
3987:
3976:ACM Transactions on Mathematical Software
3965:
3963:
3910:
3899:ACM Transactions on Mathematical Software
3831:
3548:
525:
259: = 75 (a primitive root modulo
245: = 2 + 1 = 65,537 (a
34:multiplicative group of integers modulo n
4032:
3456:
3454:
3452:
3006:// This sum is guaranteed to be 32 bits.
656:, which can be easily limited to one if
618:-bit parts, multiplies the high part by
4011:
3889:
3848:
3718:
3683:
2460:// max: 48,271 * 3,399 = 164,073,129
1809:, the first term is strictly less than
1160:The modulus must be representable in a
4130:
4076:
3960:
3729:Sinclair ZX Spectrum Basic Programming
1247:To use Schrage's method, first factor
692:When the modulus is a Mersenne prime (
644:. This can be followed by subtracting
396:combined linear congruential generator
222: = 48271 in place of 16807.
190:= 7 = 16,807 (a primitive root modulo
3767:
3751:
3749:
3697:(2nd ed.). Sinclair Research Ltd
3449:
742:cannot represent a value larger than
282: = 44,485,709,377,909. The
24:), sometimes also referred to as the
4118:Primes just less than a power of two
3941:
3642:"Technical Correspondence: Response"
3261:This generator passes BigCrush from
482: − 1, and it is such when
297:
4012:Fenerty, Paul (11 September 2006).
1760:
1501:
1137:
1103:, which is the initial assumption.
873:. To see this, consider two cases:
26:Park–Miller random number generator
13:
3814:Greenberger, Martin (April 1961).
3746:
1984:
1021:will never occur, so an offset of
434:
366:be seeded with a value coprime to
226:This revised constant is used in
14:
4154:
4111:
4033:L’Ecuyer, Pierre (January 1999).
3706:The ZX81 uses p=65537 & a=75
2537:or use two 16×16-bit multiplies:
1126:to produce a product larger than
580:
1307:. Then, each iteration, compute
1240:, then the double-width product
1199:, commonly achieved by choosing
1175:is restricted. We require that
942: + 1)-bit number, and
778:bits will be strictly less than
538:{\displaystyle \mathbb {Z} _{m}}
4026:
4005:
3935:
3883:
3807:
3783:
3777:The Art of Computer Programming
3761:
3265:, but fails the TMFn test from
1961:by an ever-increasing quotient
1753:
1494:
4138:Pseudorandom number generators
3712:
3677:
3633:
3589:
3542:
3498:
3461:L'Ecuyer, Pierre (June 1988).
3403:
3271:Linear congruential generators
1764:
1754:
1726:
1710:
1677:
1665:
1659:
1643:
1601:
1585:
1505:
1495:
1474:
1462:
1449:
1437:
1431:
1417:
1396:
1384:
1156:, but this comes at the cost:
1099: − 1 <
816:bounded so that 0 ≤
564:
558:
18:Lehmer random number generator
1:
4066:10.1090/s0025-5718-99-00996-5
3397:
505:or any primitive root modulo
441:linear congruential generator
30:linear congruential generator
3890:Schrage, Linus (June 1979).
3724:"Chapter 11. Random numbers"
1351:This equality holds because
1118: = 2 − 2
1040: = 2 − 2
973:) − 2 +
7:
985: − 2 +
570:{\displaystyle \varphi (m)}
490:is a primitive root modulo
176:= 2 − 1 = 2,147,483,647 (a
10:
4159:
4043:Mathematics of Computation
3857:Mathematics of Computation
3596:Sullivan, Stephen (1993).
2412:// max: Q - 1 = 44,487
2385:// max: M / Q = A = 48,271
1032:Reducing a larger product
3942:Jain, Raj (9 July 2010).
3650:Communications of the ACM
3606:Communications of the ACM
3562:Communications of the ACM
3515:Communications of the ACM
3471:Communications of the ACM
3420:Communications of the ACM
1171:The choice of multiplier
234:random number generator.
36:. The general formula is
4106:Random Number Generators
3796:. Cray User Group 2009.
3773:Seminumerical Algorithms
3278:
3088:
2862:
2786:
2539:
2241:
2075:
1995:
290:random number generator
270:random number generator
168:Parameters in common use
930:In this case, 2 ≤
497:On the other hand, the
117:power of a prime number
32:(LCG) that operates in
3800:lrand48() % 6 + 1
3694:ZX81 Basic Programming
3689:"Chapter 5. Functions"
1776:
1517:
1225:division by a constant
1005:, the sum is at least
958: = 1. Thus,
824:= 2 − 2
571:
539:
284:GNU Scientific Library
224:
133:primitive root modulo
123:is an element of high
98:
3989:10.1145/103147.103158
3921:10.1145/355826.355828
3833:10.1145/321062.321065
3663:10.1145/159544.376068
3619:10.1145/159544.376068
3575:10.1145/159544.376068
3433:10.1145/362848.362860
1940:compile-time constant
1777:
1518:
770:(i.e. might have bit
572:
540:
400:least common multiple
215:
99:
1562:
1358:
1221:high-level languages
738:bits of the product
552:
520:
125:multiplicative order
43:
3528:10.1145/63039.63042
3484:10.1145/62959.62969
938:< 2 is an (
719: = 0 and
499:discrete logarithms
474:and the multiplier
420: − 1)···(
278: = 2 and
4143:Modular arithmetic
4101:, Vol. 26 (1951)).
4097:(journal version:
4014:"Schrage's Method"
3820:Journal of the ACM
3362:0x2e714eb2b37916a5
3350:0x12e15e35b500f16e
3220:0x2e714eb2b37916a5
3208:0x12e15e35b500f16e
1828:is chosen so that
1772:
1770:
1513:
1511:
758: − 1 ≤ 2
567:
535:
107:where the modulus
94:
3550:Marsaglia, George
3522:(10): 1192–1201.
1953:, average value (
1029: = 1.)
700:trivial, but the
622:, and adds them:
298:Choice of modulus
119:, the multiplier
4150:
4096:
4070:
4069:
4059:
4050:(225): 249–260.
4039:
4030:
4024:
4023:
4021:
4020:
4009:
4003:
4001:
3991:
3967:
3958:
3957:
3955:
3954:
3949:. pp. 19–22
3948:
3939:
3933:
3932:
3914:
3896:
3887:
3881:
3880:
3863:(196): 735–746.
3852:
3846:
3845:
3835:
3811:
3805:
3804:
3801:
3787:
3781:
3780:
3765:
3759:
3753:
3744:
3743:
3738:
3737:
3716:
3710:
3708:
3703:
3702:
3681:
3675:
3674:
3646:
3637:
3631:
3630:
3602:
3593:
3587:
3586:
3558:
3546:
3540:
3539:
3511:
3502:
3496:
3495:
3467:
3458:
3447:
3444:
3416:
3407:
3390:
3387:
3384:
3381:
3378:
3375:
3372:
3369:
3366:
3363:
3360:
3357:
3354:
3351:
3348:
3345:
3342:
3339:
3336:
3333:
3330:
3327:
3324:
3321:
3318:
3315:
3312:
3309:
3306:
3303:
3300:
3297:
3294:
3291:
3288:
3285:
3282:
3254:
3251:
3248:
3245:
3242:
3239:
3236:
3233:
3230:
3227:
3224:
3221:
3218:
3215:
3212:
3209:
3206:
3203:
3200:
3197:
3194:
3191:
3188:
3185:
3182:
3179:
3176:
3173:
3170:
3167:
3164:
3161:
3158:
3155:
3152:
3149:
3146:
3143:
3140:
3137:
3134:
3131:
3128:
3125:
3122:
3119:
3116:
3113:
3110:
3107:
3104:
3101:
3098:
3095:
3092:
3082:
3079:
3076:
3073:
3070:
3067:
3064:
3061:
3058:
3055:
3052:
3049:
3046:
3043:
3040:
3037:
3034:
3031:
3028:
3025:
3022:
3019:
3016:
3013:
3010:
3007:
3004:
3001:
2998:
2995:
2992:
2989:
2986:
2983:
2980:
2977:
2974:
2971:
2968:
2965:
2962:
2959:
2956:
2953:
2950:
2947:
2944:
2941:
2938:
2935:
2932:
2929:
2926:
2923:
2920:
2917:
2914:
2911:
2908:
2905:
2902:
2899:
2896:
2893:
2890:
2887:
2884:
2881:
2878:
2875:
2872:
2869:
2866:
2856:
2853:
2850:
2847:
2844:
2841:
2838:
2835:
2832:
2829:
2826:
2823:
2820:
2817:
2814:
2811:
2808:
2805:
2802:
2799:
2796:
2793:
2790:
2780:
2777:
2774:
2771:
2768:
2765:
2762:
2759:
2756:
2753:
2750:
2747:
2744:
2741:
2738:
2735:
2732:
2729:
2726:
2723:
2720:
2717:
2714:
2711:
2708:
2705:
2702:
2699:
2696:
2693:
2690:
2687:
2684:
2681:
2678:
2675:
2672:
2669:
2666:
2663:
2660:
2657:
2654:
2651:
2648:
2645:
2642:
2639:
2636:
2633:
2630:
2627:
2624:
2621:
2618:
2615:
2612:
2609:
2606:
2603:
2600:
2597:
2594:
2591:
2588:
2585:
2582:
2579:
2576:
2573:
2570:
2567:
2564:
2561:
2558:
2555:
2552:
2549:
2546:
2543:
2533:
2530:
2527:
2524:
2521:
2518:
2515:
2512:
2509:
2506:
2503:
2500:
2497:
2494:
2491:
2488:
2485:
2482:
2479:
2476:
2473:
2470:
2467:
2464:
2461:
2458:
2455:
2452:
2449:
2446:
2443:
2440:
2437:
2434:
2431:
2428:
2425:
2422:
2419:
2416:
2413:
2410:
2407:
2404:
2401:
2398:
2395:
2392:
2389:
2386:
2383:
2380:
2377:
2374:
2371:
2368:
2365:
2362:
2359:
2356:
2353:
2350:
2347:
2344:
2341:
2338:
2335:
2332:
2329:
2326:
2323:
2320:
2317:
2314:
2311:
2308:
2305:
2302:
2299:
2296:
2293:
2290:
2287:
2284:
2281:
2278:
2275:
2272:
2269:
2266:
2263:
2260:
2257:
2254:
2251:
2248:
2245:
2235:
2232:
2229:
2226:
2223:
2220:
2217:
2214:
2211:
2208:
2205:
2202:
2199:
2196:
2193:
2190:
2187:
2184:
2181:
2178:
2175:
2172:
2169:
2166:
2163:
2160:
2157:
2154:
2151:
2148:
2145:
2142:
2139:
2136:
2133:
2130:
2127:
2124:
2121:
2118:
2115:
2112:
2109:
2106:
2103:
2100:
2097:
2094:
2091:
2088:
2085:
2082:
2079:
2065:
2062:
2059:
2056:
2053:
2050:
2047:
2044:
2041:
2038:
2035:
2032:
2029:
2026:
2023:
2020:
2017:
2014:
2011:
2008:
2005:
2002:
1999:
1980:
1979:
1969:
1949: <
1937:
1927:
1865:
1855:
1781:
1779:
1778:
1773:
1771:
1767:
1745:
1725:
1724:
1700:
1690:
1658:
1657:
1633:
1623:
1600:
1599:
1554:
1544:
1526:so if we factor
1522:
1520:
1519:
1514:
1512:
1508:
1480:
1455:
1427:
1410:
1403:
1347:
1341:
1331:
1294:
1293:
1283:
1274:
1260:
1239:
1238:
1211:
1210:
1198:
1197:
1187:
1155:
1144:Schrage's method
1138:Schrage's method
1110: >
1067: <
1059: <
997: <
963:
957:
945:
910: <
904:
868:
863:
851:
833:
714:
688:
681:
673:
643:
642:
635:
610:
598:
576:
574:
573:
568:
544:
542:
541:
536:
534:
533:
528:
454:
453:
450:
413: − 1)(
317:Using a modulus
233:
212:
197:), now known as
156:Other names are
138:), and the seed
103:
101:
100:
95:
90:
89:
80:
79:
61:
60:
4158:
4157:
4153:
4152:
4151:
4149:
4148:
4147:
4128:
4127:
4114:
4073:
4037:
4031:
4027:
4018:
4016:
4010:
4006:
3968:
3961:
3952:
3950:
3946:
3940:
3936:
3912:10.1.1.470.6958
3894:
3888:
3884:
3869:10.2307/2938714
3853:
3849:
3812:
3808:
3799:
3788:
3784:
3766:
3762:
3754:
3747:
3735:
3733:
3717:
3713:
3700:
3698:
3682:
3678:
3644:
3638:
3634:
3600:
3594:
3590:
3556:
3547:
3543:
3509:
3503:
3499:
3465:
3459:
3450:
3414:
3408:
3404:
3400:
3392:
3391:
3388:
3385:
3382:
3379:
3376:
3373:
3370:
3367:
3364:
3361:
3358:
3355:
3352:
3349:
3346:
3343:
3340:
3337:
3334:
3331:
3328:
3325:
3322:
3319:
3316:
3313:
3310:
3307:
3304:
3301:
3298:
3295:
3292:
3289:
3286:
3283:
3280:
3256:
3255:
3252:
3249:
3246:
3243:
3240:
3237:
3234:
3231:
3228:
3225:
3222:
3219:
3216:
3213:
3210:
3207:
3204:
3201:
3198:
3195:
3192:
3189:
3186:
3183:
3180:
3177:
3174:
3171:
3168:
3165:
3162:
3159:
3156:
3153:
3150:
3147:
3144:
3141:
3138:
3135:
3132:
3129:
3126:
3123:
3120:
3117:
3114:
3111:
3108:
3105:
3102:
3099:
3096:
3093:
3090:
3084:
3083:
3080:
3077:
3074:
3071:
3068:
3065:
3062:
3059:
3056:
3053:
3050:
3047:
3044:
3041:
3038:
3035:
3032:
3029:
3026:
3023:
3020:
3017:
3014:
3011:
3008:
3005:
3002:
2999:
2996:
2993:
2990:
2987:
2984:
2981:
2978:
2975:
2972:
2969:
2966:
2963:
2960:
2957:
2954:
2951:
2948:
2945:
2942:
2939:
2936:
2933:
2930:
2927:
2924:
2921:
2918:
2915:
2912:
2909:
2906:
2903:
2900:
2897:
2894:
2891:
2888:
2885:
2882:
2879:
2876:
2873:
2870:
2867:
2864:
2858:
2857:
2854:
2851:
2848:
2845:
2842:
2839:
2836:
2833:
2830:
2827:
2824:
2821:
2818:
2815:
2812:
2809:
2806:
2803:
2800:
2797:
2794:
2791:
2788:
2782:
2781:
2778:
2775:
2772:
2769:
2766:
2763:
2760:
2757:
2754:
2751:
2748:
2745:
2742:
2739:
2736:
2733:
2730:
2727:
2724:
2721:
2718:
2715:
2712:
2709:
2706:
2703:
2700:
2697:
2694:
2691:
2688:
2685:
2682:
2679:
2676:
2673:
2670:
2667:
2664:
2661:
2658:
2655:
2652:
2649:
2646:
2643:
2640:
2637:
2634:
2631:
2628:
2625:
2622:
2619:
2616:
2613:
2610:
2607:
2604:
2601:
2598:
2595:
2592:
2589:
2586:
2583:
2580:
2577:
2574:
2571:
2568:
2565:
2562:
2559:
2556:
2553:
2550:
2547:
2544:
2541:
2535:
2534:
2531:
2528:
2525:
2522:
2519:
2516:
2513:
2510:
2507:
2504:
2501:
2498:
2495:
2492:
2489:
2486:
2483:
2480:
2477:
2474:
2471:
2468:
2465:
2462:
2459:
2456:
2453:
2450:
2447:
2444:
2441:
2438:
2435:
2432:
2429:
2426:
2423:
2420:
2417:
2414:
2411:
2408:
2405:
2402:
2399:
2396:
2393:
2390:
2387:
2384:
2381:
2378:
2375:
2372:
2369:
2366:
2363:
2360:
2357:
2354:
2351:
2348:
2345:
2342:
2339:
2336:
2333:
2330:
2327:
2324:
2321:
2318:
2315:
2312:
2309:
2306:
2303:
2300:
2297:
2294:
2291:
2288:
2285:
2282:
2279:
2276:
2273:
2270:
2267:
2264:
2261:
2258:
2255:
2252:
2249:
2246:
2243:
2237:
2236:
2233:
2230:
2227:
2224:
2221:
2218:
2215:
2212:
2209:
2206:
2203:
2200:
2197:
2194:
2191:
2188:
2185:
2182:
2179:
2176:
2173:
2170:
2167:
2164:
2161:
2158:
2155:
2152:
2149:
2146:
2143:
2140:
2137:
2134:
2131:
2128:
2125:
2122:
2119:
2116:
2113:
2110:
2107:
2104:
2101:
2098:
2095:
2092:
2089:
2086:
2083:
2080:
2077:
2067:
2066:
2063:
2060:
2057:
2054:
2051:
2048:
2045:
2042:
2039:
2036:
2033:
2030:
2027:
2024:
2021:
2018:
2015:
2012:
2009:
2006:
2003:
2000:
1997:
1987:
1985:Sample C99 code
1977:
1967:
1962:
1935:
1925:
1863:
1853:
1793: mod
1769:
1768:
1752:
1741:
1720:
1716:
1698:
1697:
1686:
1653:
1649:
1631:
1630:
1619:
1595:
1591:
1575:
1565:
1563:
1560:
1559:
1552:
1542:
1510:
1509:
1493:
1478:
1477:
1453:
1452:
1423:
1408:
1407:
1399:
1371:
1361:
1359:
1356:
1355:
1339:
1329:
1308:
1291:
1281:
1276:
1262:
1248:
1234:
1232:
1206:
1204:
1195:
1185:
1176:
1147:
1140:
1079: − 1)
961:
955:
943:
902:
861:
849:
835:
831:
715:, meaning that
705:
686:
679:
661:
640:
633:
623:
600:
590:
587:Mersenne primes
583:
553:
550:
549:
529:
524:
523:
521:
518:
517:
514:
466:to the modulus
461:
451:
448:
444:
437:
435:Relation to LCG
425:
419:
412:
390:
382:
375:
358:
338:
308:
300:
265:
254:
231:
210:
196:
185:
170:
144:
85:
81:
75:
71:
50:
46:
44:
41:
40:
12:
11:
5:
4156:
4146:
4145:
4140:
4126:
4125:
4113:
4112:External links
4110:
4109:
4108:
4102:
4072:
4071:
4057:10.1.1.34.1024
4025:
4004:
3959:
3934:
3905:(2): 132–138.
3882:
3847:
3826:(2): 163–167.
3806:
3782:
3760:
3745:
3720:Vickers, Steve
3711:
3685:Vickers, Steve
3676:
3657:(7): 108–110.
3632:
3588:
3569:(7): 105–108.
3541:
3497:
3478:(6): 742–774.
3448:
3401:
3399:
3396:
3279:
3089:
2863:
2787:
2545:lcg_parkmiller
2540:
2247:lcg_parkmiller
2242:
2081:lcg_parkmiller
2076:
2001:lcg_parkmiller
1996:
1986:
1983:
1783:
1782:
1766:
1763:
1759:
1756:
1751:
1748:
1744:
1740:
1737:
1734:
1731:
1728:
1723:
1719:
1715:
1712:
1709:
1706:
1703:
1701:
1699:
1696:
1693:
1689:
1685:
1682:
1679:
1676:
1673:
1670:
1667:
1664:
1661:
1656:
1652:
1648:
1645:
1642:
1639:
1636:
1634:
1632:
1629:
1626:
1622:
1618:
1615:
1612:
1609:
1606:
1603:
1598:
1594:
1590:
1587:
1584:
1581:
1578:
1576:
1574:
1571:
1568:
1567:
1524:
1523:
1507:
1504:
1500:
1497:
1492:
1489:
1486:
1483:
1481:
1479:
1476:
1473:
1470:
1467:
1464:
1461:
1458:
1456:
1454:
1451:
1448:
1445:
1442:
1439:
1436:
1433:
1430:
1426:
1422:
1419:
1416:
1413:
1411:
1409:
1406:
1402:
1398:
1395:
1392:
1389:
1386:
1383:
1380:
1377:
1374:
1372:
1370:
1367:
1364:
1363:
1231:is limited to
1217:
1216:
1213:
1169:
1162:signed integer
1139:
1136:
1036:to less than 2
1011:
1010:
965: = (
928:
915:
891:In this case,
889:
582:
581:Implementation
579:
566:
563:
560:
557:
532:
527:
512:
459:
436:
433:
423:
417:
410:
404:common divisor
388:
380:
373:
356:
336:
306:
299:
296:
263:
252:
194:
183:
178:Mersenne prime
169:
166:
142:
105:
104:
93:
88:
84:
78:
74:
70:
67:
64:
59:
56:
53:
49:
9:
6:
4:
3:
2:
4155:
4144:
4141:
4139:
4136:
4135:
4133:
4123:
4119:
4116:
4115:
4107:
4103:
4100:
4094:
4090:
4086:
4082:
4081:
4075:
4074:
4067:
4063:
4058:
4053:
4049:
4045:
4044:
4036:
4029:
4015:
4008:
3999:
3995:
3990:
3985:
3982:(1): 98–111.
3981:
3977:
3973:
3966:
3964:
3945:
3938:
3930:
3926:
3922:
3918:
3913:
3908:
3904:
3900:
3893:
3886:
3878:
3874:
3870:
3866:
3862:
3858:
3851:
3843:
3839:
3834:
3829:
3825:
3821:
3817:
3810:
3803:
3795:
3794:
3786:
3778:
3774:
3770:
3769:Knuth, Donald
3764:
3757:
3752:
3750:
3742:
3731:
3730:
3725:
3721:
3715:
3707:
3696:
3695:
3690:
3686:
3680:
3672:
3668:
3664:
3660:
3656:
3652:
3651:
3643:
3636:
3628:
3624:
3620:
3616:
3612:
3608:
3607:
3599:
3592:
3584:
3580:
3576:
3572:
3568:
3564:
3563:
3555:
3551:
3545:
3537:
3533:
3529:
3525:
3521:
3517:
3516:
3508:
3501:
3493:
3489:
3485:
3481:
3477:
3473:
3472:
3464:
3457:
3455:
3453:
3446:
3442:
3438:
3434:
3430:
3426:
3422:
3421:
3413:
3406:
3402:
3395:
3277:
3274:
3272:
3268:
3264:
3259:
3087:
2861:
2785:
2538:
2240:
2074:
2071:
1994:
1992:
1982:
1976:
1972:
1965:
1960:
1956:
1952:
1948:
1944:
1941:
1934:
1930:
1923:
1919:
1914:
1912:
1909: ≤
1908:
1904:
1899:
1897:
1893:
1889:
1885:
1881:
1877:
1873:
1869:
1862:
1858:
1851:
1847:
1843:
1839:
1835:
1832: ≤
1831:
1827:
1822:
1820:
1817: =
1816:
1812:
1808:
1804:
1800:
1796:
1792:
1788:
1761:
1757:
1746:
1742:
1738:
1732:
1729:
1721:
1713:
1707:
1704:
1702:
1691:
1687:
1683:
1674:
1671:
1668:
1662:
1654:
1646:
1640:
1637:
1635:
1624:
1620:
1616:
1610:
1607:
1604:
1596:
1588:
1582:
1579:
1577:
1572:
1569:
1558:
1557:
1556:
1551:
1547:
1541:
1537:
1533:
1529:
1502:
1498:
1490:
1487:
1484:
1482:
1471:
1468:
1465:
1459:
1457:
1446:
1443:
1440:
1434:
1428:
1424:
1420:
1414:
1412:
1404:
1400:
1393:
1390:
1387:
1381:
1378:
1375:
1373:
1368:
1365:
1354:
1353:
1352:
1349:
1345:
1338:
1334:
1327:
1323:
1319:
1315:
1311:
1306:
1302:
1298:
1290:
1286:
1279:
1273:
1269:
1265:
1259:
1255:
1251:
1245:
1243:
1237:
1230:
1226:
1222:
1214:
1209:
1203: ≤
1202:
1194:
1190:
1183:
1179:
1174:
1170:
1167:
1163:
1159:
1158:
1157:
1154:
1150:
1145:
1135:
1133:
1129:
1125:
1121:
1117:
1113:
1109:
1104:
1102:
1098:
1094:
1090:
1087: +
1086:
1083: =
1082:
1078:
1074:
1070:
1066:
1062:
1058:
1054:
1051: ≤
1050:
1045:
1043:
1039:
1035:
1030:
1028:
1024:
1020:
1017: =
1016:
1008:
1004:
1000:
996:
993: −
992:
988:
984:
980:
977: −
976:
972:
969: +
968:
964:
953:
950: +
949:
941:
937:
934: +
933:
929:
927:
923:
919:
916:
914:, as desired.
913:
909:
906: =
905:
898:
894:
890:
888:
884:
880:
876:
875:
874:
872:
867:
859:
856: +
855:
847:
843:
840: +
839:
834:
827:
823:
819:
815:
810:
808:
804:
800:
796:
792:
787:
785:
781:
777:
773:
769:
765:
761:
757:
754: +
753:
749:
745:
741:
737:
732:
730:
726:
723: =
722:
718:
712:
708:
703:
699:
695:
690:
684:
677:
672:
668:
664:
660:is small and
659:
655:
651:
647:
638:
631:
627:
621:
617:
612:
608:
604:
597:
593:
588:
578:
561:
555:
548:
547:Euler totient
530:
515:
508:
504:
500:
495:
493:
489:
486:is prime and
485:
481:
477:
473:
469:
465:
458:
447:
442:
432:
430:
429:Wichmann–Hill
426:
416:
409:
405:
401:
397:
392:
387:
383:
376:
369:
365:
360:
359:must be odd.
355:
351:
346:
344:
339:
332:
328:
324:
320:
315:
312:
305:
295:
293:
289:
285:
281:
277:
273:
269:
262:
258:
251:
248:
244:
240:
239:Sinclair ZX81
235:
229:
223:
221:
214:
208:
204:
200:
193:
189:
182:
179:
175:
165:
163:
159:
154:
152:
148:
141:
137:
136:
130:
126:
122:
118:
114:
110:
91:
86:
76:
72:
68:
65:
62:
57:
54:
51:
47:
39:
38:
37:
35:
31:
27:
23:
20:(named after
19:
4104:Steve Park,
4098:
4079:
4047:
4041:
4028:
4017:. Retrieved
4007:
3979:
3975:
3951:. Retrieved
3937:
3902:
3898:
3885:
3860:
3856:
3850:
3823:
3819:
3809:
3797:
3792:
3785:
3772:
3763:
3740:
3734:. Retrieved
3728:
3714:
3705:
3699:. Retrieved
3693:
3679:
3654:
3648:
3635:
3610:
3604:
3591:
3566:
3560:
3544:
3519:
3513:
3500:
3475:
3469:
3427:(2): 85–86.
3424:
3418:
3405:
3393:
3275:
3260:
3257:
3085:
2859:
2783:
2536:
2238:
2072:
2068:
1988:
1974:
1970:
1963:
1958:
1954:
1950:
1946:
1942:
1932:
1928:
1921:
1917:
1915:
1910:
1906:
1902:
1900:
1895:
1891:
1887:
1883:
1879:
1875:
1871:
1867:
1860:
1856:
1849:
1845:
1841:
1837:
1833:
1829:
1825:
1823:
1818:
1814:
1810:
1806:
1802:
1798:
1794:
1790:
1786:
1784:
1549:
1545:
1539:
1535:
1531:
1527:
1525:
1350:
1343:
1336:
1332:
1325:
1321:
1317:
1313:
1309:
1304:
1300:
1296:
1288:
1284:
1277:
1271:
1267:
1263:
1257:
1253:
1249:
1246:
1241:
1235:
1228:
1218:
1207:
1200:
1192:
1188:
1181:
1177:
1172:
1165:
1152:
1148:
1143:
1141:
1131:
1127:
1123:
1119:
1115:
1111:
1107:
1105:
1100:
1096:
1092:
1088:
1084:
1080:
1076:
1072:
1068:
1064:
1060:
1056:
1052:
1048:
1046:
1041:
1037:
1033:
1031:
1026:
1022:
1018:
1014:
1012:
1006:
1002:
998:
994:
990:
986:
982:
978:
974:
970:
966:
959:
951:
947:
939:
935:
931:
925:
921:
917:
911:
907:
900:
896:
892:
886:
882:
878:
870:
865:
857:
853:
845:
841:
837:
829:
825:
821:
820: < 2
817:
813:
811:
806:
802:
798:
794:
790:
788:
783:
779:
775:
771:
767:
763:
759:
755:
751:
747:
743:
739:
735:
733:
728:
724:
720:
716:
710:
706:
697:
693:
691:
682:
675:
670:
666:
662:
657:
653:
649:
645:
636:
629:
625:
619:
615:
613:
606:
602:
595:
591:
584:
510:
506:
502:
496:
491:
487:
483:
479:
475:
471:
467:
456:
445:
438:
421:
414:
407:
393:
385:
378:
367:
363:
361:
353:
349:
347:
342:
334:
330:
326:
323:power of two
318:
316:
310:
303:
301:
279:
275:
271:
260:
256:
249:
247:Fermat prime
242:
236:
225:
219:
216:
211:minstd_rand0
198:
191:
187:
180:
173:
171:
161:
157:
155:
150:
139:
134:
128:
120:
113:prime number
108:
106:
25:
22:D. H. Lehmer
17:
15:
4122:Prime Pages
4083:. pp.
899:< 2 and
844:) mod 2) +
702:conditional
431:generator.
321:which is a
232:minstd_rand
4132:Categories
4019:2017-10-31
3953:2017-10-31
3736:2022-05-26
3701:2024-04-21
3613:(7): 108.
3398:References
2958:0xffffffff
2916:279470273u
2849:0xfffffffb
2843:279470273u
2737:0x7fffffff
2283:0x7fffffff
2192:0x7fffffff
2153:0x7fffffff
2070:overflow.
2058:0x7fffffff
1836:(and thus
1555:, we get:
869:<
4052:CiteSeerX
3907:CiteSeerX
3536:207575300
3267:PractRand
1789:. Since
1750:⌋
1736:⌊
1730:−
1705:≡
1695:⌋
1681:⌊
1672:−
1628:⌋
1614:⌊
1488:−
1485:≡
1469:−
1444:−
1435:⋅
1391:−
1382:⋅
709:≢ 0 (mod
628:mod 2) +
556:φ
501:(to base
203:CarbonLib
131:(e.g., a
69:⋅
3998:14385204
3929:14090729
3842:17196519
3771:(1981).
3722:(1983).
3687:(1981).
3671:26156905
3627:26156905
3583:26156905
3552:(1993).
3353:<<
3344:__int128
3341:unsigned
3329:__int128
3326:unsigned
3311:>>
3299:uint64_t
3281:uint64_t
3244:>>
3211:<<
3202:__int128
3199:unsigned
3187:__int128
3184:unsigned
3160:uint64_t
3142:<<
3121:__int128
3118:unsigned
3097:__int128
3094:unsigned
3048:>>
3039:uint32_t
3018:uint32_t
2985:>>
2976:uint32_t
2922:uint32_t
2901:uint64_t
2889:uint64_t
2874:uint32_t
2868:lcg_rand
2865:uint32_t
2828:uint64_t
2798:uint32_t
2792:lcg_rand
2789:uint32_t
2752:>>
2710:>>
2692:<<
2662:uint32_t
2641:>>
2623:uint32_t
2584:uint32_t
2569:uint32_t
2551:uint32_t
2542:uint32_t
2388:uint32_t
2361:uint32_t
2358:// 3399
2337:uint32_t
2331:// 44488
2310:uint32_t
2292:uint32_t
2274:uint32_t
2253:uint32_t
2244:uint32_t
2207:>>
2168:>>
2135:uint32_t
2114:uint64_t
2102:uint64_t
2087:uint32_t
2078:uint32_t
2037:uint64_t
2007:uint32_t
1998:uint32_t
1071:≤ (
734:The low
462:must be
4093:0044899
3877:2938714
3492:9593394
3441:2749316
3263:TestU01
3045:product
3024:product
2994:product
2982:product
2952:product
2943:product
2892:product
2463:int32_t
2439:int32_t
2415:int32_t
2165:product
2147:product
2105:product
1924:
1852:
1328:
1233:√
1205:√
989:=
981:=
848:
678:
632:
464:coprime
266:). The
147:coprime
127:modulo
4091:
4087:–146.
4054:
3996:
3927:
3909:
3875:
3840:
3669:
3625:
3581:
3534:
3490:
3439:
3383:result
3380:return
3302:result
3238:return
3091:static
3057:return
2813:return
2761:return
2686:0xffff
2605:0x7fff
2526:result
2514:return
2502:result
2490:result
2466:result
2216:return
2022:return
1989:Using
1890:(1) =
924:< 2
885:= 2 −
594:= 2 −
255:) and
199:MINSTD
186:) and
4038:(PDF)
3994:S2CID
3947:(PDF)
3925:S2CID
3895:(PDF)
3873:JSTOR
3838:S2CID
3667:S2CID
3645:(PDF)
3623:S2CID
3601:(PDF)
3579:S2CID
3557:(PDF)
3532:S2CID
3510:(PDF)
3488:S2CID
3466:(PDF)
3437:S2CID
3415:(PDF)
3368:state
3323:const
3308:state
3241:state
3226:state
3181:const
3133:state
3100:state
3063:state
2955:&
2910:state
2880:state
2837:state
2819:state
2804:state
2767:state
2734:&
2683:&
2638:state
2602:&
2599:state
2578:48271
2566:const
2557:state
2520:state
2400:state
2373:state
2334:const
2307:const
2301:48271
2289:const
2271:const
2259:state
2222:state
2189:&
2150:&
2129:48271
2123:state
2093:state
2052:48271
2046:state
2028:state
2013:state
1894:<
1797:<
1342:(mod
881:<
665:<
605:(mod
509:) of
443:with
309:<
292:RANDU
228:C++11
207:C++11
115:or a
111:is a
3374:mult
3332:mult
3290:void
3284:next
3232:mult
3190:mult
3169:void
3163:next
3139:seed
3124:seed
3112:seed
3109:void
2707:high
2680:high
2626:high
2493:<
1886:) ≤
1538:) +
1534:mod
1324:) −
1320:mod
1275:and
1270:mod
1180:mod
1151:mod
877:0 ≤
836:= ((
601:2 ≡
364:must
343:must
272:RANF
268:CRAY
237:The
205:and
160:and
16:The
4085:141
4062:doi
3984:doi
3917:doi
3865:doi
3828:doi
3659:doi
3615:doi
3571:doi
3524:doi
3480:doi
3429:doi
2671:low
2587:low
2448:div
2424:rem
2391:rem
2364:div
1824:If
1758:mod
1718:mod
1651:mod
1593:mod
1530:= (
1499:mod
1295:= (
1106:If
1095:if
1047:If
954:)/2
860:)/2
789:If
516:in
288:IBM
230:'s
209:'s
149:to
145:is
83:mod
4134::
4089:MR
4060:.
4048:68
4046:.
4040:.
3992:.
3980:17
3978:.
3974:.
3962:^
3923:.
3915:.
3901:.
3897:.
3871:.
3861:57
3859:.
3836:.
3822:.
3818:.
3775:.
3748:^
3739:.
3726:.
3704:.
3691:.
3665:.
3655:36
3653:.
3647:.
3621:.
3611:36
3609:.
3603:.
3577:.
3567:36
3565:.
3559:.
3530:.
3520:31
3518:.
3512:.
3486:.
3476:31
3474:.
3468:.
3451:^
3435:.
3425:12
3423:.
3417:.
3371:*=
3356:64
3314:64
3247:64
3229:*=
3214:64
3054:);
3051:32
3042:)(
2997:+=
2991:);
2988:32
2979:)(
2758:);
2755:31
2716:);
2713:16
2695:15
2677:((
2644:15
2505:+=
2484:if
2213:);
2210:31
2174:);
2171:31
1966:=
1905:(−
1874:=
1868:rx
1866:≤
1848::
1811:am
1801:≤
1348:.
1312:≡
1310:ax
1303:)/
1280:=
1266:=
1256:+
1254:qa
1252:=
1242:ax
1184:≤
1149:ax
1108:ad
1097:ad
1089:ad
1069:am
1065:ax
1063:,
1049:ad
1034:ax
920:≤
895:+
864:−
740:ax
685:/2
683:ax
650:ad
639:/2
637:ax
626:ax
611:.
577:.
494:.
294:.
195:31
184:31
164:.
153:.
4124:.
4095:.
4068:.
4064::
4022:.
4000:.
3986::
3956:.
3931:.
3919::
3903:5
3879:.
3867::
3844:.
3830::
3824:8
3758:.
3673:.
3661::
3629:.
3617::
3585:.
3573::
3538:.
3526::
3494:.
3482::
3443:.
3431::
3389:}
3386:;
3377:;
3365:;
3359:|
3347:)
3338:(
3335:=
3317:;
3305:=
3296:{
3293:)
3287:(
3253:}
3250:;
3235:;
3223:;
3217:|
3205:)
3196:(
3193:=
3175:{
3172:)
3166:(
3157:}
3154:;
3151:1
3148:|
3145:1
3136:=
3130:{
3127:)
3115:(
3103:;
3081:}
3078:;
3075:4
3072:-
3069:x
3066:=
3060:*
3036:(
3033:*
3030:5
3027:+
3021:)
3015:(
3012:=
3009:x
3003:;
3000:4
2973:(
2970:*
2967:5
2964:+
2961:)
2949:(
2946:=
2928:;
2925:x
2919:;
2913:*
2907:*
2904:)
2898:(
2895:=
2886:{
2883:)
2877:*
2871:(
2855:}
2852:;
2846:%
2840:*
2834:*
2831:)
2825:(
2822:=
2816:*
2810:{
2807:)
2801:*
2795:(
2779:}
2776:;
2773:x
2770:=
2764:*
2749:x
2746:(
2743:+
2740:)
2731:x
2728:(
2725:=
2722:x
2704:(
2701:+
2698:)
2689:)
2674:+
2668:=
2665:x
2656:;
2653:A
2650:*
2647:)
2635:*
2632:(
2629:=
2617:;
2614:A
2611:*
2608:)
2596:*
2593:(
2590:=
2581:;
2575:=
2572:A
2563:{
2560:)
2554:*
2548:(
2532:}
2529:;
2523:=
2517:*
2511:;
2508:M
2499:)
2496:0
2487:(
2481:;
2478:t
2475:-
2472:s
2469:=
2457:;
2454:R
2451:*
2445:=
2442:t
2433:;
2430:A
2427:*
2421:=
2418:s
2409:;
2406:Q
2403:%
2397:*
2394:=
2382:;
2379:Q
2376:/
2370:*
2367:=
2355:;
2352:A
2349:%
2346:M
2343:=
2340:R
2328:;
2325:A
2322:/
2319:M
2316:=
2313:Q
2304:;
2298:=
2295:A
2286:;
2280:=
2277:M
2265:{
2262:)
2256:*
2250:(
2234:}
2231:;
2228:x
2225:=
2219:*
2204:x
2201:(
2198:+
2195:)
2186:x
2183:(
2180:=
2177:x
2162:(
2159:+
2156:)
2144:(
2141:=
2138:x
2132:;
2126:*
2120:*
2117:)
2111:(
2108:=
2099:{
2096:)
2090:*
2084:(
2064:}
2061:;
2055:%
2049:*
2043:*
2040:)
2034:(
2031:=
2025:*
2019:{
2016:)
2010:*
2004:(
1991:C
1978:⌋
1975:a
1973:/
1971:m
1968:⌊
1964:q
1959:x
1955:a
1951:a
1947:r
1943:r
1936:⌋
1933:q
1931:/
1929:x
1926:⌊
1922:r
1918:a
1911:r
1907:q
1903:r
1896:m
1892:x
1888:x
1884:q
1882:/
1880:r
1878:(
1876:x
1872:q
1870:/
1864:⌋
1861:q
1859:/
1857:x
1854:⌊
1850:r
1846:m
1842:q
1840:/
1838:r
1834:q
1830:r
1826:a
1819:m
1815:a
1813:/
1807:a
1805:/
1803:m
1799:q
1795:q
1791:x
1787:m
1765:)
1762:m
1755:(
1747:q
1743:/
1739:x
1733:r
1727:)
1722:q
1714:x
1711:(
1708:a
1692:q
1688:/
1684:x
1678:)
1675:r
1669:m
1666:(
1663:+
1660:)
1655:q
1647:x
1644:(
1641:a
1638:=
1625:q
1621:/
1617:x
1611:q
1608:a
1605:+
1602:)
1597:q
1589:x
1586:(
1583:a
1580:=
1573:x
1570:a
1553:⌋
1550:q
1548:/
1546:x
1543:⌊
1540:q
1536:q
1532:x
1528:x
1506:)
1503:m
1496:(
1491:r
1475:)
1472:r
1466:m
1463:(
1460:=
1450:)
1447:r
1441:m
1438:(
1432:)
1429:a
1425:/
1421:a
1418:(
1415:=
1405:a
1401:/
1397:)
1394:r
1388:m
1385:(
1379:a
1376:=
1369:q
1366:a
1346:)
1344:m
1340:⌋
1337:q
1335:/
1333:x
1330:⌊
1326:r
1322:q
1318:x
1316:(
1314:a
1305:a
1301:r
1299:−
1297:m
1292:⌋
1289:a
1287:/
1285:m
1282:⌊
1278:q
1272:a
1268:m
1264:r
1258:r
1250:m
1236:m
1229:a
1212:.
1208:m
1201:a
1196:⌋
1193:a
1191:/
1189:m
1186:⌊
1182:a
1178:m
1173:a
1168:.
1166:m
1153:m
1132:d
1128:e
1124:d
1120:d
1116:m
1112:m
1101:m
1093:m
1085:m
1081:d
1077:a
1073:a
1061:m
1057:x
1053:m
1042:d
1038:m
1027:d
1023:d
1019:m
1015:y
1007:d
1003:d
999:m
995:m
991:y
987:d
983:y
979:d
975:d
971:d
967:y
962:′
960:y
956:⌋
952:d
948:y
946:(
944:⌊
940:e
936:d
932:y
926:m
922:y
918:m
912:m
908:y
903:′
901:y
897:d
893:y
887:d
883:m
879:y
871:m
866:d
862:⌋
858:d
854:y
852:(
850:⌊
846:d
842:d
838:y
832:′
830:y
826:d
822:m
818:y
814:y
807:d
803:e
799:d
795:d
791:d
784:e
780:m
776:e
772:e
768:m
764:e
760:m
756:a
752:m
748:a
744:m
736:e
729:e
725:m
721:x
717:x
713:)
711:m
707:x
698:d
694:d
687:⌋
680:⌊
676:d
671:d
669:/
667:m
663:a
658:d
654:m
652:/
646:m
641:⌋
634:⌊
630:d
624:(
620:d
616:e
609:)
607:m
603:d
596:d
592:m
565:)
562:m
559:(
531:m
526:Z
513:k
511:X
507:m
503:a
492:m
488:a
484:m
480:m
476:a
472:m
468:m
460:0
457:X
452:0
449:=
446:c
424:k
422:m
418:2
415:m
411:1
408:m
389:0
386:X
381:i
379:X
374:5
372:F
368:m
357:0
354:X
350:a
337:i
335:X
331:k
327:m
319:m
311:m
307:0
304:X
280:a
276:m
264:4
261:F
257:a
253:4
250:F
243:m
220:a
192:M
188:a
181:M
174:m
151:m
143:0
140:X
135:n
129:m
121:a
109:m
92:,
87:m
77:k
73:X
66:a
63:=
58:1
55:+
52:k
48:X
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.