MTToolBox  0.2.10
AlgorithmBestBits.hpp
[詳解]
1 #ifndef MTTOOLBOX_ALGORITHM_BEST_BITS_HPP
2 #define MTTOOLBOX_ALGORITHM_BEST_BITS_HPP
3 
34 #include <iostream>
35 #include <iomanip>
36 #include <cstdlib>
37 #include <unistd.h>
38 #if __cplusplus >= 201103L
39 #include <memory>
40 #else // memory
41 #define MTTOOLBOX_USE_TR1
42 #include <tr1/memory>
43 #endif
44 #include <vector>
48 #include <MTToolBox/util.hpp>
49 
50 #if defined(DEBUG)
51 #include <sstream>
52 #endif
53 
54 namespace MTToolBox {
55  using namespace std;
56 #if defined(MTTOOLBOX_USE_TR1)
57  using std::tr1::shared_ptr;
58 #else
59  using std::shared_ptr;
60 #endif
61 
75  template<typename U>
76  class temper_params {
77  public:
86  U * param;
96  int delta;
105  int size;
106 
117  temper_params(int param_num) {
118  size = param_num;
119  delta = 0;
120  param = new U[param_num];
121  for (int i = 0; i < param_num; i++) {
122  param[i] = 0;
123  }
124  }
125 
135  delete[] param;
136  }
137 #if defined(DEBUG)
138  string toString() {
139  stringstream ss;
140  ss << "[";
141  ss << dec << delta << ":";
142  for (int i = 0; i < size; i++) {
143  ss << hex << setw(8) << setfill('0') << param[i] << ",";
144  }
145  ss << "]";
146  return ss.str();
147  }
148 #endif
149  };
150 
187  template<typename U, typename V = U>
188  class AlgorithmBestBits : public AlgorithmTempering<U, V> {
189  public:
199 
231  AlgorithmBestBits(int out_bit_length,
232  const int shift_values[],
233  int param_num,
234  int limit_v) {
235  limit = limit_v;
236  obSize = bit_size<U>();
237  bit_len = out_bit_length;
238  size = param_num;
239  shifts = new int[size];
240  num_pat = size * (size + 1) / 2;
241  for (int i = 0; i < size; i++) {
242  shifts[i] = shift_values[i];
243  }
244  }
245 
255  delete[] shifts;
256  }
257 
286  bool verbose = false) {
287  rand.resetReverseOutput();
288  if (verbose) {
289  cout << "searching from MSB" << endl;
290  }
291  shared_ptr<tempp> initial(new tempp(size));
292  initial->delta = 0;
293  for (int i = 0; i < size; i++) {
294  initial->param[i] = 0;
295  }
296  vector<shared_ptr<tempp> > params;
297  params.push_back(initial);
298  int delta = 0;
299 #if defined(DEBUG)
300  cout << "DEBUG: bit_len = " << dec << bit_len << endl;
301 #endif
302  for (int p = 0; p < limit; p++) {
303  vector<shared_ptr<tempp> > current;
304  current.clear();
305  for (unsigned int i = 0; i < params.size(); i++) {
306  search_best_temper(rand, p, *params[i],
307  current, verbose);
308  }
309  delta = rand.bitSize() * obSize;
310  for (unsigned int i = 0; i < current.size(); i++) {
311  if (current[i]->delta < delta) {
312  delta = current[i]->delta;
313  }
314  }
315 #if defined(DEBUG)
316  cout << "DEBUG: delta = " << dec << delta << endl;
317 #endif
318  if (verbose) {
319  cout << "delta = " << dec << delta << endl;
320  }
321  params.clear();
322  for (unsigned int i = 0; i < current.size(); i++) {
323  if (current[i]->delta == delta) {
324  params.push_back(current[i]);
325  }
326  }
327  }
328  U mask = 0;
329  mask = ~mask;
330  for (int i = 0; i < size; i++) {
331  rand.setTemperingPattern(mask, params[0]->param[i], i);
332  }
333  rand.setUpTempering();
334  if (verbose) {
335  cout << "delta = " << dec << delta << endl;
336  }
337  rand.resetReverseOutput();
338  return 0;
339  }
340 
351  bool isLSBTempering() const {
352  return false;
353  }
354  private:
355  int limit;
356  int bit_len;
357  int size;
358  int obSize;
359  int * shifts;
360  int num_pat;
361 
375  void search_best_temper(TemperingCalculatable<U, V>& rand,
376  int v_bit,
377  const tempp& para,
378  vector<shared_ptr<tempp> >& current,
379  bool verbose) {
380  int delta = rand.bitSize() * obSize;
381  U mask = 0;
382  mask = ~mask;
383  // size が 2 なら 111, 110, 101, 100, 011, 010, 001, 000 の8パターン
384  num_pat = size * (size + 1) / 2;
385  for (int32_t i = (1 << num_pat) -1; i >= 0; i--) {
386  if (! inRange(i, v_bit)) {
387  continue;
388  }
389  shared_ptr<tempp> pattern(new tempp(size));
390  make_pattern(*pattern, i, v_bit, para);
391 #if defined(DEBUG)
392  cout << "pattern:" << pattern->toString() << endl;
393 #endif
394  for (int j = 0; j < size; j++) {
395  rand.setTemperingPattern(mask, pattern->param[j], j);
396  }
397  pattern->delta = get_equidist(rand, v_bit + 1);
398  if (verbose) {
399  cout << "pattern->delta:" << dec << pattern->delta << endl;
400  }
401  if (pattern->delta <= delta) {
402  current.push_back(pattern);
403  delta = pattern->delta;
404  }
405  }
406  }
407 
426  int get_equidist(TemperingCalculatable<U, V>& rand,
427  int bit_length) {
428  AlgorithmEquidistribution<U, V> sb(rand, bit_length);
429  int veq[bit_length];
430  return sb.get_all_equidist(veq);
431  }
432 
460  void make_pattern(tempp& result,
461  int pat, int v, const tempp& para) const {
462  result.delta = 0;
463  for (int i = 0; i < result.size; i++) {
464  result.param[i] = para.param[i];
465  }
466  U para_mask = 0;
467  para_mask = (~para_mask) >> v;
468  int index = 0;
469  int idx = 0;
470  int rdx = size - 1;
471  U mask = 1 << (num_pat - 1);
472  int sum = 0;
473  U one = 1;
474  while (mask != 0) {
475  if ((pat & mask) && (obSize > v + sum + 1)) {
476  result.param[index] |= (one << (obSize - v - sum - 1))
477  & para_mask;
478  } else if (((pat & mask) == 0) && (obSize > v + sum + 1)) {
479  result.param[index] &= ~(one << (obSize - v - sum - 1));
480  }
481  mask = mask >> 1;
482  index = index + 1;
483  if (index >= size) {
484  sum += shifts[rdx];
485  index = idx;
486  idx++;
487  rdx--;
488  }
489  }
490 
491 #if defined(DEBUG)
492  cout << "make_pattern:" << dec << pat << ","
493  << dec << v << "," << result.toString()
494  << hex << para_mask << endl;
495 #endif
496  }
497 
522  bool inRange(int pat, int v) const {
523  int index = 0;
524  int idx = 0;
525  int rdx = size - 1;
526  U mask = 1 << (num_pat - 1);
527  int sum = 0;
528  while (mask != 0) {
529  if ((pat & mask) && (v + shifts[index] + sum > obSize)) {
530  return false;
531  }
532  mask = mask >> 1;
533  index = index + 1;
534  if (index >= size) {
535  sum += shifts[rdx];
536  index = idx;
537  idx++;
538  rdx--;
539  }
540  }
541  return true;
542  }
543  };
544 }
545 #if defined(MTTOOLBOX_USE_TR1)
546 #undef MTTOOLBOX_USE_TR1
547 #endif
548 #endif // MTTOOLBOX_ALGORITHM_BEST_BITS_HPP
int operator()(TemperingCalculatable< U, V > &rand, bool verbose=false)
テンパリングパラメータを探索する
Definition: AlgorithmBestBits.hpp:285
テンパリングパラメータ探索用の抽象クラス
virtual void resetReverseOutput()=0
出力の上位ビットと下位ビットの並びを元に戻す。
~AlgorithmBestBits()
デストラクタ
Definition: AlgorithmBestBits.hpp:254
int delta
均等分布次元の理論値との差の総和
Definition: AlgorithmBestBits.hpp:96
temper_params(int param_num)
単純なコンストラクタ
Definition: AlgorithmBestBits.hpp:117
virtual int bitSize() const =0
内部状態空間のビットサイズを返す。
temper_params< U > tempp
テンパリングパラメータのクラス
Definition: AlgorithmBestBits.hpp:198
テンパリングを行う可約ジェネレータは、このクラスを継承す ることによって、TemperingAlgorithmを使用した...
Definition: TemperingCalculatable.hpp:54
~temper_params()
デストラクタ
Definition: AlgorithmBestBits.hpp:134
int size
テンパリングパラメータの数
Definition: AlgorithmBestBits.hpp:105
bool isLSBTempering() const
LSBからのテンパリングかを示す。常にfalse。
Definition: AlgorithmBestBits.hpp:351
ユーティリティ関数群
テンパリングパラメータのクラス
Definition: AlgorithmBestBits.hpp:76
AlgorithmBestBits(int out_bit_length, const int shift_values[], int param_num, int limit_v)
Definition: AlgorithmBestBits.hpp:231
疑似乱数生成器の出力の均等分布次元を計算する。
テンパリングパラメータ探索アルゴリズムのための抽象クラス
virtual void setUpTempering()=0
テンパリングテーブルの準備が必要な場合はここで準備する。 MTGP の場合はルックアップテーブルの準備をし...
virtual void setTemperingPattern(U mask, U pattern, int index)=0
テンパリングパラメータをセットする。
疑似乱数生成器の高次元均等分布性を改善するために、テンパ リングパラメータを探索するアルゴリズム ...
Definition: AlgorithmTempering.hpp:62
U * param
テンパリングパラメータの配列
Definition: AlgorithmBestBits.hpp:86
テンパリングパラメータを探索するアルゴリズム(MT用)
Definition: AlgorithmBestBits.hpp:188
MTToolBox の名前空間