随机整数程序：批判？ [英] Random integer program: critique?
问题描述
我需要一个名为随机的快速程序从n1到n2给出一个随机的
正整数。例如，如果我输入
" random 38,43"，我希望程序打印一个随机成员
的集合{38,39,40,41 ，42,43}。
另外，我在编译器的文档中读到以下内容：
获取随机数范围0..N，使用rand（）％（N + 1）。
注意rand'的返回值的低位不是
非常随机，所以rand（）％N对于N的小值可能不是随机的
。替代但非ANSI的功能
" random（）"如果N很小，则更好。参见random（）。
打击最低有效位并非随机。问题，
而不是使用非ANSI函数，我使用了rand（），但我丢弃了4个最低有效位并将剩余的4位移位到
正确。
所以我写了以下内容，这似乎有效，但也许有办法
这可能待改进：
#include< stdio.h>
#include< stdlib.h>
#include< ; time.h>
int main（int argc，char * argv []）
{
int LoNum = 0 ;
int HiNum = 0;
int Span = 0;
int RnNum = 0;
int Shifted = 0;
int输出= 0;
/ *随机时间对随机数生成器播种：* /
srand（时间（0））;
/ *得到低和高数字：* /
LoNum = atoi（argv [1]）;
HiNum = atoi（argv [2]）;
/ *获取范围（添加一个以避免fencepost错误）：* /
Span = HiNum - LoNum + 1;
/ *获取0到2147483647之间的随机数：* /
RnNum = rand（）;
/ * Shift RnNum向右4位：* /
Shifted = RnNum> 4;
/ *设置输出为（LoNum plus （移位模数跨度））：* /
输出= LoNum +移位％跨度;
printf（"％d \ n"，输出） ;
返回0;
}
批评？评论？有问题吗？ Ewww，yucks？我确定有更好的方法可以做得更好。
我特别担心的是，如果我改变4号技术的话比特
在右边会引入任何非随机的倾斜。
-
干杯，
Robbie Hatley
lonewolf aatt well dott com
www dott well dott com slant user slant lonewolf slant
I needed a quick program called "random" that gives a random
positive integer from n1 to n2. For example, if I type
"random 38, 43", I want the program to print a random member
of the set {38, 39, 40, 41, 42, 43}.
Also, I read in my compiler''s documentation the following:
To get a random number in the range 0..N, use rand()%(N+1).
Note that the low bits of the rand''s return value are not
very random, so rand()%N for small values of N could be not
enough random. The alternative, but non-ANSI, function
"random()" is better if N is small. See "random()".
To combat the "least significant bits aren''t very random" problem,
instead of using a non-ANSI function, I used rand(), but I discarded
the 4 least significant bits and shifted the remaining bits 4 bits to
the right.
So I wrote the following, which seems to work, but maybe there''s ways
this could be improved:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(int argc, char *argv[])
{
int LoNum = 0;
int HiNum = 0;
int Span = 0;
int RnNum = 0;
int Shifted = 0;
int Output = 0;
/* Seed the random-number generator with the time: */
srand(time(0));
/* Get the low and high numbers: */
LoNum = atoi(argv[1]);
HiNum = atoi(argv[2]);
/* Get the span (add one to avoid fencepost error): */
Span = HiNum - LoNum + 1;
/* Get random number between 0 and 2147483647 inclusive: */
RnNum = rand();
/* Shift RnNum rightward 4 bits: */
Shifted = RnNum >4;
/* Set Output to (LoNum plus (Shifted modulo Span)): */
Output = LoNum + Shifted%Span;
printf("%d\n", Output);
return 0;
}
Critiques? Comments? Questions? "Ewww, yuck"s? I''m sure there''s
ways this could be done better.
I''m especially worried if my technique of shifting the number 4 bits
to the right is going to introduce any non-random skewing.
--
Cheers,
Robbie Hatley
lonewolf aatt well dott com
www dott well dott com slant user slant lonewolf slant
推荐答案
我从来没有见过这样做过，我会毫不犹豫地使用它。感觉
I''ve never seen it done that way, and I''d hesitate to use it. It feels
对我来说就像你只是在减少一个已经很小的来源或
伪随机性。
to me like you''re simply diminishing an already small source or
pseudo-randomness.
我同意。我怀疑这将是main（）的实现，所以
我假设你会把它原型化为：
unsigned int my_random （unsigned int，unsigned int）;
如果是这种情况，Martien提供的链接要好得多，而且b / b
saner方法。 br />
干杯，
--Tim
I would agree. I doubt that this will be main() in implementation, so
I''m assuming that you''ll prototype it like:
unsigned int my_random(unsigned int, unsigned int);
If that''s the case, the link provided by Martien is a much better and
saner approach.
Cheers,
--Tim
" Robbie Hatley" < lo ****** @ well.comwrites：
"Robbie Hatley" <lo******@well.comwrites:
Martien Verbruggen写道：
Martien Verbruggen wrote:
<剪断>
<snip>
>输出= LoNum +（int）（跨度*（rand（）/（RAND_MAX + 1.0）））;
>Output = LoNum + (int)(Span * (rand() / (RAND_MAX + 1.0)));
嗯。是的，我认为这会奏效。避免fencepost错误
和端点概率偏差。
Hmmm. Yes, I think that would work. Avoids fencepost errors
and endpoint probability skews.
我不确定你的意思是什么端点概率偏差但是如果
你指的是范围接近
（或者至少不是非常小于）RAND_MAX引起的问题值得指点
out是不可避免的。
I am not sure what you mean about "endpoint probability skews" but if
you are referring to the problems caused by the range being close to
(or at least not very much less than) RAND_MAX it is worth pointing
out that is does not avoid it.
涉及浮点
算术，但我的方法纯粹是积分。
Involves floating-point
arithmetic, though, whereas my method is purely integral.
值得指出的是，它并不能保证避免
fencepost错误。如果浮点实现很差
或RAND_MAX非常大，结果可能超出预期的
范围（一个）。我仍然会这样做，但是作为64位整数
变得普遍你必须注意（int）（跨度*（rand（）/（RAND_MAX
） + 1.0）））等于（而不是严格小于）Span。
< snip>
It is also worth pointing out that it does not guarantee to avoid
fencepost errors. If the floating point implementation is very poor
or RAND_MAX is very large, the result can be outside of the expected
range (by one). This is still how I would do it, but as 64 bit ints
become common you must watch out for (int)(Span * (rand() / (RAND_MAX
+ 1.0))) being equal to (rather than strictly less than) Span.
<snip>
这是实验性的转移，我不太确定，但是，b $ b。我今天才想到这一点。我想，如果
最低有效位是非随机的，则削减一些并且
使用其他而不是。
It''s the experimental bit-shifting thing I''m less sure of,
though. I just thought of that today. I figured, "if the
least significant bits are non-random, shave off a few and
use the others instead".
麻烦的是，你真的不知道其他比特是否更好。确实，一些非常简单的PRNG的问题在于底部位，但你不能确定某些实现没有
固定。这个算法只能通过n
位来解决这个问题。
如果rand（）不好你可以做的很少，除非你
确切地知道它是怎么回事。如果PRNG的质量对您的代码很重要，那么最简单的解决方案是使用您自己的算法
满足您的需求，但我敢打赌，几乎所有现代实现
现在包含一个合理的rand（）函数。
< snip test code>
The trouble is that you don''t really know that the other bits are any
better. It is true that the problem with some very simple PRNGs is in
the bottom bits but you can''t be sure that some implementation has not
"fixed" this with an algorithm that just moves the problem up by n
bits.
There is really very little you can do if rand() is bad unless you
know exactly how it is bad. If the quality of the PRNG matters to
your code, the simplest solution is to use your own algorithm that
meets your needs, but I''d bet that almost all modern implementations
now include a reasonable rand() function.
<snip test code>
相当不错。每个哈希桶的1000个/每个
项目的变化不会超过7％，并且接近钟形。
（我在复制后手动添加了X图表-n-pasting
来自节目输出的
。）
Pretty good. Never varies more than about 7% from 1000
items per hash bucket, and close to being bell-shaped.
(I added the "X" graph manually after copy-n-pasting
from program output.)
如果你想要的只是好的覆盖那么你不需要担心底部位的随机性
。重复以上步骤，没有
班次，并且你自己的PRNG非常糟糕，你会看到你得到
同样好的结果。如果底部的位置让你担心，你需要一个
测试来检测问题，以便你可以看到问题
在你做换班时消失了。
-
Ben。
If all you want is good "coverage" then you don''t need to worry about
the randomness of the bottom bits. Repeat the above, without the
shift, and with your own really bad PRNG and you will see you get
similarly "good" results. If the bottom bits worry you, you need a
test that detects the problem so that you can see that the problem
goes away when you do the shift.
--
Ben.
" Robbie Hatley" < lo ****** @ well.comwrites：
"Robbie Hatley" <lo******@well.comwrites:
/ *随机时间对随机数生成器播种：* /
srand（time（0））;
/* Seed the random-number generator with the time: */
srand(time(0));
作为警告，在许多实现中，时间（0）仅为精确到最接近的秒的
，所以如果你运行程序更多
比每秒一次（如果你有一个具有适当形式的命令历史记录的
shell，你甚至可以手动完成），你将获得
在该秒内两次都使用相同的种子。
您的实现可能有更准确的时钟可用
通过另一个接口，例如POSIX下的gettimeofday（）。
-
Ben Pfaff
http://benpfaff.org
这篇关于随机整数程序：批判？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
