关于 真正的 随机数的产生!(多线程相关)(50分)

  • 主题发起人 主题发起人 creation-zy
  • 开始时间 开始时间
C

creation-zy

Unregistered / Unconfirmed
GUEST, unregistred user!
我已经找到了产生[red]真正的[/red]随机数(种子)的方法了——该方案每次可以产生好几个数字,
根据我的统计分析,这些数字Mod [blue]1000000[/blue]之后的分布比较均匀。
原理——多任务系统中线程运行的不可再现性——即人们无法确定多个无关线程的进度关系,
要完全重现,必须达到自开机以来鼠标、键盘事件的完全一致,磁头调度的位置、时间的完全一致、
中断事件发生的完全一致、系统中线程运行的切换完全一致(注意,完全一致是指事件发生的
CPU所在周期、状态完全一致——可能吗?? 哈哈哈哈哈哈哈哈!!!)。
附源代码:
unit Thread;
interface
uses
Classes, Windows;
type
PInt=^Integer;
TGo = class(TThread)
private
Ptr:PInt;
WaitPtr:PInt;
protected
procedure Execute;
override;
public
procedure Init(PtrInt,WaitPI:PInt);
end;

implementation
procedure TGo.Execute;
begin
while WaitPtr^=0do
Sleep(1);
while not Terminateddo
Inc(Ptr^);
//此处可以改进,让线程之间相互累加。。。
end;
procedure TGo.Init(PtrInt,WaitPI: PInt);
begin
Ptr:=PtrInt;
WaitPtr:=WaitPI;
end;

end.


unit Main;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls, ExtCtrls, Spin;
type
TForm1 = class(TForm)
Button1: TButton;
Image1: TImage;
Button2: TButton;
SpinEdit1: TSpinEdit;
procedure Button1Click(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure Button2Click(Sender: TObject);
private
procedure DrawGraph;
public
{ Public declarations }
end;

var
Form1: TForm1;
implementation
{$R *.DFM}
uses
Thread;
const
ThreadNumber=6;
DivNumber=200;
ModNumber=1000000;
//产生的数字 MOD 10^6 之后的分布比较均匀
var
RecordInt:array[1..ThreadNumber]of Integer;
RandRecord:array[0..DivNumber-1]of Integer;
procedure TForm1.Button1Click(Sender: TObject);
var
Thds:array[1..ThreadNumber]of TGo;
i,Start:Integer;
Str:String;
begin
Button1.Enabled:=false;
Start:=0;
for i:=1 to ThreadNumberdo
begin
Thds:=TGo.Create(true);
RecordInt:=0;
Thds.Init(@RecordInt,@Start);
Thds.Priority:=tpTimeCritical;
//这一句有必要,否则...
end;
for i:=1 to ThreadNumberdo
Thds.Resume;
Start:=1;
Sleep(20);
//实际上的等待时间超过4秒,Why??
for i:=1 to ThreadNumberdo
Thds.Terminate;
Str:='';
for i:=1 to ThreadNumberdo
begin
Inc(RandRecord[RecordInt mod ModNumber div (ModNumber div DivNumber)]);
Str:=Str+IntToStr(RecordInt)+' ';
end;
Caption:=Str;
Button1.Enabled:=true;
Button1.SetFocus;
DrawGraph;
end;
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;
procedure TForm1.FormCreate(Sender: TObject);
var
i:Integer;
begin
for i:=0 to DivNumber-1do
RandRecord:=0;
end;
procedure TForm1.Button2Click(Sender: TObject);
var
Count:Integer;
begin
if Button2.Tag=1 then
begin
Button2.Tag:=0;
exit;
end;
Button2.Tag:=1;
Button2.Caption:='Stop';
Count:=0;
while (Button2.Tag<>0) and (Count<SpinEdit1.Value)do
begin
Button1.Click;
Application.ProcessMessages;
Inc(Count);
end;
Button2.Tag:=0;
Button2.Caption:='Start';
end;

end.

注:运行环境为:PIII800,Win NT4
每次产生6个均匀分布于 0-999999 的数字,完全重复的概率为[red]十的负三十六次方[/red]。OK?
[:)][:)][^][^]
欢迎大家提出改进意见!谢谢!
另:若分类不妥,还有劳版主,将其放到适当的分类中去,谢谢了!
 
我想知道你这个算法的效率如何?
我一般的做法是取系统时间的秒数或者毫秒数。
 
替你加入精华区
 
>>效率如何
在我的机器上每4秒才能产生一组随机数,所以我将它定位于产生随机数种子。
多线程编程我还不熟,上面的Sleep(20)实际上等了4秒!
to wjiachun:
谢谢!
 
good
[:D]还是奖励给你自己吧!
 
多人接受答案了。
 
哦!天啦~!
太高深了!
谁能帮我??除了我自己之外!;-)
 
感谢aimingoo的工作!(见LID=1019143)他对本随机数产生的原理进行了详细的评述。
下面是部分摘要:
影响creation_zy的算法的具体因素:
1. OS轮循所有线程的时间间隔. 这是一个固定值, 可以通过简单的程序得到. 程序的算法思想是:
1). 首先确定OS中当前没有大于或等于TIME_CRITICAL级别的线程. ---- OS通常情况下就是这样.
2). 创建两个TIME_CRITICAL级别的线程, 在线程的各自的程序中取OS当前时间.
3). 同时启动两个线程. 方法参见creation_zy的程序.
4). 求两个时间的差值, 这即是OS每次分配的时间间隔.
2. 计算平均每线程获得分隔时间片的机率(可能这个说法不准确, 哈哈). 这个值是:
1
-------------------------------
操作系统当前"相同优先级"线程数
简单地说, 如果使用创建n个TIME_CRITICAL级别的线程, 则每个机率为1/n;
如果创建NORMAL级别
的线程, 则每个机率大致为(1/操作系统线程数).
可见, 无论是n或者是操作系统线程数都是可知的. 即便对于未知的应用环境, 操作系统中的当前线
程数也是基本确定的. 比如我现在的Windows 2000就保持在355个线程左右.
3. 每个时间间隔中获得的时间片数, 或者这些时间片中执行的指令数.
这个值的获得是不容易的, 但是, 我们真实的目的却不是要得到具体的指令数.
由于creation_zy的设计中, 算法的核心是简单的Inc(Ptr^), 所以我们只需要知道在OS分配的时间
间隔中可以执行Inc(Ptr^)指令的个数即可.
这样的一个算法设计也是极简单的:
1). 创建TIME_CRITICAL级别的线程A, 执行Inc(Ptr^);
2). 创建TIME_CRITICAL级别的线程B, 执行Terminate A;
3). 同时启动两个线程
4). 查看Ptr^的值, 即是OS分配的时间间隔中可以执行Inc(Ptr^)指令的个数.
由于A和B具体相同的优先级, 所以它们分配CPU的机率和时间长度是一致的. 这样线程A要么在中止
前得到一个执行的机会, 要么就得不到. 这样Ptr^的值要么是0, 要么就是一个时间间隔中分配的时
间片可以执行的Inc(Ptr^)语句数.
或者我这样的说法是有些学院气的, 那么我们换个说法, 简单点的:
1. 任意一个线程受到线程轮循的机率可知, 因而可以计算出在单位时间中指定线程被轮循到的次数
1. 每线程轮循的时间间隔可知
2. 每次轮循分配的CPU时间片可知
4. 每个时间片可执行Inc(Ptr^)的次数可知
OK. 我们看看, 到底Ptr^的值是否是可计算的呢???
答案是不言自明的了吧.


对 RecordInt mod ModNumber div (ModNumber div DivNumber) 的解释:
分为两个部分:
被除数 RecordInt mod ModNumber
除数 ModNumber div DivNumber
前者就是我想要获得的,对1000000取余之后的“随机”数——只有这样处理之后,CPU对
线程时间分配的不均匀性才能明显的显现出来,而不是几乎可以忽略的“高阶无穷小”;
后者其实就是您的
This_Random_Number * DivNumber
=> i = --------------------------------
Max_Random
中将DivNumber和MaxRandom放到分母中去的结果。
例如:
线程累加的结果是123456789——RecordInt,整除ModNumber(也就是Max_Random)
之后得到了456789。假设我们希望将结果分为200个区间,就需要将其再除以 ModNumber
div DivNumber 也就是 (1000000 div 200)——5000。最终的结果就是456789 div 5000,
即91。
如您所说,由于CPU对相同优先级的线程的时间分配差别极小,才导致了我的算法中不得
不将结果进行mod才能将差别放大到有明显“随机”的效果。我在程序中之所以采用最简单
的Inc(Ptr^)作为核心算法,就是为了最大限度的暴露它的缺点(“不幸”的是,尽管这样,
它们的时间差都在10^6个CPU周期的量级左右,也就是约1/1000秒。相比整个线程的运行
时间来说,这的确算不上什么,但就是这一点点误差在电脑这个无比精确的系统中实现了
真正的随机!)。如果将其改为Inc(Ptr^,一个足够大的质数),就可以很容易的增大结果
的散乱程度;如果更进一步,将其改为Inc(Ptr^,Random(MaxDWord)),最终结果将和线程
之间的交叉次序以及交叉的位置有直接的关系——甚至根本不用什么Randomize就可以生成
永远都无法预测或重现的随机数。
我的这个程序只是追求达到“无法预测”和“无法重现”的真正“随机”效果,至于效率
高低我并不是很关心——即使它只能产生0和1,只要它满足“随机”——没有人也永远不
可能有人(或者机器、操作系统)控制产生的结果就可以了。

>>任意一个线程受到线程轮循的机率可知, 因而可以计算出在单位时间中指定线程被轮循到的次数
这个“机率”就是一个随机因素。比如,全世界平均每秒钟出生N个婴儿——这是已知的。并且每个
国家的人口数也是已知的——但是你能说清楚过去的一分钟里每个国家都有多少人出生了吗?你可能
计算得出精确的数字吗?——你顶多得到一个大概的数字——剩下的就是不可预知的随机因素了。
>>每线程轮循的时间间隔可知,每次轮循分配的CPU时间片可知,每个时间片执行Inc(Ptr^)的次数可知
在CPU周期级的时间量级看来,操作系统,特别是像Windows这样的多任务操作系统并不是一个与世
隔绝的、完美的指令执行环境。除了用户的应用程序以外,还有很多的因素无时无刻不在影响指令的
执行——时钟中断、CPU Cache的命中与否、转移预测的成败、各种中断请求、I/O请求的执行等等。
这些事件本身可以说是微不足道,但是从长远看来,它们的影响就像气象学里的“蝴蝶效应”一样,
很有可能完全改变指令的执行过程。但是,这种影响一般不会被放大到毫秒级以上的时间尺度(也有
特殊情况,比如有关物理磁盘的I/O操作——一般都超过了毫秒级)——这个时间尺度是由操作系统的
内核控制——而这种“控制”是可以预测的。为了获得完全“不可预测”的效果,我们必须让触角
探测到毫秒级以下的时间量级——线程就是一个较为理想的工具。
我可以说,如果不能做到接近CPU时钟周期级的时间精度重现(或模拟)系统启动以来的所有中断的
发生、指令的执行、I/O操作发生的情况,就不可能精确的计算出操作系统中的某几个线程在某一段
特定的时间内的执行情况。——任何事件都有可能影响到操作系统中线程的执行!
>>在小范围内是有穷尽,这意味着可穷举的可能性很大
“可穷举性”和“随机性”的好坏有关系吗?例如洗牌程序中的随机数,只要具有“不可预测性”
即可,“可穷举性”毫无意义。
还有一点,就是一直都说计算机产生的“随机数”是“伪”随机的,为什么?因为这些算法几乎都是
遵循着一个有一定规律的、可预测的算法(Delphi或Pascal的Random就是最典型的例子)。
一句话——它们都是通过对极为有限的信息进行某种可能较为复杂的数学运算而得到的——其中实际
的信息量不会超过原始信息(即种子)。
采用这种实际上不是真正随机的随机数发生器,有很大的危险被破解——即使你采用毫秒级的机器
时间作为种子,还是有人能够通过时间同步或者反算种子来破解。而我的算法最简单,但它是根本无法
预测的——每个产生的随机数都包含了新的、无法预测的信息。
 

Similar threads

S
回复
0
查看
3K
SUNSTONE的Delphi笔记
S
S
回复
0
查看
2K
SUNSTONE的Delphi笔记
S
I
回复
0
查看
772
import
I
I
回复
0
查看
562
import
I
后退
顶部