RandomLib  1.10
 All Classes Namespaces Files Functions Variables Typedefs Enumerator Friends Macros Pages
RandomEngine.hpp
Go to the documentation of this file.
1 /**
2  * \file RandomEngine.hpp
3  * \brief Header for RandomEngine.
4  *
5  * Copyright (c) Charles Karney (2006-2012) <charles@karney.com> and licensed
6  * under the MIT/X11 License. For more information, see
7  * http://randomlib.sourceforge.net/
8  **********************************************************************/
9 
10 #if !defined(RANDOMLIB_RANDOMENGINE_HPP)
11 #define RANDOMLIB_RANDOMENGINE_HPP 1
12 
13 #include <RandomLib/RandomSeed.hpp>
16 #include <limits>
17 #include <string>
18 #include <algorithm>
19 #if defined(HAVE_SSE2) && HAVE_SSE2 && defined(_MSC_VER) && !defined(_WIN64)
20 #include <new>
21 #endif
22 
23 #if !defined(RANDOMLIB_BUILDING_LIBRARY) && \
24  defined(HAVE_BOOST_SERIALIZATION) && HAVE_BOOST_SERIALIZATION
25 #include <boost/serialization/nvp.hpp>
26 #include <boost/serialization/split_member.hpp>
27 #include <boost/serialization/vector.hpp>
28 #endif
29 
30 namespace RandomLib {
31  /**
32  * \brief Uniform random number generator.
33  *
34  * This implements a generic random number generator. Such a generator
35  * requires two data holders RandomSeed, to hold the seed, and RandomEngine,
36  * to hold the state. In addition we need two piece of machinery, a "Mixer"
37  * to convert the seed into an initial state and an "Algorithm" to advance the
38  * state.
39  *
40  * @tparam Algorithm the random number algorithm.
41  * @tparam Mixer the way seeds are turned into state.
42  *
43  * RandomSeed is responsible for setting and reporting the seed.
44  *
45  * Mixer has no state and implements only static methods. It needs to have
46  * the following public interface
47  * - typedef mixer_t: a RandomType giving the output type
48  * - unsigned version: an identifying version number
49  * - static std::string Name(): an identifying name for the mixer
50  * - static method SeedToState: converts a seed into n words of state.
51  *
52  * Algorithm has no state and implements only static methods. It needs to
53  * have the following public interface
54  * - typedef engine_t: a RandomType giving the output type
55  * - typedef internal_type: a integer type used by Transition. This is
56  * usually the same as engine_t::type. However it allows the use of
57  * vector instructions on some platforms. We require that engine_t::type
58  * and internal_type line up properly in a union so that there is no need
59  * to convert the data explicitly between internal_type and
60  * engine_t::type.
61  * - unsigned version: an identifying version number
62  * - static std::string Name(): an identifying name for the mixer
63  * - enum N: the size of the state in units of engine_t.
64  * - static method Transition: steps the generator forwards or backwards.
65  * - static method Generate: tempers the state immediately prior to output
66  * - static method NormalizeState: force the initial state (the result of
67  * the Mixer) into a legal state.
68  * - static method CheckState accumulates the checksum for the state into
69  * check. In addition it throws an exception if the state is bad.
70  *
71  * RandomEngine is the glue that holds everything together. It repacks
72  * the mixer_t data from Mixer into engine_t if necessary. It deals with
73  * delivering individual random results, stepping the state forwards and
74  * backwards, leapfrogging the generator, I/O of the generator, etc.
75  *
76  * Written by Charles Karney <charles@karney.com> and licensed under the
77  * MIT/X11 License. For more information, see
78  * http://randomlib.sourceforge.net/
79  **********************************************************************/
80  template<class Algorithm, class Mixer>
82  private:
83  /**
84  * The result RandomType (carried over from the \e Algorithm).
85  **********************************************************************/
86  typedef typename Algorithm::engine_t result_t;
87  /**
88  * The RandomType used by the \e Mixer.
89  **********************************************************************/
90  typedef typename Mixer::mixer_t mixer_t;
91  /**
92  * The internal_type used by the Algorithm::Transition().
93  **********************************************************************/
94  typedef typename Algorithm::internal_type engine_type;
95  public:
96  /**
97  * The number of random bits produced by Ran().
98  **********************************************************************/
99  enum {
100  width = result_t::width
101  };
102 
103  /**
104  * A type large enough to hold \e width bits. This is used for the
105  * internal state of the generator and the result returned by Ran().
106  **********************************************************************/
107  typedef typename result_t::type result_type;
108 
109  /**
110  * The minimum result returned by Ran() = 0.
111  **********************************************************************/
112  static const result_type min = result_t::min;
113 
114  /**
115  * The maximum result returned by Ran() = 2<sup><i>w</i></sup> &minus; 1.
116  **********************************************************************/
117  static const result_type max = result_t::max;
118 
119  protected:
120 
121  /**
122  * The mask for the result_t.
123  **********************************************************************/
124  static const result_type mask = result_t::mask;
125 
126  private:
127  /**
128  * A version number "RandLib0" to ensure safety of Save/Load. The first 7
129  * bytes can be regarded as a "signature" and the 8th byte a version
130  * number.
131  **********************************************************************/
132  static const u64::type version = 0x52616e644c696230ULL; // 'RandLib0'
133  /**
134  * Marker for uninitialized object
135  **********************************************************************/
136  static const unsigned UNINIT = 0xffffffffU;
137  enum {
138  /**
139  * The size of the state in units of result_type
140  **********************************************************************/
141  N = Algorithm::N,
142  /**
143  * The size of the state in units of mixer_t::type
144  **********************************************************************/
145  NU = (N * width + mixer_t::width - 1) / mixer_t::width,
146  /**
147  * The size of the state in units of engine_type.
148  **********************************************************************/
149  NV = N * sizeof(result_type) / sizeof(engine_type)
150  };
151 
152  /**
153  * \brief Union for the state.
154  *
155  * A union to hold the state in the result_type, mixer_t::type, and
156  * engine_type representations.
157  **********************************************************************/
158  union {
159  /**
160  * the result_type representation returned by Ran()
161  **********************************************************************/
162  result_type _state[N];
163  /**
164  * the mixer_t::type representation returned by Mixer::SeedToState.
165  **********************************************************************/
166  typename mixer_t::type _stateu[NU];
167  /**
168  * the engine_type representation returned by Algorithm::Transition.
169  **********************************************************************/
170  engine_type _statev[NV];
171  };
172 
173  /**
174  * The index for the next random value
175  **********************************************************************/
176  unsigned _ptr;
177  /**
178  * How many times has Transition() been called
179  **********************************************************************/
180  long long _rounds;
181  /**
182  * Stride for leapfrogging
183  **********************************************************************/
184  unsigned _stride;
185 
186  public:
187 
188  /**
189  * \name Constructors
190  **********************************************************************/
191  ///@{
192  /**
193  * Initialize from a vector. Only the low \e 32 bits of each element are
194  * used.
195  *
196  * @tparam IntType the integral type of the elements of the vector.
197  * @param[in] v the vector of elements.
198  **********************************************************************/
199  template<typename IntType>
200  explicit RandomEngine(const std::vector<IntType>& v) { Reseed(v); }
201  /**
202  * Initialize from a pair of iterators setting seed to [\e a, \e b). The
203  * iterator must produce results which can be converted into seed_type.
204  * Only the low \e 32 bits of each element are used.
205  *
206  * @tparam InputIterator the type of the iterator.
207  * @param[in] a the beginning iterator.
208  * @param[in] b the ending iterator.
209  **********************************************************************/
210  template<typename InputIterator>
211  RandomEngine(InputIterator a, InputIterator b) { Reseed(a, b); }
212  /**
213  * Initialize with seed [\e n]. Only the low \e width bits of \e n are
214  * used.
215  *
216  * @param[in] n the new seed to use.
217  **********************************************************************/
218  explicit RandomEngine(seed_type n) { Reseed(n); }
219  /**
220  * Initialize with seed []. This can be followed by a call to Reseed() to
221  * select a unique seed.
222  **********************************************************************/
223  RandomEngine() { unsigned long s[1]; Reseed(s, s); }
224  /**
225  * Initialize from a string. See Reseed(const std::string& s)
226  *
227  * @param[in] s the string to be decoded into a seed.
228  **********************************************************************/
229  explicit RandomEngine(const std::string& s) { Reseed(s); }
230 
231  ///@}
232 
233  /**
234  * \name Functions for returning random data
235  **********************************************************************/
236  ///@{
237  /**
238  * Return \e width bits of randomness. This is the natural unit of random
239  * data produced random number generator.
240  *
241  * @return the next random number of width \e width.
242  **********************************************************************/
243  result_type Ran() throw() {
244  if (_ptr >= N)
245  Next();
246  result_type y = _state[_ptr];
247  _ptr += _stride;
248 
249  return Algorithm::Generate(y);
250  }
251 
252  /**
253  * Return 32 bits of randomness.
254  *
255  * @return a 32-bit random number.
256  **********************************************************************/
257  u32::type Ran32() throw() {
258  // return width > 32 ? u32::cast(Ran()) : Ran();
259  return u32::cast(Ran());
260  }
261 
262  /**
263  * Return 64 bits of randomness.
264  *
265  * @return a 64-bit random number.
266  **********************************************************************/
267  u64::type Ran64() throw() {
268  const u64::type x = Ran();
269  return width > 32 ? x : u64::cast(Ran()) << (64 - width) | x;
270  }
271 
272  /**
273  * Return \e width bits of randomness. Result is in [0,
274  * 2<sup><i>w</i></sup>). (This just calls Ran().)
275  *
276  * @return the next random number of width \e width.
277  **********************************************************************/
278  result_type operator()() throw() { return Ran(); }
279  ///@}
280 
281 #if defined(HAVE_SSE2) && HAVE_SSE2 && defined(_MSC_VER) && !defined(_WIN64)
282  /**
283  * new operator with alignment (needed for Visual Studio)
284  **********************************************************************/
285  void* operator new(size_t n) {
286  void* p = _aligned_malloc(n, __alignof(RandomEngine));
287  if (p == 0) throw std::bad_alloc();
288  return p;
289  }
290 
291  /**
292  * delete operator with alignment (needed for Visual Studio)
293  **********************************************************************/
294  void operator delete(void* p) { _aligned_free(p); }
295 
296  /**
297  * new[] operator with alignment (needed for Visual Studio)
298  **********************************************************************/
299  void* operator new[](size_t n) {
300  void* p = _aligned_malloc(n, __alignof(RandomEngine));
301  if (p == 0) throw std::bad_alloc();
302  return p;
303  }
304 
305  /**
306  * delete[] operator with alignment (needed for Visual Studio)
307  **********************************************************************/
308  void operator delete[](void* p) { _aligned_free(p); }
309 #endif
310 
311  /**
312  * \name Comparing Random objects
313  **********************************************************************/
314  ///@{
315  /**
316  * Test equality of two Random objects. This test that the seeds match and
317  * that they have produced the same number of random numbers.
318  *
319  * @param[in] r the RandomEngine object to compare.
320  * @return true if the RandomEngine objects produce the same results.
321  **********************************************************************/
322  bool operator==(const RandomEngine& r) const throw()
323  // Ensure that the two Random objects behave the same way. Note however
324  // that the internal states may still be different, e.g., the following all
325  // result in Random objects which are == (with Count() == 0) but which all
326  // have different internal states:
327  //
328  // Random r(0); _ptr == UNINIT
329  // r.StepCount( 1); r.StepCount(-1); _ptr == 0, _rounds == 0
330  // r.StepCount(-1); r.StepCount( 1); _ptr == N, _rounds == -1
331  { return Count() == r.Count() && _seed == r._seed &&
332  _stride == r._stride; }
333  /**
334  * Test inequality of two Random objects. See Random::operator==
335  *
336  * @param[in] r the RandomEngine object to compare.
337  * @return true if the RandomEngine objects produce different results.
338  **********************************************************************/
339  bool operator!=(const RandomEngine& r) const throw()
340  { return !operator==(r); }
341  ///@}
342 
343  /**
344  * \name Interchanging Random objects
345  **********************************************************************/
346  ///@{
347  /**
348  * Swap with another Random object.
349  *
350  * @param[in,out] t the RandomEngine object to swap with.
351  **********************************************************************/
352  void swap(RandomEngine& t) throw() {
353  _seed.swap(t._seed);
354  std::swap(_ptr, t._ptr);
355  std::swap(_stride, t._stride);
356  std::swap(_rounds, t._rounds);
357  std::swap_ranges(_state, _state + N, t._state);
358  }
359  ///@}
360 
361  /**
362  * \name Writing to and reading from a stream
363  **********************************************************************/
364  ///@{
365  /**
366  * Save the state of the Random object to an output stream. Format is a
367  * sequence of unsigned 32-bit integers written either in decimal (\e bin
368  * false, text format) or in network order with most significant byte first
369  * (\e bin true, binary format). Data consists of:
370  *
371  * - RandomLib magic string + version (2 words)
372  * - Algorithm version (1 word)
373  * - Mixer version (1 word)
374  * - _seed.size() (1 word)
375  * - _seed data (_seed.size() words)
376  * - _ptr (1 word)
377  * - _stride (1 word)
378  * - if _ptr != UNINIT, _rounds (2 words)
379  * - if _ptr != UNINIT, _state (N words or 2 N words)
380  * - checksum
381  *
382  * Shortest possible saved result consists of 8 words. This corresponds to
383  * RandomSeed() = [] and Count() = 0.
384  *
385  * @param[in,out] os the output stream.
386  * @param[in] bin if true (the default) save in binary mode.
387  **********************************************************************/
388  void Save(std::ostream& os, bool bin = true) const;
389  /**
390  * Restore the state of the Random object from an input stream. If \e bin,
391  * read in binary, else use text format. See documentation of
392  * RandomEngine::Save for the format. Include error checking on data to
393  * make sure the input has not been corrupted. If an error occurs while
394  * reading, the Random object is unchanged.
395  *
396  * @param[in,out] is the input stream.
397  * @param[in] bin if true (the default) load in binary mode.
398  * @exception RandomErr if the state read from \e is is illegal.
399  **********************************************************************/
400  void Load(std::istream& is, bool bin = true) {
401  // Read state into temporary so as not to change object on error.
402  RandomEngine t(is, bin);
403  _seed.reserve(t._seed.size());
404  *this = t;
405  }
406  ///@}
407 
408  /**
409  * \name Basic I/O
410  **********************************************************************/
411  ///@{
412  /**
413  * Write the state of a generator to stream \e os as text
414  *
415  * @param[in,out] os the output stream.
416  * @param[in] r the RandomEngine object to be saved.
417  **********************************************************************/
418  friend std::ostream& operator<<(std::ostream& os, const RandomEngine& r) {
419  r.Save(os, false);
420  return os;
421  }
422 
423  /**
424  * Read the state of a generator from stream \e is as text
425  *
426  * @param[in,out] is the output stream.
427  * @param[in] r the RandomEngine object to be loaded.
428  * @exception RandomErr if the state read from \e is is illegal.
429  **********************************************************************/
430  friend std::istream& operator>>(std::istream& is, RandomEngine& r) {
431  r.Load(is, false);
432  return is;
433  }
434  ///@}
435 
436  /**
437  * \name Examining and advancing the Random generator
438  **********************************************************************/
439  ///@{
440  /**
441  * Return the number of random numbers used. This needs to return a long
442  * long result since it can reasonably exceed 2<sup>31</sup>. (On a 1GHz
443  * machine, it takes about a minute to produce 2<sup>32</sup> random
444  * numbers.) More precisely this is the (zero-based) index of the next
445  * random number to be produced. (This distinction is important when
446  * leapfrogging is in effect.)
447  *
448  * @return the count of random numbers used.
449  **********************************************************************/
450  long long Count() const throw()
451  { return _ptr == UNINIT ? 0 : _rounds * N + _ptr; }
452  /**
453  * Step the generator forwards or backwards so that the value returned
454  * by Count() is \e n
455  *
456  * @param[in] n the new count.
457  **********************************************************************/
458  void SetCount(long long n) throw() { StepCount(n - Count()); }
459  /**
460  * Step the generator forward \e n steps. \e n can be negative.
461  *
462  * @param[in] n how much to step the generator forward.
463  **********************************************************************/
464  void StepCount(long long n) throw();
465  /**
466  * Resets the sequence. Equivalent to SetCount(0), but works by
467  * reinitializing the Random object from its seed, rather than by stepping
468  * the sequence backwards. In addition, this undoes leapfrogging.
469  **********************************************************************/
470  void Reset() throw() { _ptr = UNINIT; _stride = 1; }
471  ///@}
472 
473  /**
474  * \name Leapfrogging
475  **********************************************************************/
476  ///@{
477  /**
478  * Set leapfrogging stride to a positive number \e n and increment Count()
479  * by \e k < \e n. If the current Count() is \e i, then normally the next
480  * 3 random numbers would have (zero-based) indices \e i, \e i + 1, \e i +
481  * 2, and the new Count() is \e i + 2. However, after SetStride(\e n, \e
482  * k) the next 3 random numbers have indices \e i + \e k, \e i + \e k + \e
483  * n, \e i + \e k + 2\e n, and the new Count() is \e i + \e k + 3\e n.
484  * With leapfrogging in effect, the time to produce raw random numbers is
485  * roughly proportional to 1 + (\e n &minus; 1)/3. Reseed(...) and Reset()
486  * both reset the stride back to 1. See \ref parallel for a description of
487  * how to use this facility.
488  *
489  * @param[in] n the stride (default 1).
490  * @param[in] k the initial increment (default 0).
491  * @exception RandomErr if \e n is 0 or too large or if \e k is not less
492  * than \e n.
493  **********************************************************************/
494  void SetStride(unsigned n = 1, unsigned k = 0) {
495  // Limit stride to UNINIT/2. This catches negative numbers that have
496  // been cast into unsigned. In reality the stride should be no more than
497  // 10-100.
498  if (n == 0 || n > UNINIT/2)
499  throw RandomErr("RandomEngine: Invalid stride");
500  if (k >= n)
501  throw RandomErr("RandomEngine: Invalid offset");
502  _stride = n;
503  StepCount(k);
504  }
505  /**
506  * Return leapfrogging stride.
507  *
508  * @return the stride.
509  **********************************************************************/
510  unsigned GetStride() const throw() { return _stride; }
511  ///@}
512 
513  /**
514  * Tests basic engine.
515  *
516  * @exception RandomErr if any of the tests fail.
517  **********************************************************************/
518  static void SelfTest();
519 
520  /**
521  * Return the name of the generator. This incorporates the names of the \e
522  * Algorithm and \e Mixer.
523  *
524  * @return the name of the generator.
525  **********************************************************************/
526  static std::string Name() {
527  return "RandomEngine<" + Algorithm::Name() + "," + Mixer::Name() + ">";
528  }
529 
530  private:
531  /**
532  * Compute initial state from seed
533  **********************************************************************/
534  void Init() throw();
535  /**
536  * The interface to Transition used by Ran().
537  **********************************************************************/
538  void Next() throw() {
539  if (_ptr == UNINIT)
540  Init();
541  _rounds += _ptr/N;
542  Algorithm::Transition(_ptr/N, _statev);
543  _ptr %= N;
544  }
545 
546  u32::type Check(u64::type v, u32::type e, u32::type m) const;
547 
548  static result_type SelfTestResult(unsigned) throw() { return 0; }
549 
550  /**
551  * Read from an input stream. Potentially corrupts object. This private
552  * constructor is used by RandomEngine::Load so that it can avoid
553  * corrupting its state on bad input.
554  **********************************************************************/
555  explicit RandomEngine(std::istream& is, bool bin);
556 
557 #if !defined(RANDOMLIB_BUILDING_LIBRARY) && \
558  defined(HAVE_BOOST_SERIALIZATION) && HAVE_BOOST_SERIALIZATION
559  friend class boost::serialization::access;
560  /**
561  * Save to a boost archive. Boost versioning isn't very robust. (It
562  * allows a RandomGenerator32 to be read back in as a RandomGenerator64.
563  * It doesn't interact well with templates.) So we do our own versioning
564  * and supplement this with a checksum.
565  **********************************************************************/
566  template<class Archive> void save(Archive& ar, const unsigned int) const {
567  u64::type _version = version;
568  u32::type _eversion = Algorithm::version,
569  _mversion = Mixer::version,
570  _checksum = Check(_version, _eversion, _mversion);
571  ar & boost::serialization::make_nvp("version" , _version )
572  & boost::serialization::make_nvp("eversion", _eversion)
573  & boost::serialization::make_nvp("mversion", _mversion)
574  & boost::serialization::make_nvp("seed" , _seed )
575  & boost::serialization::make_nvp("ptr" , _ptr )
576  & boost::serialization::make_nvp("stride" , _stride );
577  if (_ptr != UNINIT)
578  ar & boost::serialization::make_nvp("rounds", _rounds )
579  & boost::serialization::make_nvp("state" , _state );
580  ar & boost::serialization::make_nvp("checksum", _checksum);
581  }
582  /**
583  * Load from a boost archive. Do this safely so that the current object is
584  * not corrupted if the archive is bogus.
585  **********************************************************************/
586  template<class Archive> void load(Archive& ar, const unsigned int) {
587  u64::type _version;
588  u32::type _eversion, _mversion, _checksum;
589  ar & boost::serialization::make_nvp("version" , _version )
590  & boost::serialization::make_nvp("eversion", _eversion )
591  & boost::serialization::make_nvp("mversion", _mversion );
592  RandomEngine<Algorithm, Mixer> t(std::vector<seed_type>(0));
593  ar & boost::serialization::make_nvp("seed" , t._seed )
594  & boost::serialization::make_nvp("ptr" , t._ptr )
595  & boost::serialization::make_nvp("stride" , t._stride );
596  if (t._ptr != UNINIT)
597  ar & boost::serialization::make_nvp("rounds", t._rounds )
598  & boost::serialization::make_nvp("state" , t._state );
599  ar & boost::serialization::make_nvp("checksum", _checksum );
600  if (t.Check(_version, _eversion, _mversion) != _checksum)
601  throw RandomErr("RandomEngine: Checksum failure");
602  _seed.reserve(t._seed.size());
603  *this = t;
604  }
605  /**
606  * Glue the boost save and load functionality together---a bit of boost
607  * magic.
608  **********************************************************************/
609  template<class Archive>
610  void serialize(Archive &ar, const unsigned int file_version)
611  { boost::serialization::split_member(ar, *this, file_version); }
612 #endif // HAVE_BOOST_SERIALIZATION
613 
614  };
615 
620 
621 } // namespace RandomLib
622 
623 namespace std {
624  /**
625  * Swap two RandomEngines. This is about 3x faster than the default swap.
626  *
627  * @tparam Algorithm the algorithm for the RandomEngine.
628  * @tparam Mixer the mixer for the RandomEngine.
629  * @param[in,out] r the first RandomEngine to swap.
630  * @param[in,out] s the second RandomEngine to swap.
631  **********************************************************************/
632  template<class Algorithm, class Mixer>
635  r.swap(s);
636  }
637 
638 } // namespace std
639 
640 #endif // RANDOMLIB_RANDOMENGINE_HPP
bool operator!=(const RandomEngine &r) const
result_t::type result_type
void Save(std::ostream &os, bool bin=true) const
Definition: Random.cpp:375
friend std::istream & operator>>(std::istream &is, RandomEngine &r)
bool operator==(const RandomEngine &r) const
RandomEngine< SFMT19937< Random_u64 >, MixerSFMT > SRandomGenerator64
RandomEngine< MT19937< Random_u64 >, MixerSFMT > MRandomGenerator64
void SetStride(unsigned n=1, unsigned k=0)
A base class for random generators.
Definition: RandomSeed.hpp:62
void Load(std::istream &is, bool bin=true)
Exception handling for RandomLib.
Definition: Random.hpp:103
#define RANDOMLIB_EXPORT
Definition: Random.hpp:83
void swap(RandomEngine &t)
The SFMT mixing functionality.
std::vector< seed_type > _seed
Definition: RandomSeed.hpp:239
void SetCount(long long n)
RandomEngine(const std::vector< IntType > &v)
seed_t::type seed_type
Definition: RandomSeed.hpp:73
void swap(RandomLib::RandomCanonical< Generator > &r, RandomLib::RandomCanonical< Generator > &s)
static std::string Name()
RandomEngine< MT19937< Random_u32 >, MixerSFMT > MRandomGenerator32
Header for RandomSeed.
void swap(RandomLib::RandomEngine< Algorithm, Mixer > &r, RandomLib::RandomEngine< Algorithm, Mixer > &s)
Header for MT19937 and SFMT19937.
Uniform random number generator.
RandomEngine< SFMT19937< Random_u32 >, MixerSFMT > SRandomGenerator32
Header for Mixer classes.
friend std::ostream & operator<<(std::ostream &os, const RandomEngine &r)
RandomEngine(const std::string &s)
unsigned GetStride() const
RandomEngine(InputIterator a, InputIterator b)
long long Count() const