=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Date: Thu, 11 May 2000 17:50:03
From: Nikolai Golovchenko <golovchenko-at-mail.ru>
To: pic microcontroller discussion list <PICLIST-at-MITVMA.MIT.EDU>
Subject: Re: Pseudorandom number generation on a PIC
--------------------------------------------------------------------------------
Here is a bit shorter version:
;Rnew = Rold * 221 + 53
;221 = 256 - 32 - 4 + 1
;256 can be eliminated
;so we need to calculate Rnew = Rold * (1 - 32 - 4) + 53 using
;truncating arithmetic
;or Rnew = Rold * (-32 - 3) + 53
clrc
rlf RANDOM, f
swapf RANDOM, w
andlw 0xE0
rrf RANDOM, f
addwf RANDOM, w
addwf RANDOM, w
addwf RANDOM, w
sublw 0x35
movwf RANDOM
Does anybody know how to estimate randomness of a pseudo-random
generator? Or what other methods are out there?
Nikolai
http://techref.massmind.org/member/NG--944
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Date: Thu, 11 May 2000 08:19:19
From: Nikolai Golovchenko <golovchenko-at-mail.ru>
To: pic microcontroller discussion list <PICLIST-at-MITVMA.MIT.EDU>
Subject: Re: Pseudorandom number generation on a PIC
--------------------------------------------------------------------------------
Hi Robert,
The congruential algorithm looks better than the shift-and-xors. I
made quick test in MATLAB for both. The results showed that
shift-and-xors (see attached .m files) also has 256 long sequence, but
the generated sequence is predicted more easily, its like
Columns 1 through 12
2 4 8 17 35 71 142 28 56 113 226 196
Columns 13 through 24
137 18 37 75 151 46 92 184 112 224 192 129
Columns 25 through 36
3 6 12 25 50 100 201 146 36 73 147 38
Columns 37 through 48
77 155 55 110 220 185 114 228 200 144 32 65
Columns 49 through 60
130 5 10 21 43 86 173 91 182 109 218 181
As you can see, it consists of small parabolas, because of
multiplication by 2.
In contrast, the congruential algorithm, e.g. Rnew = Rold * 221 + 53
gives no idea about the next result.
Columns 1 through 12
18 191 24 237 206 11 180 153 74 23 16 5
Columns 13 through 24
134 227 44 49 130 111 8 29 62 187 164 201
Columns 25 through 36
186 199 0 53 246 147 28 97 242 31 248 77
Columns 37 through 48
174 107 148 249 42 119 240 101 102 67 12 145
Columns 49 through 60
98 207 232 125 30 27 132 41 154 39 224 149
Columns 61 through 72
214 243 252 193 210 127 216 173 142 203 116 89
Columns 73 through 84
10 215 208 197 70 163 236 241 66 47 200 221
Columns 85 through 96
254 123 100 137 122 135 192 245 182 83 220 33
I would assume that the algorithm can be made quite efficiently (if
care taken with coefficients).
For this example it will look like
;221 = 256 - 32 - 4 + 1
;256 can be eliminated
;so we need to calculate Rnew = Rold * (1 - 32 - 4) + 53 using
;truncating arithmetic
clrc
rlf RANDOM, w
movwf RANDOM
swapf RANDOM, w
andlw 0xE0
rrf RANDOM, f
addwf RANDOM, w
addwf RANDOM, w
addwf RANDOM, w
addwf RANDOM, w
subwf RANDOM, w
addlw 0x35
movwf RANDOM
Nikolai
http://techref.massmind.org/member/NG--944
On Wednesday, May 10, 2000 Robert A. LaBudde wrote:
> If all that is wanted is a small run length of pseudorandom numbers, this
> can be accomplished by the following 8-bit multiplicative-additive
> congruential generator:
> X(n+1) = [27 X(n) + 3] mod 256
> = [16 X(n) + 8 X(n) + 2 X(n) + X(n) + 3] mod 256
> = [32 X(n) - 4 X(n) - X(n) + 3] mod 256
> with X(0) = 27.
> The output of this sequence should appear as reasonably 'white' noise.
> Note that 16 X(n) is X(n) shifted left 4 bits with zero fill, etc., and mod
> 256 is simply accomplished by disregarding overflow bits and keeping only
> the low order 8 bits of the addend.
> I would presume that a linear shift register algorithm would give superior
> run length and spectral properties for the same computation time. I'll try
> to dredge up a validated one and post it to the list.
> ================================================================
> Robert A. LaBudde, PhD, PAS, Dpl. ACAFS e-mail: ral-at-lcfltd.com
> Least Cost Formulations, Ltd. URL: http://lcfltd.com/
> 824 Timberlake Drive Tel: 757-467-0954
> Virginia Beach, VA 23464-3239 Fax: 757-467-2947
> "Vere scire est per causas scire"
> ================================================================