the equation I use successfully (you examine and tell me if you think this
works correctly) is
if the arguments to uniform_int's constructor are source_type __min and
source_type __max:
return
__uctype(__urng()*(int64_t(__max)-int64_t(__min))/__urng.max()-_urng.min()+uint64_t(__min));
or
return __uctype(__urng()*__urange/__urng.max()-_urng.min()+uint64_t(__min));
what the calculation is doing is that __urng() is going to hit its maximum
__urng.max() so the goal is to somehow use a ratio of
(__max-__min)*__urng()/__urng.max() (without dropping bits, this requires
converting to a LARGER data type). so you have to arrange and sequence the
equation so that the division is not the first thing you do, thereby getting a
result of 0 always because of integer division. so the ratio should not come
first, but last. the rest is getting rid of offsets. the -_urng.min() puts
the equation basis/offset at 0, and lastly,we must add the argument __min to
make the range fit properly (we have already established a proper ratio).
in place of the uint64_t you should put something equally large, an integer, it
could be best signed but I suppose that depends upon whether or not the
destination_type (Int_type) is signed or not, you want the capability to handle
the maximum size that an integer can handle, so you should choose the
appropriate int64_t or uint64_t depending on whether Int64_type is signed or
not. A double will simply convert this int64_t/uint64_t type to something with
decimal points and precision is lost.
the difference in range for losing 1 upper bit for signed/unsigned in int64_t
vs. uint64_t by defaulting only to signed only results in loss of range of
9,223,372,036,854,775,808..18,446,744,073,709,551,615 which is huge.
you can always scale down if you do it properly using a conversion like
__uctype(num) or uint
I don't remember quite how to find out the MAXINT of a given type, but I think
it's listed in the .tcc in
c:\mingw-w32-bin_i686-mingw_20111127\mingw/include/c++/4.7.0/tr1/random.h
c:\mingw-w32-bin_i686-mingw_20111127\mingw/include/c++/4.7.0/tr1/random.tcc
current implementation for uniform_int is (partially)
const __urntype __urnmin = __urng.min();
const __urntype __urnmax = __urng.max();
const __urntype __urnrange = __urnmax - __urnmin;
const __uctype __urange = __max - __min;
const __uctype __udenom = (__urnrange <= __urange
? 1 : __urnrange / (__urange + 1));
do
__ret = (__urntype(__urng()) - __urnmin) / __udenom;
while (__ret > __max - __min);
return __ret + __min;
}
>________________________________
> From: Jim Michaels <[email protected]>
>To: "[email protected]"
><[email protected]>
>Sent: Wednesday, March 14, 2012 4:23 PM
>Subject: Re: [Mingw-w64-public] problem with <random>'s uniform_int?
>
>
>
>4.7.0 20111127
>
>
>
>
>
>>________________________________
>> From: Ruben Van Boxem <[email protected]>
>>To: [email protected]
>>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" <[email protected]> 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 <[email protected]>
>>>> To: [email protected]
>>>> Sent: Wednesday, March 14, 2012 12:13 AM
>>>> Subject: Re: [Mingw-w64-public] problem with <random>'s uniform_int?
>>>>
>>>> 2012/3/14 Jim Michaels <[email protected]>:
>>>> > /*
>>>> > 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
>>>> [email protected]
>>>> 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
>>> [email protected]
>>> 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
>>[email protected]
>>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
>[email protected]
>https://lists.sourceforge.net/lists/listinfo/mingw-w64-public
>
>
>------------------------------------------------------------------------------
This SF email is sponsosred by:
Try Windows Azure free for 90 days Click Here
http://p.sf.net/sfu/sfd2d-msazure
_______________________________________________
Mingw-w64-public mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/mingw-w64-public
