1207:
22:
429:= 3, an LCG could have up to 2344 planes, theoretical maximum. A much tighter upper bound is proved in the same Marsaglia paper to be the sum of the absolute values of all the coefficients of the hyperplanes in standard form. That is, if the hyperplanes are of the form
820:
Summing the absolute values of the coefficients, we get no more than 16 planes in 3D, becoming only 15 planes on closer examination, as shown in the diagram above. Even by the standards of LCGs, this shows that RANDU is terrible: using RANDU for sampling a
908:
913:
As a result of the wide use of RANDU in the early 1970s, many results from that time are seen as suspicious. This misbehavior was already detected in 1963 on a 36-bit computer, and carefully reimplemented on the 32-bit
585:
731:
126:
465:
Now we examine the values of multiplier 65539 and modulus 2 chosen for RANDU. Consider the following calculation where every term should be taken mod 2. Start by writing the recursive relation as
288:
815:
415:
341:
957:
224:
190:
156:
828:
304:
The reason for choosing these particular values for the multiplier and modulus had been that with a 32-bit-integer word size, the arithmetic of mod 2 and
293:
IBM's RANDU is widely considered to be one of the most ill-conceived random number generators ever designed, and was described as "truly horrible" by
28:
of 100,000 values generated with RANDU. Each point represents 3 consecutive pseudorandom values. It is clearly seen that the points fall in 15
1003:
1040:. Section 3.3.4, p. 104: "its very name RANDU is enough to bring dismay into the eyes and stomachs of many computer scientists!"
992:
Compaq
Fortran Language Reference Manual (Order Number: AA-Q66SD-TK) September 1999 (formerly DIGITAL Fortran and DEC Fortran 90).
970:
471:
1227:
918:. It was believed to have been widely purged by the early 1990s but there were still FORTRAN compilers using it as late as 1999.
596:
50:
62:
1185:
1130:
1037:
236:
1024:
193:
746:
356:
46:
43:
370:
1004:"A collection of classical pseudorandom number generators with linear structures – advanced version"
307:
25:
347:
in hardware, but the values were chosen for computational convenience, not statistical quality.
418:
1007:
929:
417:
parallel hyperplanes. This indicates that low-modulus LCGs are unsuited to high-dimensional
1075:
202:
168:
159:
134:
8:
32:
1079:
903:{\displaystyle {\Big \lfloor }{\big (}2^{31}\times 3!{\big )}^{1/3}{\Big \rfloor }=2344}
29:
1098:
1063:
1167:
1126:
1103:
1033:
1159:
1093:
1083:
344:
196:
in the interval , but in practical applications are often mapped into pseudorandom
197:
915:
163:
1221:
1171:
298:
1189:
1107:
1020:
294:
1211:
1163:
825:
will only sample 15 parallel planes, not even close to the upper limit of
450:= some integer such as 0, 1, 2 etc, then the maximum number of planes is |
1088:
1147:
53:, which was used primarily in the 1960s and 1970s. It is defined by the
822:
54:
1206:
1123:
Numerical
Recipes in Fortran 77: The Art of Scientific Computing
740:) and allows us to show the correlation between three points as
580:{\displaystyle x_{k+2}=(2^{16}+3)x_{k+1}=(2^{16}+3)^{2}x_{k},}
103:
926:
The start of the RANDU's output period for the initial seed
965:
726:{\displaystyle x_{k+2}=(2^{32}+6\cdot 2^{16}+9)x_{k}=x_{k}}
963:
1, 65539, 393225, 1769499, 7077969, 26542323, … (sequence
121:{\displaystyle V_{j+1}=65539\cdot V_{j}{\bmod {2}}^{31}}
21:
350:
1186:"Donald Knuth – Computer Literacy Bookshops Interview"
932:
831:
749:
599:
474:
373:
310:
301:
badly for dimensions greater than 2, as shown below.
239:
205:
171:
137:
65:
367:-dimensional space, the points fall in no more than
590:which after expanding the quadratic factor becomes
951:
902:
809:
725:
579:
409:
335:
282:
218:
184:
150:
120:
1120:
1061:
889:
834:
1219:
283:{\displaystyle X_{j}={\frac {V_{j}}{2^{31}}}.}
868:
841:
995:
1145:
1057:
1055:
1064:"Random Numbers Fall Mainly in the Planes"
343:calculations could be done quickly, using
1097:
1087:
1052:
1001:
810:{\displaystyle x_{k+2}=6x_{k+1}-9x_{k}.}
20:
1121:Press, William H.; et al. (1992).
1220:
1114:
1032:, 2nd edition. Addison-Wesley, 1981.
1146:Greenberger, Martin (1 March 1965).
988:
986:
351:Problems with multiplier and modulus
13:
410:{\displaystyle (n!\times m)^{1/n}}
14:
1239:
1199:
1188:. 7 December 1993. Archived from
983:
1205:
921:
1025:The Art of Computer Programming
1228:Pseudorandom number generators
1178:
1139:
1043:
1014:
710:
701:
682:
673:
657:
619:
555:
535:
513:
494:
390:
374:
336:{\displaystyle 65539=2^{16}+3}
1:
977:
357:linear congruential generator
131:with the initial seed number
47:pseudorandom number generator
16:Pseudorandom number generator
1068:Proc. Natl. Acad. Sci. U.S.A
1002:Entacher, Karl (June 2000).
162:. It generates pseudorandom
7:
363:used to generate points in
10:
1244:
1062:Marsaglia, George (1968).
1030:Seminumerical Algorithms
952:{\displaystyle V_{0}=1}
1210:Quotations related to
1148:"Method in randomness"
953:
904:
811:
727:
581:
419:Monte Carlo simulation
411:
337:
284:
220:
186:
152:
122:
36:
26:Three-dimensional plot
1164:10.1145/363791.363827
1049:Knuth (1998), p. 188.
954:
905:
812:
728:
582:
412:
338:
285:
221:
219:{\displaystyle X_{j}}
194:uniformly distributed
187:
185:{\displaystyle V_{j}}
153:
151:{\displaystyle V_{0}}
123:
24:
1089:10.1073/pnas.61.1.25
1010:on 18 November 2018.
930:
829:
747:
597:
472:
371:
308:
237:
203:
169:
135:
63:
1080:1968PNAS...61...25M
44:linear congruential
949:
900:
807:
723:
577:
407:
333:
280:
216:
182:
148:
118:
37:
1192:on 28 March 2022.
1028:, Volume 2:
345:bitwise operators
275:
230:, by the formula
1235:
1209:
1194:
1193:
1182:
1176:
1175:
1143:
1137:
1136:
1125:(2nd ed.).
1118:
1112:
1111:
1101:
1091:
1059:
1050:
1047:
1041:
1018:
1012:
1011:
1006:. Archived from
999:
993:
990:
968:
958:
956:
955:
950:
942:
941:
909:
907:
906:
901:
893:
892:
886:
885:
881:
872:
871:
855:
854:
845:
844:
838:
837:
816:
814:
813:
808:
803:
802:
787:
786:
765:
764:
739:
732:
730:
729:
724:
722:
721:
694:
693:
669:
668:
650:
649:
631:
630:
615:
614:
586:
584:
583:
578:
573:
572:
563:
562:
547:
546:
531:
530:
506:
505:
490:
489:
416:
414:
413:
408:
406:
405:
401:
342:
340:
339:
334:
326:
325:
289:
287:
286:
281:
276:
274:
273:
264:
263:
254:
249:
248:
229:
226:in the interval
225:
223:
222:
217:
215:
214:
191:
189:
188:
183:
181:
180:
157:
155:
154:
149:
147:
146:
127:
125:
124:
119:
117:
116:
111:
110:
100:
99:
81:
80:
51:Park–Miller type
1243:
1242:
1238:
1237:
1236:
1234:
1233:
1232:
1218:
1217:
1202:
1197:
1184:
1183:
1179:
1144:
1140:
1133:
1119:
1115:
1060:
1053:
1048:
1044:
1019:
1015:
1000:
996:
991:
984:
980:
964:
937:
933:
931:
928:
927:
924:
888:
887:
877:
873:
867:
866:
865:
850:
846:
840:
839:
833:
832:
830:
827:
826:
798:
794:
776:
772:
754:
750:
748:
745:
744:
737:
717:
713:
689:
685:
664:
660:
645:
641:
626:
622:
604:
600:
598:
595:
594:
568:
564:
558:
554:
542:
538:
520:
516:
501:
497:
479:
475:
473:
470:
469:
449:
442:
435:
397:
393:
389:
372:
369:
368:
353:
321:
317:
309:
306:
305:
297:. It fails the
269:
265:
259:
255:
253:
244:
240:
238:
235:
234:
227:
210:
206:
204:
201:
200:
176:
172:
170:
167:
166:
142:
138:
136:
133:
132:
112:
106:
102:
101:
95:
91:
70:
66:
64:
61:
60:
30:two-dimensional
17:
12:
11:
5:
1241:
1231:
1230:
1216:
1215:
1201:
1200:External links
1198:
1196:
1195:
1177:
1158:(3): 177–179.
1138:
1131:
1113:
1051:
1042:
1013:
994:
981:
979:
976:
975:
974:
948:
945:
940:
936:
923:
920:
916:IBM System/360
899:
896:
891:
884:
880:
876:
870:
864:
861:
858:
853:
849:
843:
836:
818:
817:
806:
801:
797:
793:
790:
785:
782:
779:
775:
771:
768:
763:
760:
757:
753:
734:
733:
720:
716:
712:
709:
706:
703:
700:
697:
692:
688:
684:
681:
678:
675:
672:
667:
663:
659:
656:
653:
648:
644:
640:
637:
634:
629:
625:
621:
618:
613:
610:
607:
603:
588:
587:
576:
571:
567:
561:
557:
553:
550:
545:
541:
537:
534:
529:
526:
523:
519:
515:
512:
509:
504:
500:
496:
493:
488:
485:
482:
478:
447:
440:
433:
404:
400:
396:
392:
388:
385:
382:
379:
376:
352:
349:
332:
329:
324:
320:
316:
313:
291:
290:
279:
272:
268:
262:
258:
252:
247:
243:
213:
209:
179:
175:
145:
141:
129:
128:
115:
109:
105:
98:
94:
90:
87:
84:
79:
76:
73:
69:
15:
9:
6:
4:
3:
2:
1240:
1229:
1226:
1225:
1223:
1213:
1208:
1204:
1203:
1191:
1187:
1181:
1173:
1169:
1165:
1161:
1157:
1153:
1149:
1142:
1134:
1132:0-521-43064-X
1128:
1124:
1117:
1109:
1105:
1100:
1095:
1090:
1085:
1081:
1077:
1073:
1069:
1065:
1058:
1056:
1046:
1039:
1038:0-201-03822-6
1035:
1031:
1027:
1026:
1022:
1017:
1009:
1005:
998:
989:
987:
982:
972:
967:
962:
961:
960:
946:
943:
938:
934:
922:Sample output
919:
917:
911:
897:
894:
882:
878:
874:
862:
859:
856:
851:
847:
824:
804:
799:
795:
791:
788:
783:
780:
777:
773:
769:
766:
761:
758:
755:
751:
743:
742:
741:
718:
714:
707:
704:
698:
695:
690:
686:
679:
676:
670:
665:
661:
654:
651:
646:
642:
638:
635:
632:
627:
623:
616:
611:
608:
605:
601:
593:
592:
591:
574:
569:
565:
559:
551:
548:
543:
539:
532:
527:
524:
521:
517:
510:
507:
502:
498:
491:
486:
483:
480:
476:
468:
467:
466:
463:
461:
457:
453:
446:
439:
432:
428:
424:
420:
402:
398:
394:
386:
383:
380:
377:
366:
362:
359:with modulus
358:
348:
346:
330:
327:
322:
318:
314:
311:
302:
300:
299:spectral test
296:
277:
270:
266:
260:
256:
250:
245:
241:
233:
232:
231:
211:
207:
199:
195:
177:
173:
165:
161:
143:
139:
113:
107:
96:
92:
88:
85:
82:
77:
74:
71:
67:
59:
58:
57:
56:
52:
49:(LCG) of the
48:
45:
41:
34:
31:
27:
23:
19:
1214:at Wikiquote
1190:the original
1180:
1155:
1151:
1141:
1122:
1116:
1074:(1): 25–28.
1071:
1067:
1045:
1029:
1023:
1016:
1008:the original
997:
925:
912:
819:
735:
589:
464:
459:
455:
451:
444:
437:
430:
426:
422:
364:
360:
354:
303:
295:Donald Knuth
292:
130:
39:
38:
18:
1152:Commun. ACM
1021:Knuth D. E.
738:2 mod 2 = 0
978:References
192:which are
160:odd number
55:recurrence
1172:0001-0782
857:×
823:unit cube
789:−
736:(because
705:−
680:⋅
639:⋅
384:×
198:rationals
89:⋅
1222:Category
1108:16591687
910:planes.
890:⌋
835:⌊
425:= 2 and
355:For any
164:integers
1076:Bibcode
969:in the
966:A096555
1170:
1129:
1106:
1099:285899
1096:
1036:
421:. For
228:(0, 1)
158:as an
33:planes
1212:RANDU
458:| + |
454:| + |
312:65539
86:65539
42:is a
40:RANDU
1168:ISSN
1127:ISBN
1104:PMID
1034:ISBN
971:OEIS
898:2344
1160:doi
1094:PMC
1084:doi
959:is
462:|.
104:mod
1224::
1166:.
1154:.
1150:.
1102:.
1092:.
1082:.
1072:61
1070:.
1066:.
1054:^
985:^
973:).
852:31
691:16
647:16
628:32
544:16
503:16
445:Cx
443:+
438:Bx
436:+
431:Ax
323:16
271:31
114:31
1174:.
1162::
1156:8
1135:.
1110:.
1086::
1078::
947:1
944:=
939:0
935:V
895:=
883:3
879:/
875:1
869:)
863:!
860:3
848:2
842:(
805:.
800:k
796:x
792:9
784:1
781:+
778:k
774:x
770:6
767:=
762:2
759:+
756:k
752:x
719:k
715:x
711:]
708:9
702:)
699:3
696:+
687:2
683:(
677:6
674:[
671:=
666:k
662:x
658:)
655:9
652:+
643:2
636:6
633:+
624:2
620:(
617:=
612:2
609:+
606:k
602:x
575:,
570:k
566:x
560:2
556:)
552:3
549:+
540:2
536:(
533:=
528:1
525:+
522:k
518:x
514:)
511:3
508:+
499:2
495:(
492:=
487:2
484:+
481:k
477:x
460:C
456:B
452:A
448:3
441:2
434:1
427:n
423:m
403:n
399:/
395:1
391:)
387:m
381:!
378:n
375:(
365:n
361:m
331:3
328:+
319:2
315:=
278:.
267:2
261:j
257:V
251:=
246:j
242:X
212:j
208:X
178:j
174:V
144:0
140:V
108:2
97:j
93:V
83:=
78:1
75:+
72:j
68:V
35:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
