Random Generator

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

Hi,

I have a project where I need to generate lots of random short int (8bit). This random is not for casino, just to generate random pixel. it must be short not 200 line of code and I don't want to have external hardware like "diode noise". Quick and dirty cool random generator.

short int Random(short int MaxValue)

Any help will be apreciated

Yours truly,
Sylvain Bissonnette
www.microsyl.com

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

Someone wrote a great post in the Tutorial Forum about (P)RNGs on the AVR - probably worth a look

EDIT: this thread

https://www.avrfreaks.net/index.p...

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

LFSR's seem to be an easy way for a nice sequence of 'random' but not random numbers. Just grabbing the lowest byte is not really the best way to do this, but there are many ways to eliminate the obvious simple shifts from one value to the next. I'm lazy, so just showing simple here.

#include 

uint8_t random(void){
    //32 bit random number, from noinit sram
    static uint32_t random31 __attribute__((section(".noinit")));
    //temp storage for random number
    uint32_t temp;
    temp = random31<<1;
    //if bit31 set, or if init sram happens to be 0
    if((temp & 0x80000000)||(temp == 0)){
        //xor magic number (taps)
        temp ^= 0x20AA95B5;
    }
    //save back to random number for next time
    random31 = temp;
    //return lowest byte only
    return temp;
} 

int main(){
    while(1){
        PORTB=random();
    }
}

I wrote a Rebol app to go through this LFSR sequence
http://www.mtcnet.net/~henryvm/r...
With no graphics, it takes several hours to get through the sequence on a fairly new pc. With nice grahics updating, it takes a lot longer. No analysis is done (I can't), but the number distribution of values stays pretty 'even' in each byte.

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

Hi Sylvain,

Are you open to an assembly language solution with the following characteristics -

A byte table of 256 + 0-16 bytes starting on a flash address of form 0xYY00 and 2-4 bytes of SRAM?

Routine initialization of 4 instructions plus one scratch register (with maybe a single push/pop of this scratch register)

Runtime of about 5 instructions plus one scratch register with push/pop of the Z register?

If a cycle of longer than 256 numbers is required then a larger table (in 256 byte increments) and a about 6 instruction setup and about 12 instruction runtime is needed.

A trade off between table size and a increment of between about 4 to 10 in runtime instructions to give longer sequences is also possible.

No multiplications or shifts are needed.

Regards.

Gordon

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

Last time I needed random behaviour a timer was set up, then I picked up the TCNT as a pointer to a flash table.
The flash table was needed since the app was supposed to blink leds randomly but only one led at a time was allowed to be on.
So probably you don't need the flash table.

As long as your code don't use the same amount of clock cycles between picking up TCNT it will produce a random number between 0-255 by just reading TCNT into a register. Only one instruction to do that + hardware resources. If you already have a timer running maybe reading its TCNT is all needed.

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

Thanks for all the info, I will make some test with your proposition and I will be back on this topic to give you my result.

Yours truly,
Sylvain Bissonnette
www.microsyl.com

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

Finally it`s now done, I use the lowest bit of the ADC read and shifted 16 time in a int add with TCNT and this value is the seed for the LFSR random

Yours truly,
Sylvain Bissonnette
www.microsyl.com

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

sylvain.bissonne wrote:
Finally it`s now done, I use the lowest bit of the ADC read and shifted 16 time in a int add with TCNT and this value is the seed for the LFSR random
If your least bit of your ADC is truly random, then your most random number will be to read the ADC's LSB 16 times while shifting the LSB forward with each read. However, mostly applications do not require this degree of randomness.

Edit: fixed sentence

Last Edited: Fri. Oct 24, 2008 - 01:20 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Yes, I need a good random, it's for a AVR who drive a laser that show on the wall some game like ping pong, drive in tunnel, and more...

Yours truly,
Sylvain Bissonnette
www.microsyl.com

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

I was looking for fast pseudo random number generator few weeks ago. Haven't found any so I wrote my own. 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

Attachment(s): 

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

You might want to check out Chapter 7 of the book, "Numerical Recipes in C". I think there's a free online version of it.

For a PRNG, this is as simple as it gets:

#define M 1664525L
#define A 1013904223L

  unsigned long idum;

  idum = 0;  // seed

  idum = M * idum + A;

I haven't tried this on a ATMEGA, but it works fine on a 32-bit linux machine.

If it's working correctly, you should get this sequence, in hex:
3C6EF35F
47502932
D1CCF6E9
AAF95334
6252E503
9F2EC686
57FE6C2D
A3D95FA8
.
.
.

The 32-bit multiply might take a bit of time, but there's no division required.

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

curtvm wrote:

    static uint32_t random31 __attribute__((section(".noinit")));
 

What does that line do?

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

It defines a 32 bit unsigned int that should be placed in the section ".noinit".

For more on the ".noinit" section: http://www.nongnu.org/avr-libc/u...

In short, variables placed in this section

Quote:
will not be initialized to zero during startup

As of January 15, 2018, Site fix-up work has begun! Now do your part and report any bugs or deficiencies here

No guarantees, but if we don't report problems they won't get much of  a chance to be fixed! Details/discussions at link given just above.

 

"Some questions have no answers."[C Baird] "There comes a point where the spoon-feeding has to stop and the independent thinking has to start." [C Lawson] "There are always ways to disagree, without being disagreeable."[E Weddington] "Words represent concepts. Use the wrong words, communicate the wrong concept." [J Morin] "Persistence only goes so far if you set yourself up for failure." [Kartman]

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0
//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
//
//    8-bit random number generator.
//
//    Copyright 2011  Richard B. Johnson
//    rjohnson@Route495Software.com
//
//    You can use this if you preserve the Copyright notice above.
//
#include 

#if !defined(uint8_t)
typedef unsigned char uint8_t;
#endif

static uint8_t Seed = 0x00;
static uint8_t Magic = 0x5c;

//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
//
//   This, using the 'C' language, rotates all the bits in val to the right
//   the number of bits in nr.
//

static uint8_t RotateRight(uint8_t val, int nr)
{
    uint8_t tmp;
    while(nr--)
    {
        tmp = val & 1;
        tmp <<= 7;
        val >>= 1;
        val |= tmp;
    }
    return val;
}
//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
//
//  Ths pseudo random number generator.
//
uint8_t Rand()
{
    Seed = RotateRight(Seed, 3);
    Seed += Magic;
    
    return Seed;
}
//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
//
//   Seed the random number generator.
//
void Srand(uint8_t val)
{
    Seed = val;
}
//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
//
//    This is for testing. Define SETUP to find tha correct magic number
//    to hard-code.
//

#define TESTING

#ifdef TESTING


#define NoSETUP

int main()
{
    int i;
#ifdef SETUP
    for(;;)
    {
        Seed = 0;
        printf("%02x\n", Magic);
        i = 0;
        while(Rand())
            i++;
        if(i < 0xfe)
            Magic++;
        else
            break;
    }
#else
    for(i=0; i< 0xff; i++)
        printf("%02x\n", Rand());

#endif

    return 0;

}

#endif
//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
//-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
==================================================================================
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If you want a generator with a period of 256 it's better to generate 256 numbers with a good random number generator and store them in a lookup table in flash. It will be faster too.