RAND函数会重复吗？

灰袍法师

VBA rnd函数用什么算法不清楚，不过Excel工作表的RAND函数使用以下算法

随机小数在周期内出现重复的可能性是零
其实也完全可以把随机小数看成是15位长的随机整数，反正就是小数点的位置不同而已。

论坛也有历史贴讨论这个问题

[原创]产生不重复随机数的例子
http://club.excelhome.net/thread-12570-1-1.html

[原创]不重复随机数
http://club.excelhome.net/viewth ... p;extra=&page=1

不过我必须说，这两个贴对于rand()函数的论述，都是有错误的。

首先，按下面的资料所言，rand()函数的周期是6.95E+12，而不是上面两帖所以为的10^15

其次，周期是6.95E+12，意味着除非你连续用超过6.95万亿个随机数，否则不会出现重复，而不是一般认为的"会有重复但是机会很低"

rand函数算法的三个整数生成函数，都是精心选择的，其周期都是满的
也就是说在 30269 30307 30323的范围内，每个生成的整数都不相同

而且我验证过，按rand()函数的算法把这三个整数转化为小数，每个小数都不相同
也就是说，这三个数的组合数接近 30269*30307*30323 = 27.8万亿种

当然，rand()函数的算法把这三个小数求和，然后只取小数部分
这个过程导致最终的周期只有6.95万亿，而不是27万亿。

最后，如果是用rand()配合其它公式，比如说：生成 1-100的随机整数101个，那么重复的可能性就绝对是100%了。

===============================================
rand()函数的VBA代码实现

Sub gen_rand_numbers(arr_rnd()) '本程序用0-1随机小数填满 arr_rnd 数组，arr_rnd是一个一行N列的变体类型数组

'使用以下算法 use algorithm as http://support.microsoft.com/kb/828795/zh-cn
'Wichman, B.A. 和 I.D. Hill，Algorithm AS 183:An Efficient and Portable Pseudo-Random Number Generator，《Applied Statistics》，31，188-190，1982。

Dim ix As Long, iy As Long, iz As Long, p As Long, r As Double
Const mod1 As Long = 30269: Const mod2 As Long = 30307: Const mod3 As Long = 30323
Randomize
ix = Rnd() * mod1 '这里用了VBA内置函数生成三个随机种子，实际还可以用随机时间，鼠标位移等等方法，不依赖VBA随机函数
iy = Rnd() * mod2
iz = Rnd() * mod3
For p = LBound(arr_rnd) To UBound(arr_rnd)
    ix = 171 * ix Mod mod1
    iy = 172 * iy Mod mod2
    iz = 170 * iz Mod mod3
    r = ix / mod1 + iy / mod2 + iz / mod3
    arr_rnd(p) = r - Int(r)
Next p
End Sub
==================================================
RAND()函数的源代码
An Efficient and Portable Pseudo-Random Number Generator

      real function random()
c
c     Algorithm AS 183 Appl. Statist. (1982) vol.31, no.2
c
c     Returns a pseudo-random number rectangularly distributed
c     between 0 and 1.   The cycle length is 6.95E+12 (See page 123
c     of Applied Statistics (1984) vol.33), not as claimed in the
c     original article.
c
c     IX, IY and IZ should be set to integer values between 1 and
c     30000 before the first entry.
c
c     Integer arithmetic up to 30323 is required.
c
      integer ix, iy, iz
      common /randc/ ix, iy, iz
c
      ix = 171 * mod(ix, 177) - 2 * (ix / 177)
      iy = 172 * mod(iy, 176) - 35 * (iy / 176)
      iz = 170 * mod(iz, 178) - 63 * (iz / 178)
c
      if (ix .lt. 0) ix = ix + 30269
      if (iy .lt. 0) iy = iy + 30307
      if (iz .lt. 0) iz = iz + 30323
c
c     If integer arithmetic up to 5212632 is available, the preceding
c     6 statements may be replaced by:
c
c     ix = mod(171 * ix, 30269)
c     iy = mod(172 * iy, 30307)
c     iz = mod(170 * iz, 30323)
c
      random = mod(float(ix) / 30269. + float(iy) / 30307. +
     +                        float(iz) / 30323., 1.0)
      return
      end

[ 本帖最后由 灰袍法师 于 2011-6-17 23:16 编辑 ]

zhuying0511

楼上砖家...NB

灰袍法师

原帖由 zhuying0511 于 2011-1-16 19:47 发表
楼上砖家...NB

谢谢

所谓砖家，就是在该领域犯过最多错误的人

[ 本帖最后由 灰袍法师 于 2011-1-16 20:58 编辑 ]

ehiseh

谢谢高手，受益了

chenzyyysl

原帖由 灰袍法师 于 2011-1-15 22:55 发表
首先，按下面的资料所言，rand()函数的周期是6.95E+12，而不是上面两帖所以为的10^15

其次，周期是6.95E+12，意味着除非你连续用超过6.95千亿个随机数，否则不会出现重复，而不是一般认为的"会有重复但是机会很低

法师这个理解有点问题吧？

灰袍法师

原帖由 chenzyyysl 于 2011-6-17 02:34 发表

法师这个理解有点问题吧？

有何问题？

chenzyyysl

rept("1,2,3",n),周期为3，第4个才重复。
rept("1,1,2,3",n),周期为4，第2个就重复了。
应当是没分开讨论重复序列与重复值的差别吧。

当然，周期6.95E+12，15位精度，不重复也是能办到的。不过粗看下，源代码里并没有特别的语句处理重复值，就不知是否该算法天然能保证周期内无重复值。

顺便说一下，如果取的精度不大于12位，周期内肯定会有重复值，但周期还是那么多。

个人看法，请法师斧正。

灰袍法师

原帖由 chenzyyysl 于 2011-6-17 08:19 发表
rept("1,2,3",n),周期为3，第4个才重复。
rept("1,1,2,3",n),周期为4，第2个就重复了。
应当是没分开讨论重复序列与重复值的差别吧。

由于每一个伪随机数都是由上一个伪随机数按同样的计算生成

所以绝对不会出现 "a,a,b,c"这样的序列

rand在周期内绝对不重复的，而且在周期＋1的数字绝对等于第一个数字，也就是再重新循环生成一次跟上一个周期相同的所有数字。

当然，有些更复杂的生成算法，会用前几个伪随机数来计算下一个伪随机数，这样它出现一个与以前生成数字相同的时候，也不一定会立即重复整个周期。

如 下一个随机数 = 计算 (前面第一个，前面第3个，前面第17个，前面第43个)

这样的算法将在 前面第一个，前面第3个，前面第17个，前面第43个 都相同的时候才出现周期重复。

但是，这样做，并不一定保证其生成序列满足 均匀，周期很长 这两个要求。

另外你提到，计算结果取12位精度会缩短出现重复的周期，这个当然了

我们说生成随机数序列的周期，都是指最原始的 0-1小数序列的周期，而不是指生成我们实际需要的随机数的周期

btw：我把RAND()的生成算法写成VB程序，运行了20小时还没有碰到重复

鉴于我的电脑每3.75秒验证1亿个左右，那么现在至少可以确定

RAND()函数至少有 20 * 3600 / 3.75 = 1.9万亿 长度的周期，在周期内没有重复。

唉。。。。。。验证6.95万亿需要超过72小时，还是算了。

[ 本帖最后由 灰袍法师 于 2011-6-17 23:23 编辑 ]

chenzyyysl

对于周期为无穷大的真随机数，如果取15位精度，大约在E8个左右得到重复值的可能性就接近为1了。

只是对“伪随机数在周期内绝对不重复的”的理由不确定，法师既然已验证了E11没有重复，至少可以估计伪随机数的均匀性比真随机数还高。

如上述猜想成立，那用伪随机数模拟，以获得重复值的比率或概率为目的情况，是否会产生较大的误差？

其它方面赞同法师的见解，并无疑问。

灰袍法师

原帖由 chenzyyysl 于 2011-6-17 20:07 发表
对于周期为无穷大的真随机数，如果取15位精度，大约在E8个左右得到重复值的可能性就接近为1了。
只是对“伪随机数在周期内绝对不重复的”的理由不确定，法师既然已验证了E11没有重复，至少可以估计伪随机数的均匀 ...

你的疑问根源于把rand()的0-1均匀分布的小数 和实际使用的 随机数混为一谈

实际使用的随机数往往是 rand() * ( b - a ) + a，所以几乎不可能没有重复，重复程度跟 b-a的大小，和生成随机数个数等等有关

但是rand() * ( b - a ) + a通常无需考虑周期，因为一般 b-a都是很小的数字，而生成n个随机数的n又很小

rand的周期相对于实际应用长得恐怖，所以用起来就跟真随机数的无穷周期一样。

当然，如果你的实际应用就是要生成 几万亿个15位小数精度 的随机小数，那么rand就不够好了。

这也是为什么伪随机数生成器一般要求周期越长越好（嗯。。。。。。虽然超过double类型的周期似乎没必要）

你说“用伪随机数模拟，以获得重复值的比率或概率为目的情况，是否会产生较大的误差？”
这个还是要看你的要求精度有多高，生成的随机数有多少个，如：VBA的rnd函数，周期只有2^24即 16M左右，远远不如rand函数
http://club.excelhome.net/viewth ... p;page=1#pid4957352

如果你用rnd生成 32M个随机数，那么刚好每个数字都出现两次。。。。。。

自然这种情况下就不能用rnd了，但是用rand还是很好的，因此随机数生成器的周期越长越好。

另一方面，真实随机数既然有无限的周期长度，那么它的精度就不重要了

扔完美硬币只有两种结果，精度为2^1, 但把n次扔硬币当作一个随机数，就可以实现无限精度的随机数。

所以真实随机数根本不存在什么精度，周期，均匀性，重复等等问题。

真实随机数也许会出现重复，但是rand在周期内不会有重复，这并不表明rand比真实随机数更好，而是表明存在一个可以被检测出来的缺陷。。。。。。

但是，实际使用的随机数数量不多（相对于6.95万亿而言，简直微不足道），所以实际上无法被检测出来！

[ 本帖最后由 灰袍法师 于 2011-6-17 23:25 编辑 ]