ハルトン数列

非常に安易であるにも関わらず,程々に有用なのに,

日本語の文章がなかったので,勝手に意訳してまとめてみた.

ハルトン数列(Halton sequence)は,自然数を突っ込めば,0から1までの擬似乱数を作る.
次に示すとても簡単なアイディアだけど,ちょっぴり凄い.

作り方

1. 底を決める.例えば2.

2. 順番に数をカウントアップする.1,2,3,4,5,6,7…

3. それらを2進数表記して,小数点以下から逆に読み,また10進数表記に戻す.

2進数小数は小数点以下から順に1/2の位,1/4の位,1/8の位,,,と読んでいく.(と自然数の底変換と整合性が取れる.)

例えば,

元の数 2進数表記 逆読み2進数 得られた10進数表記
1 1.0 0.1 1/2
2 10.0 0.01 1/4
3 11.0 0.11 3/4
4 100.0 0.001 1/8
5 101.0 0.101 5/8
6 110.0 0.011 3/8
7 111.0 0.111 7/8

という感じ.底を3に変えても同様のものができる.

コンピュータと親和性がよい.コードは次の通り.

The input number is X.
The output number is Y.

Y = 0
half = 1 / 2.
do {
 digit = X%2 ;
 Y = Y + digit * half;
 X = ( X - digit ) / 2;
half = half / 2;
} while ( X!=0 )

そして,察しの通り「均等に」バラつく.望ましい性質の一つである.Wikipedia に比較画像がある.

さて,Halton数列は全ての2進数小数を表す.しかし,有理数全体ではない.(1/3などがない)

Halton数列は自然数全体とone-to-one correspondence(一対一対応)しているので,Halton数列の濃度は\aleph _0の可算無限個.

有理数の濃度も\aleph _0と言われるけど,有理数から1/3などの数をカウントしなくても濃度は変わらないなんて,やっぱり濃度はオカルト不思議だ.

 

ところで,コンピュータはどうやって任意の有理数を実現するのかといえば,そこには無限和が隠されている.

\dfrac{1}{3}=\dfrac{1}{2^2}+\dfrac{1}{2^4}+\dfrac{1}{2^6}+\cdots

(証明は各自.数式クリックでWikipediaへ飛ぶ)

実際には無限は計算できないので,部分和で留めておくのであり,これが浮動小数点数の精度になる.

 

Halton数列.将来,何かの役に立つかもしれない.

広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中