[prev in list] [next in list] [prev in thread] [next in thread]
List: kde-core-devel
Subject: Re: Review Request: Convenience KRandom methods
From: Thomas_Lübking <thomas.luebking () web ! de>
Date: 2010-08-13 20:53:23
Message-ID: 20100813205323.22336.33868 () vidsolbach ! de
[Download RAW message or body]
> 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.
> 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.
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 ;-)
- Thomas
-----------------------------------------------------------
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
>
>
[Attachment #3 (text/html)]
<html>
<body>
<div style="font-family: Verdana, Arial, Helvetica, Sans-Serif;">
<table bgcolor="#f9f3c9" width="100%" cellpadding="8" style="border: 1px #c9c399 \
solid;"> <tr>
<td>
This is an automatically generated e-mail. To reply, visit:
<a href="http://reviewboard.kde.org/r/4992/">http://reviewboard.kde.org/r/4992/</a>
</td>
</tr>
</table>
<br />
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: \
10px;"> <p style="margin-top: 0;">On August 13th, 2010, 11:03 a.m., <b>Ivan \
Cukic</b> wrote:</p> <blockquote style="margin-left: 1em; border-left: 2px solid \
#d0d0d0; padding-left: 10px;">
<table width="100%" border="0" bgcolor="white" style="border: 1px solid #C0C0C0; \
border-collapse: collapse; margin: 2px padding: 2px;"> <thead>
<tr>
<th colspan="4" bgcolor="#F0F0F0" style="border-bottom: 1px solid #C0C0C0; \
font-size: 9pt; padding: 4px 8px; text-align: left;"> <a \
href="/r/4992/diff/3/?file=33701#file33701line55" style="color: black; font-weight: \
bold; text-decoration: underline;">trunk/KDE/kdelibs/kdecore/util/krandom.cpp</a> \
<span style="font-weight: normal;">
(Diff revision 3)
</span>
</th>
</tr>
</thead>
<tbody style="background-color: #e4d9cb; padding: 4px 8px; text-align: center;">
<tr>
<td colspan="2"><pre style="font-size: 8pt; line-height: 140%; margin: 0; \
"></pre></td> <td colspan="2"><pre style="font-size: 8pt; line-height: 140%; margin: \
0; ">int KRandom::random( int min, int max )</pre></td>
</tr>
</tbody>
<tbody>
<tr>
<th bgcolor="#b1ebb0" style="border-right: 1px solid #C0C0C0;" \
align="right"><font size="2"></font></th> <td bgcolor="#c5ffc4" width="50%"><pre \
style="font-size: 8pt; line-height: 140%; margin: 0; "></pre></td> <th \
bgcolor="#b1ebb0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid \
#C0C0C0;" align="right"><font size="2">55</font></th> <td bgcolor="#c5ffc4" \
width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "> <span \
class="k">return</span><span class="p">(</span> <span class="n">random</span><span \
class="p">()</span> <span class="o">%</span> <span class="p">(</span><span \
class="n">max</span><span class="o">-</span><span class="n">min</span><span \
class="o">+</span><span class="mi">1</span><span class="p">)</span> <span \
class="o">+</span> <span class="n">min</span> <span class="p">);</span></pre></td> \
</tr>
</tbody>
</table>
<pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: \
-pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">As far as the % goes, \
I'd say it is ok (apart from previous comments)</pre> </blockquote>
<p>On August 13th, 2010, 11:06 a.m., <b>Ivan Cukic</b> wrote:</p>
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: \
10px;"> <pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: \
-pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">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</pre>
</blockquote>
<p>On August 13th, 2010, 11:28 a.m., <b>Christoph Feck</b> wrote:</p>
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: \
10px;"> <pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: \
-pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">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.</pre> </blockquote>
<p>On August 13th, 2010, 6:41 p.m., <b>Ingo Klöcker</b> wrote:</p>
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: \
10px;"> <pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: \
-pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">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.</pre> </blockquote>
<p>On August 13th, 2010, 7:27 p.m., <b>Thomas Lübking</b> wrote:</p>
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: \
10px;"> <pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: \
-pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">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.</pre> </blockquote>
</blockquote>
<pre style="margin-left: 1em; white-space: pre-wrap; white-space: -moz-pre-wrap; \
white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">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 ;-)</pre> <br />
<p>- Thomas</p>
<br />
<p>On August 12th, 2010, 1:40 p.m., Sebastian Trueg wrote:</p>
<table bgcolor="#fefadf" width="100%" cellspacing="0" cellpadding="8" \
style="background-image: \
url('http://reviewboard.kde.orgrb/images/review_request_box_top_bg.png'); \
background-position: left top; background-repeat: repeat-x; border: 1px black \
solid;"> <tr>
<td>
<div>Review request for kdelibs.</div>
<div>By Sebastian Trueg.</div>
<p style="color: grey;"><i>Updated 2010-08-12 13:40:52</i></p>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Description </h1>
<table width="100%" bgcolor="#ffffff" cellspacing="0" cellpadding="10" style="border: \
1px solid #b8b5a0"> <tr>
<td>
<pre style="margin: 0; padding: 0; white-space: pre-wrap; white-space: \
-moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: \
break-word;">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. :)</pre> </td>
</tr>
</table>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Diffs</b> </h1>
<ul style="margin-left: 3em; padding-left: 0;">
<li>trunk/KDE/kdelibs/kdecore/util/krandom.h <span style="color: \
grey">(1162164)</span></li>
<li>trunk/KDE/kdelibs/kdecore/util/krandom.cpp <span style="color: \
grey">(1162164)</span></li>
</ul>
<p><a href="http://reviewboard.kde.org/r/4992/diff/" style="margin-left: 3em;">View \
Diff</a></p>
</td>
</tr>
</table>
</div>
</body>
</html>
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic