Random Review

From: Thomas Holenstein (tholenst_at_[hidden])
Date: 2000-06-08 04:24:01

Hello boosters,

This is afaik the first formal review comment.  I think, one should
post the result first.  
Result:  Include the random library into the boost library, because
a random generator library is missing in the STL.  Jens Library
provides a clean solution to this problem.

I had quite a deep look at the random library.  Personally, I do not
have much experience with random numbers expect, of course, by using
them..  I was not able to test everything, anyhow.

Because this mail has grown quite much, I'd like to say the imho most
important points right away.

 (1) I think, the library is very good. It should be added to the 
     boost library. Note that I vote for inclusion of the library even
     if the other things I mention here are discarded.

 (2) Remove the iterator interface of your function objects and the
     class generator_iterator.  They do not deal with generating random
     numbers.  Instead, we should provide a generic class like
     generator_iterator in e.g. utility.hpp.

 (3) The distributions should be default constructable where possible.
     I would like to be able to write:
       boost::uniform_01<boost::mt19937> rand;
     or
       boost::uniform_int<boost::mt19937> rand(0, 5);
     Then, the Template UniformRandomNumberGenerator argument probably
     would go last.  This would require defining a new constructor, 
     as far as I can see.  I would also reorder the arguments because of
     this.

There is one small bug which needs to be fixed before the library goes
to the webpage:  the nondeterministic generator random_device does not
provide min() and max().  Also, I think the points (2) and (3) needs
to be discussed before the library goes to the webpage.

Keep in mind that I recommend accepting the library, not depending on
whether Jens decides to incorporate any suggested change.  This is
because I think the library is very useful as is.

Design: (this is the important stuff.  Documentation and implementation is
=======  changed easily.  Should be discussed right away.)

Iterator interfaces
-------------------
I would not include the iterator interface.  I think, this is a
missing library function: taking a input iterator and turning it into
a function object and vice versa.  If there would be such a function
in boost, the random number library gets simpler, because it
has an easier interface. (btw.:  I think, there is a complete iterator
  library missing in C++ STL.  One could, for example, 
  have functions concatenating two iterators, returning an 
  iterator, or merging two "sorted iterators" and returning
  a "single sorted iterator".  For multithreading support, a function
  returning a "pipe" -- as a input and a ouptut iterator -- would be a 
  easy to use producer/consumer scheme. But more of that later, 
  when this mailing list is not so high volume like now)

Furthermore I think that the generator_iterator is not needed and should be 
removed.  Generator_iterator is in fact something I would provide more
generally in utility.hpp or so.  It probably can already be used that
way.

If you do not want to remove the iterator interface, then I think
"operator();" should behave like "operator*(); operator++();".
Unfortunately, the following two programs do *not* generate the same
output, as I would expect:
------------------------- prog 1
/* defs skipped */
  gen g;
  boost::uniform_int<gen> rand(g, 0, 500);
  for (int i=0; i < 5; ++i) {
    std::cout << rand() << std::endl;
  }
------------------------- prog 2
  gen g;
  boost::uniform_int<gen> rand(g, 0, 500);
  for (int i=0; i < 5; ++i) {
    std::cout << *rand << std::endl;
    ++rand;
  }
------------------------- end

I would also prefer the exclusive maximum for floating point generators.
uniform_01 could also get a fixed_range then.  Note that now uniform_01
does not return the same range as uniform_real(0,1).  And 1-epsilon may not
be exactly the number you'r looking for anyhow (I did not think about that
much...)

Streamable concept:
-------------------
Why are distributions not streamable?  I could think of cases where this
could be useful.  Of course this must be used with care, the complete
generator is streamed too.

nondet_random
-------------
Nondet random clearly misses member function min and max.  
Now it is no uniform_random_generator.

================================================
    The rest is minor, because it can be changed anytime...
================================================
Compiling:
==========
The patch "config.hpp.diff" fails.  It seems to me that it has not to
+ be applied in the current version.

  

I tried it with a more or less recent egcs on linux.  I never had problem
compiling, except that I had to remove the std:: the lines 773 and 867
from random.hpp:

I changed:
  typedef std::ptrdiff_t difference_type;
into
  typedef ptrdiff_t difference_type;

Note that I'm using a g++ which supports std:: and my libstdc++-v3 does too.
I did not have a closer look on this.  It seems my (quite new) libstdc++-v3
version does not place ptrdiff_t in namespace std.

I did not find BOOST_STDINT_H_HAS_UINT64_T defined anywhere, so I could
not test rand48 at first.  I defined it myself, it did not compile, because of
some missing operator>>.

Apart from that, I did not have any problem compiling and running.

random_test.cpp compiled well too.  Note: there were many buckets with
too great distance.  Especially the 2nd last one had about 30
(guessed) buckets which were out of the confidence interval (don't
know how normal this is...)

Documentation & usage:
======================

I think the documentation still needs some work.  Probably some simple
examples would be useful, for people which just want some quick and
easy random numbers.  This should have a single example page, some bit
more than the provided demo.  One of the first examples could be:

---------------------------------------------------
#include <iostream>
#include "boost/random.hpp"

typedef boost::minstd_rand generator;

int main() 
{
  generator g;
  boost::uniform_01<generator> rand(g);
  for (int i=0; i < 10; ++i) 
    std::cout << rand() << std::endl;
}
----------------------------------------------

I think the biggest problem for newbies, is that they have to use a
generator and a distribution to generate numbers.  So, such an example
would be useful. 

Below, I suggest some improvements for the documentation:

random-concepts.html
--------------------

I'm not sure how a user has to provide a numeric_limits<T>, but afaik
he is not allowed to put anything in namespace std.  So probably (?) the
first table means numeric_limits<T>::is_specialized is true.

random-generators.html
----------------------
This documentation has a small flaw because my netscape nearly does not
distinguish between <h2> and <h3> (this is, of course not your fault).
May be you could insert a <hr> before a <h2>.

I would not document the modulus arithmetic class, as I think this is
*not* in the interface you provide.  Someday, in the far future, you may
want to use the boost::modulo_arithmetics class (not existing yet), and
you want to change.

In the table, generators seem to be faster the larger the "approximate
relative speed" is.  This makes sense for me, but I think "approximate
relative running time" would be more intuitive, as I am used to measure 
performance in seconds.  So probably you should use the table on the bottom.

I would prefere the hyperlinks from the top not going to the specializations
but to the beginning of the paragraph.  I.e. the link in "minstd_rand" should
go to detail::linear_congruential.

The note in detail::linear_congruential probably means minstd_rand, and not 
rand48, does it?

In section detail::inversive_congruential you write "Instantiations of
class template mersenne_twister model..." instead of inversive_congruential.

random-distributions.html
-------------------------

Seems very good.  Maybe, the corresponding constructor call could go into 
the table on the top for each distribution.  But this is a detail.

lognormal_distribution: Please remove the lognormal_distribution
default parameters.  They don't exist, and their values don't work.
Furthermore, you say, "mean and dev are the parameters for the
distribution", but there is no "dev".

uniform_sphere: Detail: lib.alg.generate seems to be 25.2.6, not 26.2.6.  

uniform_sphere: The point with returning a vector has already been
discussed.  Additionally, consider returning an iterator, or a c_array
("nicos" array).  The Iterator would iterator through the dimensions.
(Maybe this is a stupid idea...)

random-misc.html
----------------
No comments here.  Seems very good.

Implementation:
===============

These are only minor and short:
  - Do we need to include <string>?
  - Maybe, later you can remove #include <vector> (Not now, of course).
  - You should document (with few words) that has_fixed_range is also
    compiler dependent.
  - Line 745:  enum { has_fixed_range = true }; probably should be
               enum { has_fixed_range = false};
  - What purpose serves generator_reference_t anyhow?
    I did not find it documented nor used in random.hpp.
  - Why is the triangle distribution undocumented?
  - I would not restrict uniform_sphere on dimensions > 1.  One day,
    I might be happy me general procedure using the 
    implementation works also if dimension == 1.  Note that everything
    is well defined (it's a distribution with possible outcomes -1, 1)
  - I think your implementation does not work if someone decides, e.g.
    to use Rational Class as Real numbers.  Probably, you should assert
    std::numeric_limits<base_result>::is_specialized.  Exception safety
    would also be unclear, if types like IntType and RealType were 
    classes.
  - Probably a compile time assertion should be a boost-library.  A first
    version (compiling with gcc 2.95.2) could look like one of the following
    two variants. Maybe, someone has an even better trick.
  

---------------------------------------------------- compile time asserts
// This detects compile time errors at run time.
template<bool Truth>
struct Dispatch_type_ {};

inline void compiletime_assert(Dispatch_type_<true>) 
{
}

inline void compiletime_assert(Dispatch_type_<false> ) 
{
  throw "Compile Time Assertion";
}

template <bool b>
inline void ct_assert() 
{
  compiletime_assert(Dispatch_type_<b>());
}

int main() 
{
  const bool disp = std::numeric_limits<int>::is_integer;
  ct_assert<disp>();
  exit(0);
}
------------------------------------------------------------
Alternatively: the following does not compile, if the
assert fails, but with a strange error message:
------------------------------------------------------------
template<bool Truth>
struct ct_assert {};

template<>
struct ct_assert<true> 
{};

template<>
struct ct_assert<false>
{
private:
  ct_assert();
};

int main() 
{
  const bool disp = std::numeric_limits<int>::is_integer;;
  ct_assert<disp>();
  exit(0);
}
------------------------------------------------------------

Have a nice day...
     Thomas