Metoda prostředku čtverce

Orientovaný graf zachycující přechody mezi sto možnými stavy na dvouciferných desítkových číslech

Metoda prostředku čtverce je v matematice jednou z klasických metod generování pseudonáhodných čísel. Matematik John von Neumann ji vymyslel kolem roku 1946[1], popsal ji na konferenci v roce 1949[2] a jak pozdější analýzy ukázaly, ve skutečnosti je z hlediska náhodnosti vytvářených posloupností poměrně špatná.[1]

Popis metody

Na začátku je jako vnitřní stav zvoleno náhodné semínko o sudém počtu, tedy 2n číslicích. Toto číslo je umocněno na druhou a případně doplněno zleva nulami na 4n číslic. Z takto vzniklého čísla je vzato prostředních 2n číslic, které je jednak výstupem a jednak novým vnitřním stavem pro další iteraci.

Příklad

Následující příklad s dvoucifermými čísly začíná číslem 62 a velice rychle degeneruje na posloupnost nul:

62 · 62 = 3844
84 · 84 = 7056
5 · 5 = 0025
2 · 2 = 0004
0 · 0 = 0000
…

Odkazy

Reference

V tomto článku byly použity překlady textů z článků Mittquadratmethode na německé Wikipedii a Middle-square method na anglické Wikipedii.

  1. ↑ a b KNUTH, Donald E. Umění programování 2. díl – Seminumerické algoritmy. Brno: Computer Press, 2010. ISBN 978-80-251-2898-5. Kapitola III. Náhodná čísla, s. 3. 
  2. ↑ NEUMANN, John von. Various techniques used in connection with random digits. In: HOUSEHOLDER, A.S.; FORSYTHE, G.E.; GERMOND, H.H. Monte Carlo Method, National Bureau of Standards Applied Mathematics Series. Washington D.C.: U.S. Government Printing Office, 1951. (anglicky)

Literatura

  • KNUTH, Donald E. Umění programování 2. díl – Seminumerické algoritmy. Brno: Computer Press, 2010. ISBN 978-80-251-2898-5. Kapitola III. Náhodná čísla, s. 3. 

Média použitá na této stránce

Middle square method 2 digits.svg
Autor: Cmglee, Licence: CC BY-SA 3.0
Directed graph of all 100 2-digit pseudorandom numbers obtained using the middle-square method.