[2839] | 1 | #ifndef __HALTON_H
|
---|
| 2 | #define __HALTON_H
|
---|
| 3 |
|
---|
| 4 | #include <iostream>
|
---|
| 5 |
|
---|
| 6 |
|
---|
| 7 | /** Assert whether the argument is a prime number.
|
---|
| 8 | @param number the number to be checked
|
---|
| 9 | */
|
---|
| 10 | inline bool IsPrime(const int number)
|
---|
| 11 | {
|
---|
| 12 | bool isIt = true;
|
---|
| 13 |
|
---|
| 14 | for(int i = 2; i < number; ++ i)
|
---|
| 15 | {
|
---|
| 16 | if(number % i == 0)
|
---|
| 17 | {
|
---|
| 18 | isIt = false;
|
---|
| 19 | break;
|
---|
| 20 | }
|
---|
| 21 | }
|
---|
| 22 |
|
---|
| 23 | if(number == 2)
|
---|
| 24 | {
|
---|
| 25 | isIt = false;
|
---|
| 26 | }
|
---|
| 27 |
|
---|
| 28 | return isIt;
|
---|
| 29 | }
|
---|
| 30 |
|
---|
| 31 |
|
---|
| 32 | /**
|
---|
| 33 | Find the nth prime number.
|
---|
| 34 | @param index the ordinal position in the sequence
|
---|
| 35 | */
|
---|
| 36 | inline int FindPrime(const int index)
|
---|
| 37 | {
|
---|
| 38 |
|
---|
| 39 | const int primes[] = {-1, 1, 3, 5, 7, 11, 13};
|
---|
| 40 | if (index <= 6)
|
---|
| 41 | return primes[index];
|
---|
| 42 |
|
---|
| 43 | int prime = 1;
|
---|
| 44 | int found = 1;
|
---|
| 45 | while(found != index) {
|
---|
| 46 | prime += 2;
|
---|
| 47 | if(IsPrime(prime) == true) {
|
---|
| 48 | found++;
|
---|
| 49 | }
|
---|
| 50 | }
|
---|
| 51 | return prime;
|
---|
| 52 | }
|
---|
| 53 |
|
---|
| 54 |
|
---|
| 55 | inline float halton(float baseRec, float prev)
|
---|
| 56 | {
|
---|
| 57 | float r = 1.0f - prev;
|
---|
| 58 |
|
---|
| 59 | if (baseRec < r)
|
---|
| 60 | return prev + baseRec;
|
---|
| 61 |
|
---|
| 62 | float h = baseRec;
|
---|
| 63 |
|
---|
| 64 | float hh;
|
---|
| 65 |
|
---|
| 66 | do
|
---|
| 67 | {
|
---|
| 68 | hh = h;
|
---|
| 69 | h *= baseRec;
|
---|
| 70 | } while (h > r);
|
---|
| 71 |
|
---|
| 72 | return prev + hh + h - 1.0f;
|
---|
| 73 | }
|
---|
| 74 |
|
---|
| 75 |
|
---|
| 76 | template<int T> struct Halton
|
---|
| 77 | {
|
---|
| 78 | static float _invBases[T];
|
---|
| 79 | float _prev[T];
|
---|
| 80 |
|
---|
| 81 | public:
|
---|
| 82 |
|
---|
| 83 | void Reset()
|
---|
| 84 | {
|
---|
| 85 | for (int i=0; i < T; i++)
|
---|
| 86 | _prev[i] = 0;
|
---|
| 87 | }
|
---|
| 88 |
|
---|
| 89 | Halton(const bool initializeBases)
|
---|
| 90 | {
|
---|
| 91 | for (int i=0; i < T; i++)
|
---|
| 92 | {
|
---|
| 93 | int base = FindPrime(i+1);
|
---|
| 94 |
|
---|
| 95 | if (base == 1)
|
---|
| 96 | base++;
|
---|
| 97 | _invBases[i] = 1.0f/base;
|
---|
| 98 | }
|
---|
| 99 | }
|
---|
| 100 |
|
---|
| 101 | Halton()
|
---|
| 102 | {
|
---|
| 103 | Reset();
|
---|
| 104 | }
|
---|
| 105 |
|
---|
| 106 | void GetNext(float *a)
|
---|
| 107 | {
|
---|
| 108 | for (int i=0; i < T; i++)
|
---|
| 109 | {
|
---|
| 110 | a[i] = halton(_invBases[i], _prev[i]);
|
---|
| 111 | _prev[i] = a[i];
|
---|
| 112 | }
|
---|
| 113 | }
|
---|
| 114 |
|
---|
| 115 | };
|
---|
| 116 |
|
---|
| 117 | struct Halton2
|
---|
| 118 | {
|
---|
| 119 | static float _invBases[2];
|
---|
| 120 | float _prev[2];
|
---|
| 121 |
|
---|
| 122 | public:
|
---|
| 123 |
|
---|
| 124 | void Reset()
|
---|
| 125 | {
|
---|
| 126 | _prev[0] =_prev[1] = 0;
|
---|
| 127 | }
|
---|
| 128 |
|
---|
| 129 | Halton2()
|
---|
| 130 | {
|
---|
| 131 | _invBases[0] = 1.0f / 2;
|
---|
| 132 | _invBases[1] = 1.0f / 3;
|
---|
| 133 | Reset();
|
---|
| 134 | }
|
---|
| 135 |
|
---|
| 136 | void GetNext(float &a, float &b)
|
---|
| 137 | {
|
---|
| 138 | a = halton(_invBases[0], _prev[0]);
|
---|
| 139 | b = halton(_invBases[1], _prev[1]);
|
---|
| 140 |
|
---|
| 141 | _prev[0] = a;
|
---|
| 142 | _prev[1] = b;
|
---|
| 143 | }
|
---|
| 144 | };
|
---|
| 145 |
|
---|
| 146 |
|
---|
| 147 |
|
---|
| 148 | struct HaltonSequence
|
---|
| 149 | {
|
---|
| 150 | public:
|
---|
| 151 | int index;
|
---|
| 152 |
|
---|
| 153 | static int sPregeneratedDim;
|
---|
| 154 | static int sPregeneratedNumber;
|
---|
| 155 | static float *sPregeneratedValues;
|
---|
| 156 |
|
---|
| 157 | // special construtor for pregenerating static halton sequences
|
---|
| 158 | HaltonSequence(const int dim, const int number);
|
---|
| 159 |
|
---|
| 160 | HaltonSequence(): index(1) {}
|
---|
| 161 |
|
---|
| 162 | void Reset()
|
---|
| 163 | {
|
---|
| 164 | index = 1;
|
---|
| 165 | }
|
---|
| 166 |
|
---|
| 167 | void
|
---|
| 168 | GetNext(const int dimensions, float *p);
|
---|
| 169 |
|
---|
| 170 | void GenerateNext()
|
---|
| 171 | {
|
---|
| 172 | ++ index;
|
---|
| 173 | }
|
---|
| 174 |
|
---|
| 175 | double GetNumber(const int dimension)
|
---|
| 176 | {
|
---|
| 177 | int base = FindPrime(dimension);
|
---|
| 178 | if(base == 1) {
|
---|
| 179 | base++; //The first dimension uses base 2.
|
---|
| 180 | }
|
---|
| 181 |
|
---|
| 182 | int _p1 = base;
|
---|
| 183 | float _ip1 = 1.0f/base;
|
---|
| 184 | float p, u=0.0f;
|
---|
| 185 | int kk, a;
|
---|
| 186 |
|
---|
| 187 | // the first coordinate
|
---|
| 188 | for (p = _ip1, kk = index ; kk ; p *= _ip1, kk /= _p1)
|
---|
| 189 | if ((a = kk % _p1))
|
---|
| 190 | u += a * p;
|
---|
| 191 |
|
---|
| 192 | return u;
|
---|
| 193 | }
|
---|
| 194 |
|
---|
| 195 | /**
|
---|
| 196 | Returns the nth number in the sequence, taken from a specified dimension.
|
---|
| 197 | @param index the ordinal position in the sequence
|
---|
| 198 | @param dimension the dimension
|
---|
| 199 | */
|
---|
| 200 | double GetNumberOld(const int dimension)
|
---|
| 201 | {
|
---|
| 202 | int base = FindPrime(dimension);
|
---|
| 203 | if(base == 1)
|
---|
| 204 | {
|
---|
| 205 | ++ base; //The first dimension uses base 2.
|
---|
| 206 | }
|
---|
| 207 |
|
---|
| 208 | double remainder;
|
---|
| 209 | double output = 0.0;
|
---|
| 210 | double fraction = 1.0 / (double)base;
|
---|
| 211 | int N1 = 0;
|
---|
| 212 | int copyOfIndex = index;
|
---|
| 213 |
|
---|
| 214 | if ((base >= 2) && (index >= 1))
|
---|
| 215 | {
|
---|
| 216 | while(copyOfIndex > 0)
|
---|
| 217 | {
|
---|
| 218 | N1 = (copyOfIndex / base);
|
---|
| 219 | remainder = copyOfIndex % base;
|
---|
| 220 | output += fraction * remainder;
|
---|
| 221 | copyOfIndex = (int)(copyOfIndex / base);
|
---|
| 222 | fraction /= (double)base;
|
---|
| 223 | }
|
---|
| 224 | return output;
|
---|
| 225 | }
|
---|
| 226 | else
|
---|
| 227 | {
|
---|
| 228 | std::cerr<<"Error generating Halton sequence."<<std::endl;
|
---|
| 229 | exit(1);
|
---|
| 230 | }
|
---|
| 231 | }
|
---|
| 232 | };
|
---|
| 233 |
|
---|
| 234 |
|
---|
| 235 | #endif
|
---|