• Welcome to our site! Electro Tech is an online community (with over 170,000 members) who enjoy talking about and building electronic circuits, projects and gadgets. To participate you need to register. Registration is free. Click here to register now.

Tiny Random Number Generator challenge

Status
Not open for further replies.

Mr RB

Well-Known Member
Does anyone know a good way of generating a random(ish) number very fast and simple, ie minimum number of PIC 16F instructions or minimum steps in a C algorithm that will compile down to a few PIC instructions.

The goals (in order of priority);
* very small code size
* very fast
* minimal ram vars needed (1 byte is good)
* reasonably random
* produces a 2bit or 3bit random number as the result
* the 2 or 3 bits will be in the least sig bits of the working/output register

The randomness does not need to be perfect. A sequence that repeats after a hundred cycles or so would be ok, or more than a hundred would be better.

It is to be used for hobby robots etc that often need to choose between a few options, like turn left/right etc or make random sound 1,2,3,4 etc. You get the idea.

I'd like to avoid the use of multiplications (as a PIC 16F has no hardware multiplier), and avoid multiple cycles/loops etc as used in most of the "standard" simle RNG systems. Something that toggles a bit mask, does a RRF, does an XOR with the previous value etc. As long as it only takes a few simple operations and doesn't need looping or anything that takes up ROM or wastes time. RAM is more available than ROM, so something that saves a handful of ROM words while needing just another RAM byte would be the better choice. My apps usually have a couple of "temp" RAM vars that can be used by anything, so these would be available too.

Or maybe some system that makes use a free running timer, I always have a timer free running at 1:1 prescaler if that helps. Although my preference is not to use a timer.

As always I am open to totally off-the-wall solutions... ;)
 
Last edited:

Pommie

Well-Known Member
Most Helpful Member
If no one answers then I'll post one tomorrow. Too late, and far too much beer, to work it out now.

Mike.
 

bobledoux

Member
Look at Microchip Application Note AN544. See page 4-35. The code requires two file registers and twelve programming steps.
 

Franchie

New Member
Here is a fairly standard way, pretty boring, but somewhat effective...
It just requires a byte shift and a XOR, pretty easy for the PIC :D.
Here is some pseudo-c code:
Code:
unsigned char rng()
{
	static unsigned char history = 0x01;		/* Seed, choose whatever you like! */
	history <<= 1;
	history |= (((history&2)>>1) ^ ((history&128)>>7));
	return history&3;						/* 2-bit output */
}
This should (if I can still think) produce 2^7-1 unique random numbers before repeating the sequence... Basically play on a variation of this, and its great! :p

Hope this helps,
Franchie
 

Mr RB

Well-Known Member
Franchie -
Code looks good, no non-binary math etc, but I compiled your code and it's still pretty large and slow. It compiles to 38 PIC instructions. Some of that is the compilers stack management, so it could probably be swapped with a bit of inline assembly etc to get it down in code size. Also the >>7 is pretty nasty, 7 loops of 6 instructions (ouch) but again that could probably be re-written in assembler with bit7 handling. It might still be overkill anyway, giving a good 8bit random number when I just need a couple of fairly random bits...

bobledoux-
I read up on AN544. That psuedo random code doesn't look too bad;
Code:
01136 ;*******************************************************************
01137 ;
01138 ; Random Number Generator
01139 ;
01140 ; This routine generates a 16 Bit Pseudo Sequence Random Generator
01141 ; It is based on Linear shift register feedback. The sequence
01142 ; is generated by (Q15 xorwf Q14 xorwf Q12 xorwf Q3 )
01143 ;
01144 ; The 16 bit random number is in location RandHi(high byte)
01145 ; & RandLo (low byte)
01146 ;
01147 ; Before calling this routine, make sure the initial values
01148 ; of RandHi & RandLo are NOT ZERO
01149 ; A good chiose of initial random number is 0x3045
01150 ;*******************************************************************
01151 ;
0311 01152 Random16
0311 1A19 01153 rlcf RandHi,W
0312 0C19 01154 xorwf RandHi,W
0313 1B0A 01155 rlcf WREG, F ; carry bit = xorwf(Q15,14)
01156 ;
0314 1D19 01157 swapf RandHi, F
0315 1C18 01158 swapf RandLo,W
0316 230A 01159 rlncf WREG, F
0317 0C19 01160 xorwf RandHi,W ; LSB = xorwf(Q12,Q3)
0318 1D19 01161 swapf RandHi, F
0319 B501 01162 andlw 0x01
031A 1B18 01163 rlcf RandLo, F
031B 0D18 01164 xorwf RandLo, F
031C 1B19 01165 rlcf RandHi, F
031D 0002 01166 return
Looks pretty good in terms of code size, 2 ram, speed, no looping etc. It does have a problem that it only generates ONE random bit, the LSB, then shifts everything left. So it does require 2 loops to make 2 random bits.

The trouble is I've been doing some testing and it looks like i need something LESS random. The need for the RNG is to give a more "organic" behaviour to a 2 wheel robot.

The robot moves forward 10 inches, then chooses to turn right or left about 30 degrees. Then repeat. When using very random data the robot can pick "right" many times in a row, so he just ends up turning around in a circle and instead of looking organic and "random" it just looks kinda broken and stupid.

Likewise when it plays a random sound out of 4, it can play the same sound a few times in a row which looks VERY un-random even seems "broken". :(

Now i'm thinking we might need one of Pommie's beer solutions. ;)

I'm think the best solution might be a psuedo RNG 1bit generator (something like the AN544 example) with a "watchdog" that will never let it make the same type of bit more than 3 times, ie never more than 3 "1"bits in a row. Then have 2 of them (with separate seeds of course) to make the 2bits required.

The result would be a 2bit RNG that will never make either bit the same for more than 3 "rolls" and would obviously never make the same 2bit number for more than 3 rolls.

That will work exactly as i need, and appear to be very "random" in an organic way but is looking large and clunky.

Now it comes down to a small fast way to do this. The next example in AN544 is a "gaussian distributed noise generator" that makes random noise to be used in sound generation etc. That type of system might be good as it has reduced chances of making the same bit over and over. But it's rather large, multiple looping etc. :(

Maybe something like the rotating logic register (code above) but with the logic arranged in a way that just won't produce the same bit 3 times in a row?
 

Mr RB

Well-Known Member
Currently I'm leaning toward a "kludge" solution; just using a 8 byte lookup table that has 64 bits and a simple pointer index.

This will repeat the same 64 "random" bits but it does have the advantage of being quick, fairly small code and fast execution time. And it has a great advantage that the bit sequence can be seen and "tuned" by eye to give the kind of psuedo random moving behaviour that will make the robot appear organic and random.

Any thoughts?
 

gabeNC

Member
Just so I understand... are you randomizing the pointer or going through the table sequentially?
 

Pommie

Well-Known Member
Most Helpful Member
Well, my contribution uses 4 ram locations but does produce pretty random numbers. You xor together bits 30 and 27 and feed that into the bottom bit with the other bits shifted left one. You can normally do AND #$48 and ADD #$38 (with the MS byte) to get the random bit into bit 7 of the accumulator. The whole thing is about 7 instructions, call it twice and you have two random bits. I did post a Swordfish version but cant find it.

Mike.
 

Mr RB

Well-Known Member
GabeNC -
Yes I was just thinking of running the 64 bits sequentially with a incrementing pointer. For the second random bit needed; just use the pointer for bit1 but add 32 to it so it is significantly out of phase with bit1 but is still fast to execute.

That is crude I know, if the bot was always making 1in4 decisions the patterns would be obvious, but most decisions are 1in2 with sometimes 1in4 so it would be workable.

Well, my contribution uses 4 ram locations but does produce pretty random numbers. You xor together bits 30 and 27 and feed that into the bottom bit with the other bits shifted left one. You can normally do AND #$48 and ADD #$38 (with the MS byte) to get the random bit into bit 7 of the accumulator. The whole thing is about 7 instructions, call it twice and you have two random bits. I did post a Swordfish version but cant find it.
...
That sounds very similar to the AN544 example I posted above, but they use a 16bit working register and XOR 3 bits to get the new one.

I'm getting a bit obsessed by the "not repeating any bit more than 3 times thing".

My little robot looks so stoopid going round and round in circles. ;)

For the repeating of any type of bit; ideally there should be a fairly even spread of X and XX units with some occasional XXX units and never a XXXX unit. Maybe something based on 3bit binary math, that has 2in8 chance of being a XXX (ie 000 and 111) and 2in8 of being X (010 and 101) and 4in8 odds of being a XX (001 011 100 110), then ensuring that the next 3 bit number must start with a different bit type so that always adds 1 more X unit for every 8 combos.

If I was a math guy I'd have a probability formula for that but i'm just a visualisation guy. :)
 

Nigel Goodwin

Super Moderator
Most Helpful Member
Doesn't really quite meet your requirements, but here's some code I used back in 2001 (from the date in the file) - the receiver software is at the bottom of the page.

Cybot IR Obstacle Detector Page

The robot is controlled via a radio module, with simple commands, but also includes IR 'radar' - if the left sensor detects something then it moves right, and if the right sensor detects something it moves left. The problem was if both sensors detected something - originally I had it reverse, but that was fairly rubbish :D. So next I had it always turn one way, but obviously that was only right half of the time.

I came up with a very simple, completely random (as far I know) solution.

The robot uses software PWM, using timer interrupts, so I used that to increment a counter every interrupt. The 'both sensors' triggered routine simply checks bit 0 of that counter, and turns left or right accordingly - and the counter interrupts are so much faster than real life, that it gives a nice random movement.
 

bananasiong

New Member
How about ADC with the analog input pin floating? You're not going to know what number you will be getting and it should be pretty random. How fast do you want it to be?
 

Noggin

Member
How about ADC with the analog input pin floating? You're not going to know what number you will be getting and it should be pretty random. How fast do you want it to be?
I tried that before and found out that it was far from random. I then tried using just the last bit in the following algorithm:

1. Read ADC value
2. Note LSB of ADC conversion
3. Read ADC value
4. Note LSB of ADC conversion
5. If bits were 0 then 1, shift 0 into a register
6. If bits were 1 then 0, shift 1 into a register
7. If bits were 1 then 1 or 0 then 0, do not shift anything into the register
8. Repeat until you have stored 8 bits

The idea is that there has to be just as many transitions from 1 to 0 as there are from 0 to 1 and I figured I'd get an even distribution. Turns out though that reading the ADC value seemed to cause a pattern to appear so that I actually received far more 0's then 1's (or more 1's than 0's, I don't remember). By inserting a few mS delay between ADC readings, the results were darn near random.

I then used 3 NOR gates in a loop and tied one of the gate's output to an input on the AVR. Instead of reading the ADC value of a floating pin, I read the digital value of the NOR gate and applied the same algorithm to it. It was much faster and just as random.

I think this algorithm would take more code space than RB wants to use though.
 
Last edited:

Pommie

Well-Known Member
Most Helpful Member
To convert Franchie's example into asm ,
Code:
unsigned char rng()
{
	static unsigned char history = 0x01;		/* Seed, choose whatever you like! */
	history <<= 1;
	history |= (((history&2)>>1) ^ ((history&128)>>7));
	return history&3;						/* 2-bit output */
}
Becomes,
Code:
Rand	rlf	Random,w	;shift and move to W
	andlw	0x82		;keep bits 7 and 1
	addlw	0x7e		;xor into bit 7
	addlw	0x80		;move to carry bit
	rlf	Random,f	;shift into seed
	return
You only get 1 random bit per call but it's pretty compact.

Edit, Random has to be seeded with a non zero value.

Mike.
 
Last edited:

Mr RB

Well-Known Member
Nigel-
Nice robot! Lots of nice stuff on your cybot page too.

Nigel-bananasong-noggin-
Thanks but I really wanted to avoid a hardware solution.

Pommie-
Wow I'm amazed you got Franchie's C code minimalised down to 5 assembler instructions!!! :eek: That makes you 7.6 times smarter than my C compiler! ;)

That is some seriously nice work. I changed your constants to binary for clarity, then wrapped it in a loop and simulated it in MPLAB;

Code:
;==============================================================================
; test franchies simple 1byte RNG
; using pommies clever asm code
;==============================================================================
; config for 16F628
	__CONFIG   _CP_OFF & _WDT_OFF & _PWRTE_ON & _XT_OSC & _MCLRE_ON & _BODEN_ON & _LVP_OFF
	include <p16f628.inc>

	CBLOCK 0x20			; start of ram in 16F628
		bitcount			; number of bits to make
		random			; the 1byte random number
	ENDC

;==============================================================================
; Code here
	org 0x000 			; 
reset
	goto main				;

;==============================================================================
main
	movlw b'11010010'		; seed RNG
	movwf random			;

	; loop here and make 8 random bits
rng_make8bits
	movlw d'8'			;
	movwf bitcount			;

rng_make1bit
	rlf random,w			; shift and move to w
	andlw b'10000010'		; keep only bit7 and bit1
	addlw b'01111110'		; xor bit7^bit1 into bit7 (brilliant)
						; truth table of (addlw b'01111110');
						; (7^1 -> 7)
						;  1^1 = 0
						;  0^0 = 0
						;  1^0 = 1
						;  0^1 = 1

	addlw b'10000000'		; move w bit7 into carry
	rlf random,f			; put carry in bit0

	; now it has generated 1 random bit
	decfsz bitcount,f;		
	goto rng_make1bit		;

	; now it has generated 8 random bits
	; (breakpoint here for testing)
	goto rng_make8bits		;
	end
I wrapped it at 8 bits generated then used a breakpoint and the watchwindow set to display in binary. I'm rusty with MPLAB so there may be easier ways, but it was easy enough to generate the random data and cut/paste it to a text file;

Code:
(rng bit = 7^1, seed = 11010010)
11000110111101101011011001001000
11100001011111001010111001101000 
10011110001010000110000010000001
11111101010100110011101110100101
This looks pretty good, no repeats in 128 bits but like "good" random data there were some strings of 6,5,4. It's still amazingly good for 5 asm instructions, Franchie's process is excellent.

Since this is so fast and small I can just add a watchdog on the end to ensure there are no bitstrings longer than 3. But before doing that I wanted to test some variations, there may be a setup that produces randomish data but with only short strings.

I modded Pommie's code to do (5^1) instead of (7^1);
Code:
	; 5^1
	rlf random,w			; shift and move to w
	andlw b'00100010'		; keep only bit5 and bit1
	addlw b'00011110'		; xor bit5^bit1 into bit5 (brilliant)
	andlw b'00100000'		; keep only bit5
	addlw b'11100000'		; move w bit5 into carry
	rlf random,f			; put carry in bit0
This worked great and made no bitstring longer than 3;
Code:
(rng bit = 5^1, seed = 11010010)
11100101110010111001011100101110
01011100101110010111001011100101
(repeats pattern 1110010)

(rng bit = 5^1, seed = 10000010)
00011111010100110001000011111010
10011000100001111101010011000100
(repeats 000111110101001100010)
But it repeats badly, then changing the seed changes the output and lengthens the repeat.

So now Franchie provided a great process and Pommie got it down to 5 instructions, looks like I have a choice of coding a small post-process to ensure there are no bitstrings longer than 3, OR keep messing with the orig process to find a "random enough" system that only has short bitstrings...

Thanks again everybody this has been great teamwork. :)
 
Last edited:

Mr RB

Well-Known Member
Darn thought I had it done with just 7 extra instructions...
But not quite.

Code:
;==============================================================================
; test franchies simple 1byte RNG
; using pommies clever asm code
; plus romans kludge to kill xxxx0000 and xxxx1111
;==============================================================================
; config for 16F628
	__CONFIG   _CP_OFF & _WDT_OFF & _PWRTE_ON & _XT_OSC & _MCLRE_ON & _BODEN_ON & _LVP_OFF
	include <p16f628.inc>

	CBLOCK 0x20			; start of ram in 16F628
		bitcount		; number of bits to make
		random			; the 1byte random number
	ENDC

;==============================================================================
; Code here

	org 0x000 			; 
reset
	goto main			;

;==============================================================================
main
	movlw b'11010010'		; seed RNG
	movwf random			;

	; loop here and make 8 random bits
rng_make8bits

	movlw d'8'			;
	movwf bitcount			;

rng_make1bit

	rlf random,w			; shift and move to w
	andlw b'10000010'		; keep only bit7 and bit1
	addlw b'01111110'		; xor bit7^bit1 into bit7 (brilliant)
					; truth table of (addlw b'01111110');
					; (7^1 -> 7)
					;  1^1 = 0
					;  0^0 = 0
					;  1^0 = 1
					;  0^1 = 1

	addlw b'10000000'		; move w bit7 into carry
	rlf random,f			; put carry in bit0

	; test if random is xxxx1111 or xxxx0000
	; if so; invert the new random bit (bit0)

	incf random,w			; is now xxxx0000 or xxxx0001
	andlw b'00001111'		; keep last 4 bits
	sublw d'1'			; sub to test w
	movlw b'00000000'		; load w ready to NOT invert random bit0
	skpnc				; skip if w was > 1
	movlw b'00000001'		; load w to invert random bit0
	xorwf random,f			; invert bit0 if needed


	; now it has generated 1 random bit
	decfsz bitcount,f;		
	goto rng_make1bit		;

	; now it has generated 8 random bits
	; (breakpoint here for testing)
	goto rng_make8bits		;
	end
I added a basic kludge to check for 1111 and 0000 string and if so; invert the last (new) bit. But it kills the RNG, makes it repeat after 34 bits;

Code:
(New test (7^1) and check for 0000 and 1111
and invert bit0 if needed.)
11000110111010010110001101110100
10110001101110100101100011011101
00101100011011101001011000110111
01001011000110111010010110001101
(has a 34bit repeat...)
So now it looks like I have to copy each new RNG bit to an output buffer, then do the 1111/0000 correction on the output buffer to preserve the integrity of the RNG.

Now the code is starting to get big again...
 
Last edited:

Mr RB

Well-Known Member
Ok, I think i got it. I changed the kludge so when it detects 1111 or 0000; instead of just inverting the most recent bit it inverts bit3 too (so it xors random with 00001001).

Code:
;==============================================================================
; test franchies simple 1byte RNG
; using pommies clever asm code
; plus romans kludge to kill xxxx0000 and xxxx1111
;==============================================================================
; config for 16F628
	__CONFIG   _CP_OFF & _WDT_OFF & _PWRTE_ON & _XT_OSC & _MCLRE_ON & _BODEN_ON & _LVP_OFF
	include <p16f628.inc>

	CBLOCK 0x20			; start of ram in 16F628
		bitcount			; number of bits to make
		random			; the 1byte random number
	ENDC

;==============================================================================
; Code here

	org 0x000 			; 
reset
	goto main				;

;==============================================================================
main
	movlw b'11010010'		; seed RNG
	movwf random			;

	; loop here and make 8 random bits
rng_make8bits

	movlw d'8'			;
	movwf bitcount			;

rng_make1bit

	rlf random,w			; shift and move to w
	andlw b'10000010'		; keep only bit7 and bit1
	addlw b'01111110'		; xor bit7^bit1 into bit7 (brilliant)
						; truth table of (addlw b'01111110');
						; (7^1 -> 7)
						;  1^1 = 0
						;  0^0 = 0
						;  1^0 = 1
						;  0^1 = 1

	addlw b'10000000'		; move w bit7 into carry
	rlf random,f			; put carry in bit0

	; test if random is xxxx1111 or xxxx0000
	; if so; invert the new random bit (bit0)

	incf random,w			; is now xxxx0000 or xxxx0001
	andlw b'00001111'		; keep last 4 bits
	sublw d'1'			; sub to test w
	movlw b'00000000'		; load w ready to NOT invert random bit0
	skpnc				; skip if w was > 1
	movlw b'00001001'		; load w to invert random bit0 (and bit3)
	xorwf random,f			; invert bit0 if needed


	; now it has generated 1 random bit
	decfsz bitcount,f;		
	goto rng_make1bit		;

	; now it has generated 8 random bits
	; (breakpoint here for testing)
	goto rng_make8bits		;
	end
There are lots of repeating short strings in the output (which you expect because it can never get a 1111 or 0000) but the RNG always shakes itself up again after a while.

For a psuedo RNG to make a robot look "organically random" I can live with this (sill uses only 12 PIC insts);

Code:
(7^1, seed 11010010, on 1111 or 0000 we
xor random with 00001001);
11000110011010001000110111010001
00011011101000100011011101000100
01100110100010011100110100010011
10011010001001110011010001000110
01101000100011011101000100011011
10100010001101110100010001100110
10001001110011010001001110011010
00100111001101000100011001101000
 
Last edited:

Noggin

Member
I wasn't suggesting that you try what I had written out, I'm sure the code output is much too large. I only put it out there because I had been down the road of trying to use the ADC as someone else tried and that was my experiences with it. I needed something in hardware though as I was working on a security device for cash dispensers.

If you're curious about seeing how random your generator is, check out the Diehard tests. Here's a little bit of info at Wikipedia: Diehard tests - Wikipedia, the free encyclopedia
 
Last edited:

Pommie

Well-Known Member
Most Helpful Member
I see you like the xor kludge, I thought it was rather clever. I can't claim credit for it though, I first came across it about 20 years ago in 6502.

In your final code, can you save an instruction by doing,
Code:
	movlw b'00001001'		; load w to invert random bit0 (and bit3)
	skpnc				; skip if w was > 1
	xorwf random,f			; invert bit0 if needed
Mike.
 
Last edited:

Mr RB

Well-Known Member
Thanks Noggin I did appreciate your input. :) And yeah hardware RNG is probably the best anyway (as in most random) compared to a math sequence, i've used hardware RNG before, usually to "break up" a pretty good software RNG.

The output from my final system (in post16) is most UN-random, it would score terrible on the Diehard tests as it has lots of 14bit strings that are very similar and then the entire system repeats at 120bits.

But Franchies 8bit RNG (is really a 7bit RNG as it left-shifts the seed before generating) can never go more than 128bits without repeating as the very best case, so getting mine to 120bits before full repeat AND making sure there can never be any bitstring longer than 3 bits is no easy task.

For the job of getting a robot to pick right/left it is pretty much perfect for organic looking behaviour and randomly covering the search area.

But if anyone can get getter randomness from just 12 insts AND not exceed 3bit strings, or can get the total thing under 12 insts than that would be most welcome.

(edit) Sorry Pommie we posted at the same time! Hmm, smaller again! That's cool, down to 11 instructions;

Code:
	rlf random,w			; shift and move to w
	andlw b'10000010'		; keep only bit7 and bit1
	addlw b'01111110'		; xor bit7^bit1 into bit7 (brilliant)
	addlw b'10000000'		; move w bit7 into carry
	rlf random,f			; put carry in bit0

	; test if random is xxxx1111 or xxxx0000
	; if so; invert the new random bit (bit0)
	incf random,w			; is now xxxx0000 or xxxx0001
	andlw b'00001111'		; keep last 4 bits
	sublw d'1'			; sub to test w
	movlw b'00001001'		; load w to invert random bit0 (and bit3)
	skpnc				; skip if w was > 1
	xorwf random,f			; invert bit0 if needed
 
Last edited:

Mr RB

Well-Known Member
I had an idea last night; instead of making a good RNG to start and then squishing it down to ensure no string is longer than 3, to try the other approach. ie make a bad RNG that can never exceed a string of 3, then do something to "shake it up" a little and improve the randomness slightly...

It seems to work pretty good.

I started with the most basic RNG possible that can't produce more than 3bits in a row;

Code:
	movlw d'46'			; main toggle on 128/46 
	addwf rngloop,f		;
By adding 46 to a variable rngloop, bit7 of rngloop toggles every 2 or 3 bits. Since bit7 toggles every 128 counts, the output is 128/46 =2.78260869565 so it mostly produces strings of 3bits with some 2bit strings, and is 100% successful that it can never make a bitstring longer than 3, see its output;

Code:
(128/46 =2.78260869565)
10001110011100011100011000111000
11000111000111001110001110001100
01110001100011100011100111000111
00111000111000110001110001110011
So that is the bad RNG that can't make longer than 3bit strings. And 2.78260869565 is random enough that even with all the short term repeats, there is a good long term random factor that will shake it up every so often.

Now to add a second process that forces bit7 of rngloop to toggle more frequently. This will convert some of the 3bit and 2bit strings to 2bit and 1bit strings BUT still never allowing any string to exceed 3bits...

Code:
	; make a random bit in rngloop,7 (total 7 instructions)
	movlw d'46'			; main toggle on 128/46 
	addwf rngloop,f		;

	movlw d'104'			; force to toggle 256/104
	addwf rngforced,f		;
	movlw (d'128'-d'46')	; this forces temp,7 to toggle
	skpnc				;
	addwf rngloop,f		;
The second process is just another additive loop, that adds 104 to a variable (rngforced). This overflows rngforced every 256/104 (2.46153846153) bits. When this happens, rngloop bit7 is forced to toggle.

So there are 2 systems toggling the random bit; every 2.78260869565 bits there is a natural toggle, then every 2.46153846153 bits there is an additional forced toggle. So now the output sequence contains bitstrings of 1, 2 and 3 but still can never exceed 3. See the output;

Code:
(128/46 =2.78260869565,
+forced toggle on 256/104
=2.46153846153)
11001001101100100110110100010111
01000101110100100110110010011011
01000101110100010111010010011011
00100110110100010111010011011001
00100110110010011011001011011001
00110110010010011011001011101000
10110110010011011001001011101000
10111010001011011001001101100100
I call it a "dual tuned" RNG. Since it is for robot "random personality" you can adjust the max string length from 3 to any value by changing the first constant (46) and you can adjust the number of short bitstrings by tuning the second constant (104). I chose the values above becasue I wanted mainly 1 and 2 length strings with just some occasional 3 strings.

For short term randomness you can tune it to do the "flavour" of decision making to make the robot seem organic as it mnoves around. And long term randomness is excellent beacuse of the "beat" of 2 very large numbers of the 2 systems interacting.

And it's just 7 PIC instructions;
Code:
;==============================================================================
; "Dual tuned" RNG 
; open-source - RomanBlack 13 Sept 2009
; uses dual loops to set the RNG max stringlength and spread
;==============================================================================
; config for 16F628
	__CONFIG   _CP_OFF & _WDT_OFF & _PWRTE_ON & _XT_OSC & _MCLRE_ON & _BODEN_ON & _LVP_OFF
	include <p16f628.inc>

	CBLOCK 0x20			; start of ram in 16F628
		bitcount			; number of bits to make
		random			; the 1byte random number
		rngloop			; for main RNG loop
		rngforced			; for "forced toggle" loop
	ENDC

;==============================================================================
; Code here

	org 0x000 			; 
reset
	goto main				;

;==============================================================================
main

	; loop here and make 8 random bits
rng_make8bits

	movlw d'8'			;
	movwf bitcount			;

rng_make1bit

	; make a random bit in rngloop,7 (total 7 instructions)
	movlw d'46'			; main toggle on 128/46 
	addwf rngloop,f		;

	movlw d'104'			; force to toggle 256/104
	addwf rngforced,f		;
	movlw (d'128'-d'46')	; this forces rngloop,7 to toggle
	skpnc				;
	addwf rngloop,f		;

	; the new random bit is in rngloop,7
	rlf rngloop,w 			; get rngloop,7 in carry
	rlf random,f			; put carry in random,0

	; now it has generated 1 random bit
	decfsz bitcount,f;		
	goto rng_make1bit		;

	; now it has generated 8 random bits
	; (breakpoint here for testing)
	goto rng_make8bits		;
	end				

(128/46 =2.78260869565,
forced toggle on 256/104
=2.46153846153)
11001001101100100110110100010111
01000101110100100110110010011011
01000101110100010111010010011011
00100110110100010111010011011001
00100110110010011011001011011001
00110110010010011011001011101000
10110110010011011001001011101000
10111010001011011001001101100100
 
Last edited:
Status
Not open for further replies.

Latest threads

EE World Online Articles

Loading
Top