Omnimaga
Calculator Community => TI Calculators => ASM => Topic started by: Xeda112358 on April 20, 2015, 09:48:20 am
-
EDIT:23-June-2015 Runer took a look at my LFSR code and suggested changing it to a Galois LFSR using the inverted mask and the code is much simpler.
I have a bunch of Pseudo-Random Number Generators (PRNGs), so instead of spamming the Optimized Routines topic, I'll post here until I have it all sorted out.
So this is my most recent work and I think zillions times better than previous work. It has a period of 4,294,901,760 (65536*65535) and takes a tiny 308cc in the worst case. It passes a chaos game test that I wrote, it is very nicely distributed (mostly uniform, but not *exactly* so). As a comparison, I wrote a Combined LCG that had a fairly long period (on a similar scale to this), but it took ~1500cc, and yesterday I realized that it might not touch a dust of numbers on it's range (this depends on the upper bound for prime gaps since it used multiplication, and a modulus [which may have remedied the multiplication]).
So the method I chose was to use a Lehmer RNG which is a special case LCG (Linear Congruential Generator) that had a period of 65536 (75*seed mod 65537 ->seed) and a 16-bit LFSR (Linear Feedback Shift Register) with maximal period, so 65535. I then add the two. The whole process cycles every gcd(65535,65536) iterations. However, since they are consecutive integers, they are coprime, so the cycle is of length 65536*65535.
Now I will give all three PRNGs -- the Lehmer RNG, which is pretty good on its own, the LFSR which is very fast, and the combined PRNG:
lehmer:
;;Input:
;; (seed) has the seed value of the RNG
;;Output:
;; (seed) is updated, HL is the result
;;Destroys:
;; A,DE,BC
;;Timing:
;; if seed>0 231cc or 232cc, condition dependent
;; if seed=0 91cc
;; if smc=1 subtract 6cc
;;Size: 44 bytes
;;Notes:
;; Uses the Lehmer RNG used by the Sinclair ZX81
;; 75x mod 65537 -> x
;; 0 is never a possibility, but 65536, the maximum value, is. I encode 65536 as 0, so the seed is only 2 bytes.
#IF smc == 0
ld hl,(seed)
#ELSE
seed = $+1
ld hl,0
#ENDIF
;multiply by 75
ld c,l
ld b,h
xor a
adc hl,hl \ jr z,special \ ld d,a \ rla
add hl,hl \ rla
add hl,hl \ rla \ add hl,bc \ adc a,d
add hl,hl \ rla
add hl,hl \ rla \ add hl,bc \ adc a,d
add hl,hl \ rla \ add hl,bc
;modulo 65537, see note below on how this works
ld e,a
sbc hl,de
jr nc,$+3
inc hl
ld (seed),hl
ret
special:
;In the case that HL=0, this should be interpreted as 65536 = -1 mod 65537, so return -75 mod 65537 = -74 mod 65536 in HL
ld hl,-74
ld (seed),hl
ret
;mod by 2^16 + 1 (a prime)
;current form is A*2^16+HL
;need:
; (A*2^16+HL) mod (2^16+1)
;add 0 as +1-1
; (A*(2^16+1-1)+HL) mod (2^16+1)
;distribute
; (A*(2^16+1)-A+HL) mod (2^16+1)
;A*(2^16+1) mod 2^16+1 = 0, so remove
; (-A+HL) mod (2^16+1)
;Oh hey, that's easy! :P
;I use this trick everywhere, you should, too.
smc=1
LFSR16:
;;Input: (seed1) is non-zero
;;Output: (seed1) updated, HL is the result
;;Destroys: A
;;13 bytes
;;66cc, add 6cc if not using smc
#IF smc == 0
ld hl,(seed1)
#ELSE
seed1 = $+1
ld hl,1
#ENDIF
add hl,hl
sbc a,a
and %00101101
xor l
ld l,a
ld (seed1),hl
ret
smc = 1
prng16:
;;Input:
;; (seed1) is a non-zero 16-bit int
;; (seed2) is a 16-bit int
;;Output:
;; HL is the pseudo random number
;; DE is the output of the LFSR
;; BC is the previous seed of the Lehmer PRNG
;; (seed1) is the output of the LFSR
;; (seed2) is the output of the Lehmer PRNG
;;Destroys: A
;;Notes:
;; This uses a 16-bit Lehmer PRNG, and an LFSR
;; The period is 4,294,901,760 (65536*65535)
;; Technically,the Lehmer PRNG here can have values from 1 to 65536. In this application, we store 65536 as 0.
;;Speed:
;; If smc = 0, add 12cc
;; 293+a-c, a,b,c are {0,1}
;; probability a= 1 is 38/65536
;; probability c= 1 is 1/65536
;; Average: 293+39/65536 = 293.00059509277cc
;; Best:293cc
;; Worst:294cc
;;50 bytes
#IF smc == 0
ld hl,(seed2)
#ELSE
seed2 = $+1
ld hl,0
#ENDIF
;multiply by 75
ld c,l
ld b,h
xor a
adc hl,hl \ jr nz,$+3 \ inc a \ rla
add hl,hl \ rla
add hl,hl \ rla \ add hl,bc \ adc a,d
add hl,hl \ rla
add hl,hl \ rla \ add hl,bc \ adc a,d
add hl,hl \ rla \ add hl,bc
ld e,a
sbc hl,de
jr nc,$+3
inc hl
ld (seed2),hl
ex de,hl
#IF smc == 0
ld hl,(seed1)
#ELSE
seed1 = $+1
ld hl,1
#ENDIF
add hl,hl
sbc a,a
and %00101101
xor l
ld l,a
ld (seed1),hl
add hl,de
ret
-
Here is a much better PRNG, probably the best I have created in terms of speed, period length, and quality.
- Speed: It is very fast at 291cc.
- Period Length The cycle size is over 1.84*1019.
- Quality: It passes all the tests at CAcert Labs. (http://www.cacert.at/cgi-bin/rngresults)
- It would take over 11 million years at the calculator's max speed to reach the full cycle.
rand:
;;Tested and passes all CAcert tests
;;Uses a very simple 32-bit LCG and 32-bit LFSR
;;it has a period of 18,446,744,069,414,584,320
;;roughly 18.4 quintillion.
;;291cc
seed1_0=$+1
ld hl,12345
seed1_1=$+1
ld de,6789
ld b,h
ld c,l
add hl,hl \ rl e \ rl d
add hl,hl \ rl e \ rl d
inc l
add hl,bc
ld (seed1_0),hl
ld hl,(seed1_1)
adc hl,de
ld (seed1_1),hl
ex de,hl
seed2_0=$+1
ld hl,9876
seed2_1=$+1
ld bc,54321
add hl,hl \ rl c \ rl b
ld (seed2_1),bc
sbc a,a
and %11000101
xor l
ld l,a
ld (seed2_0),hl
ex de,hl
add hl,bc
ret