用伪随机数生成器Random生成随机数序列

  1. 云栖社区>
  2. 博客>
  3. 正文

用伪随机数生成器Random生成随机数序列

吞吞吐吐的 2017-10-18 18:13:00 浏览1061
展开阅读全文

  在程序设计过程中,我们经常需要用到不同的随机数序列,于是我们写下了这样的程序:

None.gif//TickCount.CS
None.gif
public class MainClass
ExpandedBlockStart.gif
{
InBlock.gif    
public static void Main()
ExpandedSubBlockStart.gif    
{
InBlock.gif        
for(int i=0; i<10; i++)//生成10个随机序列
ExpandedSubBlockStart.gif
        {
InBlock.gif            CreateRand();
ExpandedSubBlockEnd.gif        }

ExpandedSubBlockEnd.gif    }

InBlock.gif
InBlock.gif    
public static void CreateRand()
ExpandedSubBlockStart.gif    
{
InBlock.gif        Random random 
= new Random();
InBlock.gif        
for(int i=0;i<6;i++)//6个数字的随机序列
InBlock.gif
            Console.Write(string.Format("{0} ",random.Next()));
InBlock.gif        Console.WriteLine();
ExpandedSubBlockEnd.gif    }

ExpandedBlockEnd.gif}

     然而不幸的是,我们却得到了几个相同的序列,在我的计算机上(AMD 1.49GHz CPU,512M内存,WinXp+Sp2)编译和运行结果如下:

None.gifE:CSC>csc tickcount.cs
None.gifMicrosoft (R) Visual C# 
2005 编译器 版本 8.00.50727.42
None.gif用于 Microsoft (R) Windows (R) 
2005 Framework 版本 2.0.50727
None.gif版权所有 (C) Microsoft Corporation 
2001-2005。保留所有权利。
None.gif
None.gifE:CSC
>tickcount.exe
None.gif
733598421 1904084089 330766232 1331029161 1336728080 1887876763
None.gif
733598421 1904084089 330766232 1331029161 1336728080 1887876763
None.gif
733598421 1904084089 330766232 1331029161 1336728080 1887876763
None.gif
733598421 1904084089 330766232 1331029161 1336728080 1887876763
None.gif
733598421 1904084089 330766232 1331029161 1336728080 1887876763
None.gif
733598421 1904084089 330766232 1331029161 1336728080 1887876763
None.gif
733598421 1904084089 330766232 1331029161 1336728080 1887876763
None.gif
733598421 1904084089 330766232 1331029161 1336728080 1887876763
None.gif
1215178376 1762749978 309033493 1619713897 294892275 1327336430
None.gif
1215178376 1762749978 309033493 1619713897 294892275 1327336430

    前8个“随机”序列是相同的,后2个“随机”序列也是相同的,这不是我们希望得到的结果,我们希望得到的是互不相同的随机数序列!为什么会得到相同的序列呢?究其原因,就是Random类只是一个伪随机数生成器,并不能产生"绝对随机"的随机数。这里“伪”不是表示“假”的意思,而是表示“有规律”的意思,也就是说:计算机产生的伪随机数既是随机的又是有规律的。


    伪随机数(有库函数产生)与“理想中的”“真”随机数不同,伪随机数是由可确定的(deterministic)函数产生,虽然随机函数可以产生有随机特征的数字序列,但这些数字并不不具备真随机数的一些特性,并非统计意义上的随机数。伪随机数是可以确定的:知道序列中的一个数就可以获得其他剩下数字的有关信息;事实上,如果知道了序列的初始值(种子)通常可以确定整个序列。记得大一上计算机专业基础课的第一节课上,老师就给我们介绍了计算机程序的5个特性(详见附1),其中的一点就是确定性,即“对于相同的输入只能得出相同的输出”,伪随机数的生成正是符合这条金科玉律。下面我们来观察伪随机数生成器Random的两个构造函数:

ExpandedBlockStart.gif public Random() : this(Environment.TickCount){}//默认构造函数,以TickCount作为随机数种子
None.gif
 public Random(int Seed)
ExpandedBlockStart.gif
{
InBlock.gif            
this.SeedArray = new int[0x38];
InBlock.gif            
int num2 = 0x9a4ec86 - Math.Abs(Seed);
InBlock.gif            
this.SeedArray[0x37= num2;
InBlock.gif            
int num3 = 1;
InBlock.gif            
for (int i = 1; i < 0x37; i++)
ExpandedSubBlockStart.gif            
{
InBlock.gif                
int index = (0x15 * i) % 0x37;
InBlock.gif                
this.SeedArray[index] = num3;
InBlock.gif                num3 
= num2 - num3;
InBlock.gif                
if (num3 < 0)
ExpandedSubBlockStart.gif                
{
InBlock.gif                    num3 
+= 0x7fffffff;
ExpandedSubBlockEnd.gif                }

InBlock.gif                num2 
= this.SeedArray[index];
ExpandedSubBlockEnd.gif            }

InBlock.gif            
for (int j = 1; j < 5; j++)
ExpandedSubBlockStart.gif            
{
InBlock.gif                
for (int k = 1; k < 0x38; k++)
ExpandedSubBlockStart.gif                
{
InBlock.gif                    
this.SeedArray[k] -= this.SeedArray[1 + ((k + 30% 0x37)];
InBlock.gif                    
if (this.SeedArray[k] < 0)
ExpandedSubBlockStart.gif                    
{
InBlock.gif                        
this.SeedArray[k] += 0x7fffffff;
ExpandedSubBlockEnd.gif                    }

ExpandedSubBlockEnd.gif                }

ExpandedSubBlockEnd.gif            }
//根据程序的确定性,显然传入相同的Seed,将得到同样的SeedArray
InBlock.gif
            this.inext = 0;
InBlock.gif            
this.inextp = 0x15;
InBlock.gif            Seed 
= 1;
ExpandedBlockEnd.gif}

         Random类的默认构造函数中,以系统启动后经过的毫秒数TickCount作为随机数种子,在MSDN中,针对Environment.TickCount有这样一句注释:“TickCount 属性的分辨率不能小于500毫秒。”。也就是说:在0.5秒之内,我们将得到相等的TickCount值;再啰嗦点儿就是说:在0.5秒之内通过默认的构造函数构造的所有Random实例都有相同的SeedArray,相同的数据源在同一台计算机上经过相同的算法处理后,理所当然应该得出相同的结果序列了^_^。

        虽然MSDN中说“TickCount属性的分辨率不能小于500毫秒”,但我在自己的机器上测试了一下,结果略有偏差,下面是测试代码和编译运行结果:

None.gif//TickCount2.CS
None.gif
using System;
None.gif
public class MainClass
ExpandedBlockStart.gif
{
InBlock.gif    
public static void Main()
ExpandedSubBlockStart.gif    
{
InBlock.gif        
long start;
InBlock.gif               
long end = start = Environment.TickCount;
InBlock.gif        
while(end == start) //测试系统能分辨的TickCount的取值间隔
ExpandedSubBlockStart.gif
        {
InBlock.gif            end 
= Environment.TickCount;
ExpandedSubBlockEnd.gif        }

InBlock.gif        Console.Write(
"Ticks:");
InBlock.gif        Console.WriteLine(end 
- start);
InBlock.gif
InBlock.gif        DateTime startTime;
InBlock.gif        DateTime endTime 
= startTime  = DateTime.Now;
InBlock.gif        
while(endTime == startTime)//测试系统能分辨的DateTime的取值间隔
ExpandedSubBlockStart.gif
        {
InBlock.gif            endTime 
= DateTime.Now;
ExpandedSubBlockEnd.gif        }

InBlock.gif        Console.Write(
"Time:");
InBlock.gif        Console.WriteLine(endTime 
- startTime);    
ExpandedSubBlockEnd.gif    }

ExpandedBlockEnd.gif}

None.gif
//在我的计算机上编译和运行结果如下:
None.gif
E:CSC>csc tickcount2.cs
None.gifMicrosoft (R) Visual C# 
2005 编译器 版本 8.00.50727.42
None.gif用于 Microsoft (R) Windows (R) 
2005 Framework 版本 2.0.50727
None.gif版权所有 (C) Microsoft Corporation 
2001-2005。保留所有权利。
None.gif
None.gifE:CSC
>tickcount2.exe
None.gifTicks:
10
None.gifTime:
00:00:00.0100144

       啊哈,我的机器上TickCount的分辨率约为10毫秒(0.0100144秒)^_^

 

  
       说了这么多,我们了解到在一段很小的时间段内(我的机器上约是10毫秒),由默认构造函数生成的不同Random实例将产生相同的“随机”数(或“随机”数序列)。现在回到文章开头的问题上,如果我们想在很短的时间内得到不同的“随机”数序列,该怎么办呢?一个解决办法就是在短时间内不要构造不同的Random实例,而是使用同一个Random实例,代码示例(对TickCount1.CS稍加修改)和编译运行结果如下:

None.gif//TickCount3.CS
None.gif
using System;
None.gif
public class MainClass
ExpandedBlockStart.gif
{
InBlock.gif    
public static void Main()
ExpandedSubBlockStart.gif    
{        
InBlock.gif        Random random 
= new Random();
InBlock.gif        
for(int i=0; i<10; i++)//生成10个随机序列
ExpandedSubBlockStart.gif
        {
InBlock.gif            CreateRand(random);
ExpandedSubBlockEnd.gif        }

ExpandedSubBlockEnd.gif    }

InBlock.gif
InBlock.gif    
public static void CreateRand(Random random)
ExpandedSubBlockStart.gif    
{
InBlock.gif        
for(int i=0;i<6;i++)//6个数字的随机序列
InBlock.gif
            Console.Write(string.Format("{0} ",random.Next()));
InBlock.gif        Console.WriteLine();
ExpandedSubBlockEnd.gif    }

ExpandedBlockEnd.gif}

None.gif
ExpandedBlockStart.gif
/// 程序运行编译和运行结果如下:
None.gifE:CSC>csc tickcount3.cs
None.gifMicrosoft (R) Visual C# 
2005 编译器 版本 8.00.50727.42
None.gif用于 Microsoft (R) Windows (R) 
2005 Framework 版本 2.0.50727
None.gif版权所有 (C) Microsoft Corporation 
2001-2005。保留所有权利。
None.gif
None.gifE:CSC
>tickcount3.exe
None.gif
1881514665 187597856 1876537022 2146319285 138059684 807943728
None.gif
576262772 779063600 1237870363 742301708 2044162198 1694855412
None.gif
2005040916 325723903 736394631 133990481 1511650304 169478959
None.gif
686369588 305867187 1159984149 953908396 1685499642 741064817
None.gif
1282574331 555617587 1241463657 736349125 596033346 794494845
None.gif
780261119 120040711 1518990931 565960940 45469235 1597098033
None.gif
1712262257 825399914 282791381 388999071 1341257075 448146946
None.gif
633252151 635828560 2022035278 1352429249 463708613 1214940829
None.gif
439459392 1663640291 751889087 1823526590 292520889 1908503776
None.gif
1336657042 927606269 649581861 1135472205 863744954 1729925744


    这样的结果“从一定程度上”符合了“在短时间内生成不同的随机数序列”,然而,事情远没有这么简单:这里我用引号强调了只是从“一定程度上”符合而已,实际上并不完全符合“随机”的要求。要想完全符合“随机”的要求(例如在加密程序中),必须使用真随机数!真随机数与伪随机数相反,其生成过程必须独立于它的生成函数,所以即使知道了真随机数序列中的一些数,外界也无法推算序列中的其他数。


附1 - 计算机程序的5个特性:
有穷性:一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束,且每一步都可在有穷时间内完成; 
确定性:算法中每一条指令必须有确切的含义,读者理解时不会产生二义性。有任何条件下,算法只有唯一的一条执行路径,即对于相同的输入只能得出相同的输出。 
可行性:一个算法是能行的,即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 
输入:一个算法有零个或多个的输入,这些输入取自于某个特定的对象的集合。 
输出:一个算法有一个或多个的输出。这些输出是同输入有着某些特定关系的量。 


附2 - Random类源代码(经Reflector.exe反汇编得到):

None.gifnamespace System
ExpandedBlockStart.gif
{
InBlock.gif    
using System.Globalization;
InBlock.gif    
using System.Runtime.InteropServices;
InBlock.gif
InBlock.gif    [Serializable, ComVisible(
true)]
InBlock.gif    
public class Random
ExpandedSubBlockStart.gif    
{
InBlock.gif        
private int inext;
InBlock.gif        
private int inextp;
InBlock.gif        
private const int MBIG = 0x7fffffff;//0111 1111 1111 1111 1111 1111 1111 1111
InBlock.gif
        private const int MSEED = 0x9a4ec86;//0000 1001 1010 0100 1110 1100 1000 0110
InBlock.gif
        private const int MZ = 0;
InBlock.gif        
private int[] SeedArray;
InBlock.gif
InBlock.gif        
public Random() : this(Environment.TickCount)
ExpandedSubBlockStart.gif        
{
ExpandedSubBlockEnd.gif        }

InBlock.gif        
ExpandedSubBlockStart.gif        
/*
InBlock.gif         * Environment.TickCount方法
InBlock.gif         * public static int TickCount
InBlock.gif         * {
InBlock.gif         *    get
InBlock.gif         *    {
InBlock.gif         *        return nativeGetTickCount();
InBlock.gif         *    }
InBlock.gif         * }
InBlock.gif         * 
InBlock.gif         * [MethodImpl(MethodImplOptions.InternalCall)]
InBlock.gif         * private static extern int nativeGetTickCount();
ExpandedSubBlockEnd.gif        
*/

InBlock.gif
InBlock.gif        
public Random(int Seed)
ExpandedSubBlockStart.gif        
{
InBlock.gif            
this.SeedArray = new int[0x38];
InBlock.gif            
int num2 = 0x9a4ec86 - Math.Abs(Seed);
InBlock.gif            
this.SeedArray[0x37= num2;
InBlock.gif            
int num3 = 1;
InBlock.gif            
for (int i = 1; i < 0x37; i++)
ExpandedSubBlockStart.gif            
{
InBlock.gif                
int index = (0x15 * i) % 0x37;
InBlock.gif                
this.SeedArray[index] = num3;
InBlock.gif                num3 
= num2 - num3;
InBlock.gif                
if (num3 < 0)
ExpandedSubBlockStart.gif                
{
InBlock.gif                    num3 
+= 0x7fffffff;
ExpandedSubBlockEnd.gif                }

InBlock.gif                num2 
= this.SeedArray[index];
ExpandedSubBlockEnd.gif            }

InBlock.gif            
for (int j = 1; j < 5; j++)
ExpandedSubBlockStart.gif            
{
InBlock.gif                
for (int k = 1; k < 0x38; k++)
ExpandedSubBlockStart.gif                
{
InBlock.gif                    
this.SeedArray[k] -= this.SeedArray[1 + ((k + 30% 0x37)];
InBlock.gif                    
if (this.SeedArray[k] < 0)
ExpandedSubBlockStart.gif                    
{
InBlock.gif                        
this.SeedArray[k] += 0x7fffffff;
ExpandedSubBlockEnd.gif                    }

ExpandedSubBlockEnd.gif                }

ExpandedSubBlockEnd.gif            }
//传入相同的Seed,将得到同样的SeedArray
InBlock.gif
            this.inext = 0;
InBlock.gif            
this.inextp = 0x15;
InBlock.gif            Seed 
= 1;
ExpandedSubBlockEnd.gif        }

InBlock.gif
InBlock.gif        
private double GetSampleForLargeRange()
ExpandedSubBlockStart.gif        
{
InBlock.gif            
int num = this.InternalSample();
InBlock.gif            
if ((((this.InternalSample() % 2== 0? 1 : 0!= 0)
ExpandedSubBlockStart.gif            
{
InBlock.gif                num 
= -num;
ExpandedSubBlockEnd.gif            }

InBlock.gif            
double num2 = num;
InBlock.gif            num2 
+= 2147483646;
InBlock.gif            
return (num2 / 4294967293);
ExpandedSubBlockEnd.gif        }

InBlock.gif
InBlock.gif        
private int InternalSample()
ExpandedSubBlockStart.gif        
{
InBlock.gif            
int index = this.inext;
InBlock.gif            
int inextp = this.inextp;
InBlock.gif            
if (++index >= 0x38)
ExpandedSubBlockStart.gif            
{
InBlock.gif                index 
= 1;
ExpandedSubBlockEnd.gif            }

InBlock.gif            
if (++inextp >= 0x38)
ExpandedSubBlockStart.gif            
{
InBlock.gif                inextp 
= 1;
ExpandedSubBlockEnd.gif            }

InBlock.gif            
int num = this.SeedArray[index] - this.SeedArray[inextp];
InBlock.gif            
if (num < 0)
ExpandedSubBlockStart.gif            
{
InBlock.gif                num 
+= 0x7fffffff;
ExpandedSubBlockEnd.gif            }

InBlock.gif            
this.SeedArray[index] = num;
InBlock.gif            
this.inext = index;
InBlock.gif            
this.inextp = inextp;
InBlock.gif            
return num;
ExpandedSubBlockEnd.gif        }

InBlock.gif
InBlock.gif        
public virtual int Next()
ExpandedSubBlockStart.gif        
{
InBlock.gif            
return this.InternalSample();
ExpandedSubBlockEnd.gif        }

InBlock.gif
InBlock.gif        
public virtual int Next(int maxValue)
ExpandedSubBlockStart.gif        
{
InBlock.gif            
if (maxValue < 0)
ExpandedSubBlockStart.gif            
{
ExpandedSubBlockStart.gif                
throw new ArgumentOutOfRangeException("maxValue"string.Format(CultureInfo.CurrentCulture, Environment.GetResourceString("ArgumentOutOfRange_MustBePositive"), new object[] "maxValue" }));
ExpandedSubBlockEnd.gif            }

InBlock.gif            
return (int) (this.Sample() * maxValue);
ExpandedSubBlockEnd.gif        }

InBlock.gif
InBlock.gif        
public virtual int Next(int minValue, int maxValue)
ExpandedSubBlockStart.gif        
{
InBlock.gif            
if (minValue > maxValue)
ExpandedSubBlockStart.gif            
{
ExpandedSubBlockStart.gif                
throw new ArgumentOutOfRangeException("minValue"string.Format(CultureInfo.CurrentCulture, Environment.GetResourceString("Argument_MinMaxValue"), new object[] "minValue""maxValue" }));
ExpandedSubBlockEnd.gif            }

InBlock.gif            
long num = maxValue - minValue;
InBlock.gif            
if (num <= 0x7fffffff)
ExpandedSubBlockStart.gif            
{
InBlock.gif                
return (((int) (this.Sample() * num)) + minValue);
ExpandedSubBlockEnd.gif            }

InBlock.gif            
return (((int) ((long) (this.GetSampleForLargeRange() * num))) + minValue);
ExpandedSubBlockEnd.gif        }

InBlock.gif
InBlock.gif        
public virtual void NextBytes(byte[] buffer)
ExpandedSubBlockStart.gif        
{
InBlock.gif            
if (buffer == null)
ExpandedSubBlockStart.gif            
{
InBlock.gif                
throw new ArgumentNullException("buffer");
ExpandedSubBlockEnd.gif            }

InBlock.gif            
for (int i = 0; i < buffer.Length; i++)
ExpandedSubBlockStart.gif            
{
InBlock.gif                buffer[i] 
= (byte) (this.InternalSample() % 0x100);
ExpandedSubBlockEnd.gif            }

ExpandedSubBlockEnd.gif        }

InBlock.gif
InBlock.gif        
public virtual double NextDouble()
ExpandedSubBlockStart.gif        
{
InBlock.gif            
return this.Sample();
ExpandedSubBlockEnd.gif        }

InBlock.gif
InBlock.gif        
protected virtual double Sample()
ExpandedSubBlockStart.gif        
{
InBlock.gif            
return (this.InternalSample() * 4.6566128752457969E-10);
ExpandedSubBlockEnd.gif        }

ExpandedSubBlockEnd.gif    }

ExpandedBlockEnd.gif}

本文转自Silent Void博客园博客,原文链接:http://www.cnblogs.com/happyhippy/archive/2007/04/03/698384.html,如需转载请自行联系原作者

网友评论

登录后评论
0/500
评论
吞吞吐吐的
+ 关注