📄 rand.20000223.html
字号:
<html><!-- Mirrored from c-faq.com/lib/rand.20000223.html by HTTrack Website Copier/3.x [XR&CO'2008], Sat, 14 Mar 2009 08:03:00 GMT --><head><title></title></head><body>[This is a reply from meto a correspondent of minewho had asked about some of the expressionsin the answer to <a href="randrange.html">question 13.16</a> in the FAQ list.I have edited the text slightly for this web page.]<p>Date: Wed, 23 Feb 2000 07:08:14 -0800 (PST)<br>Message-Id: <200002231508.HAA07282@mail.eskimo.com><br>Subject: Re: C FAQ error?<p>The water is surprisingly deep here. I was initially ratheralarmed by your note, because after rummaging around for some ofmy old random number testbeds and dusting them off, I found thatthe expression<pre> rand() / (RAND_MAX/N + 1)</pre>from the FAQ list doesn't behave as well as I expected it to.When I then attempted to rederive the appropriate expression,my first attempt led to<pre> rand() / ((RAND_MAX + 1) / N)</pre>which is exactly what you suggested. But it turns out that thelatter expression doesn't work in the general case. Supposethat <TT>RAND_MAX</TT> is 21 and <TT>N</TT> is 10. (As it happens, this was thefirst example I tried.) So <TT>((RAND_MAX + 1) / N)</TT> is then 2, andwhen <TT>rand()</TT> returns 20 or 21, the value of the expression is 10,which is not in [0, <TT>N</TT>).<p>I want to study your... derivation some more,because I think it's basically sound, for the ``|<TT>RAND_MAX</TT>+1| is aprecise multiple of |<TT>N</TT>|'' case. I suspect that the flaw, however,is in your assumption that if <TT>RAND_MAX</TT>+1 is not a multiple of <TT>N</TT>,the same logic applies. You have to make sure that the resultfalls the right way when the intermediate quotient discards anonzero remainder, and for this expression, it doesn't.<p>Unfortunately, I don't immediately remember how I originallyderived the expression<pre> rand() / (RAND_MAX/N + 1)</pre>I share your unease about its dissimilarity to the (much cleaner)floating-point version<pre> rand() / (RAND_MAX + 1.0) * N</pre>I do remember testing the expressions in the FAQ list quitethoroughly, and I've found <a href="rand.931117.html">an article</a> I posted long ago whichdiscusses them in some detail, and which suggests that I putquite a bit of time into that initial derivation. (It alsosuggests that I wasn't perfectly happy with the expression then,either.) That article, as I read it now, is nowhere as clearas I'd like, and I was about to be at a loss to explain how<pre> rand() / (RAND_MAX/N + 1)</pre>works at all, until I discovered that the expression isessentially the same one I explain in the answer to exercise 8at <a href="http://www.eskimo.com/~scs/cclass/asgn.beg/PS3a.html">http://www.eskimo.com/~scs/cclass/asgn.beg/PS3a.html</a>, whichis worth reading. (I must confess, though, that I can't imaginewhat I was thinking when I started throwing that much detailaround in the third week of an allegedly beginning programmingclass.) But going back to the <TT>RAND_MAX</TT>=21, <TT>N</TT>=10 case, it turnsout that dividing <TT>rand()</TT> by 3, such that we never emit 8 or 9 atall, is about the best we can do; what we're seeing is one of theways that any of these expressions begins to fail when <TT>RAND_MAX</TT>+1is neither a multiple of nor much greater than <TT>N</TT>.<p>For my own reference, here's another way of deriving theexpression <TT>rand() / ((RAND_MAX + 1) / N)</TT>, even though thatexpression doesn't work. We want to divide <TT>rand</TT>'s output bysome integer y such that the answer is always in the range0 <= <TT>rand()</TT>/y < <TT>N</TT>. Now when rand returns <TT>RAND_MAX</TT>, the result<TT>RAND_MAX</TT>/y should be just barely less than <TT>N</TT>; one way ofachieving this would be if it were the case that (<TT>RAND_MAX</TT>+1)/ydid equal <TT>N</TT>. So if we set (<TT>RAND_MAX</TT>+1)/y = <TT>N</TT>, we can easilysolve for y = (<TT>RAND_MAX</TT>+1)/<TT>N</TT>.<p>But wait! If we want <TT>RAND_MAX</TT>/y to be just barely less than <TT>N</TT>,the other way to achieve it is to subtract 1 in the denominator.So if <TT>RAND_MAX</TT>/(y-1) = <TT>N</TT>, we have y = <TT>RAND_MAX</TT>/<TT>N</TT> + 1, and thismust be where the expression in the FAQ list comes from, afterall.</body><!-- Mirrored from c-faq.com/lib/rand.20000223.html by HTTrack Website Copier/3.x [XR&CO'2008], Sat, 14 Mar 2009 08:03:00 GMT --></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -