Pseudorandom number generators based on infinite words

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21340%2F14%3A00221667" target="_blank" >RIV/68407700:21340/14:00221667 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

čeština

Original language name

Generátory pseudonáhodných čísel založené na nekonečných slovech

Original language description

V článku ukážeme, jak lze využít nekonečných aperiodických slov ke konstrukci generátorů náhodných čísel. Zavedeme třídu slov s~{bf dobře rozmístěnými výskyty}, pro niž jsme dokázali, že při kombinaci periodických generátorů podle slov z této třídy vznikají generátory aperiodické, jež navíc nemají mřížkovou strukturu. Slova s~dobře rozmístěnými výskyty zahrnují např. slova sturmovská a Arnouxova-Rauzyova slova, z nichž některá se dají generovat rychlým algoritmem, protože jsou pevnými body morfismů. Právě generátory pseudonáhodných čísel založené na pevných bodech morfismů, které mají dobře rozmístěné výskyty, jsme také otestovali bateriemi statistických testů TestU01 a PractRand. Ukázalo se, že nová metoda podstatně zlepšuje statistické vlastnosti generovaných náhodných čísel za cenu pouze zanedbatelně zvýšené výpočetní a paměťové náročnosti.

Czech name

Generátory pseudonáhodných čísel založené na nekonečných slovech

Czech description

V článku ukážeme, jak lze využít nekonečných aperiodických slov ke konstrukci generátorů náhodných čísel. Zavedeme třídu slov s~{bf dobře rozmístěnými výskyty}, pro niž jsme dokázali, že při kombinaci periodických generátorů podle slov z této třídy vznikají generátory aperiodické, jež navíc nemají mřížkovou strukturu. Slova s~dobře rozmístěnými výskyty zahrnují např. slova sturmovská a Arnouxova-Rauzyova slova, z nichž některá se dají generovat rychlým algoritmem, protože jsou pevnými body morfismů. Právě generátory pseudonáhodných čísel založené na pevných bodech morfismů, které mají dobře rozmístěné výskyty, jsme také otestovali bateriemi statistických testů TestU01 a PractRand. Ukázalo se, že nová metoda podstatně zlepšuje statistické vlastnosti generovaných náhodných čísel za cenu pouze zanedbatelně zvýšené výpočetní a paměťové náročnosti.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

<a href="/en/project/GA13-03538S" target="_blank" >GA13-03538S: Algorithms, Dynamics and Geometry of Numeration systems</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2014

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Pokroky matematiky, fyziky a astronomie

ISSN

0032-2423

e-ISSN

—

Volume of the periodical

59

Issue of the periodical within the volume

3

Country of publishing house

CZ - CZECH REPUBLIC

Number of pages

12

Pages from-to

211-222

UT code for WoS article

—

EID of the result in the Scopus database

—