[Bug libstdc++/33815] tr1::uniform_int isn't uniform

[pcarlini at suse dot de]

------- Comment #14 from pcarlini at suse dot de  2007-10-21 11:33 -------
(In reply to comment #13)
> Sure thing.

Excellent.

> I will need a little bit of time to familiarize myself with the current code.
> Also, I will need a little bit of help in finding my way around. E.g., where do
> the test-cases for tr1/random go?

Well in testsuite/tr1/5_numerical_facilities/random, no?

Do you have at hand the specifications? Would be N1836 for TR1 and the last
working paper N2369 for C++0x. Everything from:

 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/

Frankly, I would suggest concentrating more on the C++0x specifications, for
the future: the random facilities will be rather different in C++0x! In TR1
some bits were simply broken in the design, like the idea of variate_generator,
which doesn't exist anymore in C++0x. For TR1 we have to live with that.

> Finally, I will need a little bit of guidance with regard to the process of
> submitting patches. Is there a web-page for first-timers that describes the
> submission process?

Of course you have to read:

  http://gcc.gnu.org/contribute.html

Otherwise, have a look to the patches posted on gcc-patches@ and libstdc++@.
But really, here we care about the algorithm, I can take care of the minor
issues.

Anyway, the MOST important thing at this stage is the Copyright Assignment!
Yours' in any case would be a non-trivial contribution, we need it. Please
start on that as soon as possible, it takes a lot of time. Again, see the above
link. In practice, you should now request the form to assignments@gnu.org.

Finally (I will be disconnected for some days), wanted to mention that, for the
present, I'm thinking about a relatively small change similar to what GSL is
doing (and your idea, I think, but I didn't really read it because I don't want
to plagiarize before your Assignment is in place and then proper credits):

Index: random
===================================================================
--- random      (revision 129509)
+++ random      (working copy)
@@ -1603,17 +1603,7 @@
       template<typename _UniformRandomNumberGenerator>
         result_type
         _M_call(_UniformRandomNumberGenerator& __urng,
-               result_type __min, result_type __max, true_type)
-        {
-         // XXX Must be fixed to also work when __urng.max() - __urng.min()
-         // is smaller than __max - __min.
-         typedef typename __gnu_cxx::__add_unsigned<typename
-           _UniformRandomNumberGenerator::result_type>::__type __utype;
-         return result_type((__max - __min + 1.0L)
-                            * (__utype(__urng()) - __utype(__urng.min()))
-                            / (__utype(__urng.max())
-                               - __utype(__urng.min()) + 1.0L)) + __min;
-       }
+               result_type __min, result_type __max, true_type);

       template<typename _UniformRandomNumberGenerator>
         result_type
Index: random.tcc
===================================================================
--- random.tcc  (revision 129509)
+++ random.tcc  (working copy)
@@ -750,6 +750,31 @@
     }


+  template<typename _IntType>
+    template<typename _UniformRandomNumberGenerator>
+      typename uniform_int<_IntType>::result_type
+      uniform_int<_IntType>::
+      _M_call(_UniformRandomNumberGenerator& __urng,
+             result_type __min, result_type __max, true_type)
+      {
+       // XXX Must be fixed to also work when __urng.max() - __urng.min()
+       // is smaller than __max - __min.
+       typedef typename __gnu_cxx::__add_unsigned<typename
+         _UniformRandomNumberGenerator::result_type>::__type __utype;
+
+       result_type __ret;
+
+       __utype __umin = __urng.min();
+       __utype __umax = __urng.max();
+       __utype __denom = (__umax - __umin) / (__max - __min + 1);
+
+       do
+         __ret = (__utype(__urng()) -  __umin) / __denom;
+       while (__ret > __max - __min);
+
+       return __ret + __min;
+      }
+
   template<typename _IntType, typename _CharT, typename _Traits>
     std::basic_ostream<_CharT, _Traits>&
     operator<<(std::basic_ostream<_CharT, _Traits>& __os,


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33815