原创 随机数算法

 ;==============================================================================
; 主    题: 线性叠加伪随机数函数
; 关 键 词: 随机数,8位单片机,random,8 bit mcu
; 参考资料: 1.<<Linear Congruential Pseudo-Random Number Generator Routines>>
;              by Bruce Clark, 7 Jun 2004
;           2.<<The Art Of Computer Programming, Volume 2>>
;              by Donald Knuth
; 作    者：ning 2006-9-21
;==============================================================================
    8位单片机很多地方需要随机数，比如游戏的洗牌，可在timer中取数，但是随机数质
量不高。随机数是一个既简单又复杂的问题,这里的例子使用了众所周知的线性叠加法，没
有完美的方法产生随机数，不过线性叠加法是一个合适的方法,彻底解决8位机随机数的问
题。
    伪随机数函数总是返回可预知的数字,像抛骰子，如果抛足够多次，那么我们得到了一
个足够长的数字序列，
    3,1,5,1,4,6,5,4,6,5,4,5,6,1,3,2,1,6,4,6,5,4,3,2,1,3,2,1,4,2,3,1,3......
    如果从序列中一个接一个的取出数字,那么数字就看似随机。
    问题的关键是从这序列的哪个点(数字)开始取数？这个开始的点(数字)叫做种子。
    注意，如果从相同的点(种子)开始，将会得到相同的数字,这是因为我们是从固定的序
列中取数字(所以叫伪随机)。但这却是一个有用的特性，我们可以每次从不同的点取数，即
改变种子！

    在6502上,8位或16位随机数是最常用的，函数返回一个32位的数字,范围0~2^32。名
词"线性叠加"听起来容易范晕, 其实只涉及二个内容:乘法和加法。三个步骤：
 1. 为了取得新的种子(也就是从序列开始的那个点的数字)，旧的种子和一个常数A相乘，
 2. 所得结果然后和第二个常数c相加。
 3. 新的种子是结果的低32位(记住,这个函数返回32位数字)。保留低32位很重要,用来获
    得下一个种子。

    计算公式:
    种子 = A * 种子 + C
 此公式在几何图中表示一条直线，而且新种子由旧种子反复相加得来，所以叫线性叠加。

    随机数函数的关键在于选择优秀的"常数A"(也叫乘数A),其实也就是选择了一个固定
的数字序列。"常数c",不像乘数A那样重要，但是它一定是个奇数。事实上， c可选1，而
且这是例程所使用的,因为它会简化计算。
    注意，奇数(旧的种子)乘奇数(乘数A)是奇数,再加奇数(常数c)将会是一个偶数；偶数
(旧的种子)乘奇数(乘数A),加奇数(常数c)将会是一个奇数。如此种子将会在奇数和偶数之
间转变。因为种子的变化足够随机，所以新种子的值可以作为8位或16位随机数。

    子程序F_RandomSeed，计算 "种子 = 乘数 * 种子+1" (记得,c=1)。有三个版本:

 (1) 快速版本, 速度快，但占用Rom多。
 (2) 兼顾版本，速度和占用Rom适中，空间和速度是在另外二个版本之间。
     兼顾版B， 使用了另一个神奇的数字66066(10进制).
 (3) 最小版本，速度慢，但占用Rom小。

    三个版本中使用的乘数1664525(10进制)=19660D(16进制),是从<<计算机程序的艺术,
第2册>>一书中选出，这是一个神奇的数字，经过论证和测试，这个数字对产生随机数至
关重要。想进一步研究的朋友可以阅读原著(参考资料2)，书中以特别专业的数学方法讨论
了随机数问题。这里只是应用了其中的两个常数1664525(10进制)和69069(10进制),这里不
作讨论，因为篇幅问题是借口，其实自己没弄懂。

;==============================================================================
; 快速版本
;==============================================================================

    丰收先要选好种子，育种很重要，同样，获得随机种子是重要的一步。

    种子变量设定在零页RAM可以提高速度。
    程序F_RandomSeed计算 1664525*种子，需要5个字节(R_Seed0~R_Seed3,R_Temp)。
    F_GeneratTables预先计算1664525*X(x=0~255),生成四个256字节的列表T3,T2,T1,T0.

 T3,X = 表T3的第X字节 = 1664525 * X的第31~24位(X = 0 to 255)
 T2,X = 表T2的第X字节 = 1664525 * X的第23~16位(X = 0 to 255)
 T1,X = 表T1的第X字节 = 1664525 * X的第15~ 8位(X = 0 to 255)
 T0,X = 表T0的第X字节 = 1664525 * X的第 7~ 0位(X = 0 to 255)

    对于单片机来说 使用1K RAM很夸张，也可以不用F_GeneratTables，直接把随机数表存
在ROM中。

;==============================================================================
; 伪随机数函数的线性叠加
; 计算 Seed = 1664525 * Seed + 1
;------------------------------------------------------------------------------
; 输入:
;   R_Seed0 <--- 种子0
;   R_Seed1 <--- 种子1
;   R_Seed2 <--- 种子2
;   R_Seed3 <--- 种子3
; 回返:
;   种子0 ---> R_Seed0
;   种子1 ---> R_Seed1
;   种子2 ---> R_Seed2
;   种子3 ---> R_Seed3
; 重写
;   R_Temp
;------------------------------------------------------------------------------
; 为提高速度R_Seed0，R_Seed1，R_Seed2，R_Seed3，R_Temp选零页Ram
; 每张列表从Rom地址 xx00h 处开始 或在Rom中
;------------------------------------------------------------------------------
; 空间: 程序58个字节
;       列表1024个字节
; 速度: 调用F_RandomSeed需要94个周期
;==============================================================================
F_RandomSeed:
         CLC                    ; 计算低32位:
         LDX    R_Seed0         ; 1664525*($100* R_Seed1+ R_Seed0)+1
         LDY    R_Seed1
         LDA    T0,X
         ADC    #1
         STA    R_Seed0
         LDA    T1,X
         ADC    T0,Y
         STA    R_Seed1
         LDA    T2,X
         ADC    T1,Y
         STA    R_Temp
         LDA    T3,X
         ADC    T2,Y
         TAY                    ; 把字节3留在Y中
         CLC                    ; 加低32位:
         LDX    R_Seed2         ; 1664525*($10000* R_Seed2)
         LDA    R_Temp
         ADC    T0,X
         STA    R_Seed2
         TYA
         ADC    T1,X
         CLC
         LDX    R_Seed3         ; 加低32位:
         ADC    T0,X            ; 1664525*($1000000* R_Seed3)
         STA    R_Seed3
         rts

;==============================================================================
; 产生T0，T1，T2和T3列表，使用F_GeneratTables，列表在ram中
;==============================================================================
F_GeneratTables:
         LDX    #0              ;1664525*0=0
         STX    T0
         STX    T1
         STX    T2
         STX    T3
         INX
         CLC
L_GT1:
         LDA    T0-1,X          ;把1664525加入
         ADC    #$0D            ;字节0
         STA    T0,X
         LDA    T1-1,X
         ADC    #$66            ;字节1
         STA    T1,X
         LDA    T2-1,X
         ADC    #$19            ;字节2
         STA    T2,X
         LDA    T3-1,X
         ADC    #$00            ;字节3
         STA    T3,X
         INX                    ;进位C=0退出
         BNE    L_GT1
         RTS

;------------------------------------------------------------------------------
; 生成的列表,如果不要F_GeneratTables，可以直接将此表放在Rom中
;------------------------------------------------------------------------------
;1664525 * X的第31~24位(X = 0 to 255)
T3:
 .DB $00,$00,$00,$00,$00,$00,$00,$00,$00,$00,$00,$01,$01,$01,$01,$01
 .DB $01,$01,$01,$01,$01,$02,$02,$02,$02,$02,$02,$02,$02,$02,$02,$03
 .DB $03,$03,$03,$03,$03,$03,$03,$03,$03,$04,$04,$04,$04,$04,$04,$04
 .DB $04,$04,$04,$05,$05,$05,$05,$05,$05,$05,$05,$05,$05,$06,$06,$06
 .DB $06,$06,$06,$06,$06,$06,$06,$07,$07,$07,$07,$07,$07,$07,$07,$07
 .DB $07,$08,$08,$08,$08,$08,$08,$08,$08,$08,$08,$09,$09,$09,$09,$09
 .DB $09,$09,$09,$09,$09,$0A,$0A,$0A,$0A,$0A,$0A,$0A,$0A,$0A,$0A,$0B
 .DB $0B,$0B,$0B,$0B,$0B,$0B,$0B,$0B,$0B,$0C,$0C,$0C,$0C,$0C,$0C,$0C
 .DB $0C,$0C,$0C,$0C,$0D,$0D,$0D,$0D,$0D,$0D,$0D,$0D,$0D,$0D,$0E,$0E
 .DB $0E,$0E,$0E,$0E,$0E,$0E,$0E,$0E,$0F,$0F,$0F,$0F,$0F,$0F,$0F,$0F
 .DB $0F,$0F,$10,$10,$10,$10,$10,$10,$10,$10,$10,$10,$11,$11,$11,$11
 .DB $11,$11,$11,$11,$11,$11,$12,$12,$12,$12,$12,$12,$12,$12,$12,$12
 .DB $13,$13,$13,$13,$13,$13,$13,$13,$13,$13,$14,$14,$14,$14,$14,$14
 .DB $14,$14,$14,$14,$15,$15,$15,$15,$15,$15,$15,$15,$15,$15,$16,$16
 .DB $16,$16,$16,$16,$16,$16,$16,$16,$17,$17,$17,$17,$17,$17,$17,$17
 .DB $17,$17,$18,$18,$18,$18,$18,$18,$18,$18,$18,$18,$19,$19,$19,$19

;1664525 * X的第23~16位(X = 0 to 255)
T2:
 .DB $00,$19,$32,$4C,$65,$7E,$98,$B1,$CB,$E4,$FD,$17,$30,$4A,$63,$7C
 .DB $96,$AF,$C9,$E2,$FB,$15,$2E,$48,$61,$7A,$94,$AD,$C7,$E0,$F9,$13
 .DB $2C,$46,$5F,$78,$92,$AB,$C5,$DE,$F7,$11,$2A,$44,$5D,$76,$90,$A9
 .DB $C3,$DC,$F5,$0F,$28,$42,$5B,$74,$8E,$A7,$C1,$DA,$F3,$0D,$26,$40
 .DB $59,$72,$8C,$A5,$BF,$D8,$F1,$0B,$24,$3E,$57,$70,$8A,$A3,$BD,$D6
 .DB $EF,$09,$22,$3C,$55,$6E,$88,$A1,$BB,$D4,$ED,$07,$20,$3A,$53,$6C
 .DB $86,$9F,$B9,$D2,$EB,$05,$1E,$38,$51,$6A,$84,$9D,$B7,$D0,$E9,$03
 .DB $1C,$36,$4F,$68,$82,$9B,$B5,$CE,$E7,$01,$1A,$34,$4D,$66,$80,$99
 .DB $B3,$CC,$E5,$FF,$18,$32,$4B,$64,$7E,$97,$B1,$CA,$E3,$FD,$16,$30
 .DB $49,$62,$7C,$95,$AE,$C8,$E1,$FB,$14,$2D,$47,$60,$7A,$93,$AC,$C6
 .DB $DF,$F9,$12,$2B,$45,$5E,$78,$91,$AA,$C4,$DD,$F7,$10,$29,$43,$5C
 .DB $76,$8F,$A8,$C2,$DB,$F5,$0E,$27,$41,$5A,$74,$8D,$A6,$C0,$D9,$F3
 .DB $0C,$25,$3F,$58,$72,$8B,$A4,$BE,$D7,$F1,$0A,$23,$3D,$56,$70,$89
 .DB $A2,$BC,$D5,$EF,$08,$21,$3B,$54,$6E,$87,$A0,$BA,$D3,$ED,$06,$1F
 .DB $39,$52,$6C,$85,$9E,$B8,$D1,$EB,$04,$1D,$37,$50,$6A,$83,$9C,$B6
 .DB $CF,$E9,$02,$1B,$35,$4E,$68,$81,$9A,$B4,$CD,$E7,$00,$19,$33,$4C

;1664525 * X的第15~ 8位(X = 0 to 255)
T1:
 .DB $00,$66,$CC,$32,$98,$FE,$64,$CA,$30,$96,$FC,$62,$C8,$2E,$94,$FA
 .DB $60,$C6,$2C,$92,$F9,$5F,$C5,$2B,$91,$F7,$5D,$C3,$29,$8F,$F5,$5B
 .DB $C1,$27,$8D,$F3,$59,$BF,$25,$8B,$F2,$58,$BE,$24,$8A,$F0,$56,$BC
 .DB $22,$88,$EE,$54,$BA,$20,$86,$EC,$52,$B8,$1E,$84,$EB,$51,$B7,$1D
 .DB $83,$E9,$4F,$B5,$1B,$81,$E7,$4D,$B3,$19,$7F,$E5,$4B,$B1,$17,$7E
 .DB $E4,$4A,$B0,$16,$7C,$E2,$48,$AE,$14,$7A,$E0,$46,$AC,$12,$78,$DE
 .DB $44,$AA,$10,$77,$DD,$43,$A9,$0F,$75,$DB,$41,$A7,$0D,$73,$D9,$3F
 .DB $A5,$0B,$71,$D7,$3D,$A3,$09,$70,$D6,$3C,$A2,$08,$6E,$D4,$3A,$A0
 .DB $06,$6C,$D2,$38,$9E,$04,$6A,$D0,$36,$9C,$03,$69,$CF,$35,$9B,$01
 .DB $67,$CD,$33,$99,$FF,$65,$CB,$31,$97,$FD,$63,$C9,$2F,$95,$FC,$62
 .DB $C8,$2E,$94,$FA,$60,$C6,$2C,$92,$F8,$5E,$C4,$2A,$90,$F6,$5C,$C2
 .DB $28,$8E,$F5,$5B,$C1,$27,$8D,$F3,$59,$BF,$25,$8B,$F1,$57,$BD,$23
 .DB $89,$EF,$55,$BB,$21,$88,$EE,$54,$BA,$20,$86,$EC,$52,$B8,$1E,$84
 .DB $EA,$50,$B6,$1C,$82,$E8,$4E,$B4,$1A,$81,$E7,$4D,$B3,$19,$7F,$E5
 .DB $4B,$B1,$17,$7D,$E3,$49,$AF,$15,$7B,$E1,$47,$AD,$13,$7A,$E0,$46
 .DB $AC,$12,$78,$DE,$44,$AA,$10,$76,$DC,$42,$A8,$0E,$74,$DA,$40,$A6

;1664525 * X的第 7~ 0位(X = 0 to 255)
T0:
 .DB $00,$0D,$1A,$27,$34,$41,$4E,$5B,$68,$75,$82,$8F,$9C,$A9,$B6,$C3
 .DB $D0,$DD,$EA,$F7,$04,$11,$1E,$2B,$38,$45,$52,$5F,$6C,$79,$86,$93
 .DB $A0,$AD,$BA,$C7,$D4,$E1,$EE,$FB,$08,$15,$22,$2F,$3C,$49,$56,$63
 .DB $70,$7D,$8A,$97,$A4,$B1,$BE,$CB,$D8,$E5,$F2,$FF,$0C,$19,$26,$33
 .DB $40,$4D,$5A,$67,$74,$81,$8E,$9B,$A8,$B5,$C2,$CF,$DC,$E9,$F6,$03
 .DB $10,$1D,$2A,$37,$44,$51,$5E,$6B,$78,$85,$92,$9F,$AC,$B9,$C6,$D3
 .DB $E0,$ED,$FA,$07,$14,$21,$2E,$3B,$48,$55,$62,$6F,$7C,$89,$96,$A3
 .DB $B0,$BD,$CA,$D7,$E4,$F1,$FE,$0B,$18,$25,$32,$3F,$4C,$59,$66,$73
 .DB $80,$8D,$9A,$A7,$B4,$C1,$CE,$DB,$E8,$F5,$02,$0F,$1C,$29,$36,$43
 .DB $50,$5D,$6A,$77,$84,$91,$9E,$AB,$B8,$C5,$D2,$DF,$EC,$F9,$06,$13
 .DB $20,$2D,$3A,$47,$54,$61,$6E,$7B,$88,$95,$A2,$AF,$BC,$C9,$D6,$E3
 .DB $F0,$FD,$0A,$17,$24,$31,$3E,$4B,$58,$65,$72,$7F,$8C,$99,$A6,$B3
 .DB $C0,$CD,$DA,$E7,$F4,$01,$0E,$1B,$28,$35,$42,$4F,$5C,$69,$76,$83
 .DB $90,$9D,$AA,$B7,$C4,$D1,$DE,$EB,$F8,$05,$12,$1F,$2C,$39,$46,$53
 .DB $60,$6D,$7A,$87,$94,$A1,$AE,$BB,$C8,$D5,$E2,$EF,$FC,$09,$16,$23
 .DB $30,$3D,$4A,$57,$64,$71,$7E,$8B,$98,$A5,$B2,$BF,$CC,$D9,$E6,$F3

;==============================================================================
;  最小版本
;==============================================================================

    对于单片机来说，使用1K RAM或rom来完成一个随机数，是很浪费的，以下是最小版本，
但是程序执行周期长。程序每次计算所需要的列表值。

;==============================================================================
; 线性叠加伪随机数函数
; 计算 R_Seed=1664525 * R_Seed + 1
;------------------------------------------------------------------------------
; 输入:
;   R_Seed0 <--- 种子0
;   R_Seed1 <--- 种子1
;   R_Seed2 <--- 种子2
;   R_Seed3 <--- 种子3
; 回返:
;   种子0 ---> R_Seed0
;   种子1 ---> R_Seed1
;   种子2 ---> R_Seed2
;   种子3 ---> R_Seed3
; 重写
;   R_Temp,R_Temp+1,R_Temp+2,R_Temp+3
; 注意
;   R_Temp~R_Temp+3 和 L_Rand6 是高字节在前,低字节在后
;------------------------------------------------------------------------------
; 空间: 53个字节
; 速度: 调用F_RandomSeed平均2744个周期
;       1624+70* N(N=种子数) =  1624~3864个周期
;==============================================================================
F_RandomSeed:
         LDA    #1              ; R_Temp=1，需要给定初始值
         LDX    #3
L_Rand1  STA    R_Temp,X
         LSR
         DEX
         BPL    L_Rand1
         LDY    #$20            ; 计算种子 = 种子 * L_Rand4+ R_Temp
         BNE    L_Rand5         ; 总是分支
L_Rand2  BCC    L_Rand4         ; 如果零被移位，分支
         CLC                    ; 把乘数加入乘积
         LDX    #3
L_Rand3  LDA    R_Temp,X
         ADC    T_Rand6,X       ;源码有误，已改正
         STA    R_Temp,X
         DEX
         BPL    L_Rand3
L_Rand4  ROR    R_Temp          ; 右移结果
         ROR    R_Temp+1
         ROR    R_Temp+2
         ROR    R_Temp+3
L_Rand5  ROR    R_Seed3         ; 右移种子
         ROR    R_Seed2
         ROR    R_Seed1
         ROR    R_Seed0
         DEY
         BPL    L_Rand2
         RTS

T_Rand6    .DB  $00,$19,$66,$0D ;乘数(高字节在前)

;==============================================================================
;  兼顾版本 乘数1664525(10进制)
;==============================================================================

    兼顾版本 是不用上面的循环加来做乘法，而是在必要的时候加上 种子,$100* 种子,
$10000* 种子,来获得数字序列，这样能够提高速度，又不增加太多代码。

    分解公式表

       b7 b6 b5 b4 b3 b2 b1 b0
  $0D = 0  0  0  0  1  1  0  1 b    ---> +种子
  $66 = 0  1  1  0  0  1  1  0 b    ---> *$100h
  $19 = 0  0  0  1  1  0  0  1 b    ---> *$10000h
  $00 = 0  0  0  0  0  0  0  0 b    --->
        |  |  |  |  |  |  |  |
        |  |  |  |  |  |  |  |
        V  V  V  V  V  V  V  V
          左 左 左 左 左 左
          移 移 移 移 移 移
          6  5  4  3  2  1
          位 位 位 位 位 位

那么 种子*bit0 时，种子*$10000+种子
     种子*bit1 时，种子*$100，      左移1位
     种子*bit2 时，种子*$100+种子， 左移2位
     种子*bit3 时，种子*$10000+种子，左移3位
     种子*bit4 时，种子*$10000，    左移4位
     种子*bit5 时，种子*$100，      左移5位
     种子*bit6 时，种子*$100，      左移6位

;==============================================================================
; 伪随机数函数的线性叠加
; 计算 R_Seed=1664525 * R_Seed + 1
;------------------------------------------------------------------------------
; 输入:
;   R_Seed0 <--- 种子0
;   R_Seed1 <--- 种子1
;   R_Seed2 <--- 种子2
;   R_Seed3 <--- 种子3
; 回返:
;   种子0 ---> R_Seed0
;   种子1 ---> R_Seed1
;   种子2 ---> R_Seed2
;   种子3 ---> R_Seed3
; 重写
;   R_Temp,R_Temp+1,R_Temp+2,R_Temp+3
;-------------------------------------------------------------------------------
;   空间: 106个字节
;   速度: F_RandomSeed 517个周期
;===============================================================================
F_RandomSeed:
         CLC                    ; 复制种子进入R_Temp
         LDA    R_Seed0         ; 计算 种子 = 种子 *$10000+ 种子 +1
         STA    R_Temp
         ADC    #1
         STA    R_Seed0
         LDA    R_Seed1
         STA    R_Temp+1
         ADC    #0
         STA    R_Seed1
         LDA    R_Seed2
         STA    R_Temp+2
         ADC    R_Temp
         STA    R_Seed2
         LDA    R_Seed3
         STA    R_Temp+3
         ADC    R_Temp+1
         STA    R_Seed3
;-------------------------------------------------
;因为$0019660D 的Bit7=0，所以只需6次移位
;-------------------------------------------------
         LDY    #5
L_Rand1  ASL    R_Temp          ; 左移旧的种子
         ROL    R_Temp+1
         ROL    R_Temp+2
         ROL    R_Temp+3
;-------------------------------------------------
; 从 L_Rand4 列表取得 X, 4个索引值对应4种情况，数值选的巧妙！
; X=$00, 种子 = 种子 +$10000* R_Temp
; X=$01, 种子 = 种子 +$100  * R_Temp
; X=$FE, 种子 = 种子 +$10000* R_Temp+ R_Temp
; X=$FF, 种子 = 种子 +$100  * R_Temp+ R_Temp
;-------------------------------------------------
         LDX    L_Rand4,Y
         BPL    L_Rand2         ; 分支如果 X=$00 或 X=$01
         CLC                    ; 种子 = 种子 +R_Temp
         LDA    R_Seed0
         ADC    R_Temp
         STA    R_Seed0
         LDA    R_Seed1
         ADC    R_Temp+1
         STA    R_Seed1
         LDA    R_Seed2
         ADC    R_Temp+2
         STA    R_Seed2
         LDA    R_Seed3
         ADC    R_Temp+3
         STA    R_Seed3
         INX                    ; $ FE->$00,$ FF->$01
         INX
L_Rand2  CLC
         BEQ    L_Rand3         ; 如果 X=$00, 种子 =种子 + R_Temp*$10000
         LDA    R_Seed1         ; 种子 = 种子 + R_Temp*$100
         ADC    R_Temp
         STA    R_Seed1
L_Rand3  LDA    R_Seed2
         ADC    R_Temp,X
         STA    R_Seed2
         LDA    R_Seed3
         ADC    R_Temp+1,X
         STA    R_Seed3
         DEY
         BPL    L_Rand1
         RTS

L_Rand4    .DB  $01,$01,$00,$FE,$FF,$01

;==============================================================================
;  改进的 兼顾版本B 选择新的 乘数=69069(10进制)
;==============================================================================

    兼顾版本B中, 用69069(10进制)替换1664525(10进制)作乘数,也就是说，选择了另外一
个数字序列，这个乘数也是<<计算机程序的艺术,第2册>>一书中选出，经过论证和测试，
这个数字虽不及1664525做乘数好，但也是个神奇的数字,而且可以进一步减小程序时间。

;===============================================================================
; 伪随机数函数的线性叠加
; 计算种子 = 种子 * 69069 + 1
;-------------------------------------------------------------------------------
; 输入:
;   R_Seed0 <--- 种子0
;   R_Seed1 <--- 种子1
;   R_Seed2 <--- 种子2
;   R_Seed3 <--- 种子3
; 回返:
;   种子0 ---> R_Seed0
;   种子1 ---> R_Seed1
;   种子2 ---> R_Seed2
;   种子3 ---> R_Seed3
; 重写
;   R_Temp,R_Temp+1,R_Temp+2,R_Temp+3
;--------------------------------------------------------------------------------
;   空间: 173个字节
;   速度: F_RandomSeed 326个周期
;================================================================================
F_RandomSeed:
         LDA    R_Seed0         ; R_Temp= 种子 *2
         ASL
         STA    R_Temp
         LDA    R_Seed1
         ROL
         STA    R_Temp+1
         LDA    R_Seed2
         ROL
         STA    R_Temp+2
         LDA    R_Seed3
         ROL
         STA    R_Temp+3
         CLC                    ; R_Temp= R_Temp+ 种子 (= 种子 *3)
         LDA    R_Seed0
         ADC    R_Temp
         STA    R_Temp
         LDA    R_Seed1
         ADC    R_Temp+1
         STA    R_Temp+1
         LDA    R_Seed2
         ADC    R_Temp+2
         STA    R_Temp+2
         LDA    R_Seed3
         ADC    R_Temp+3
         STA    R_Temp+3
         CLC                    ; 种子 = 种子 +$10000* 种子
         LDA    R_Seed2
         ADC    R_Seed0
         TAX                    ; 把字节2保存在X中(利于提高速度)
         LDA    R_Seed3
         ADC    R_Seed1
         TAY                    ; 把字节3保存在Y中
         CLC                    ; 种子 = 种子 +$100* 种子
         LDA    R_Seed1
         ADC    R_Seed0
         PHA                    ; 压入堆栈字节1
         TXA
         ADC    R_Seed1
         TAX
         TYA
         ADC    R_Seed2
         TAY
         LDA    R_Temp          ; R_Temp= R_Temp*4(= 旧种子 *$0C)
         ASL
         ROL    R_Temp+1
         ROL    R_Temp+2
         ROL    R_Temp+3
         ASL
         ROL    R_Temp+1
         ROL    R_Temp+2
         ROL    R_Temp+3
         STA    R_Temp
         CLC                    ; 种子 = 种子 +R_Temp
         ADC    R_Seed0
         STA    R_Seed0
         PLA                    ; 弹出堆栈的字节1
         ADC    R_Temp+1
         STA    R_Seed1
         TXA
         ADC    R_Temp+2
         TAX
         TYA
         ADC    R_Temp+3
         TAY
         CLC
         LDA    R_Temp          ; 种子 = 种子 + R_Temp*$100
         ADC    R_Seed1
         STA    R_Seed1
         TXA
         ADC    R_Temp+1
         TAX
         TYA
         ADC    R_Temp+2
         TAY
         LDA    R_Temp          ; R_Temp= R_Temp*$10(= 旧的种子 *$C0)
         ASL                    ; 置R_Temp字节0到A
         ROL    R_Temp+1
         ROL    R_Temp+2
         ROL    R_Temp+3
         ASL
         ROL    R_Temp+1
         ROL    R_Temp+2
         ROL    R_Temp+3
         ASL
         ROL    R_Temp+1
         ROL    R_Temp+2
         ROL    R_Temp+3
         ASL
         ROL    R_Temp+1
         ROL    R_Temp+2
         ROL    R_Temp+3
         SEC                    ; 种子 = 种子 +R_Temp+1
         ADC    R_Seed0
         STA    R_Seed0
         LDA    R_Temp+1
         ADC    R_Seed1
         STA    R_Seed1
         TXA
         ADC    R_Temp+2
         STA    R_Seed2
         TYA
         ADC    R_Temp+3
         STA    R_Seed3
         RTS

    以上的两个兼顾版本，已经是实用的程序，R_Seed3,R_Seed2本身就可作随机数使用，
用户可以自己完成 0~2^32 范围随机，解决 不是2的倍数范围的几率微小不均等问题。但
还是忍不住要接着说...

;==============================================================================
; 调用F_RandomSeed函数
;==============================================================================

    好了，我们有了好种子，比如杂交水稻或玉米，就要播种和收获了。有时间我会写一本
农业方面的书，比如中国农业史，或世界农业概况，跑题了......
    现在我们已经有了实用的F_RandomSeed子程序，如何调用它，产生任意范围的随机数。

 随机数在 0~  255($FF)  之间,使用R_Seed3。
 随机数在 0~65535($FFFF)之间,使用R_Seed2作为低的字节,R_Seed3作为高的字节
 随机数在 0~1           之间,使用R_Seed3的Bit7
 随机数在 0~3           之间,使用R_Seed3的Bit6,Bit7
 随机数在 0~7           之间,使用R_Seed3的Bit5~Bit7.....

 随机数在 0~2^n         之间,比较容易获得，但是
 随机数在 0~5           之间,怎么办?

   解决的方法是种子(32Bit)乘6(5加1)，变成40位，高8位保存在A中,A中就是0~5的随机数

    产生任意随机数的程序有8bit和16bit两个版本，分别是F_Random8,F_Random16

;==============================================================================
; 线性叠加伪随机数函数
; 取得种子并且获得来自它的一个8位的随机数
; 调用F_RandomSeed子程序
;------------------------------------------------------------------------------
; 输入:
;   A <--- 范围上限
; 输出:
;   A ---> 随机数 (0<= 随机数<范围上限)
; 重写
;   R_Mod,R_Temp,R_Temp+1,R_Temp+2
; 注意
;   在调用F_RandomSeed之后，R_Temp~R_Temp+2的内容被改写
;============================================================================
F_Random8:
         STA    R_Mod           ; 保存随机范围到R_Mod
         JSR    F_RandomSeed    ; 取得下个种子
         LDA    #0              ; 种子乘R_Mod
         STA    R_Temp+2
         STA    R_Temp+1
         STA    R_Temp
         SEC
         ROR    R_Mod           ; 移出R_Mod，将循环8次
L_R8A
         BCC    L_R8B           ; 如果c=0,分支
         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
;--------------------------------------------------------------------------------