RANDU
 |
В данной статье или разделе имеется список источников или внешних ссылок, но источники отдельных утверждений остаются неясными из-за отсутствия сносок. Утверждения, не подкреплённые источниками, могут быть поставлены под сомнение и удалены. Вы можете улучшить статью, внеся более точные указания на источники.
|
RANDU — линейный конгруэнтный генератор псевдослучайных чисел, вошедший в употребление в 1960-х. Он определяется рекуррентным соотношением:
- <math>V_{j+1} \equiv (65539 V_j) \mod 2^{31}</math>
где <math>V_0</math> нечётное.
Псевдослучайные числа вычисляются следующим образом:
- <math>X_{j} \equiv V_{j} / 2^{31}</math>
Популярно мнение, что данный алгоритм — один из наименее продуманных генераторов псевдослучайных чисел среди когда-либо предложенных. Так, он не проходит спектральный тест при количестве измерений, превышающем 2.
Основанием для выбора параметров генератора послужило то, что в рамках целочисленной 32-битной машинной арифметики операции по модулю <math>2^{31}</math>, в частности, умножение произвольного числа на <math>65539=2^{16}+3</math>, выполняются эффективно. В то же время такой выбор обладает и принципиальным недостатком. Рассмотрим следующее выражение (будем полагать, что все операции выполняются по модулю <math>2^{31}</math>):
- <math>x_{k+2}=(2^{16}+3) x_{k+1}=(2^{16}+3 )^2 x_{k}</math>
откуда, раскрыв квадратичный сомножитель, получаем:
- <math>x_{k+2}=(2^{32}+6 \cdot2^{16} +9 )x_{k}=[6 \cdot (2^{16}+3)-9]x_{k}</math>
что, в свою очередь, показывает наличие линейной зависимости (а следовательно, и полной корреляции) между тремя соседними элементами последовательности:
- <math>x_{k+2}=6x_{k+1}-9x_{k}</math>
Как следствие корреляции, точки в трёхмерном пространстве, координаты которых получены по данному алгоритму, располагаются на сравнительно небольшом количестве плоскостей (в приведённом примере — на 15 плоскостях).[1]
Пример
Пример псевдослучайной последовательности, порождаемой алгоритмом RANDU при начальном значении <math>V_0=1</math>:
1
65539
393225
1769499
7077969
26542323
95552217
334432395
1146624417
1722371299
14608041
...
134633675
1893599841
1559961379
907304297
2141591611
388843697
238606867
79531577
477211307
1
Цитаты
Само его название — RANDU (похоже на «random» — «случайный» — Прим. ред.), способно вызвать испуг в глазах и спазмы в желудке у многих учёных, специализирующихся на компьютерах![2]
Оригинальный текст (англ.)…its very name RANDU is enough to bring dismay into the eyes and stomachs of many computer scientists![3]
Один из нас вспоминает, что получил однажды графическое изображение «случайной» последовательности, состоящее всего из 11 плоскостей. В ответ на это консультант вычислительного центра по программированию заявил, что генератор случайных чисел использовался неверно: «Мы гарантируем, что каждое число случайно само по себе, но не гарантируем, что случайно более чем одно из них». Попробуйте такое понять.
Оригинальный текст (англ.)One of us recalls producing a «random» plot with only 11 planes, and being told by his computer center’s programming consultant that he had misused the random number generator: «We guarantee that each number is random individually, but we don’t guarantee that more than one of them is random». Figure that out.[4]
Напишите отзыв о статье "RANDU"
Примечания
- ↑ George Marsaglia. [www.pubmedcentral.nih.gov/articlerender.fcgi?artid=285899 Random Numbers Fall Mainly in the Planes] // Proc National Academy of Sciences : журнал. — сентябрь 1968. — Т. 61, № 1. — С. 25—28.
- ↑ Дональд Кнут. Глава 3.3. Спектральный критерий // Искусство программирования = The Art of Computer Programming. — 3-е изд. — М.: «Вильямс», 2007. — Т. 2. Получисленные алгоритмы. — С. 129—130. — 832 с. — ISBN 5-8459-0081-6 (русс.) ISBN 0-201-89684-2 (англ.).
- ↑ Donald E. Knuth. The Art of Computer Programming. — 3rd ed. — Boston: Addison-Wesley, 1998. — Т. 2. Seminumerical Algorithms.
- ↑ William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Numerical Recipes in C: The Art of Scientific Computing. — 2nd ed. — Cambridge University Press, 1992. — P. 277. — ISBN 0-521-43108-5.
Дополнительная литература
- М. Максимов. Случайны ли случайные числа? — Журнал «Наука и жизнь», № 10, 1986.
Ссылки
- [www.youtube.com/watch?v=7wVk_XsxyNk RANDU random number generator fails 3D+ spectral tests]
Отрывок, характеризующий RANDU
– Ну, что, князь? – спросил Козловский.– Приказано составить записку, почему нейдем вперед.
– А почему?
Князь Андрей пожал плечами.
– Нет известия от Мака? – спросил Козловский.
– Нет.
– Ежели бы правда, что он разбит, так пришло бы известие.
– Вероятно, – сказал князь Андрей и направился к выходной двери; но в то же время навстречу ему, хлопнув дверью, быстро вошел в приемную высокий, очевидно приезжий, австрийский генерал в сюртуке, с повязанною черным платком головой и с орденом Марии Терезии на шее. Князь Андрей остановился.
– Генерал аншеф Кутузов? – быстро проговорил приезжий генерал с резким немецким выговором, оглядываясь на обе стороны и без остановки проходя к двери кабинета.
– Генерал аншеф занят, – сказал Козловский, торопливо подходя к неизвестному генералу и загораживая ему дорогу от двери. – Как прикажете доложить?
Неизвестный генерал презрительно оглянулся сверху вниз на невысокого ростом Козловского, как будто удивляясь, что его могут не знать.
– Генерал аншеф занят, – спокойно повторил Козловский.
Лицо генерала нахмурилось, губы его дернулись и задрожали. Он вынул записную книжку, быстро начертил что то карандашом, вырвал листок, отдал, быстрыми шагами подошел к окну, бросил свое тело на стул и оглянул бывших в комнате, как будто спрашивая: зачем они на него смотрят? Потом генерал поднял голову, вытянул шею, как будто намереваясь что то сказать, но тотчас же, как будто небрежно начиная напевать про себя, произвел странный звук, который тотчас же пресекся. Дверь кабинета отворилась, и на пороге ее показался Кутузов. Генерал с повязанною головой, как будто убегая от опасности, нагнувшись, большими, быстрыми шагами худых ног подошел к Кутузову.
– Vous voyez le malheureux Mack, [Вы видите несчастного Мака.] – проговорил он сорвавшимся голосом.
Лицо Кутузова, стоявшего в дверях кабинета, несколько мгновений оставалось совершенно неподвижно. Потом, как волна, пробежала по его лицу морщина, лоб разгладился; он почтительно наклонил голову, закрыл глаза, молча пропустил мимо себя Мака и сам за собой затворил дверь.
Слух, уже распространенный прежде, о разбитии австрийцев и о сдаче всей армии под Ульмом, оказывался справедливым. Через полчаса уже по разным направлениям были разосланы адъютанты с приказаниями, доказывавшими, что скоро и русские войска, до сих пор бывшие в бездействии, должны будут встретиться с неприятелем.
Князь Андрей был один из тех редких офицеров в штабе, который полагал свой главный интерес в общем ходе военного дела. Увидав Мака и услыхав подробности его погибели, он понял, что половина кампании проиграна, понял всю трудность положения русских войск и живо вообразил себе то, что ожидает армию, и ту роль, которую он должен будет играть в ней.
Невольно он испытывал волнующее радостное чувство при мысли о посрамлении самонадеянной Австрии и о том, что через неделю, может быть, придется ему увидеть и принять участие в столкновении русских с французами, впервые после Суворова.
Но он боялся гения Бонапарта, который мог оказаться сильнее всей храбрости русских войск, и вместе с тем не мог допустить позора для своего героя.
Взволнованный и раздраженный этими мыслями, князь Андрей пошел в свою комнату, чтобы написать отцу, которому он писал каждый день. Он сошелся в коридоре с своим сожителем Несвицким и шутником Жерковым; они, как всегда, чему то смеялись.
– Что ты так мрачен? – спросил Несвицкий, заметив бледное с блестящими глазами лицо князя Андрея.
– Веселиться нечему, – отвечал Болконский.
В то время как князь Андрей сошелся с Несвицким и Жерковым, с другой стороны коридора навстречу им шли Штраух, австрийский генерал, состоявший при штабе Кутузова для наблюдения за продовольствием русской армии, и член гофкригсрата, приехавшие накануне. По широкому коридору было достаточно места, чтобы генералы могли свободно разойтись с тремя офицерами; но Жерков, отталкивая рукой Несвицкого, запыхавшимся голосом проговорил:
