int i;
do
{
i = 5 * (rand5() - 1) + rand5(); // i is now uniformly random between 1 and 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1; // result is now uniformly random between 1 and 7
那我们该怎么做呢?我们生成一个介于0和1之间的无限精确的随机实数(假装我们实际上可以计算并存储这样一个无限精确的数字 - 我们稍后会修复它) . 我们可以通过在基数5中生成其数字来生成这样的数字:我们选择随机数0. a 1 a 2 a 3 ...,其中每个数字ai通过调用 rand5() 来选择 . 例如,如果我们的RNG为所有 i 选择ai = 1,则忽略不是非常随机的事实,这将对应于实数1/5 1/52 1/53 ... = 1/4(几何系列的总和) .
好的,所以我们've picked a random real number between 0 and 1. I now claim that such a random number is uniformly distributed. Intuitively, this is easy to understand, since each digit was picked uniformly, and the number is infinitely precise. However, a formal proof of this is somewhat more involved, since now we'处理连续分布而不是离散分布,所以我们需要证明我们的数字位于区间[ a , b ]的概率等于该区间的长度 b - a . 证明留给读者练习=) .
int rand7() {
i = 5 * rand5() + rand5();
max = 25;
//i is uniform among {0 ... max-1}
while(i < max%7) {
//i is uniform among {0 ... (max%7 - 1)}
i *= 5;
i += rand5(); //i is uniform {0 ... (((max%7)*5) - 1)}
max %= 7;
max *= 5; //once again, i is uniform among {0 ... max-1}
}
return(i%7);
}
我们跟踪循环在变量 max 中可以产生的最大值 . 如果到目前为止reult在max%7和max-1之间,则结果将在该范围内均匀分布 . 如果没有,我们使用余数,它在0和最大%7-1之间是随机的,另一次调用rand()来产生一个新的数字和一个新的最大值 . 然后我们重新开始 .
public static int random_7() {
int returnValue = 0;
while (returnValue == 0) {
for (int i = 1; i <= 3; i++) {
returnValue = (returnValue << 1) + random_5_output_2();
}
}
return returnValue;
}
private static int random_5_output_2() {
while (true) {
int flip = random_5();
if (flip < 3) {
return 0;
}
else if (flip > 3) {
return 1;
}
}
}
19
int randbit( void )
{
while( 1 )
{
int r = rand5();
if( r <= 4 ) return(r & 1);
}
}
int randint( int nbits )
{
int result = 0;
while( nbits-- )
{
result = (result<<1) | randbit();
}
return( result );
}
int rand7( void )
{
while( 1 )
{
int r = randint( 3 ) + 1;
if( r <= 7 ) return( r );
}
}
import random
def rand5():
return random.randint(1, 5)
def rand7():
while True:
r = 5 * (rand5() - 1) + rand5()
#r is now uniformly random between 1 and 25
if (r <= 21):
break
#result is now uniformly random between 1 and 7
return r % 7 + 1
假设 rand(n) 这里的意思是“从 0 到 n-1 的均匀分布中的随机整数”,这里有's a code sample using Python'的randint,它具有这种效果 . 它仅使用 randint(5) 和常量来产生 randint(7) 的效果 . 实际上有点傻
from random import randint
sum = 7
while sum >= 7:
first = randint(0,5)
toadd = 9999
while toadd>1:
toadd = randint(0,5)
if toadd:
sum = first+5
else:
sum = first
assert 7>sum>=0
print sum
static struct rand_buffer {
unsigned v, count;
} buf2, buf3;
void push (struct rand_buffer *buf, unsigned n, unsigned v)
{
buf->v = buf->v * n + v;
++buf->count;
}
#define PUSH(n, v) push (&buf##n, n, v)
int rand16 (void)
{
int v = buf2.v & 0xf;
buf2.v >>= 4;
buf2.count -= 4;
return v;
}
int rand9 (void)
{
int v = buf3.v % 9;
buf3.v /= 9;
buf3.count -= 2;
return v;
}
int rand7 (void)
{
if (buf3.count >= 2) {
int v = rand9 ();
if (v < 7)
return v % 7 + 1;
PUSH (2, v - 7);
}
for (;;) {
if (buf2.count >= 4) {
int v = rand16 ();
if (v < 14) {
PUSH (2, v / 7);
return v % 7 + 1;
}
PUSH (2, v - 14);
}
// Get a number between 0 & 25
int v = 5 * (rand5 () - 1) + rand5 () - 1;
if (v < 21) {
PUSH (3, v / 7);
return v % 7 + 1;
}
v -= 21;
PUSH (2, v & 1);
PUSH (2, v >> 1);
}
}
unsigned rand5()
{
return rand() % 5;
}
unsigned rand7()
{
int r;
do
{
r = rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
} while (r > 15623);
return r / 2232;
}
int rand7(){
static int a=0;
static int e=0;
int r;
a = a * 5 + rand5();
e = e + 5; // added 5/7ths of a rand7 number
if ( e<7 ){
a = a * 5 + rand5();
e = e + 5; // another 5/7ths
}
r = a % 7;
e = e - 7; // removed a rand7 number
a = a % 7;
return r;
}
import random
x = []
for i in range (0,7):
x.append (0)
t = 0
tt = 0
for i in range (0,700000):
########################################
##### qq.py #####
r = int (random.random () * 5)
t = (t + r) % 7
########################################
##### qq_notsogood.py #####
#r = 20
#while r > 6:
#r = int (random.random () * 5)
#r = r + int (random.random () * 5)
#t = r
########################################
x[t] = x[t] + 1
tt = tt + 1
high = x[0]
low = x[0]
for i in range (0,7):
print "%d: %7d %.5f" % (i, x[i], 100.0 * x[i] / tt)
if x[i] < low:
low = x[i]
if x[i] > high:
high = x[i]
diff = high - low
print "Variation = %d (%.5f%%)" % (diff, 100.0 * diff / tt)
public class SevenFromFive
{
public SevenFromFive()
{
// this outputs a uniform ditribution but for some reason including it
// screws up the output distribution
// open question Why?
this.fifth = new ProbabilityCondensor(5, b => {});
this.eigth = new ProbabilityCondensor(8, AddEntropy);
}
private static Random r = new Random();
private static uint Rand5()
{
return (uint)r.Next(0,5);
}
private class ProbabilityCondensor
{
private readonly int samples;
private int counter;
private int store;
private readonly Action<bool> output;
public ProbabilityCondensor(int chanceOfTrueReciprocal,
Action<bool> output)
{
this.output = output;
this.samples = chanceOfTrueReciprocal - 1;
}
public void Add(bool bit)
{
this.counter++;
if (bit)
this.store++;
if (counter == samples)
{
bool? e;
if (store == 0)
e = false;
else if (store == 1)
e = true;
else
e = null;// discard for now
counter = 0;
store = 0;
if (e.HasValue)
output(e.Value);
}
}
}
ulong buffer = 0;
const ulong Mask = 7UL;
int bitsAvail = 0;
private readonly ProbabilityCondensor fifth;
private readonly ProbabilityCondensor eigth;
private void AddEntropy(bool bit)
{
buffer <<= 1;
if (bit)
buffer |= 1;
bitsAvail++;
}
private void AddTwoBitsEntropy(uint u)
{
buffer <<= 2;
buffer |= (u & 3UL);
bitsAvail += 2;
}
public uint Rand7()
{
uint selection;
do
{
while (bitsAvail < 3)
{
var x = Rand5();
if (x < 4)
{
// put the two low order bits straight in
AddTwoBitsEntropy(x);
fifth.Add(false);
}
else
{
fifth.Add(true);
}
}
// read 3 bits
selection = (uint)((buffer & Mask));
bitsAvail -= 3;
buffer >>= 3;
if (selection == 7)
eigth.Add(true);
else
eigth.Add(false);
}
while (selection == 7);
return selection;
}
}
import numpy
def rand1_5():
return numpy.random.randint(5)+1
def rand1_7():
q = 0
for i in xrange(7): q+= rand1_5()
return q%7 + 1
149
只需缩放第一个函数的输出
0) you have a number in range 1-5
1) subtract 1 to make it in range 0-4
2) multiply by (7-1)/(5-1) to make it in range 0-6
3) add 1 to increment the range: Now your result is in between 1-7
30 回答
这相当于亚当罗森菲尔德的解决方案,但对于一些读者可能会更清楚一些 . 它假设rand5()是一个返回1到5范围内的统计随机整数的函数 .
它是如何工作的?想象一下:想象一下在纸上打印出这个双维阵列,将它固定在飞镖板上并随意投掷飞镖 . 如果您达到非零值,则它是1到7之间的统计随机值,因为有相同数量的非零值可供选择 . 如果你达到零,只要继续投掷飞镖直到你达到非零 . 这就是这段代码的作用:i和j索引在飞镖板上随机选择一个位置,如果我们没有得到好的结果,我们就会继续投掷飞镖 .
就像亚当说的那样,在最坏的情况下,这可以永远运行,但从统计上来说,最糟糕的情况从未发生 . :)
没有(完全正确的)解决方案将在恒定的时间内运行,因为1/7是基数5中的无限小数 . 一个简单的解决方案是使用拒绝采样,例如:
这具有预期的25/21 = 1.19循环迭代的运行时间,但是永远循环的概率极小 .
除了my first answer之外,我还想添加另一个答案 . 此答案尝试最小化每次调用
rand7()
的rand5()
调用次数,以最大化随机性的使用 . 也就是说,如果你认为随机性是一种宝贵的资源,我们希望尽可能多地使用随机性,而不丢弃任何随机位 . 这个答案也与Ivan's answer中提出的逻辑有一些相似之处 .entropy of a random variable是一个明确定义的数量 . 对于具有相等概率(均匀分布)的N个状态的随机变量,熵是log2N . 因此,
rand5()
具有大约2.32193位的熵,并且rand7()
具有大约2.80735位的熵 . 如果我们希望最大化我们对随机性的使用,我们需要在每次调用rand5()
时使用所有2.32193位的熵,并将它们应用于生成每次调用rand7()
所需的2.80735位熵 . 那么,基本限制是我们不能比每次调用rand7()
的log(7)/ log(5)= 1.20906调用rand5()
更好 .附注:除非另有说明,否则本答案中的所有对数均为基数2 . 将假定
rand5()
返回[0,4]范围内的数字,并假设rand7()
返回[0,6]范围内的数字 . 将范围分别调整为[1,5]和[1,7]是微不足道的 .那我们该怎么做呢?我们生成一个介于0和1之间的无限精确的随机实数(假装我们实际上可以计算并存储这样一个无限精确的数字 - 我们稍后会修复它) . 我们可以通过在基数5中生成其数字来生成这样的数字:我们选择随机数0.
a
1a
2a
3 ...,其中每个数字ai通过调用rand5()
来选择 . 例如,如果我们的RNG为所有i
选择ai = 1,则忽略不是非常随机的事实,这将对应于实数1/5 1/52 1/53 ... = 1/4(几何系列的总和) .好的,所以我们've picked a random real number between 0 and 1. I now claim that such a random number is uniformly distributed. Intuitively, this is easy to understand, since each digit was picked uniformly, and the number is infinitely precise. However, a formal proof of this is somewhat more involved, since now we'处理连续分布而不是离散分布,所以我们需要证明我们的数字位于区间[
a
,b
]的概率等于该区间的长度b - a
. 证明留给读者练习=) .现在我们有一个从[0,1]范围内均匀选择的随机实数,我们需要将它转换为[0,6]范围内的一系列均匀随机数,以生成
rand7()
的输出 . 我们如何做到这一点?正好与我们刚刚做的相反 - 我们将其转换为基数为7的无限精确小数,然后每个基数为7的数字将对应于rand7()
的一个输出 .以前面的例子为例,如果我们的
rand5()
产生1的无限流,那么我们的随机实数将是1/4 . 将1/4转换为基数7,我们得到无限小数0.15151515 ...,因此我们将产生1,5,1,5,1,5等输出 .好的,我们有主要想法,但我们有两个问题左:我们实际上无法计算或存储无限精确的实数,那么我们如何只处理它的有限部分呢?其次,我们如何实际将其转换为7?
我们可以将0到1之间的数字转换为基数7的一种方法如下:
乘以7
结果的组成部分是下一个7位数
减去整数部分,只留下小数部分
转到第1步
为了处理无限精度的问题,我们计算了部分结果,并且我们还存储了结果可能的上限 . 也就是说,假设我们两次调用
rand5()
并且它两次都返回1 . 到目前为止我们生成的数字是0.11(基数5) . 无论对rand5()
产生的无限系列调用的其余部分如何,我们生成的随机实数将永远不会大于0.12:0.11≤0.11xyz... <0.12始终为真 .所以,跟踪到目前为止的当前数字,以及它可能采取的最大值,我们将这两个数字转换为基数7.如果他们同意第一个
k
数字,那么我们可以安全地输出下一个k
数字 - 无论什么是5位数的无限流,它们永远不会影响基数7表示的下一个k
数字!这就是算法 - 生成
rand7()
的下一个输出,我们只生成rand5()
的数字,因为我们需要确保我们确切地知道随机实数转换为基数7的下一个数字的值 . 这是一个Python实现,带有测试工具:请注意
rand7_gen()
返回一个生成器,因为它具有内部状态,涉及将数字转换为基数7.测试工具调用next(r7)
10000次以生成10000个随机数,然后测量它们的分布 . 仅使用整数数学,因此结果完全正确 .另请注意,这里的数字非常大,非常快 . 5和7的力量迅速增长 . 因此,由于bignum算法,在生成大量随机数后,性能将开始明显降低 . 但请记住,我的目标是最大化随机位的使用,而不是最大化性能(尽管这是次要目标) .
在一次运行中,我对
rand5()
进行了12091次调用,对于rand7()
进行了10000次调用,平均达到log(7)/ log(5)调用的最小值达到4位有效数字,结果输出均匀 .为了将此代码移植到一种语言,该语言不必将
pow5
和pow7
的值限制为原生积分类型的最大值 - 如果它们变得太大,则重置所有内容并重新开始 . 这会将每次调用rand5()
的平均调用次数增加到rand7()
,但希望即使对于32位或64位整数也不应该增加太多 .(我偷了Adam Rosenfeld's answer并使其运行速度提高了约7% . )
假设rand5()以相等的分布返回{0,1,2,3,4}中的一个,并且目标是返回{0,1,2,3,4,5,6},具有相等的分布 .
我们跟踪循环在变量
max
中可以产生的最大值 . 如果到目前为止reult在max%7和max-1之间,则结果将在该范围内均匀分布 . 如果没有,我们使用余数,它在0和最大%7-1之间是随机的,另一次调用rand()来产生一个新的数字和一个新的最大值 . 然后我们重新开始 .编辑:期望调用rand5()的次数在此等式中为x:
Algorithm:
图7的序列可以以3比特的顺序表示
使用rand(5)随机填充每个位0或1 .
例如:call rand(5)和
如果结果为1或2,则用0填充该位
如果结果为4或5,则用1填充该位
如果结果为3,则忽略并再次执行(拒绝)
这样我们可以用0/1随机填充3位,从而得到1-7的数字 .
EDIT: 这似乎是最简单,最有效的答案,所以这里有一些代码:
编辑:这不太奏效 . 它在1000左右大约2个部分(假设完美的兰德5) . 水桶得到:
通过切换到的总和
似乎每增加2个就会获得一个数量级
顺便说一句:上面的错误表不是通过抽样生成的,而是通过以下递归关系生成的:
下列使用随机数发生器在{1,2,3,4,5,5,7}上产生均匀分布,在{1,2,3,4,5}上产生均匀分布 . 代码很乱,但逻辑很明确 .
如果我们考虑尝试给出最有效答案的附加约束,即给出输入流的一个
I
,从1-5的长度m
的均匀分布的整数输出一个流O
,从1-7的均匀分布的整数相对于m
的最长长度,比如L(m)
.分析这个的最简单方法是将流I和_2640083分别视为5进制和7进制数 . 这是通过主答案获取流
a1, a2, a3,... -> a1+5*a2+5^2*a3+..
以及类似于流O
的想法来实现的 .然后,如果我们采用长度为
m choose n s.t. 5^m-7^n=c
的输入流的一部分,其中c>0
并且尽可能小 . 然后是从长度为m的输入流到从1
到5^m
的整数以及从1到7^n
的整数到长度为n的输出流的另一个统一映射的统一映射,其中我们可能必须从输入流中丢失一些情况 . 映射的整数超过7^n
.因此,这为
m (log5/log7)
提供了一个大约m (log5/log7)
的值,大约为.82m
.上述分析的难点在于方程式
5^m-7^n=c
,它不容易精确解决,并且从1
到5^m
的均匀值超过7^n
并且我们失去效率的情况 .问题是如何接近m(log5 / log7)的最佳可能值 . 例如,当这个数接近整数时,我们能找到一种方法来实现这个精确的整数输出值吗?
如果
5^m-7^n=c
然后从输入流我们有效地生成从0
到(5^m)-1
的均匀随机数,并且不使用任何高于7^n
的值 . 但是,可以挽救这些值并再次使用 . 它们有效地生成从1到5^m-7^n
的统一数字序列 . 因此,我们可以尝试使用它们并将它们转换为7位数,以便我们可以创建更多的输出值 .如果我们让
T7(X)
成为random(1-7)
整数的输出序列的平均长度,这些整数是从大小为X
的统一输入派生的,并假设为5^m=7^n0+7^n1+7^n2+...+7^nr+s, s<7
.然后是
T7(5^m)=n0x7^n0/5^m + ((5^m-7^n0)/5^m) T7(5^m-7^n0)
,因为我们的长度没有序列,概率为7 ^ n0 / 5 ^ m,残差为5^m-7^n0
,概率为(5^m-7^n0)/5^m)
.如果我们继续代替我们获得:
于是
另一种方法是:
最好的情况是我原来的那个
5^m=7^n+s
,其中s<7
.那么
T7(5^m) = nx(7^n)/(7^n+s) = n+o(1) = m (Log5/Log7)+o(1)
和以前一样 .最糟糕的情况是我们只能找到k和s.t 5 ^ m = kx7 s .
其他案件介于两者之间 . 看看我们能为非常大的m做得多好,这将是有趣的,即我们可以得到错误项有多好:
一般来说似乎不可能实现
e(m) = o(1)
但希望我们可以证明e(m)=o(m)
.然后整个事情依赖于
5^m
的7位数字的分布,用于m
的各种值 .我确信有很多理论可以解决这个问题,我可能会在某些方面回顾一下 .
这里有家庭作业问题吗?
此函数执行原始“基数5”数学运算以生成0到6之间的数字 .
这是Adam's answer的一个有效的Python实现 .
我喜欢抛出我正在研究Python的算法,所以我可以玩它们,我想我会在这里发布它,希望它对那里的人有用,而不是花了很长时间才能拼凑起来 .
为什么不这么简单?
由于模数的原因,在此解决方案中获得1和7的可能性较低,但是,如果您只是想要一个快速且可读的解决方案,那么这就是要走的路 .
假设 rand(n) 这里的意思是“从 0 到 n-1 的均匀分布中的随机整数”,这里有's a code sample using Python'的randint,它具有这种效果 . 它仅使用 randint(5) 和常量来产生 randint(7) 的效果 . 实际上有点傻
亚当罗森菲尔德正确答案背后的前提是:
x = 5 ^ n(在他的情况下: n = 2)
操纵n rand5调用以获得范围[1,x]内的数字 y
z =((int)(x / 7))* 7
如果y> z,请再试一次 . 否则返回y%7 1
当n等于2时,你有4个扔掉可能性:y = {22,23,24,25} . 如果你使用n等于6,你只有1次丢弃:y = {15625} .
5 ^ 6 = 15625
7 * 2232 = 15624
你多次调用rand5 . 但是,获得丢弃值(或无限循环)的可能性要小得多 . 如果有办法让y没有可能的丢弃值,我还没有找到它 .
这是我的答案:
它比其他人复杂一点,但我相信它最大限度地减少了对rand5的调用 . 与其他解决方案一样,它可能会循环很长时间 .
简单高效:
(灵感来自What's your favorite "programmer" cartoon?) .
与所选解决方案不同,算法将在恒定时间内运行 . 然而,它确实比rand5多2次调用,而不是所选解决方案的平均运行时间 .
请注意,此生成器并不完美(数字0的机会比任何其他数字多0.0064%),但对于大多数实际用途,恒定时间的保证可能超过这种不准确性 .
Explanation
这个解决方案来源于数字15,624可被7整除的事实,因此如果我们可以随机均匀地生成0到15,624之间的数字,然后取mod 7,我们就可以获得一个接近均匀的rand7生成器 . 0到15,624之间的数字可以通过滚动rand5 6次并使用它们形成基数为5的数字来统一生成,如下所示:
然而,mod 7的属性允许我们稍微简化等式:
所以
变
Theory
数字15,624不是随机选择的,但可以使用fermat的小定理来发现,该定理指出如果p是素数则
所以这给了我们,
(5 ^ 6)-1等于
这是一个基数为5的数字,因此我们可以看到这个方法可以用于从任何随机数发生器到任何其他随机数发生器 . 虽然在使用指数p-1时总是引入朝向0的小偏差 .
只要没有可供选择的七种可能性,绘制另一个随机数,将可能性的数量乘以5 . 在Perl中:
我不喜欢从1开始的范围,所以我将从0开始:-)
你去,统一发布和零rand5电话 .
需要事先设定种子 .
我知道它已被回答,但这似乎工作正常,但我不能告诉你它是否有偏见 . 我的“测试”表明它至少是合理的 .
也许亚当罗森菲尔德会好心评论?
我(天真?)的想法是这样的:
累积rand5,直到有足够的随机位来制作rand7 . 这最多需要2兰特5 . 为了得到rand7号码,我使用了积累值mod 7 .
为了避免累加器溢出,并且由于累加器是mod 7,那么我采用累加器的mod 7:
rand7()函数如下:
(我让rand5的范围是0-4,rand7同样是0-6 . )
编辑:为1亿次试验添加了结果 .
'真实'rand函数mod 5或7
rand5:avg = 1.999802 0:20003944 1:19999889 2:20003690 3:19996938 4:19995539 rand7:avg = 3.000111 0:14282851 1:14282879 2:14284554 3:14288546 4:14292388 5:14288736 6:14280046
我的rand7
平均看起来不错,数字分布看起来也不错 .
randt:avg = 3.000080 0:14288793 1:14280135 2:14287848 3:14285277 4:14286341 5:14278663 6:14292943
上面引用了优雅的算法,但这里有一种方法可以解决它,尽管它可能是迂回的 . 我假设从0生成的值 .
R2 =随机数生成器给出小于2的值(样本空间= {0,1}})
R8 =随机数生成器给出小于8的值(样本空间= {0,1,2,3,4,5,6,7})
为了从R2生成R8,您将运行R2三次,并将所有3次运行的组合结果用作3位二进制数 . 以下是R2运行三次时的值范围:
0 0 0 - > 0
.
.
1 1 1 - > 7
现在从R8生成R7,如果它返回7,我们只需再次运行R7:
迂回解决方案是从R5生成R2(就像我们从R8生成R7),然后从R2生成R8,然后从R8生成R7 .
这是一个完全适合整数的解决方案,在最佳值的4%左右(即{0..4}中每个{0..4}使用1.26随机数) . Scala中的代码,但数学应该在任何语言中合理清晰:你利用7 ^ 9 7 ^ 8非常接近5 ^ 11的事实 . 那么你在基数5中选择一个11位数字,然后将其解释为基数7中的9位数字(如果它在范围内(给出9个基数为7的数字)),或者如果它超过9位数字等则为8位数字:
如果将测试粘贴到解释器(实际上是REPL),则会得到:
分布很好且平坦(在每个箱中10 ^ 8的1/7内约10k,如从大约高斯分布所预期的那样) .
通过使用滚动总数,您可以同时使用
保持平等分配;和
不必牺牲随机序列中的任何元素 .
这两个问题都是简单的
rand(5)+rand(5)...
型解决方案的问题 . 以下Python代码显示了如何实现它(大部分证明了分发) .此输出显示结果:
一个简单的
rand(5)+rand(5)
,忽略那些返回超过6的情况,其典型变化为18%,是上述方法的100倍:而且,根据Nixuz的建议,我已经清理了脚本,所以你可以提取并使用
rand7...
的东西:这个答案更像是从Rand5函数中获得最大熵的实验 . 因此,有点不清楚,几乎肯定比其他实现慢很多 .
假设0-4的均匀分布并从0-6得到均匀分布:
每次调用Rand5时添加到缓冲区的位数目前为4/5 * 2,因此为1.6 . 如果包含的1/5概率值增加0.05,那么1.65但是请参阅代码中的注释,我必须禁用它 .
通过调用Rand7 = 3 1/8 *消耗的比特(3 1/8 *(3 1/8 *(...
这是3 3/8 3/64 3/512 ...所以大约3.42
通过从七位数中提取信息,我每次调用收回1/8 * 1/7位,因此大约为0.018
这给每次呼叫净消耗3.4比特,这意味着每个Rand7对Rand5的比率是2.125 . 最佳值应为2.1 .
我认为这种方法明显慢于其他许多方法,除非调用Rand5的成本非常昂贵(比如说要调用一些外部的熵源) .
在PHP中
循环产生一个介于16和127之间的随机数,除以16以创建一个介于1和7.9375之间的浮点数,然后向下舍入得到1到7之间的int . 如果我没有弄错,则有16/112的机会获得7个结果中的任何一个 .
你需要的函数是rand1_7(),我写了rand1_5(),你可以测试它并绘制它 .
只需缩放第一个函数的输出