再论随机数的发生算法 (50分)

先祝大家新年好！给各位拜个年了！
偶尔看到:
http://www.delphibbs.com/delphibbs/dispq.asp?lid=626178
因为Delphi产生的随机数字是伪随机的，其所有的随机性都来自第一次的Randomize,
其随机性约 1e-6/0.1=1/100000，用于加密等应用将有遭到破解的危险！
想到应该如何产生一个随机数，
我希望产生随机数的方法，即不需要特殊的硬件，又能有真正的不可预测性，
而且产生的速度要能够令人接受。
对原帖进行查找，发现了如下帖子对我很有启发，
http://www.delphibbs.com/delphibbs/dispq.asp?lid=650976
http://www.delphibbs.com/delphibbs/dispq.asp?LID=1019143
http://www.delphibbs.com/delphibbs/dispq.asp?lid=622076
经过仔细思考，我想到了一个产生随机数的办法，特贴出来供各位参考。
如有不正确的地方，还请各位指正！
原理：我发现硬盘有个指标叫平均寻道时间，精确到0.1ms,是不是0.1ms以下的时间是随机数呢？
经过测试，证实确实硬盘的读写时间到0.01ms级别的时候基本符合均匀随机分布！这样，
这样，利用磁盘读写包括机械动作，延迟时间(约ms级)远慢于电子设备的响应时间(约us~ns级)，
从而利用高速计数器来获得不同写磁盘的时间，用其中的随机性来获得随机数。下面是代码：
测试平台: K6-2-450+128SDRAM+Win2K+Delphi7(Build4.453)
测试人: DarwinZhang 时间: 2003.1.31
--------------------UnitReadHD.pas---------------------------
unit UnitReadHD;
interface
uses
Classes,Windows;
//获得若干个整数随机变量 0~MaxValue-1区间 随机数据空间 数据长度
procedure DarwinZhangRandom(MaxValue:Integer;
DatasIntegerArray;
DataLength:Integer);

implementation
procedure DarwinZhangRandom(MaxValue:Integer;
DatasIntegerArray;
DataLength:Integer);
//获得一个
const
TempFN='C:/DarwinZhangTempFile.Temp';
BufferSize=512;
var
Buf:Array [0..BufferSize-1] of Byte;
f:File of Byte;
bt,et:Int64;
i,j,OldTP,
Hi,RealValue:Integer;
xouble;
begin
OldTP:=GetThreadPriority(GetCurrentThread);
SetThreadPriority(GetCurrentThread,THREAD_PRIORITY_TIME_CRITICAL);
X:=ln(MaxValue)/ln(64);
Hi:=Trunc(x);
if X=Hi then
Dec(Hi);
//获得一个随机数需要获得的次
RealValue:=1 shl (Hi*6+6);
//区间大小
try
for i:=0 to DataLength-1do
begin
Datas:=0;
for j:=0 to Hido

begin
QueryPerformanceCounter(bt);
AssignFile(f,TempFN);
Rewrite(f);
BlockWrite(f,Buf,BufferSize);
CloseFile(f);
DeleteFile(TempFN);
QueryPerformanceCounter(et);
Datas:=Datas+((et-bt) mod 64)shl (j*6);
//获得写一个扇区的时间
end;
Datas:=Round(Datas*MaxValue/RealValue);
end;
finally
SetThreadPriority(GetCurrentThread,OldTP);
end;
end;

end.

----------------------------unit1.pas-仅作测试用而已----------------------------
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ExtCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
Button2: TButton;
Button3: TButton;
Image1: TImage;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
private
{ Private declarations }
procedure DrawGraph;
public
{ Public declarations }
end;

var
Form1: TForm1;
implementation
{$R *.dfm}
uses UnitReadHD;
//DarwinZhang的随机数产生方法，用DarwinZhang的图形显示方法
const MaxTime=10000;
var Datas:Array [0..MaxTime-1] of Integer;
procedure TForm1.Button1Click(Sender: TObject);
var
i:Integer;
bt,etWord;
begin
if Button1.Tag<>0 then
exit;
Button1.Tag:=1;

bt:=GetTickCount;
DarwinZhangRandom(200,@Datas,MaxTime);
et:=GetTickCount;

//利用面来显示随机分布情况
Image1.Canvas.Brush.Color:=clGreen;
Image1.Canvas.FillRect(Rect(0,0,200,200));
for i:=0 to MaxTime-1do
Image1.Canvas.Pixels[(i mod 200),(Datas mod 200)]:=Clred;
Caption:='';
for i:=0 to 9do
Caption:=Caption+IntToStr(Datas[i*100])+' ';
ShowMessage(IntToStr(et-bt));
//生成10000随机数总时间,大约8ms产生一个随机数
Button1.Tag:=0;
end;

//Delphi的随机数产生方法，用DarwinZhang的图形显示方法
procedure TForm1.Button2Click(Sender: TObject);
const MaxTime=10000;
var
i:Integer;
bt,etWord;
begin
if Button2.Tag<>0 then
exit;
Button2.Tag:=1;
bt:=GetTickCount;
Randomize;
for i:=0 to MaxTime-1do
begin
// Randomize;
//把这一句有效，效果很差
Datas:=Random(200);
end;

et:=GetTickCount;
Image1.Canvas.Brush.Color:=clGreen;
Image1.Canvas.FillRect(Rect(0,0,200,200));
for i:=0 to MaxTime-1do
Image1.Canvas.Pixels[(i mod 200),Datas]:=Clred;
Caption:='';
for i:=0 to 9do
Caption:=Caption+IntToStr(Random(200))+' ';
ShowMessage(IntToStr(et-bt));
Button2.Tag:=0;
end;


const
DivNumber=2000;
var
RandRecord:array[0..DivNumber-1]of Integer;
procedure TForm1.DrawGraph;
//显示产生的数字是否均匀（此处分了200个区间，效果还可以）
var
i,h,w,x1,x2,y,max:Integer;
begin
h:=Image1.Height;
w:=Image1.Width;
max:=0;
for i:=0 to DivNumber-1do
if max<RandRecord then
max:=RandRecord;
with Image1.Canvasdo
begin
Brush.Color:=clBlack;
FillRect(Rect(0,0,w,h));
if max=0 then
exit;
Brush.Color:=clLime;
for i:=0 to DivNumber-1do
begin
x1:=w*i div DivNumber;
x2:=w*(i+1) div DivNumber;
y:=h*RandRecord div max;
FillRect(Rect(x1,h,x2,h-y));
end;
end;
end;
//DarwinZhang的随机数产生方法，用creation-zy----aimingoo的图形显示方法
procedure TForm1.Button3Click(Sender: TObject);
const MaxTime=600;
var
Datas:Array [0..MaxTime-1] of Integer;
i:Integer;
begin
if Button3.Tag<>0 then
exit;
Button3.Tag:=1;
DarwinZhangRandom(DivNumber,@Datas,MaxTime);
FillChar(RandRecord,SizeOf(RandRecord),0);
for i:=0 to MaxTime -1do
Inc(RandRecord[Datas]);
DrawGraph;
Button3.Tag:=0;
end;

end.

实验的结果基本达到我的预想！随机数的分布比较理想，基本符合均匀分布，
条件也很简单：只要您的C:盘上有一个蔟的空间(约2~32K Bytes)就可以！
而且速度可以接受: 2^1000(大约10^300)种可能每秒。
对比Delphi和aimingoo的随机算法，我的算法速度上要慢很多，但我的随机数的不可预测性要高很多。
看creation-zy兄的算法，有个疑问，windows的调度线程时间片算法产生的分配差额是否是真正随机。
我对windows的内核并无了解，如果是等待硬盘或响应其他外设产生的延时确实能引起的分配差，
那么本质上和我的原理是相类似的，但我的方法产生速度要快很多。

没有真正的随机, 看似随机其实是与TIME运算产生的
现实世界了都没随机何况电脑里呢.没有偶然,一切都是必然的
为什么是必然的,因为因果,因果定律最基本定律,是不可违反的
天上下雨了每一滴都落在该落的位置,因为因果.

to 火龙真人:
这里不讨论哲学命题，只看能否被计算即方法预测。要谈哲学请到
http://www.delphibbs.com/delphibbs/dispq.asp?lid=1595491
这里只看算法，谢谢！

to 火龙真人:
您的论断非常正确——但是——没有任何实用性。因为预测是建立在对过去、现在的精确
把握之上的：为了计算明天的气温，全球无数个气象站+无数台超级计算机都在满负荷工作，
但是结果的误差仍然不可避免。
比如，请您计算一下5分钟后您自己口腔某点的温度（精确到亿分之一度即可）；或者，我通过
多线程的不可预测性产生的下一个随机数是多少：））
to DarwinZhang兄：
从您的思路看来，“随机性”应该是没问提了，并且效率也很高。
Good!
又想到了一些东西，似乎有可能“兵不血刃”的实现随机：
注意到在Linux的ping命令的时间显示是以毫微秒为单位的，ping 127.0.0.1的结果大约在
0.0xx毫秒左右（记得不大清楚了，可能差了一两个数量级）——这意味着：虽然这个ping命
令只调用了本地、没有机械损耗的硬件（网卡），但是，它的调用时间仍然具有随机性。又
因为在Windows环境下，我们可以通过QueryPerformanceCounter获得极为精确的时间——有
了这两点，我们完全有可能在亚毫秒的时间内产生一个无法预测、无法重现的随机数。
推广：如果我们将ping调用改成某个比较费CPU的调用（比如说创建一个ActiveX对象），
那就更加实用了：）

呵呵，道家和佛家还真是有共同语言呢。
to creation-zy兄:
用创建ActiveX对象似乎不行吧？因为这个时间一定是固定的吧？
它只在电子设备中操作,可是精确到us~ns级别的吧？
网卡也是电子设备，因为网卡速度达10M~100M它的速度应该也是精确到到ns级别吧？
如果要到网路上进行Ping,那么会不会有什么侦探方法来破解随机性呢？
另外，是否有硬盘不真正执行物理上的写操作而之写到缓冲区就直接返回的情况呢？
creation-zy兄见多识广，请指教一二！

我曾经写过一个磁盘读写速度测试软件。在我的机器上：PIV 1.6A 512MDDR Windows 2000
Advanced Server 60G，对600M的文件进行随机寻道测试，统计下来与硬盘的平均寻道时间
相当接近，但是，当文件小于100M的时候，平均寻道时间随着测试次数的增加而趋向于0（只有
0.00x毫秒！）——这只能说明系统已经差不多将文件全部读入内存！

我将你在 http://www.delphibbs.com/delphibbs/dispq.asp?lid=626178 中的程序中插入
了一个 Repaint;
——结果就在100左右振荡，已经有了随机性；如果将Repaint改成Sleep(1)
就更加明显了。我觉得一个需要内存超过200K的ActiveX组件的创建应该比Repaint一次要长
吧——既然Repaint已经不太好预测了，创建ActiveX的耗时不就更加随机了？

to creation-zy兄:
1."系统已经差不多将文件全部读入内存"
嘻嘻，这正是我不用读而变成用写的原因哪！我现在就是担心它写是不是什么时候也会来假的。
2.如果将Repaint改成Sleep(1)就更加明显了。
我奇怪为什么将我的程序中的写文件代码变成Sleep(1)却大约要200ms?????
我的程序可是在TIME_CRITICAL下面运行哪！

我不让windows来接管我的消耗时间，主要是我对windows不放心，怕它不是真随机，是伪随机。
最好要是能直接对外部设备操作就好了，可是win2k不让。[]

>>TIME_CRITICAL
唉！我就是栽在这玩意儿上面了...好像用了它以后线程的切换会发生延迟，建议还是不
用为好...
我没注意你用的是写文件，我觉得有些不妥（个人感觉而已）。

是不是可以这样：
function GenRandom:Integer;
var
bt,et:Int64;
Str:String;
i:Integer;
begin
Str:='';
for i:=1 to 10do
//要增加随机性，只要增大这个 10 即可——代价是时间
begin
QueryPerformanceCounter(bt);
Sleep(1);
// or Form1.Repaint;
QueryPerformanceCounter(et);
Str:=Str+IntToStr(et-bt)+#9;
end;
//Memo1.Lines.Add(Str);
Result:=MD5(Str);
//自己写一个杂凑算法将字符串变成Integer
end;

下面是我试验产生的三组结果Str（产生一组数据需要10ms多一点时间）：
26850 55818 55882 55903 55933 55896 55926 56000 55924 55793
38454 57343 54572 55848 55857 55927 56190 55643 55933 55900
26156 55863 56365 55458 56080 66327 45544 55665 55920 55928
每个数字的信息量在6bit左右，10个数字就是60bit——如果被杂凑成32bit的Integer...
应该没什么问题吧...

多谢creation-zy兄！
1.好像用了它以后线程的切换会发生延迟
我怎么不用TIME_CRITICAL要300ms？奇怪？？？[] 继续查......
放到同一个单元里面sleep(1)就是10ms,古怪。
2.
用repaint可以达到 1bit/ms的速度，与写磁盘的速度差不多！

to creation-zy兄： “写文件，我觉得有些不妥”
我也不想写，可是读有问题，必须每次读不同的地方才不会被windows缓冲，这不好办。
而能够产生外设延迟的好象只有硬盘可靠了，只好写了。

随机数的主要目的并不是单纯的均匀分布,最需要的功能是产生数据的不确定性(无规律性)
和相对唯一性.我认为Delphi自带的函数足以实现我们一般的随机数需求.
或许您的寻道算法有用武之地,但我真想不出有什么用处.

to yinxuetao:主要是加密方面的运用。
to creation-zy兄: 我这里无论如何Sleep(1)都是大于10ms的。
系统K62-450+128SDRam+Win2k+Delphi7。请问您的系统？

收藏这个帖子

看来要去了解一下windows系统原理了。

数学问题
如果用硬盘访问时间的话，
我觉得只是一种权益之计，不是问题的根本

对此感兴趣。

to DarwinZhang兄：
我这里是: 毒龙1800+, 256M DDR333, 60G, Windows XP Professional, Delphi5。
试验程序如下：
procedure TForm1.Button4Click(Sender: TObject);
var
i:Integer;
OldTickCountWord;
begin
Time,EndTime:Int64;
begin
OldTickCount:=GetTickCount;
for i:=1 to 100do
begin
//QueryPerformanceCounter(begin
Time);
//QueryPerformanceCounter的耗时可以忽略
Sleep(1);
//QueryPerformanceCounter(EndTime);
end;
Caption:=IntToStr(GetTickCount-OldTickCount);
end;
我发现GetTickCount只能精确到15ms左右，上面的代码我的运行结果在200ms左右。若将
Sleep(1) 改成 Sleep(10)，结果则在1063－1078之间。
下面的程序采用QueryPerformanceCounter计时：
procedure TForm1.Button4Click(Sender: TObject);
var
m:Integer;
begin
Time,EndTime,Fq:Int64;
begin
QueryPerformanceCounter(begin
Time);
Sleep(1);
QueryPerformanceCounter(EndTime);
m:=EndTime-begin
Time;
QueryPerformanceFrequency(Fq);
Caption:=FloatToStr(1000*m/Fq)+'ms';
end;
显示结果在0.99到1.92毫秒之间。如果将Sleep(1)改成Sleep(10)，结果则在9.7到10.9毫
秒之间。

to DarwinZhang兄：
哈哈！我又找到一个可以精确到CPU的时钟周期的计时方法：
在586及以上档次处理器中，已经有了一条专用的指令来测试主频，那就是 RDTSC指令，
意思是读取时间标记计数器(Read Time-Stamp Counter)，Time-stamp counter 是处理器内
部的一个64位的MSR (model specific register)，它每个时钟增加一个记数。在处理器复
位的时候，初始值为0，RDTSC 指令把 TSC的值低32位装入EAX中，高32位装入EDX中。如果
CPU的主频是200MHz，那么在一秒钟内，TSC的值增加 200,000,000 次。所以在计算的时候，
把两次的TSC差值除以两次的时间差值就是CPU的主频。
( from: http://asm001.home.chinaren.com/program/cpuspeed.htm )
下面是一个使用RDTSC指令以及QueryPerformanceCounter、QueryPerformanceFrequency
计算CPU主频的一段代码：
function GetCPUSpeed:do
uble;
const
DelayTime=200;
// measure time in ms
QPC_Time=5000;
//QueryPerformanceCounter调用所需大致CPU周期数
var
TimerHi,TimerLoWORD;
begin
Time,EndTime,Frq:Int64;
begin
asm
dw 310Fh // rdtsc
mov TimerLo, eax
mov TimerHi, edx
end;
QueryPerformanceCounter(begin
Time);
Sleep(DelayTime);
QueryPerformanceCounter(EndTime);
asm
dw 310Fh // rdtsc
sub eax, TimerLo
sbb edx, TimerHi
mov TimerLo, eax
mov TimerHi, edx
end;
QueryPerformanceFrequency(Frq);
//目前的CPU在200ms内的周期数还不会超过MaxDWORD，TimerHi始终为0，可以忽略
Result:=(TimerLo-QPC_Time)/(EndTime-begin
Time)*Frq*0.000001;
//MHz
end;

to creation-zy兄：
非常感谢！有了rdtsc我们甚至可以精确到ns级别了。
这可以极大的提高随机数字的产生速度！
至于是否能够获得其它的方法,现在正在实验中。
另外，我的测试sleep(1)代码如下：
procedure TForm1.Button4Click(Sender: TObject);
var
i:Integer;
bt,etWord;
begin
bt:=GetTickCount;
for i:=0 to 1000do
Sleep(1);
et:=GetTickCount;
ShowMessage(IntToStr(et-bt));
end;
结果大约在10.000~10.012s之间震荡，非常奇怪。

其实还有一个效率问题，就是多长的时间延迟，可以获得最大的随机行（可能性）