Very fast/small random number generator

Go To Last Post
81 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hello,

I'm trying to find a means of producing a pseudo-random s 8-bit values in AVR assembly (ATmega) using as few processor cycles as possible.

I'm aware of LFSR-type approaches, but even for an 8-bit value, these would be too slow (for a Galois configuration, I estimate around 50 cycles). If possible, something in the region of 5 cycles would be ideal.

For up to 10000 iterations, I'd be looking for the algorithm to produce fairly white noise. Use of some sort of LUT is practical as long as it is fairly small (16 bytes?), I'm really pushed for program space and CPU time on this one!

Is what I'm asking totally unrealistic? Any ideas greatly appreciated.

Matt.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Have you tried searching for "random AND diode"? Though the downside of using a Z diode is the length of time the ADC conversion will take - but at least that can be happening while you get on with other things.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I did consider that approach, but given that I need these values generated in very fast succession, I cannot wait for the ADC.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Do you have 8 pins? Put the diode thingy on each pin, and read the logic values with a single port read. Ouila--instant 8-bit random number. One cycle; one word.

Lee

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Nice idea. I'm really looking for a software only approach though (I'm being picky, I know) and in any case, I don't have any I/O pins left.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I got excellent results by just pulling code bytes out of flash from an incrementing pointer. The hex dump of flash looks pretty random.

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

How "random" does it need to be?
The simplest way is to use:
seed = seed*b + 1 % m;
This is called the Linear Congruential Method (I quote from Robert Sedgewick's "Algorithms in C"), and returns an integer between 0 and m-1.
Google it, there are "requirements" for the value of b, and you should use the more significant bits in preference to the less significant, if you don't use all the result.
Having a hardware multiply instruction at your disposal, this should be quick and easy to do in assembly language.

Four legs good, two legs bad, three legs stable.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0
;************************************************************************
;* NOISE.ASM:	White noise generator (output = PD6 ATmega8)
;************************************************************************

.include "m8def.inc"


	rjmp	RESET				;reset vector


	.def	temp 	= r16
	.def	byte0 	= r17			; 7  6  5  4  3  2  1  0
	.def	byte1 	= r18			;15 14 13 12 11 10  9  8
	.def	byte2	= r19			;23 22 21 20 19 18 17 16

	.equ	output	= 6			;output -> PD6




;* Main program

RESET:	ldi	temp, high(RAMEND)		;setup stack
	out	SPH, temp
	ldi	temp, low(RAMEND)		;point in RAMEND
	out	SPL, temp

;length 23bit
;14 cycles = 71,429 kHz @ 1MHz RC-clock
;repeat = 2^23/71429 = 8388608/71429 = 117,4sec

	ser	temp
	out	DDRD, temp			;PORTD all outputs
	ldi	byte0, 0x11
loop:	mov	temp, byte2
	andi	temp, 0b01000010		;17,22	1	1	1
	breq	cy2				;	2	1	1
	cpi	temp, 0b01000010		;		1	1
	breq	cy1				;		2	1
	sec					;			1
	rjmp	s1				;			2
cy2:	clc					;	1			
	clc					;	1
cy1:	clc					;	1	1
	clc					;	1	1
s1:	rol	byte0
	rol	byte1
	rol	byte2
	sbrc	byte0, 0			;if bit0 = 0,
	cbi	PORTD, output			; -> PD6 lo
	sbrs	byte0, 0			;if bit0 = 1,
	sbi	PORTD, output			; -> PD6 hi
	rjmp 	loop				; loop for ever

RES

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

bobgardner wrote:
I got excellent results by just pulling code bytes out of flash from an incrementing pointer. The hex dump of flash looks pretty random.

That is a nifty idea. How do you handle "unprogrammed pages"?

Markus

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If the program is 8k, just check the pointer when you increment it and wrap it back to 0x0060 or wherever code starts when it gets to the end of the code. I'm paying forward. That trick is on freaks here somewhere... back about '03 or so....

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Firstly, Bob, that is absolute genius! It is quite important that the random numbers generated in my application are fairly white, spectrally, so I'm not sure this method would work for me, but I'll put that one in my remembering place!

Thanks for the code and reference Res and John.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Randomness is funny... I tried several pseudo random numbers that use shift and exclusive or, and they always looked like they were shifting (doh! thats what they were doing!). I just wanted to vibrate a needle a little like the motor was running.... I think the code trick works, because a great programmer like me doesnt have any repeating sequences in his programs.. they are all in subroutines, so the sequence thru the program really doesnt repeat till the end of the program!

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

I think the code trick works, because a great programmer like me doesnt have any repeating sequences in his programs..

Are you sure? See below.

Quote:

they are all in subroutines, so the sequence thru the program really doesnt repeat till the end of the program!

Real programmers don't use many subroutines, right js?

Quote:

bobgardner wrote:
I got excellent results by just pulling code bytes out of flash from an incrementing pointer. The hex dump of flash looks pretty random.

I was skeptical, since common op codes are repeated quite often. So I whipped up a VisualBASIC program and set it on about a 16k Mega169 program. "Pretty random"? I think not.

0 163
1 226
2 138
3 286
4 12
5 13
6 17
7 50
8 109
9 45
10 66
11 17
12 110
13 22
14 544
15 215
16 51
17 85
18 9
19 13
20 42
21 50
22 24
23 67
24 33
25 32
26 27
27 22
28 78
29 190
30 226
31 253
32 69
33 9
34 13
35 83
36 55
37 11
38 5
39 89
40 20
41 15
42 5
43 28
44 5
45 147
46 84
47 293
48 103
49 24
50 2
51 7
52 10
53 5
54 6
55 2
56 2
57 7
58 10
59 3
60 4
61 1
62 15
63 8
64 11
65 9
66 3
67 2
68 10
69 7
70 6
71 7
72 19
73 11
74 12
75 3
76 11
77 5
78 6
79 151
80 71
81 6
82 14
83 41
84 24
85 60
86 6
87 2
88 4
89 19
90 19
91 4
92 45
93 37
94 27
95 72
96 37
97 10
98 3
99 2
100 6
101 3
102 42
103 3
104 17
105 15
106 5
107 14
108 18
109 18
110 24
111 23
112 48
113 17
114 4
115 5
116 12
117 6
118 0
119 32
120 19
121 10
122 10
123 2
124 5
125 1
126 2
127 52
128 26
129 270
130 3
131 65
132 5
133 9
134 7
135 4
136 9
137 25
138 4
139 4
140 2
141 4
142 11
143 17
144 32
145 499
146 31
147 923
148 651
149 134
150 88
151 61
152 65
153 29
154 53
155 47
156 7
157 3
158 6
159 74
160 247
161 27
162 36
163 46
164 38
165 56
166 70
167 8
168 53
169 32
170 55
171 43
172 17
173 9
174 122
175 99
176 148
177 90
178 33
179 22
180 12
181 10
182 2
183 17
184 1
185 54
186 22
187 48
188 21
189 47
190 7
191 188
192 163
193 21
194 11
195 8
196 2
197 1
198 10
199 1
200 2
201 6
202 3
203 4
204 11
205 11
206 1
207 37
208 25
209 4
210 10
211 16
212 5
213 19
214 6
215 3
216 19
217 2
218 13
219 12
220 19
221 15
222 23
223 72
224 1636
225 162
226 87
227 92
228 60
229 73
230 85
231 49
232 161
233 70
234 406
235 79
236 113
237 88
238 101
239 157
240 464
241 25
242 20
243 46
244 185
245 67
246 27
247 42
248 29
249 42
250 100
251 87
252 64
253 70
254 33
255 139
ATmega169 instruction use summary:
adc   : 155 add   : 159 adiw  :  79 and   :  78 andi  :  39 asr   :   0 
bclr  :   0 bld   :  18 brbc  :   0 brbs  :   0 brcc  :   4 brcs  :   0 
break :   0 breq  :  79 brge  :   9 brhc  :   0 brhs  :   0 brid  :   0 
brie  :   0 brlo  :  61 brlt  :   3 brmi  :   1 brne  :  97 brpl  :   0 
brsh  :  59 brtc  :   4 brts  :   0 brvc  :   0 brvs  :   0 bset  :   0 
bst   :   3 call  : 499 cbi   :  40 cbr   :   0 clc   :   1 clh   :   0 
cli   :  11 cln   :   0 clr   :  87 cls   :   0 clt   :  11 clv   :   0 
clz   :   0 com   :  42 cp    :  82 cpc   :  41 cpi   : 110 cpse  :   1 
dec   :  16 eor   :  17 fmul  :   0 fmuls :   0 fmulsu:   0 icall :   0 
ijmp  :   0 in    :  48 inc   :  31 jmp   :  71 ld    : 166 ldd   : 174 
ldi   :1241 lds   : 285 lpm   :  14 lsl   : 119 lsr   :   7 mov   : 377 
movw  : 202 mul   :  44 muls  :   0 mulsu :   0 neg   :   0 nop   :   1 
or    :  26 ori   :   7 out   :  70 pop   : 113 push  : 113 rcall :  82 
ret   :  73 reti  :   5 rjmp  : 220 rol   : 119 ror   :   6 sbc   :  15 
sbci  : 151 sbi   :  39 sbic  :  11 sbis  :  41 sbiw  :  51 sbr   :  11 
sbrc  :  12 sbrs  :  23 sec   :   1 seh   :   0 sei   :   9 sen   :   0 
ser   :   1 ses   :   0 set   :  11 sev   :   0 sez   :   0 sleep :   0 
spm   :   0 st    : 513 std   :  25 sts   : 292 sub   :  16 subi  : 217 
swap  :   2 tst   :  29 wdr   :   5 
Instructions used: 75 out of 111 (67.6%)

ATmega169 memory use summary [bytes]:
Segment   Begin    End      Code   Data   Used    Size   Use%
---------------------------------------------------------------
[.cseg] 0x000000 0x003f1a  16084     70  16154   16384  98.6%

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Graph that and see if you can see a pattern. Actually, putting it in a wav file and looping it really reveals periodicity.... I was trying to loop engine sounds for a sim using jupiter systems on a digidesign board... they had 3 or 4 different looping search/splice algorithms, a couple of them patented! and they all sounded like a washing machine. The only way to loop a noise is with tedious trial and error like splicing a tape.

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Or run it through a rigorous test...

Chuck Baird

"I wish I were dumber so I could be more certain about my opinions. It looks fun." -- Scott Adams

http://www.cbaird.org

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Here's a good, quick RNG. The period (2^31-1) is prime so it's not easy to short-circuit it. Half the time it takes 6 cycles and the other half it takes 15, for an average of 10.5, if it's register-based as shown. You can make a quicker, shorter one by using a 15 or 16 bit algorithm instead of 31. How to choose the polynomial? It's a black art, but CRC polynomials generally work well. In fact this kind of RNG is mathematically the same as taking the CRC of an infinite string of 1's. If you already have a CRC routine in your code you get an RNG for free.

; 31-bit random number
; primitive polynomial order 31
; (1)0100000 10101010 10010101 10110101 (20 AA 95 B5)
; shift before XOR
rand_31:
	lsl	r4			; shift first
	rol	r5
	rol	r6
	rol	r7
	sbrs	r7,7			; test MSB
	ret				; clear, no XOR
	ldi	r24,0xB5		; first poly byte
	eor	r4,r24			; XOR it in
	ldi	r24,0x95		; second byte of poly
	eor	r5,r24
	ldi	r24,0xAA		; same routine
	eor	r6,r24
	ldi	r24,0x20
	eor	r7,r24

	ret
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Going on John Brown's suggestion, here is an excellent 16 bit LC algorithm, tried and tested:

X(n+1) = (2053.X(n) + 13849) mod 65536

It meets Knuth's requirements that the first parameter [2053]mod 8 = 5, and [2053] and [13849] have no common factors. The period is 65535 (result 0x0000 is missing). Interestingly, 2053 is 2^11+2^2+1, and (x16+x11+x2+1) is a known primitive polynomial mod 2, so you can use 2053 (0x0805) in a shift generator. The problem with running the LC algorithm on an AVR is the 16x16 multiply. It takes rather more time than you have to spare.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Beyond opcode distribution, flash randomness is determined by the sequence of byte values. This graph shows an ATmega32 binary to display digits on a TWI interfaced 4x7 LED device. The pattern appears subjectively somewhat more random than similar plots of congruent algorithms I've seen before.

This would be random enough for some applications and not enough for others.

(Notice the vector table at the beginning.)

Attachment(s): 

C: i = "told you so";

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

Graph that and see if you can see a pattern

I don't care about a "pattern"--your claim was to use flash contents in a random number generator. Whether as seed, or number, no matter--as I surmised common op codes and scratch register usage skews the results so they really aren't useful as your "seems random" claim.

Yes, there will be a pattern as a study of the AVR instruction set reveals.

Lee

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
Real programmers don't use many subroutines, right js?
Wouldn't know, I'm an UNREAL programmer :lol:

John Samperi

Ampertronics Pty. Ltd.

https://www.ampertronics.com.au

* Electronic Design * Custom Products * Contract Assembly

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Unreal programmers use subroutines at 90 degrees to the rest of the world... ;)

One thing which has not been discussed here is the probability distribution desired by the OP; the two most common I believe (IANA statistician) being equal density distribution and poisson distribution.

Most of the proposals here approximate equal density - there's approximately the same chance of any number being produced as any other, on a long run, but in many cases you'll need the poisson curve, (the bell-shaped 'normal' curve) where most values occur close to a median but with decreasing numbers of outliers as you move further from the medium.

For the latter, I *believe* that multiplying two or more equal density numbers together produces a good approximation.

Neil

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
poisson distribution.
That's French for fish, right? :lol:

John Samperi

Ampertronics Pty. Ltd.

https://www.ampertronics.com.au

* Electronic Design * Custom Products * Contract Assembly

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
For the latter, I *believe* that multiplying two or more equal density numbers together produces a good approximation.

A moments thought about a pair of dice leads me, also, to "believe" you're right about this.

Four legs good, two legs bad, three legs stable.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thanks Peret for your suggestions. Certainly, your CRC-like one seems the cheapest (CPU memory/cycles) I've seen so far that will likely fit my requirements. Unfortunately, this app doesn't have any pre-existing CRC code in it... That would make life too easy ;-)

Matt.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

The complex conjugate of a Real programmer must surely be an Imaginary Programmer. He THINKS he can write a tight program.

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

When someone needs a random number, they want to add it to something steady to make it look random... they dont want to make it rock or wiggle or oscillate or any other word that connotes periodic movement. No pattern. I claim pulling bytes out of flash does this well. LT refutes it buy making a table of OPCODE FREQUENCY.... bzzzzzt.... foul! opcodes are words.... Go redo with byte frequency... I stand by my claim... I dump flash in bytes, I see a bunch of happy faces and funny characters and it sure looks random. I'll sniff it later on and see if it smells random. And I'm gonna make a hex to wav converter and I'll listen to one of my programs to see if it sounds random. and it will have a nice smooth pink whoosh to it. Then we'll listen to LTs program and it will sound like an old model T pockceta pocketa pocketa.

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

It is quite trivial in Rebol to convert hex files to sound, so I whipped up a little program, input a large hex file, and out came-
http://www.mtcnet.net/~henryvm/A...

From what I hear, I think Bob will have to rethink his randomness from flash memory thing.

See what you think.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

LT refutes it buy making a table of OPCODE FREQUENCY.... bzzzzzt.... foul! opcodes are words.... Go redo with byte frequency... I stand by my claim...

...and I refute it, again. The table >>is<< the "byte frequency"--the number of times each byte value showed up in that 16k .HEX file.

I added the op code table from the assembler output as I thought it might be of interest in grasping the wide imbalance in the counts--many values are in the single digits, and many are in the hundreds. As a sage recently said--"bzzzzzt".

I picked a couple of the bigger numbers and looked through the .LST file to see what it represented, and it is often a common op code, plus other random ;) occurrences. The biggest value that I saw was 224 = 0xe0. Nearly all the uses were as an encoding for using R30 in an instruction. My compiler uses R30 as the primary scratchpad, so there are many many uses of that.

No, Bob, not a bzzzzzt. No, Bob, not a flaw in opcodes being words. No, Bob, it WAS a count of the number of occurrences of each value. Lessee--if the 16k were totally full and the distribution was even we'd expect a count of 64 for each value. Many are 1/10 of that. Quite a few are 10x that. As cpluscon said it may be good enough for some applications. It may be good enough for your golden ears. With my hex file, one byte out of 10 has the same 224 value! .WAV that.

It might be kind of interesting to run my program against your Imagecraft .HEX, if you care to post one. I'd guess it wouldn't have the big R30 peak but would have others.

Lee

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

curtvm wrote:
From what I hear, I think Bob will have to rethink his randomness from flash memory thing.

:D :lol: :P :wink:

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Here is the power spectrum of my hex file. I'd guess a hum rather than whoosh.

Attachment(s): 

C: i = "told you so";

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

curtvm wrote:
It is quite trivial in Rebol to convert hex files to sound, so I whipped up a little program, input a large hex file, and out came-
http://www.mtcnet.net/~henryvm/A...

From what I hear, I think Bob will have to rethink his randomness from flash memory thing.

See what you think.


I think that after clicking on the link you gave that I may need to move you from the "trusted" list to the "troll" list.

LOL

Lee

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I think that may have been a hex file I read from a mega88 when I accidentally hooked up the cable tv to my stk500.

I did just make a little program to play hex files (converted to binary first), and at first everything sounded like an electric shaver, but now that I made a couple changes, things are starting to sound 'white', whatever 'white' sounds like.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Surprise! (I like ol Gomer!) Anyway, white is 'treble-lier' than pink, because the freq resp rises at 3dB per octave. It hisses. Pink whooshes.

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

A Binary Maximal Length Sequence of 2^n-1 length is generated with an n bit shift reg with taps at the bits of the CRC polynomial. So if you use one of those numbers every pass, 30 per sec, it takes 500 sec to repeat (16k sequence)... about 9 min. Something that repeats every second or so sounds periodic, like a machine... rum rum rum rum.... Can you rework your vb prog to find the longest substring in the sequence? My def of 'good' is 30 numbers a sec shouldnt repeat for about 10 sec... so are there any substrings of 300 bytes? If there are a lot, you will hear it/see it/smell it/taste it. I think its a duck!

Imagecraft compiler user

Last Edited: Fri. Oct 12, 2007 - 03:20 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I just used Cooledit2000 to generate a .wav (well actually a .raw) file of white noise (pink and brown options also available). So I have a file of supposedly random data. If I now run this through xxd to convert it to C source and build it into an AVR project I have a table of completely random 8 bit values I could use. Of course a second of noise at 8KHz costs 8KB of code space!

I imagine the free to download and use Audacity could be used to do the same.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Dave Johnson wrote Cooledit. Seems like a way cool dude. Did you ever see his Kaliedoscope screen saver? Snoqualmie falls? Wonder if you can retire after Adobe buys your program?

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

bobgardner wrote:
A Binary Maximal Length Sequence of 2^(n-1) length with an n bit shift reg with taps at the bits of the CRC polynomial. So if you use one of those numbers every pass, 30 per sec, it takes 500 sec to repeat (16k sequence)... about 9 min.
If I knew half of what you smart guys are talking about, well, I wouldn't exactly know what I would do, but if I knew, I would know.

bobgardner wrote:
Something that repeats every second or so sounds periodic, like a machine... rum rum rum rum....
Now your talking my language. You mean like the sound the Russian sub made in 'Hunt for the Red October', when Jonesy sped up the tape of the sub sound to 10x? I'm hearing that on some files I try.

here's my little app-
http://www.mtcnet.net/~henryvm/A...
not much thought went into it, so be careful

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

here's my little app-
http://www.mtcnet.net/~henryvm/A...
not much thought went into it, so be careful

>>I<< ain't click'n on that link. "Fool me once, ..." ;)

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
poisson distribution...
That's French for fish, right?

One man's fish is another man's poisson.

Chuck Baird

"I wish I were dumber so I could be more certain about my opinions. It looks fun." -- Scott Adams

http://www.cbaird.org

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

barnacle wrote:
Unreal programmers use subroutines at 90 degrees to the rest of the world... ;)
Neil

That's why they prefer orthogonal instruction sets.

Jim

Your message here - reasonable rates.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

barnacle wrote:
Unreal programmers use subroutines at 90 degrees to the rest of the world... ;)
Neil

That's why they prefer orthogonal instruction sets.

Jim

Your message here - reasonable rates.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Achieving (and analyzing for) proper randomness is more difficult than you might think - here's a good resource (chapter 7). Chi-squared is the test we apply in the gaming industry.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Knuth spends a lot of time on random numbers in his Art series.

At the macro level true randomness seems elusive to the point of impossibility. Yet randomness is allegedly inherent at the quantum level. Perhaps another of nature's paradoxes.

EDIT: I've read that a simple test for randomness is to note the compression achieved when zipping. The higher the compression the lower the randomness. For best results the data should be not be encoded in ASCII.

C: i = "told you so";

Last Edited: Fri. Oct 12, 2007 - 05:41 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

cpluscon wrote:
Knuth spends a lot of time on random numbers in his Art series.

At the macro level true randomness seems elusive to the point of impossibility. Yet randomness is allegedly inherent at the quantum level. Perhaps another of nature's paradoxes.

Yes, or perhaps our understanding of the ‘quantum level’ is random? :wink:
Cheers,
John


PS:
Peret the link looks like it has a lot on really cool functions, Thanks for posting it!!!

Resistance is futile…… You will be compiled!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
Peret the link looks like it has a lot on really cool functions, Thanks for posting it!!!

It's an excellent book - I have the dead tree version but the whole thing is available online. It's a book I open nearly every week.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
It's an excellent book...

I have the first edition, hardback, from 1988. Your link inspired me to possibly upgrade to the current 3rd edition, so I looked on Amazon, and the reviews for it (the C++ 3rd edition) are all over the place. It seems that the objections are that the C++ part is artificially grafted onto the superior 2nd edition, the one you gave the link for that is available online.

Chuck Baird

"I wish I were dumber so I could be more certain about my opinions. It looks fun." -- Scott Adams

http://www.cbaird.org

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I bought it in Pascal back when I was a Turbo Pascal 7 enthusiast.

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Just downloaded the whole thing... Another bunch of PDFs to add to my ever growing collection of 'ebooks'... Now if only someone would bring out a DECENT electronic paper device, I might be able to start reading the things (I hate reading on screen and value the toner in my printer too much).

Matt.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Sony has a cool ebook device, looks pretty much like paper (flat, readable under any light that paper is readable). but it's expensive, like $300 last time I checked.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

That's the problem. WAY too expensive for such a specialized device. I thought the whole point of this electronic paper technology was to provide a cheap alternative to LCD. I appreciate it is not very wide spread yet, but to me, that argument is not enough on its own. I can't see it competing effectively in the high-res display market for quite some time.

For ebook applications, I'd be perfectly happy with reflective LCD.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Try to see at the 8-bit CRC

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

[OT]
If the mentioned item from SONY is what I think it is, it's using a special bi-stable type LCD.
I have seen this, and the contrast and general readability is superb. Much higher then normal LCD. Also, it use very little power, as it only need power to alter the state of a pixel. It's so good you can actually use it to display "POWER IS OFF" when the power is ... off.
[/OT]
It isn't easy to define what random really is, but in micro controller applications one need to ask if true, or even pseudo random numbers are needed.

If the UC is used in military ultra top secret transmission coding, it needs to be precisely random.
If it's used to "shake" a needle indicator, or make a toy robot pick a new direction to move in, it doesn't have to be very random (there is no such thing as 20% random but you get the idea). It just have to be perceived as random.

I couldn't be bothered to generate a binary AVR program file to test the LPM theory, but loading terminal.exe (brays terminal program) as a 8bit RAW pcm file produced something that sounded very much like white noise.
Graphing it using 8192 FFT samples confirmed this.

However, I realize that Terminal.exe is compiled to run on a fundamentally different architecture, but it confirms the general idea that program code could be used as a source for a pseudo-random number.

LPM r16,Z+
LPM r17,Z+
EOR r16,r17

This bit is the best 5-cycle RND function I can come up with.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
This bit is the best 5-cycle RND function I can come up with.

What happens when Z passes the top of flash? If the LPM instruction maps it back to 0 at that point, then maybe it's not too bad. If the LPM returns 0xFF or 0x00 for some number of bytes until Z reaches some magical value, this this method is going to have some serious holes in it.

Not to mention the block of interrupt vectors, etc., which are going to skew the EOR. But it's an interesting idea.

Chuck Baird

"I wish I were dumber so I could be more certain about my opinions. It looks fun." -- Scott Adams

http://www.cbaird.org

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Combining two not so good randon sources is a good idea, but there are correlations two bytes in a row. If the random funktion is not called in equal time intervalls it should be better to use a timer value as a second source of randomness. This would at least make all numbers equally likely.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

DukerX wrote:
[OT]
If the mentioned item from SONY is what I think it is, it's using a special bi-stable type LCD.
I have seen this, and the contrast and general readability is superb. Much higher then normal LCD. Also, it use very little power, as it only need power to alter the state of a pixel. It's so good you can actually use it to display "POWER IS OFF" when the power is ... off.
[/OT]
It isn't easy to define what random really is, but in micro controller applications one need to ask if true, or even pseudo random numbers are needed.

If the UC is used in military ultra top secret transmission coding, it needs to be precisely random.
If it's used to "shake" a needle indicator, or make a toy robot pick a new direction to move in, it doesn't have to be very random (there is no such thing as 20% random but you get the idea). It just have to be perceived as random.

I couldn't be bothered to generate a binary AVR program file to test the LPM theory, but loading terminal.exe (brays terminal program) as a 8bit RAW pcm file produced something that sounded very much like white noise.
Graphing it using 8192 FFT samples confirmed this.

However, I realize that Terminal.exe is compiled to run on a fundamentally different architecture, but it confirms the general idea that program code could be used as a source for a pseudo-random number.

LPM r16,Z+
LPM r17,Z+
EOR r16,r17

This bit is the best 5-cycle RND function I can come up with.

by combining 2 sequential values in flash, you're not gaining any randomness... you might as well just spit out one of the values directly.

Sticking with the flash concept. Why not fill the unused pages of flash with a random sequence of numbers, and then just use that as a lookup?

Writing code is like having sex.... make one little mistake, and you're supporting it for life.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I'm a little bit late in this discussion. But I think a good and fast solution to get in very short intervals random numbers would be to combine the flash read method with a true random source.

As Lee already pointed out is reading the program code to get a random number not optimal because of the poor distribution (Is this right word? :? ) of the values. So I created an array located in flash memory which contains all numbers from 0 to 255 in a diced order where each number occures only once.

The ADC is always a good random source. At least the LSB will toggle at random when reading a constant voltage. So I used the ADC as true random source.

My program below was written for an ATmega88 running at 7.3728 MHz. IDE is WinAVR20080512, Optimization -O3 (speed).

In the simulator of AVR Studio, it takes up to 40 cycles to get one random byte.

I have recorded more than 400 thousand random numbers generated with the code below and fed them into my random number analysis tool which I have published here. The analysis tool didn't recognice any periodical behaviour in this (short) sequence. The attached picture shows the occurance of each number.

#include 
#include 
#include 
#include 



void init (void);



// Diced Values From 0x00 To 0xFF, Each Value Appears Only Once.
const uint8_t RAND_LOOKUP[256] PROGMEM =
{
    0x18,	0xC7,	0x0B,	0xF6,	0xFF,	0xB0,	0xAF,	0x2E,
    0x2D,	0xF7,	0xB1,	0xE2,	0x20,	0x26,	0x45,	0x08,
    0x53,	0xE6,	0x3D,	0xB3,	0xD4,	0x16,	0xD1,	0xCF,
    0x34,	0x1B,	0x9F,	0x13,	0x76,	0xF0,	0x31,	0x4C,
    0x9B,	0x3F,	0x50,	0x01,	0xF4,	0xBB,	0x6D,	0x75,
    0xDA,	0x69,	0xB4,	0x60,	0x63,	0x3C,	0x3A,	0x12,
    0xCA,	0xD2,	0x55,	0x6B,	0xFD,	0xB2,	0x7D,	0xD5,
    0x57,	0x27,	0xE7,	0x82,	0xC9,	0x9D,	0x58,	0xF5,
    0x5F,	0x4D,	0x38,	0xC5,	0xE4,	0x1D,	0xE3,	0xC1,
    0x54,	0x89,	0x8B,	0x0E,	0xFB,	0x05,	0xA7,	0xF3,
    0x1F,	0x62,	0x7E,	0x2B,	0xA6,	0x39,	0x0C,	0xE8,
    0xAB,	0x11,	0x03,	0x36,	0x72,	0x49,	0xBF,	0x41,
    0x59,	0xDD,	0xDB,	0x6A,	0x98,	0x30,	0xF1,	0x42,
    0x52,	0x99,	0x61,	0xA4,	0xBD,	0xB5,	0x2F,	0x0F,
    0x33,	0xF9,	0x28,	0x92,	0x77,	0x90,	0x3B,	0x04,
    0xD9,	0x15,	0xB8,	0x44,	0xE9,	0x7F,	0xDF,	0xD3,
    0x94,	0x81,	0x6E,	0x24,	0xAC,	0xFC,	0x2C,	0xA9,
    0x46,	0xDE,	0x65,	0x19,	0x9E,	0x4F,	0xA1,	0x8C,
    0xD6,	0xEE,	0xB7,	0xC6,	0x95,	0x85,	0x79,	0x96,
    0x43,	0x29,	0x3E,	0x86,	0x5D,	0xFE,	0x51,	0x7A,
    0xEC,	0x0A,	0xC3,	0x67,	0xC2,	0xEF,	0xE0,	0x2A,
    0x6F,	0xB6,	0x91,	0x47,	0xD0,	0xA8,	0x74,	0x02,
    0x87,	0x9C,	0xDC,	0xA2,	0xB9,	0xBA,	0x09,	0x14,
    0xCC,	0x7B,	0xAE,	0x70,	0xD7,	0xC0,	0xE5,	0xD8,
    0x83,	0x7C,	0x07,	0xF8,	0x71,	0x48,	0x0D,	0x78,
    0x1C,	0xAA,	0x97,	0xA0,	0x23,	0xBC,	0x73,	0x1E,
    0xF2,	0x93,	0x10,	0xC4,	0x37,	0x56,	0x8D,	0x22,
    0x4E,	0xAD,	0x5E,	0x5C,	0x35,	0x9A,	0xED,	0xBE,
    0x84,	0xA5,	0xA3,	0xCE,	0x5B,	0x66,	0x06,	0x1A,
    0x5A,	0x4B,	0x8A,	0xCD,	0x64,	0xEA,	0x17,	0xC8,
    0x8F,	0x8E,	0x88,	0xEB,	0x21,	0x68,	0x4A,	0x32,
    0x6C,	0xCB,	0x25,	0x40,	0xFA,	0x80,	0xE1,	0x00
};



uint8_t random_value[512];



int main (void)
{
    #define inc_value byte[1]
    #define index byte[0]
    
    union rand_parameter_t
    {
        uint8_t byte[2];
        uint16_t word;
    }
    rand;
    
    uint8_t temp;
    uint8_t adc_result;
    uint8_t *rand_ptr;
    uint8_t ch;
    
    init();
    
    /********************************
    ***** Init Random Parameter *****
    ********************************/
    for (uint8_t count = 16; count > 0; count--)
    {
        // Wait Until ADC Has Finished Operation
        loop_until_bit_is_clear (ADCSRA, ADSC);
        
        // Get ADC Result
        adc_result = ADCL;
        temp = ADCH;
        
        // Re-Start ADC
        ADCSRA |= (1 << ADSC);
            
        // Only LSB Of ADC Result Is Used As True Random Source
        adc_result &= 0x01;
        rand.word <<= 1;
        rand.word |= adc_result;
    }
    
    while (1)
    {
        /********************************************
        ****** Generate 512 Byte Random Values ******
        ********************************************/
        for (rand_ptr = &random_value[0]; rand_ptr <= &random_value[511]; rand_ptr++)
        {
            // Check If ADC Has Finished Operation
            if (bit_is_clear (ADCSRA, ADSC))
            {
                // Get ADC Result
                adc_result = ADCL;
                temp = ADCH;
                
                // Re-Start ADC
                ADCSRA |= (1 << ADSC);
                
                // Only Bit0 Of ADC Result Is Used As True Random Source
                adc_result &= 0x01;
                rand.word <<= 1;
                rand.word |= adc_result;
            }
            
            // Update Random Lookup Table Index
            rand.index += rand.inc_value;
            // Read Random Byte From Lookup Table
            *rand_ptr = pgm_read_byte (&RAND_LOOKUP[rand.index]);
        }
        
        
        /*****************************************
        ****** Send Generated Random Values ******
        *****************************************/
        for (rand_ptr = &random_value[0]; rand_ptr <= &random_value[511]; rand_ptr++)
        {
            // Get Generated Random Byte
            temp = *rand_ptr++;
            // Convert High Nibble Of Random Number Into A Hex Character
            ch = (uint8_t) (temp >> 4);
            
            if (ch < 10)
            {
                ch += '0';
            }
            else
            {
                ch += (-10 + 'A');
            }
            
            // Send High Nibble Of Random Number
            loop_until_bit_is_set (UCSR0A, UDRE0);
            UDR0 = ch;
            
            // Convert Low Nibble Of Random Number Into A Hex Character
            ch = temp & 0x0F;
            
            if (ch < 10)
            {
                ch += '0';
            }
            else
            {
                ch += (-10 + 'A');
            }
            
            // Send Low Nibble Of Random Number
            loop_until_bit_is_set (UCSR0A, UDRE0);
            UDR0 = ch;
            
            // Send New Line Characters
            loop_until_bit_is_set (UCSR0A, UDRE0);
            UDR0 = '\r';
            loop_until_bit_is_set (UCSR0A, UDRE0);
            UDR0 = '\n';
        }
        
        // Give My Poor PC Some Time To Handle All The Incoming Data
        _delay_ms (1000);
    }
    
    return 0;
}



void init (void)
{
    uint16_t temp;

    PORTB = 0xFF;
    PORTC = 0xFF;
    PORTD = 0xFF;
    
    // Init UART: 19200 Baud, 8 Data Bits, No Parity, 1 Stop Bit
    UCSR0B = (1 << TXEN0);
    UCSR0C = (1 << UCSZ01) | (1 << UCSZ00);
    UBRR0 = F_CPU / 16 / 19200 - 1;
    
    // Init ADC: Vref = AVCC, ADC Input = 1.1V Bandgap, ADC Clock = F_CPU / 8 = 921.6kHz
    // The ADC Result Will Always Jitter For At Least 1 LSB. This LSB Is Taken As True Random Source
    // We Don't Need Any Accurcy, So We Can Run The ADC At Max Speed.
    ADMUX = (1 << REFS0) | (1 << MUX3)  | (1 << MUX2) | (1 << MUX1);
    ADCSRA = (1 << ADEN) | (1 << ADPS1) | (1 << ADPS0);
    
    // Make Dummy Conversation To Init ADC
    ADCSRA |= (1 << ADSC);
    loop_until_bit_is_clear (ADCSRA, ADSC);
    temp = ADCW;
    
    // Start ADC
    ADCSRA |= (1 << ADSC);
}

Regards
Sebastian

EDIT:
Here's the mixed code of the random number generation loop:

        /********************************************
        ****** Generate 512 Byte Random Values ******
        ********************************************/
        for (rand_ptr = &random_value[0]; rand_ptr <= &random_value[511]; rand_ptr++)
 28e:	82 e0       	ldi	r24, 0x02	; 2
 290:	af 3f       	cpi	r26, 0xFF	; 255
 292:	b8 07       	cpc	r27, r24
 294:	11 f0       	breq	.+4      	; 0x29a 
 296:	08 f0       	brcs	.+2      	; 0x29a 
 298:	bd cf       	rjmp	.-134    	; 0x214 
        {
            // Check If ADC Has Finished Operation
            if (bit_is_clear (ADCSRA, ADSC))
 29a:	80 91 7a 00 	lds	r24, 0x007A
 29e:	86 fd       	sbrc	r24, 6
 2a0:	0f c0       	rjmp	.+30     	; 0x2c0 
            {
                // Get ADC Result
                adc_result = ADCL;
 2a2:	20 91 78 00 	lds	r18, 0x0078
                temp = ADCH;
 2a6:	80 91 79 00 	lds	r24, 0x0079
                
                // Re-Start ADC
                ADCSRA |= (1 << ADSC);
 2aa:	80 91 7a 00 	lds	r24, 0x007A
 2ae:	80 64       	ori	r24, 0x40	; 64
 2b0:	80 93 7a 00 	sts	0x007A, r24
                
                // Only Bit0 Of ADC Result Is Used As True Random Source
                adc_result &= 0x01;
                rand.word <<= 1;
                rand.word |= adc_result;
 2b4:	21 70       	andi	r18, 0x01	; 1
 2b6:	30 e0       	ldi	r19, 0x00	; 0
 2b8:	cc 0f       	add	r28, r28
 2ba:	dd 1f       	adc	r29, r29
 2bc:	c2 2b       	or	r28, r18
 2be:	d3 2b       	or	r29, r19
            }
            
            // Update Random Lookup Table Index
            rand.index += rand.inc_value;
 2c0:	7e 01       	movw	r14, r28
 2c2:	ef 2d       	mov	r30, r15
 2c4:	ec 0f       	add	r30, r28
 2c6:	ce 2f       	mov	r28, r30
            // Read Random Byte From Lookup Table
            *rand_ptr = pgm_read_byte (&RAND_LOOKUP[rand.index]);
 2c8:	f0 e0       	ldi	r31, 0x00	; 0
 2ca:	ec 5c       	subi	r30, 0xCC	; 204
 2cc:	ff 4f       	sbci	r31, 0xFF	; 255
 2ce:	e4 91       	lpm	r30, Z+
 2d0:	ed 93       	st	X+, r30
 2d2:	9a cf       	rjmp	.-204    	; 0x208 

Attachment(s): 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Real programmers don't care about how many subroutines they use, they care about their length... ;)

You could pull a random number of non-contiguous byte values from the working registers, and CRC-8 them together on interrupt or even use a MD5 hash of the entire registers... Buffer them in a fixed length FIFO and grab a new one everytime you need it...

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

AllN wrote:
cpluscon wrote:
Knuth spends a lot of time on random numbers in his Art series.

At the macro level true randomness seems elusive to the point of impossibility. Yet randomness is allegedly inherent at the quantum level. Perhaps another of nature's paradoxes.

Yes, or perhaps our understanding of the ‘quantum level’ is random? :wink:
Cheers,
John


PS:
Peret the link looks like it has a lot on really cool functions, Thanks for posting it!!!

At quantum level randomness is inherent as long as you do not possess the ability to measure the quantum object's heading... What if you could sample it faster than it can travel? Maybe there's such a thing as a "quantum pattern"... ;)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Last time I needed a RND value an 8-bit timer was set up to run with no prescaler. Each time I needed the RND value I just read the timer.
Surely not perfect but uses just one instruction.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If the app has any interaction with human beings (i.e. buttons) then just time between button presses and inject this entropy into a PRNG

(Linux uses both user interaction timing and ethernet packet arrival times to inject the entropy into /dev/random)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I think an unused timer/counter is good resource for random seed.
Let it count in a high speed, and read the value when a random value is needed.
we can set a "press any key to continue" status to get a single random number.

but it is not a good idea when you need many random values.

hello world!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Really late into this discussion.

One of the things Matt didn't specify was whether or not all possible 8-bit combinations must be included in the random number set. That would be a critical factor in selecting an algorithm.

Jim

 

Until Black Lives Matter, we do not have "All Lives Matter"!

 

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

MicCYB wrote:
I think an unused timer/counter is good resource for random seed.
Let it count in a high speed, and read the value when a random value is needed.
we can set a "press any key to continue" status to get a single random number.

but it is not a good idea when you need many random values.

This is fine, as long as your request for values is at a period greater than the overflow period of the timer itself. Otherwise you have a statistically higher probability that the next value read will be higher than the current one, except when close to the overflow, at which point the next value will be lower. This may be fine for some applications, but realize that the trend will be visible.

Writing code is like having sex.... make one little mistake, and you're supporting it for life.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
the trend will be visible.

we can use it as a seed,
change the bit sequence
and invert certain bits to make it invisible

Ran = TCNT0;//the trend may be visible
SWAP(Ran);
Ran ^= 0xa5;
Ran -= 0xa5;//and now the trend is invisible

hello world!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

peret wrote:
In fact this kind of RNG is mathematically the same as taking the CRC of an infinite string of 1's. If you already have a CRC routine in your code you get an RNG for free.

I already got crc8 in my code. But CRC'ing a stream of 1's repeats itself every 254 or so characters. But CRCing a 0, 1, 2... stream does not. I haven't tested it but it should have a period of at least 255*255 or so, no?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

While not very random, this seems random enough for say, LED blinking delays or something similar. Sure, if you'd run fourier or something like that on the output signal, I can't imagine you getting something whitenoisy, nor something nonrepeating:

#include 
#include 

int main(int argc, char *argv[])
{
 int x = 1,temp =0;
 int in[256];
 for(temp = 0; temp != 256; temp++) in[temp] =0;
 for(temp = 0; temp != 50000; temp++)
 {
  printf("%i\n",(temp >> 2) & 0xFF);
  temp *=3;
  temp &= 0xFFFF; //this was done on a computer, with 32bit ints, so I wanted to limit it.
 }
}

Simply multiply by 3, & it with 0xFF and you get some seamingly random numbers. Nothing perfect, but fast and small.

There are pointy haired bald people.
Time flies when you have a bad prescaler selected.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Or there was that 0xDEADBEEF prng here. Warning, 32bit ints though.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Some time ago I wroted such a (2^9)-1 PRBS in assembly.
That's the circuit , that's the program and that's the video of the slow version of it.
But you can speed it up by changing the Timers and so.

First, do what you can - then, do what's possible - suddenly, you'll do the impossible. (Thadëus Judas )

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
I already got crc8 in my code. But CRC'ing a stream of 1's repeats itself every 254 or so characters. But CRCing a 0, 1, 2... stream does not. I haven't tested it but it should have a period of at least 255*255 or so, no?

It will have a period of 2^N-1, the same as any shift register generator, since there are only 2^N-1 possible different states (plus 0). So an 8 bit CRC has a period of 255, as you discovered. Feeding it 0, 1, 2 etc will not make it a better RNG. It may look more random, but it will have missing values.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

peret wrote:
It will have a period of 2^N-1, the same as any shift register generator, since there are only 2^N-1 possible different states (plus 0). So an 8 bit CRC has a period of 255, as you discovered. Feeding it 0, 1, 2 etc will not make it a better RNG. It may look more random, but it will have missing values.

But if I need very long non repeating sequences of almost-random-bytes then this is ideal, no?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

non repeating sequences of almost-random

That looks oxymoronic to me. If it's non-repeating then after the first 254 values ave been output I think I'd have a pretty fair chance of guessing the next number! In fact, even before the end, the pool of numbers still to be output would be so small I'd have a pretty strong chance of guessing them.

For true randomness you need the injection of some entropy.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

What I meant was that if I don't need pure white noise but instead pseudo random sequences then it is appropriate. I did a quick test with this CRC[i++] thing and in a sequence of 2k or so I had trouble finding two identical pairs of bytes (meaning I didn't find any but I checked only ten or so).
I think the right way to ask is what is the period of this PRNG in 16bit (or more for that matter) values?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

There are tests you can apply, though they're much too complicated to explain here and you'll need to look them up online. The standard test is Chi-squared but for CRC[i++] you would probably need to run "correlation in n-space" to get a feel for its strengths and shortcomings. The real question is, is it good enough for you? If it does the job you need, it doesn't need to be strong enough for Atlantic City.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

peret wrote:
Going on John Brown's suggestion, here is an excellent 16 bit LC algorithm, tried and tested:

X(n+1) = (2053.X(n) + 13849) mod 65536

... The problem with running the LC algorithm on an AVR is the 16x16 multiply. It takes rather more time than you have to spare.

Sure it has a few multiplies, but if you get 16-bits at once from a single loop then bits/cycle is way better than the LFSR method. Am i missing something? How many pseudo-random bits can I grab per iteration?

I implemented and tested this method, as well as a 16-bit LFSR. But i'm confused about this bits/iteration issue. Normal LFSR implementations seem to grab 1 bit per iteration and shift them together into the pseudo-random number, so you need 16 loops to get 16 bits. I made a periodicity checker, and I still get a 2^16 period if I grab 16 bits at once rather than 1 from the standard LFSR. So, i guess there must be some quality/distribution problem as to why nobody does it that way?

confused!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
Normal LFSR implementations seem to grab 1 bit per iteration and shift them together into the pseudo-random number, so you need 16 loops to get 16 bits.

Yes, and also no. A LFSR generates a complete new number - all 16 bits - for every 1-bit iteration. Its weakness is sequential correllation - a small number is followed by another small number too frequently. But if all you care about are individual bits, that may not worry you. The sequential correllation problem is only a problem for sequences of less than n numbers, so if you run 16 (or more) loops between picks it disappears, but then you run into problems of short cycling unless the number of loops you run between picks is relatively prime to 2^n-1. Since the only factor of 16 is 2, and 2^n-1 is always an odd number, 16 is safe.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If you look at the video linked above, you can see the correlation between sequential patterns -- the bits slide to the right. And yes, the PRNG only gives you one bit, so you need to repeat it n-times to get an n-bit random number. I think the easiest random generator is the n=n*m+p. FOr 8-bits this is a single multiply, which is fast on the chips with built in hardware multiply. Even 16x16 multiply is quite fast, 4 multiplies and associated additions.

Random numbers are always facinating.

David

Dr. David Harris OpenLCB Development Team openlcb.org

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
And yes, the PRNG only gives you one bit, so you need to repeat it n-times to get an n-bit random number.

Huh? Half the time, the shifted bits are XORed with the magic number, so all the bits have the potential to change on every operation. It produces a new n-bit random number every time. See Knuth, vol 2. If sequential correllation is a problem, use a Bays-Durham shuffle.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

peret wrote:
Quote:
And yes, the PRNG only gives you one bit, so you need to repeat it n-times to get an n-bit random number.

Huh? Half the time, the shifted bits are XORed with the magic number, so all the bits have the potential to change on every operation. It produces a new n-bit random number every time. See Knuth, vol 2. If sequential correllation is a problem, use a Bays-Durham shuffle.

hmm, i've done a bit of digging on this subject. it looks like it is a question of how good you want the random numbers to be. it seems that while the LFSR does generate a unique n-bit number each iteration and cycle through 2^n numbers (just like the linear congruential method), the randomness quality is not so good you do that. if you use the standard (slower) LFSR method of getting 1 bit per cycle and using n cycles to make an n-bit number, the quality is better. you still get 2^n total numbers.

As far as the linear congruential method, Wikipedia says that:
- the low bits of the linear congruential method are very non-random, you should only use the high bits. Several of the implementations listed in wikipedia (such as glibc) use bits 16..30 of a 32 bit generator.
- the LFSR method has better random quality than the linear congruential method

Then I discovered XORSHIFT, which appears to be all around better than both of the older methods as far as speed, size and randomness quality. ie, anything i care about. finding the correct key-shift bits i had to do by brute force, but it seems to work very nicely and yields 8 random bits in 25 clock cycles. More info:
http://www.jstatsoft.org/v08/i14...

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thanks for pointers to the XORSHIFT algorithm -- looks like a good random number method :-). I think the speed of the Xorshift and multiply-with-carry methods will depend on where the processor has barrel-shifter and/or multiply instructions. The larger ATMegas do have a MUL instruction that takes only 2 cycles for an 8-bit multiply. However, they only shift instructions that shift by one bit, which take 1 cycle each, so probably making the multiply methods faster. However, I think one would have to actually code them -- the Wikipedia 32-bit algorithm uses shifts of 11-bits left and 19- and 8-bits right. These are really only shifts by 3 and some byte-moving, while a 32x32 bit multiply on an ATMega will take 16 multiplies and associated additions.

...pondering...

David

Dr. David Harris OpenLCB Development Team openlcb.org

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Two years ago I posted very fast pseudorandom number generator. It is based on MLS generator - shift register with feedback. It is faster than other implementation as it calulates 8 random bits at once.
I've stored shift register in GPIOR registers as they offered faster acces, but it can be rewritten to use RAM.
I have version with 15 bit feedback register (periode 32767, [15 14] polynome) and 23 bit register (periode 8,388,607 [23 14] polynome).31 bit version can be written with minor mods, but I did not need such long periode. Each length supports 8 bits and 16 bit output.
Size and timing for 15 bit register (including C call):
8 bit rnd, 26 bytes 19 cycles
16 bit rnd 40 bytes 26 cycles
Size and timing for 23 bit register (including C call):
8 bit rnd, 30 bytes 21 cycles
16 bit rnd, 44 bytes 28 cycles
actual calculation takes 7 cycles per output byte in all 4 cases, rest is call overhead, so it can be optimized if more random bytes is needed at once.
Asm routine was written following Rowley Crossworks register convention.
Note1: shift registers has to be initialized with seed >1 as bit 0 is not used.
Note2: to make periode practically infinite, occasionally alter shift reg. bits with bit 0 of ADC result (1 bit is enough)

C usage example:

unsigned int rnd16(void);
unsigned int w[200];

GPIOR0=2;GPIOR1=0; // initialize seed
for (i=1;i<200;i=++) w[i]=rnd16();

Enjoy, Ivan

;RND.asm
; Pseudo Random Number Generator functions  8/16 bit  15/23 bit Maximum Lengts Sequences
; (c) Ivan Mellen, Oct 2008
; imellen at embeddedsignals dot com

; C interface
;unsigned char rnd8(void);    // 8 bit rnd, 26 bytes 19 cycles  [15 14] MLS
;unsigned int rnd16(void);    //16 bit rnd  40 bytes 26 cycles  [15 14] MLS
;unsigned char rnd8_23(void); // 8 bit rnd, 30 bytes 21 cycles  [23 14] MLS
;unsigned int rnd16_23(void); //16 bit rnd, 44 bytes 28 cycles  [23 14] MLS



; Crossworks C /ASM interface:
; R27 (and R26 for int) input / output from function
; asm fun can use R20-27,R0-1, R30-31

#include 

; Go to code section.
        code
        even

;-------------------------------------------------------------------
;unsigned char rnd8(void); //8 bit rnd, 26 bytes 19 cycles (7c iteration) [15 14] MLS
; periode: 32,767  (4096 unique bytes, remaining 7 iteration shifted version)

  public _rnd8

_rnd8 proc
        in r27,17  ;L  reg17 is L
        in r26,18  ;H  reg 18 is H
        ldi r24,0 ;this will save cycles in multi byte version

        mov r23,r27 ;AL=L
        mov r22,r26 ;AH=H

        lsl r23
        rol r22  ;AH:AL <<1

        eor r26,r22 ;AH=AH eor H

        lsl r26; C<-AH.7, AH<<1   new L byte
        adc r27,r24 ;L.0 <-C
     
      
        out 17,r26  ; new L.1-7 is eor product0-6 (msb eor is in r27.0)
        out 18,r27  ;old L is new H   also return value (top 8 bits HL) 
        ret
        endproc
;-------------------------------------------------------------------
;unsigned int rnd16(void); //16 bit rnd   40 bytes 26 cycles (14c iteration) [15 14] MLS
; periode: 32767  (2048 unique words, remaining 15 iterations shifted version)
     public _rnd16

_rnd16 proc
        in r27,17  ;L  reg17 is L
        in r26,18  ;H  reg 18 is H
        ldi r24,0 ;this will save cycles in multi byte version

        mov r23,r27 ;AL=L
        mov r22,r26 ;AH=H

        lsl r23
        rol r22  ;AH:AL <<1

        eor r26,r22;AH=AH eor H

        lsl r26; C<-AH.7, AH<<1   new L byte    new L
        adc r27,r24 ;L.0 <-C   ;first 8 bits    new H  1st return value (high part)

        ; get 2nd byte

        mov r23,r26 ;AL=L
        mov r22,r27 ;AH=H

        lsl r23
        rol r22  ;AH:AL <<1

        eor r27,r22 ;AH=AH eor H

        lsl r27; C<-AH.7, AH<<1   new L byte
        adc r26,r24 ;L.0 <-C  ;first 8 bits    new H  2nd return value (low part)
      
        out 17,r27  ; new L.1-7 is eor product0-6 (msb eor is in r26.0)
        out 18,r26  ;old L is new H   also return value (top 8 bits HL) 
        ret
        endproc


;-------------------------------------------------------------------
;unsigned char rnd8_23(void); //8 bit rnd, 30 bytes 21 cycles (7c iteration)  [23 14] MLS 
; periode: 8,388,607  (1,0485,576 unique bytes, remaining 7 iteration shifted version)
  public _rnd8_23

_rnd8_23 proc
        in r26,17  ;L  GPIOR0 is L
        in r27,18  ;H  GPIOR1 is M
        in r25,19  ;H  GPIOR2 is H
        ldi r24,0 ;this will save cycles in multi byte version

        mov r20,r26 ;L2=L
        mov r21,r27 ;M2=M

        lsl r20
        rol r21  ;M2:L2 <<1

        eor r21,r25 ;M2 = M2 eor H

        lsl r21; C<-M2.7, M2<<1   new L byte
        adc r26,r24 ;L.0 <-C      new M byte
                          ; M  is new H byte (also output)
      
        out 17,r21  ; new L.1-7 is eor product6-0 (msb eor is in r27.0)
        out 18,r26  ;old L + bit 0 from eor bit 7 is new M
        out 19,r27  ;old M is new H   also return value (top 8 bits HML) 
        ret
        endproc

;-------------------------------------------------------------------
;unsigned int rnd16_23(void); //16 bit rnd, 44 bytes 28 cycles (14c iteration)  [23 14] MLS 
; periode: 8,388,607  (524288 unique words, remaining 15 iteration shifted version)
  public _rnd16_23

_rnd16_23 proc
        in r26,17  ;L  GPIOR0 is L
        in r25,18  ;H  GPIOR1 is M
        in r27,19  ;H  GPIOR2 is H
        ldi r24,0 ;this will save cycles in multi byte version

        mov r20,r26 ;L2=L
        mov r21,r25 ;M2=M

        lsl r20
        rol r21  ;M2:L2 <<1

        eor r27,r21 ;H = M2 eor H

        lsl r27; C<-H.7, H<<1     new L byte 27
        adc r26,r24 ;L.0 <-C      new M byte 26
                          ; M  is new H byte 25
   ; get 2nd byte -----------------
        mov r20,r27 ;L2=L
        mov r21,r26 ;M2=M
       
        lsl r20
        rol r21  ;M2:L2 <<1

        eor r25,r21 ;H = M2 eor H

        lsl r25; C<-H.7, H<<1     new L byte 25
        adc r27,r24 ;L.0 <-C      new M byte 27(also output)
                          ; M  is new H byte 26(also output)
      
        out 17,r25  ; new L.1-7 is eor product6-0 (msb eor is in r27.0)
        out 18,r27  ;old L + bit 0 from eor bit 7 is new M
        out 19,r26  ;old M is new H  
        ret
        endproc

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thanks!

Dr. David Harris OpenLCB Development Team openlcb.org