Review Request: Convenience KRandom methods
Sebastian Trueg
trueg at kde.org
Wed Aug 18 13:59:53 BST 2010
> On 2010-08-13 11:03:31, Ivan Cukic wrote:
> > trunk/KDE/kdelibs/kdecore/util/krandom.cpp, line 55
> > <http://reviewboard.kde.org/r/4992/diff/3/?file=33701#file33701line55>
> >
> > As far as the % goes, I'd say it is ok (apart from previous comments)
>
> Ivan Cukic wrote:
> My mistake, it is not :)
>
> Imagine the following:
> random() gives from 0 to 10
> min = 0
> max = 7
>
> this function would give priority to 0 1 and 2
> 0 1 2 3 4 5 6 7 8 9 10
> ______________________
> 0 1 2 3 4 5 6 7 0 1 2
>
> Christoph Feck wrote:
> In other words, there cannot exist any mapping from a uniform random integer distribution in the range [a,b] to a different integer range [d,e] resulting in a uniform distribution.
>
> Since even floats have limited precision in a computer, you cannot solve the problem mathematically correct anyway.
>
> Ivan Cukic wrote:
> Mapping no, but the following should be mathematically correct (c-like pseudo code - didn't try to compile):
>
> int range = max - min + 1;
> int timesInPool = RAND_MAX / range;
>
> int value;
>
> while ((value = random()) >= timesInPool) {
> }
>
> value %= range;
>
> The standard example is to use
> while (value > range) ...
> but that is rather inefficient, especially for smaller ranges.
>
> Theoretically, the above could end up in an endless loop, but with probability = 0. The worst case scenarion would be to have the range of RAND_MAX / 2 + 1.
>
> Anyhow, a limit to number of whiles can be added just in case. The uniformity grows with exponent (I think) of the defined limit.
>
>
> Ingo Klöcker wrote:
> You can solve this problem correctly. Here is a trivial (but terribly inefficient) solution which works for any 0 <= min <= max <= RAND_MAX:
>
> int KRandom::random( int min, int max )
> {
> while ( true ) {
> const int r = random();
> if ( min <= r && r <= max )
> return r;
> }
> }
>
> Making this method work for any ints with max <= min + RAND_MAX (e.g. for min = -1 and max = 1) and more efficiently by throwing away at most max - min values in the range [0,RAND_MAX] is left as an exercise for the reader.
>
> Thomas Lübking wrote:
> That's not necessary.
> Sure: Ivans exmple looks horrible, but random() returns (ideally, the random generator ain't perfect as well) even distributed numbers across the (positive) long range (0-2**31-1 according to posix requirements)
>
> so in worst case (max-min)/2 numbers would be biased by.00000000046566128752 == 1/(2**31-1)
> (0,1&2 have a probability of 2/11 compared to 1/11 of the rest in the example, for 12 base numbers 0,1,2&3 would be biased by 1/12 since they appear by 2/12 instead of 1/12)
> - Sorry, i must I must confess that i've no ida about proper english terms on this - bash me if they make no sense ;-)
>
> You can however pretty safely assume that this imprecision is shadowed by the general random generator weakness.
>
> If it's _really_ a problem you'd kick the overweightened values (preknown) by a chance of 1/(2**31-1) (ie. random() == n, you can pick your birthdate for n, it doesn't matter) and try again.
>
> Thomas Lübking wrote:
> errr... "me" == "brain dead" == "bread"
> you'd kick them in (max-min-1)/(2**31-1) of all cases, ie. if min <= random() <= max
> (yes - it is f*** confusing, tststs ;-)
To be honest: this is all a bit much for a small method in kdelibs. At this point I change my opinion to: use boost or nothing or an ugly fallback. Thus, the question changes to: how about an optional dependency on boost?
- Sebastian
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
http://reviewboard.kde.org/r/4992/#review7029
-----------------------------------------------------------
On 2010-08-12 13:40:52, Sebastian Trueg wrote:
>
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> http://reviewboard.kde.org/r/4992/
> -----------------------------------------------------------
>
> (Updated 2010-08-12 13:40:52)
>
>
> Review request for kdelibs.
>
>
> Summary
> -------
>
> The KRandom namespace is quite useful. However, applications need to be full of code snippets that calculate a random number in a range. IMHO it makes perfect sense to do this once in the library. Thus, I am proposing this patch to introduce two methods providing random numbers from a range.
> Feel free to improve the implementation. :)
>
>
> Diffs
> -----
>
> trunk/KDE/kdelibs/kdecore/util/krandom.h 1162164
> trunk/KDE/kdelibs/kdecore/util/krandom.cpp 1162164
>
> Diff: http://reviewboard.kde.org/r/4992/diff
>
>
> Testing
> -------
>
>
> Thanks,
>
> Sebastian
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.kde.org/pipermail/kde-core-devel/attachments/20100818/f8452538/attachment.htm>
More information about the kde-core-devel
mailing list