Re: [Mingw-w64-public] problem with <random>'s uniform_int?

[Jim M. <jmi...@ya...>]

4.7.0 20111127





>________________________________
> From: Ruben Van Boxem <van...@gm...>
>To: min...@li... 
>Sent: Wednesday, March 14, 2012 1:09 AM
>Subject: Re: [Mingw-w64-public] problem with <random>'s uniform_int?
> 
>
>Op 14 mrt. 2012 09:00 schreef "Jim Michaels" <jmi...@ya...> het volgende:
>>
>> this is not about rand_s.
>> I am using mt19937 from <random>.  this is mersenne twister random number number generator, entirely different, much more random, has a *far longer* (like 10^604 or 2^604 or something like that) sequence and more complicated.
>>
>> anyway, my point *wasn't* about the random number generator - you missed the point - I even put the point of the problem in the Abstract so people would have a clue.
>>
>> I was pointing out that the output range of uniform_int is severely crippled.  it stays in the upper end of the data type instead of spreading/distributing the input evenly across the range of min0 to max0, which are specified in the arguments of uniform_int's constructor.
>>
>> that *IS* what uniform_int is supposed to do isn't it?  I assume I read http://en.wikipedia.org/wiki/Uniform_distribution_%28discrete%29
>> correctly...
>What GCC version? Does the same happen with std::uniform_int_distribution with -std=c++0x?
>Using tr1 now is stupid btw, every decent compiler and library have these things in the std namespace where they belong.
>Ruben
>>
>>
>>> ________________________________
>>> From: Kai Tietz <kti...@go...>
>>> To: min...@li... 
>>> Sent: Wednesday, March 14, 2012 12:13 AM
>>> Subject: Re: [Mingw-w64-public] problem with <random>'s uniform_int?
>>>
>>> 2012/3/14 Jim Michaels <jmi...@ya...>:
>>> > /*
>>> > Author: Jim Michaels
>>> > Creation Date: 3/13/2012
>>> > Current Date: 3/13/2012
>>> > Abstract: Shows what I think is a bug in <random>'s uniform_int
>>> >     distribution where the mt19937 random number generator I am
>>> >     feeding through it has its numbers concentrated around the
>>> >     upper portion of the range rather than spread out across the
>>> >     entire range of the data type. Am I not undertsanding what
>>> >     uniform_int is supposed to do? or is it not supposed to
>>> >     produce discrete statistical uniform distributions?
>>> > */
>>> >
>>> >
>>> >
>>> > #include <tr1/random>
>>> > #include <tr1/stdint.h>
>>> > #include <iostream>
>>> > using namespace std;
>>> >
>>> > std::tr1::mt19937 gen;//mersenne twister random number generator
>>> > #if defined(__MINGW32__)||defined(_MSC_VER)||defined(__BORLANDC__)
>>> > std::tr1::uniform_int<> u(0ULL, 0xffffffffffffffffULL);
>>> > #else
>>> > std::tr1::uniform_int<> u(0Ui64, 0xffffffffffffffffUi64);
>>> > #endif
>>> >
>>> > inline uint64_t random(void) {
>>> >     return u(gen);
>>> > }
>>> >
>>> > int main(void) {
>>> >     int x;
>>> >     bool isFirst=true;
>>> >     uint64_t mn=0,mx=0,cur=0;
>>> >     for (x=0; x < 100; x++) {
>>> >         cout.fill('0');
>>> >         cout.width(20);
>>> >         cur=random();
>>> >         if (isFirst) {
>>> >             mn=cur;
>>> >             mx=cur;
>>> >             isFirst=false;
>>> >         }
>>> >         cout<<cur<<endl;
>>> >         if (cur>mx) mx=cur;
>>> >         if (cur<mn) mn=cur;
>>> >     }
>>> >     cout<<endl<<"min=";
>>> >     cout.fill('0');
>>> >     cout.width(20);
>>> >     cout<<mn<<"\nmax=";
>>> >     cout.fill('0');
>>> >     cout.width(20);
>>> >     cout<<mx<<"\ndifference=";
>>> >     cout.fill('0');
>>> >     cout.width(20);
>>> >     cout<<mx-mn<<endl;
>>> >     return 0;
>>> > }
>>> > //problem: this hovers way too long around
>>> > /*
>>> > sample output:
>>> > 18446744072913795932
>>> > 18446744073304931054
>>> > 18446744073000918905
>>> > 18446744073575839711
>>> > 18446744073337503749
>>> > 18446744072130546618
>>> > 18446744071764878885
>>> > 18446744071763422559
>>> > 18446744073678977040
>>> > 18446744073527044839
>>> > 18446744073694353124
>>> > 18446744073558749017
>>> > 18446744073570802426
>>> > 18446744072532038929
>>> > 18446744073583248563
>>> > 18446744073628418359
>>> > 18446744073525585066
>>> > 18446744072842422873
>>> > 18446744072851762780
>>> > 18446744073347638446
>>> > 18446744072162347015
>>> > 18446744072817088873
>>> > 18446744073187415213
>>> > 18446744073535572907
>>> > 18446744071577799048
>>> > 18446744072230969164
>>> > 18446744072841661626
>>> > 18446744073061566917
>>> > 18446744073426054765
>>> > 18446744072341001254
>>> > 18446744072329729627
>>> > 18446744072669053378
>>> > 18446744072595640013
>>> > 18446744072606313980
>>> > 18446744072229840436
>>> > 18446744072447029159
>>> > 18446744072838875481
>>> > 18446744073161637570
>>> > 18446744073684075993
>>> > 1844674407295130874 5
>>> > 18446744072944631962
>>> > 18446744072398850529
>>> > 18446744072694865646
>>> > 18446744073495756929
>>> > 18446744072264748328
>>> > 18446744072702453906
>>> > 18446744072829941902
>>> > 18446744072190477567
>>> > 18446744072824680856
>>> > 18446744072461283062
>>> > 18446744073369711431
>>> > 18446744072655938920
>>> > 18446744072882903664
>>> > 18446744072445861649
>>> > 18446744072333885098
>>> > 18446744072228208822
>>> > 18446744072467034220
>>> > 18446744072180375568
>>> > 18446744072738533078
>>> > 18446744073536653217
>>> > 18446744071878841848
>>> > 18446744073180228744
>>> > 18446744071928290152
>>> > 18446744072885671619
>>> > 18446744072641251774
>>> > 18446744072941808995
>>> > 18446744072940068643
>>> > 18446744071587653283
>>> > 18446744073452171529
>>> > 18446744072417095975
>>> > 18446744073240984662
>>> > 18446744073534709601
>>> > 18446744071909774250
>>> > 18446744071764857140
>>> > 18446744072686194971
>>> > 18446744072892367725
>>> > 18446744073025437414
>>> > 18446744073660252266
>>> > 18446744072911911023
>>> > 18446744073405741205
>>> > 18 446744073311686108
>>> > 18446744073058725738
>>> > 18446744073516353565
>>> > 18446744072060476037
>>> > 18446744072759924511
>>> > 18446744073655691123
>>> > 18446744072982966111
>>> > 18446744072823059978
>>> > 18446744071928274454
>>> > 18446744071967957672
>>> > 18446744071775629235
>>> > 18446744072561930879
>>> > 18446744073353901113
>>> > 18446744072400586818
>>> > 18446744072334388088
>>> > 18446744072666734544
>>> > 18446744072651826116
>>> > 18446744071826455169
>>> > 18446744071853359699
>>> > 18446744071679627487
>>> >
>>> > min=18446744071577799048
>>> > max=18446744073694353124
>>> > difference=00000000002116554076
>>> > */
>>> >
>>> >
>>> > -------------
>>> > Jim Michaels
>>>
>>> Hello Jim,
>>>
>>> This random-number generation is based on value-range of rand (gcc
>>> doesn't use here rand_s which would provide better random-values).
>>> Its range for random-numbers is in range of 0-0x7fff (which your test
>>> explicit proves, as C++'s random-implementation expands range by
>>> another 16-bits).
>>>
>>> So the issue isn't in <random> implementation, but in the limited
>>> range of random-number generation by msvcrt's rand() function.
>>>
>>> By looking more detailed into this you can find that MS' rand function
>>> is using here a linear congruential scheme. The function is
>>> multiplying and adding to a number, which is taken module 2^32, and
>>> returning the upper 16 bit modulo 2^15 as "random" number.
>>> Because it is multiplying and adding numbers, which are coprime to the
>>> modulus, this creates a sort of uniformaly distributed numbers.
>>> Base function is a linear function f(x) = ((x * prime-1) + prime-2) % 2^32.
>>> The final result is (f(x) >> 16) & 0x7fff;
>>> The prime-1 is 214013, and the prime-2 is 2531011.
>>>
>>> Regards,
>>> Kai
>>>
>>> ------------------------------------------------------------------------------
>>> Virtualization & Cloud Management Using Capacity Planning
>>> Cloud computing makes use of virtualization - but cloud computing 
>>> also focuses on allowing computing to be delivered as a service.
>>> http://www.accelacomm.com/jaw/sfnl/114/51521223/
>>> _______________________________________________
>>> Mingw-w64-public mailing list
>>> Min...@li...
>>> https://lists.sourceforge.net/lists/listinfo/mingw-w64-public
>>>
>>>
>>
>> ------------------------------------------------------------------------------
>> Virtualization & Cloud Management Using Capacity Planning
>> Cloud computing makes use of virtualization - but cloud computing
>> also focuses on allowing computing to be delivered as a service.
>> http://www.accelacomm.com/jaw/sfnl/114/51521223/
>> _______________________________________________
>> Mingw-w64-public mailing list
>> Min...@li...
>> https://lists.sourceforge.net/lists/listinfo/mingw-w64-public
>>
>------------------------------------------------------------------------------
>Virtualization & Cloud Management Using Capacity Planning
>Cloud computing makes use of virtualization - but cloud computing 
>also focuses on allowing computing to be delivered as a service.
>http://www.accelacomm.com/jaw/sfnl/114/51521223/
>_______________________________________________
>Mingw-w64-public mailing list
>Min...@li...
>https://lists.sourceforge.net/lists/listinfo/mingw-w64-public
>
>
>