📄 randomicity.txt
字号:
CLC ; 加上种子,保存高8位到A
TAX
LDA R_Temp
ADC R_Seed0
STA R_Temp
LDA R_Temp+1
ADC R_Seed1
STA R_Temp+1
LDA R_Temp+2
ADC R_Seed2
STA R_Temp+2
TXA
ADC R_Seed3
L_R8B
ROR ; 乘积右移
ROR R_Temp+2
ROR R_Temp+1
ROR R_Temp
LSR R_Mod ; 直到所有8位的R_Mod已经循环移出
BNE L_R8A
RTS
这里是任意16位随机数版本,F_RandomSeed16
;==============================================================================
; 线性叠加伪随机数函数
; 取得下一个种子并且获得来自它的一个16位的随机数
; 需要F_RandomSeed子程序
;-------------------------------------------------------------------------------
; 输入:
; R_Mod,R_Mod+1 <--- 随机数范围
; 输出:
; R_Rnd,R_Rnd+1 ---> 0 <= 随机数 < R_Mod+1,R_Mod
; 重写
; R_Temp
;===============================================================================
F_Random16
JSR F_RandomSeed ; 取得下个种子
LDA #0 ; 种子乘R_Mod
STA R_Rnd+1
STA R_Rnd
STA R_Temp
LDY #16
L_R16A LSR R_Mod+1 ; 移出R_Mod，将循环16次
ROR R_Mod
BCC L_R16B ; 如果c=0,分支
CLC ; 加上种子,保存乘积高16位到R_Rnd，R_Rnd+1
ADC R_Seed0
TAX
LDA R_Temp
ADC R_Seed1
STA R_Temp
LDA R_Rnd
ADC R_Seed2
STA R_Rnd
LDA R_Rnd+1
ADC R_Seed3
STA R_Rnd+1
TXA
L_R16B ROR R_Rnd+1 ; 乘积右移
ROR R_Rnd
ROR R_Temp
ROR
DEY
BNE L_R16A
RTS
因为种子有2^32可能的值，当范围是2^n(n=1,2,3,..,32)时,所有的可能值，产生的几
率均等，然而,用6举例来说，却存在非常小的几率不均等性，因为 2^32 不是 6 的倍数。
但是 2^32 - 4 是 6 倍数,解决的方法是,剔除种子的四个值，再次调用F_RandomSeed。因
因为只有四个值从 2^32中剔除,它的可能性十分小，最多二次连续的种子值被剔除，调用
两次F_RandomSeed。优秀的数字序列确实如此。
问题是剔除哪4个值?为了要回答这一问题, 一个较简单的例子,4位的种子，范围上限=7,调用
16-2次F_RandomSeed后表现出多样性。 因为只有16种可能的值,所有的列出了所有的数，
连同对应的 种子*范围上限 一起。
种子 种子*7
---- --------
0000 000 0000 --->剔除
0001 000 0111 --->
0010 000 1110 --->
0011 001 0101
0100 001 1100
0101 010 0011
0110 010 1010
0111 011 0001 --->剔除
1000 011 1000 --->
1001 011 1111 --->
1010 100 0110
1011 100 1101
1100 101 0100
1101 101 1011
1110 110 0010
1111 110 1001
^
|
随机数0~6
上面的随机数高3位(种子*范围上限),0和3发生三次，而且其余发生两次。 注意低4位(种子
*范围上限)，当高3位是 000 或 011，低4位小于2的种子剔除。有二个方法决定种子的取舍
(a)如果 种子低位*范围上限 小于种子值,剔除此数字，
或者
(b)如果 低位大于或等于16-种子值，剔除此数。
后者因为它能更快速地被实现，所以使用次方法。对于 32 位的情形，检查种子的低
32位*范围上限的乘积 是否小于 （2^32-种子），判断是否剔除。
唯一的剩余问题是, 多少种子值应该被剔除? 这能由 2^32/范围上限（随机数范围）计算。除
法的余数就是要剔除的种子数。
这部分的子程序返回的随机数几率均衡，所以叫 F_URandom 。返回的随机数，R_Rnd,
范围0<= R_Rnd< R_Mod 之间。 有二个版本, （1）对于8位的R_Rnd和R_Mod,（2）对于16位
的R_Rnd和R_Mod。
8位的版本,叫做 F_URandom8
;==============================================================================
; 伪随机数函数的线性叠加
; 取得下种子并且获得来自它的8位随机数
; 需要F_RandomSeed子程序
;------------------------------------------------------------------------------
; 输入:
; A <--- 随机数范围
; 输出:
; A ---> 随机数 0<= 随机数 < 范围
; 重写
; R_Mod,R_Rem,R_Temp,R_Temp+1,R_Temp+2,R_Temp+3
;===============================================================================
F_URandom8
STA R_Mod ; 保存随机数范围
LDX #32 ; 计算 2^32/R_Mod的余数
LDA #1
BNE L_UR8B
L_UR8A ASL ; 被除数左移
BCS L_UR8C ; c=1 分支
L_UR8B CMP R_Mod
BCC L_UR8D ; 如果部分被除数 <R_Mod 分支
L_UR8C SBC R_Mod ; 减去R_Mod
L_UR8D DEX
BPL L_UR8A
STA R_Rem ; 保存余数到R_Rem
L_UR8E JSR F_RandomSeed
LDA #0 ; 种子*R_Mod
STA R_Temp+3
STA R_Temp+2
STA R_Temp+1
STA R_Temp
LDY R_Mod ; 保存R_Mod到Y
SEC
ROR R_Mod ; 右移一位(循环8次)
L_UR8F BCC L_UR8G ; c=0 ，分支
CLC ; 加种子到R_Temp
TAX
LDA R_Temp
ADC R_Seed0
STA R_Temp
LDA R_Temp+1
ADC R_Seed1
STA R_Temp+1
LDA R_Temp+2
ADC R_Seed2
STA R_Temp+2
LDA R_Temp+3
ADC R_Seed3
STA R_Temp+3
TXA
L_UR8G ROR R_Temp+3 ; 乘积右移
ROR R_Temp+2
ROR R_Temp+1
ROR R_Temp
ROR
LSR R_Mod ; 直到所有8位的R_Mod都移出
BNE L_UR8F
CLC ; 把余数加入乘积
ADC R_Rem
BCC L_UR8H ; 如果没有8位进位，分支
INC R_Temp ; 乘积字节1 加1
BNE L_UR8H ; 如果没有16位进位，分支
INC R_Temp+1 ; 乘积字节2 加1
BNE L_UR8H ; 如果没有24位进位，分支
INC R_Temp+2 ; 乘积字节2 加1
STY R_Mod ; 保存R_Mod (不影响Z标志!)
BEQ L_UR8E ; 如果32位进位，分支
L_UR8H LDA R_Temp+3 ; 乘积高8位，返回A
RTS
这里是 F_URandom 的 16 位版本,叫做了 F_URandom16。
;==============================================================================
; 伪随机数函数的线性叠加
; 取得下种子并且获得来自它的16位的随机数
; 需要F_RandomSeed子程序
;------------------------------------------------------------------------------
; 输入:
; MOD=modulus
; 输出:
; R_Rnd= random number,0<= R_Rnd< R_Mod
; 重写
; R_RemH,R_RemL,TEMP,R_Temp,R_Temp+1,R_Temp+2 和 R_Temp+3
;==============================================================================
F_URandom16
LDX #32 ; 计算 2^32/R_Mod
LDA #0
STA R_RemH
SEC ; 准备移位
L_UR16A ROL ; 被除数左移
ROL R_RemH
BCS L_UR16B ; 如果移出1，分支
TAY ; 比较部分被除数和R_Mod
CMP R_Mod
LDA R_RemH
SBC R_Mod +1
TYA
BCC L_UR16C ; 如果部分被除数 <R_Mod，分支
L_UR16B SBC R_Mod ; 减去R_Mod (计算余数)
TAY
LDA R_RemH
SBC R_Mod +1
STA R_RemH
TYA
CLC
L_UR16C DEX
BPL L_UR16A
STA R_RemL ; 储存余数低字节 R_Rem
LDA R_Mod +1 ; 储存R_Mod高字节
STA TEMP
L_UR16D JSR F_RandomSeed
LDA R_Mod ; 储存R_Mod低字节到R_Temp+3
STA R_Temp+3
LDA #0 ; 种子乘R_Mod
STA R_Rnd+1
STA R_Rnd
STA R_Temp+2
STA R_Temp+1
LDY #16
L_UR16E LSR R_Mod+1 ; 右移
ROR R_Mod
BCC L_UR16F ; 如果零被移出，分支
CLC ; 增加种子,保存乘积高16位到 R_Rnd
TAX
LDA R_Temp+1
ADC R_Seed0
STA R_Temp+1
LDA R_Temp+2
ADC R_Seed1
STA R_Temp+2
LDA R_Rnd
ADC R_Seed2
STA R_Rnd
LDA R_Rnd+1
ADC R_Seed3
STA R_Rnd+1
TXA
L_UR16F ROR R_Rnd+1 ; 乘积右移
ROR R_Rnd
ROR R_Temp+2
ROR R_Temp+1
ROR R_Temp
ROR
DEY
BNE L_UR16E
CLC ; 把余数加入乘积
ADC R_RemL
LDA R_Temp
ADC R_RemH
BCC L_UR16G ; 如果没有16位进位，分支
INC R_Temp+1 ; 乘积的字节2，加1
BNE L_UR16G ; 如果没有24位进位，分支
LDA R_Temp+3 ; 保存R_Mod
STA R_Mod
LDA TEMP
STA R_Mod +1
INC R_Temp+2 ; 乘积的字节3，加1
BEQ L_UR16D ; 如果32位进位，分支
L_UR16G RTS
;=============================================================================
8位单片机随机数问题解决了，但是新的问题又来了，
1. 因为最初开始的种子是 00000000hex，刚开始几次的随机数不理想，调用多少次后，随
机数才表现出理想效果？ (4 bit 16-2次后，32bit 多少次后？）
2. 两个神奇的数字，1664525(10进制)和69069(10进制)是如何得到的？用这个数产生的数
字序列是否是最完美的？是否有更完美的数字？如何得出？
3. 种子从00000000hex开始，调用多少次F_RandomSeed后，种子是否可以回到00000000hex?
种子从00000000hex开始，调用2^32次后，种子回零，是否有这样的神奇系数和列表？
理论上，使用例子的最快版本，调用F_RandomSeed 2^32次，用4M 主频单片机，0.5uS
一条指令速度，全速运行，大约需要56.07小时。以上的例子都经过6502 simulator V1.1.9.21
测试。最多运行了40分钟，没有发现种子全部回零。
有人能够论证或测试以上的问题吗？
喂！数学或编程的各路英雄，谁敢接招？
;--------------------------------------------------------------------------------
; end of the file 2006-09-23
;--------------------------------------------------------------------------------⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -