|
Packit |
67cb25 |
/* Author: G. Jungman
|
|
Packit |
67cb25 |
*/
|
|
Packit |
67cb25 |
/* Implementation for Sobol generator.
|
|
Packit |
67cb25 |
* See
|
|
Packit |
67cb25 |
* [Bratley+Fox, TOMS 14, 88 (1988)]
|
|
Packit |
67cb25 |
* [Antonov+Saleev, USSR Comput. Maths. Math. Phys. 19, 252 (1980)]
|
|
Packit |
67cb25 |
*/
|
|
Packit |
67cb25 |
#include <config.h>
|
|
Packit |
67cb25 |
#include <gsl/gsl_qrng.h>
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* maximum allowed space dimension */
|
|
Packit |
67cb25 |
#define SOBOL_MAX_DIMENSION 40
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* bit count; assumes sizeof(int) >= 32-bit */
|
|
Packit |
67cb25 |
#define SOBOL_BIT_COUNT 30
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* prototypes for generator type functions */
|
|
Packit |
67cb25 |
static size_t sobol_state_size(unsigned int dimension);
|
|
Packit |
67cb25 |
static int sobol_init(void * state, unsigned int dimension);
|
|
Packit |
67cb25 |
static int sobol_get(void * state, unsigned int dimension, double * v);
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* global Sobol generator type object */
|
|
Packit |
67cb25 |
static const gsl_qrng_type sobol_type =
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
"sobol",
|
|
Packit |
67cb25 |
SOBOL_MAX_DIMENSION,
|
|
Packit |
67cb25 |
sobol_state_size,
|
|
Packit |
67cb25 |
sobol_init,
|
|
Packit |
67cb25 |
sobol_get
|
|
Packit |
67cb25 |
};
|
|
Packit |
67cb25 |
const gsl_qrng_type * gsl_qrng_sobol = &sobol_type;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* primitive polynomials in binary encoding
|
|
Packit |
67cb25 |
*/
|
|
Packit |
67cb25 |
static const int primitive_polynomials[SOBOL_MAX_DIMENSION] =
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
1, 3, 7, 11, 13, 19, 25, 37, 59, 47,
|
|
Packit |
67cb25 |
61, 55, 41, 67, 97, 91, 109, 103, 115, 131,
|
|
Packit |
67cb25 |
193, 137, 145, 143, 241, 157, 185, 167, 229, 171,
|
|
Packit |
67cb25 |
213, 191, 253, 203, 211, 239, 247, 285, 369, 299
|
|
Packit |
67cb25 |
};
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* degrees of the primitive polynomials */
|
|
Packit |
67cb25 |
static const int degree_table[SOBOL_MAX_DIMENSION] =
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
0, 1, 2, 3, 3, 4, 4, 5, 5, 5,
|
|
Packit |
67cb25 |
5, 5, 5, 6, 6, 6, 6, 6, 6, 7,
|
|
Packit |
67cb25 |
7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
|
|
Packit |
67cb25 |
7, 7, 7, 7, 7, 7, 7, 8, 8, 8
|
|
Packit |
67cb25 |
};
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* initial values for direction tables, following
|
|
Packit |
67cb25 |
* Bratley+Fox, taken from [Sobol+Levitan, preprint 1976]
|
|
Packit |
67cb25 |
*/
|
|
Packit |
67cb25 |
static const int v_init[8][SOBOL_MAX_DIMENSION] =
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
0, 1, 1, 1, 1, 1, 1, 1, 1, 1,
|
|
Packit |
67cb25 |
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
|
|
Packit |
67cb25 |
1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
|
|
Packit |
67cb25 |
1, 1, 1, 1, 1, 1, 1, 1, 1, 1
|
|
Packit |
67cb25 |
},
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
0, 0, 1, 3, 1, 3, 1, 3, 3, 1,
|
|
Packit |
67cb25 |
3, 1, 3, 1, 3, 1, 1, 3, 1, 3,
|
|
Packit |
67cb25 |
1, 3, 1, 3, 3, 1, 3, 1, 3, 1,
|
|
Packit |
67cb25 |
3, 1, 1, 3, 1, 3, 1, 3, 1, 3
|
|
Packit |
67cb25 |
},
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
0, 0, 0, 7, 5, 1, 3, 3, 7, 5,
|
|
Packit |
67cb25 |
5, 7, 7, 1, 3, 3, 7, 5, 1, 1,
|
|
Packit |
67cb25 |
5, 3, 3, 1, 7, 5, 1, 3, 3, 7,
|
|
Packit |
67cb25 |
5, 1, 1, 5, 7, 7, 5, 1, 3, 3
|
|
Packit |
67cb25 |
},
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
0, 0, 0, 0, 0, 1, 7, 9, 13, 11,
|
|
Packit |
67cb25 |
1, 3, 7, 9, 5, 13, 13, 11, 3, 15,
|
|
Packit |
67cb25 |
5, 3, 15, 7, 9, 13, 9, 1, 11, 7,
|
|
Packit |
67cb25 |
5, 15, 1, 15, 11, 5, 3, 1, 7, 9
|
|
Packit |
67cb25 |
},
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
0, 0, 0, 0, 0, 0, 0, 9, 3, 27,
|
|
Packit |
67cb25 |
15, 29, 21, 23, 19, 11, 25, 7, 13, 17,
|
|
Packit |
67cb25 |
1, 25, 29, 3, 31, 11, 5, 23, 27, 19,
|
|
Packit |
67cb25 |
21, 5, 1, 17, 13, 7, 15, 9, 31, 9
|
|
Packit |
67cb25 |
},
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
|
|
Packit |
67cb25 |
0, 0, 0, 37, 33, 7, 5, 11, 39, 63,
|
|
Packit |
67cb25 |
27, 17, 15, 23, 29, 3, 21, 13, 31, 25,
|
|
Packit |
67cb25 |
9, 49, 33, 19, 29, 11, 19, 27, 15, 25
|
|
Packit |
67cb25 |
},
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
|
|
Packit |
67cb25 |
0, 0, 0, 0, 0, 0, 0, 0, 0, 13,
|
|
Packit |
67cb25 |
33, 115, 41, 79, 17, 29, 119, 75, 73, 105,
|
|
Packit |
67cb25 |
7, 59, 65, 21, 3, 113, 61, 89, 45, 107
|
|
Packit |
67cb25 |
},
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
|
|
Packit |
67cb25 |
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
|
|
Packit |
67cb25 |
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
|
|
Packit |
67cb25 |
0, 0, 0, 0, 0, 0, 0, 7, 23, 39
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
};
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* Sobol generator state.
|
|
Packit |
67cb25 |
* sequence_count = number of calls with this generator
|
|
Packit |
67cb25 |
* last_numerator_vec = last generated numerator vector
|
|
Packit |
67cb25 |
* last_denominator_inv = 1/denominator for last numerator vector
|
|
Packit |
67cb25 |
* v_direction = direction number table
|
|
Packit |
67cb25 |
*/
|
|
Packit |
67cb25 |
typedef struct
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
unsigned int sequence_count;
|
|
Packit |
67cb25 |
double last_denominator_inv;
|
|
Packit |
67cb25 |
int last_numerator_vec[SOBOL_MAX_DIMENSION];
|
|
Packit |
67cb25 |
int v_direction[SOBOL_BIT_COUNT][SOBOL_MAX_DIMENSION];
|
|
Packit |
67cb25 |
} sobol_state_t;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* NOTE: I fixed the size for the preliminary implementation.
|
|
Packit |
67cb25 |
This could/should be relaxed, as an optimization.
|
|
Packit |
67cb25 |
*/
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
static size_t sobol_state_size(unsigned int dimension)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
return sizeof(sobol_state_t);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
static int sobol_init(void * state, unsigned int dimension)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
sobol_state_t * s_state = (sobol_state_t *) state;
|
|
Packit |
67cb25 |
unsigned int i_dim;
|
|
Packit |
67cb25 |
int j, k;
|
|
Packit |
67cb25 |
int ell;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
if(dimension < 1 || dimension > SOBOL_MAX_DIMENSION) {
|
|
Packit |
67cb25 |
return GSL_EINVAL;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* Initialize direction table in dimension 0. */
|
|
Packit |
67cb25 |
for(k=0; k<SOBOL_BIT_COUNT; k++) s_state->v_direction[k][0] = 1;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* Initialize in remaining dimensions. */
|
|
Packit |
67cb25 |
for(i_dim=1; i_dim
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
const int poly_index = i_dim;
|
|
Packit |
67cb25 |
const int degree_i = degree_table[poly_index];
|
|
Packit |
67cb25 |
int includ[8];
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* Expand the polynomial bit pattern to separate
|
|
Packit |
67cb25 |
* components of the logical array includ[].
|
|
Packit |
67cb25 |
*/
|
|
Packit |
67cb25 |
int p_i = primitive_polynomials[poly_index];
|
|
Packit |
67cb25 |
for(k = degree_i-1; k >= 0; k--) {
|
|
Packit |
67cb25 |
includ[k] = ((p_i % 2) == 1);
|
|
Packit |
67cb25 |
p_i /= 2;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* Leading elements for dimension i come from v_init[][]. */
|
|
Packit |
67cb25 |
for(j=0; j<degree_i; j++) s_state->v_direction[j][i_dim] = v_init[j][i_dim];
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* Calculate remaining elements for this dimension,
|
|
Packit |
67cb25 |
* as explained in Bratley+Fox, section 2.
|
|
Packit |
67cb25 |
*/
|
|
Packit |
67cb25 |
for(j=degree_i; j
|
|
Packit |
67cb25 |
int newv = s_state->v_direction[j-degree_i][i_dim];
|
|
Packit |
67cb25 |
ell = 1;
|
|
Packit |
67cb25 |
for(k=0; k
|
|
Packit |
67cb25 |
ell *= 2;
|
|
Packit |
67cb25 |
if(includ[k]) newv ^= (ell * s_state->v_direction[j-k-1][i_dim]);
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
s_state->v_direction[j][i_dim] = newv;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* Multiply columns of v by appropriate power of 2. */
|
|
Packit |
67cb25 |
ell = 1;
|
|
Packit |
67cb25 |
for(j=SOBOL_BIT_COUNT-1-1; j>=0; j--) {
|
|
Packit |
67cb25 |
ell *= 2;
|
|
Packit |
67cb25 |
for(i_dim=0; i_dim
|
|
Packit |
67cb25 |
s_state->v_direction[j][i_dim] *= ell;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* 1/(common denominator of the elements in v_direction) */
|
|
Packit |
67cb25 |
s_state->last_denominator_inv = 1.0 /(2.0 * ell);
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* final setup */
|
|
Packit |
67cb25 |
s_state->sequence_count = 0;
|
|
Packit |
67cb25 |
for(i_dim=0; i_dim<dimension; i_dim++) s_state->last_numerator_vec[i_dim] = 0;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
return GSL_SUCCESS;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
static int sobol_get(void * state, unsigned int dimension, double * v)
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
sobol_state_t * s_state = (sobol_state_t *) state;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
unsigned int i_dimension;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* Find the position of the least-significant zero in count. */
|
|
Packit |
67cb25 |
int ell = 0;
|
|
Packit |
67cb25 |
int c = s_state->sequence_count;
|
|
Packit |
67cb25 |
while(1) {
|
|
Packit |
67cb25 |
++ell;
|
|
Packit |
67cb25 |
if((c % 2) == 1) c /= 2;
|
|
Packit |
67cb25 |
else break;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
/* Check for exhaustion. */
|
|
Packit |
67cb25 |
if(ell > SOBOL_BIT_COUNT) return GSL_EFAILED; /* FIXME: good return code here */
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
for(i_dimension=0; i_dimension
|
|
Packit |
67cb25 |
const int direction_i = s_state->v_direction[ell-1][i_dimension];
|
|
Packit |
67cb25 |
const int old_numerator_i = s_state->last_numerator_vec[i_dimension];
|
|
Packit |
67cb25 |
const int new_numerator_i = old_numerator_i ^ direction_i;
|
|
Packit |
67cb25 |
s_state->last_numerator_vec[i_dimension] = new_numerator_i;
|
|
Packit |
67cb25 |
v[i_dimension] = new_numerator_i * s_state->last_denominator_inv;
|
|
Packit |
67cb25 |
}
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
s_state->sequence_count++;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
return GSL_SUCCESS;
|
|
Packit |
67cb25 |
}
|