halton序列是怎麼確定的？

本人小白，請教各路大俠，halton序列，以2為底的序列x的取值順序為1?2,1?4,3?4,1?8,5?8,3?8,7?8,1?16,9?16

這是怎麼確定的？求詳解，百度百科的看不太懂

另外還有代碼提問

class Halton {

double value, inv_base;

public :

void number(int i, int base) {

double f = inv_base = 1.0 / base;

value = 0.0;

while (i &> 0) {

value += f * ( double )(i%base);

i /= base;

f *= inv_base;

}

}

void next() {

double r = 1.0 - value - 0.0000001;

if (inv_base& else {

double h = inv_base, hh;

do {hh = h; h *= inv_base;} while(h &>=r);

value += hh + h - 1.0;

}

}

double get() { return value; }

};

代碼里的 i 代表什麼？

---

把序列寫成二進位小數：

1/2 -&> 0.1

1/4 -&> 0.01

3/4 -&> 0.11

1/8 -&> 0.001

5/8 -&> 0.101

3/8 -&> 0.011

7/8 -&> 0.111

1/16 -&> 0.0001

9/16 -&> 0.1001

……

可以看出來，小數點後的部分正是二進位正整數序列1, 10, 11, 100, 101, 110, 111, 1000, 1001……每個數的各位逆序。

---

我的理解： Halton序列是反覆分別依次切割區間得來的。

用2切割（0,1），

第一次得到（0，1/2），（1/2，/1）

第二次得到（0，1/4），（1/4，1/2），（1/2，3/4），（3/4，1）

第一次得到（0，1/8），（1/8，1/4），（1/4，3/8），（3/8，1/2），（1/2，5/8），（5/8，3/4）,（3/4，7/8），（7/8，1）

當然，輸出序列的時候是依次輸出..

可以參看wiki的圖示：https://upload.wikimedia.org/wikipedia/commons/thumb/a/a5/Halton_sequence_2_3.svg/250px-Halton_sequence_2_3.svg.png

---

推薦閱讀：