Van der Corputova sekvence - Van der Corput sequence
A van der Corputova sekvence je příkladem nejjednodušší jednorozměrné sekvence s nízkou odchylkou přes jednotkový interval; poprvé to popsal v roce 1935 holandský matematik J. G. van der Corput. Je konstruován obrácením základna-n zastoupení sekvence z přirozená čísla (1, 2, 3, …).
The b- reprezentace kladného celého čísla n (≥ 1) je
kde b je základ, ve kterém je číslo n je znázorněno a 0 ≤ dk(n) < b, tj k-tá číslice v b-ary expanze n.v n-té číslo v posloupnosti van der Corput je
Příklady
Například získat desetinný van der Corputova sekvence, začneme dělením čísel 1 až 9 v desetinách (X/ 10), poté změníme jmenovatele na 100, abychom se začali dělit na setiny (X/100). Pokud jde o čitatele, začneme se všemi dvoucifernými čísly od 10 do 99, ale v zpět pořadí číslic. V důsledku toho získáme čitatele seskupené podle koncové číslice. Nejprve všechny dvouciferné čitatele, které končí číslicí 1, takže další čitatelé jsou 01, 11, 21, 31, 41, 51, 61, 71, 81, 91. Potom čitatelé končící na 2, takže jsou 02, 12 , 22, 32, 42, 52, 62, 72, 82, 92. Za po čitatelích končících na 3: 03, 13, 23 atd. ...
Sekvence tedy začíná
nebo v desetinném vyjádření:
- 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.01, 0.11, 0.21, 0.31, 0.41, 0.51, 0.61, 0.71, 0.81, 0.91, 0.02, 0.12, 0.22, 0.32, …,
Totéž lze udělat pro binární číselná soustava a binární van der Corputova sekvence je
- 0.12, 0.012, 0.112, 0.0012, 0.1012, 0.0112, 0.1112, 0.00012, 0.10012, 0.01012, 0.11012, 0.00112, 0.10112, 0.01112, 0.11112, …
nebo ekvivalentně
Prvky van der Corputovy sekvence (v jakékoli základně) tvoří a hustá sada v jednotkovém intervalu; to znamená, že pro jakékoli reálné číslo v [0, 1] existuje a subsekvence van der Corputovy sekvence konverguje na toto číslo. Jsou taky ekvidistribuováno přes jednotkový interval.
C implementace
dvojnásobek korputa(int n, int základna){ dvojnásobek q=0, bk=(dvojnásobek)1/základna; zatímco (n > 0) { q += (n % základna)*bk; n /= základna; bk /= základna; } vrátit se q;}
Viz také
- Bit-reverzní permutace
- Konstrukce sekvencí s nízkou odchylkou
- Haltonova sekvence, přirozené zobecnění van der Corputovy sekvence do vyšších dimenzí
Reference
- van der Corput, J.G. (1935), „Verteilungsfunktionen (Erste Mitteilung)“ (PDF), Sborník Koninklijke Akademie van Wetenschappen te Amsterdam (v němčině), 38: 813–821, Zbl 0012.34705
- Kuipers, L .; Niederreiter, H. (2005) [1974], Rovnoměrné rozdělení sekvencí, Dover Publications, str. 129 158, ISBN 0-486-45019-8, Zbl 0281.10001