Generating random numbers takes too long!

My LED multiplexing code operates at a rate of about 20-30 µS per column. I want to add some random behavior, but the random() function takes as much as 130 µS per call. So if I try to call it while multiplexing, the last column appears to flash brighter.

My temporary workaround is to generate a large number of random ints into an array beforehand, during setup, but I am limited by the paltry flash size.

Does anyone know of a quicker way to generate random numbers on the fly?

Maybe:
http://sensorium.github.io/Mozzi/doc/html/group__random.html#details

These replace Arduino random() which is so slow it will stop your audio. They can even be used to generate audio noise.

I do not know how granular the library is, so I do not know if there is a bloat issue... but, try it.

Ray

Wow, that sounds like exactly what I'm looking for, but can you expand on your notes? What do you mean by bloat issue?

might try another random generator, please time this one for the records

/*
An example of a simple pseudo-random number generator is the 
Multiply-with-carry method invented by George Marsaglia. It is 
computationally fast and has good (albeit not cryptographically 
strong) randomness properties.[7] (note that this example is not 
thread safe):

m_w = <choose-initializer>;    // must not be zero 
m_z = <choose-initializer>;    /* must not be zero 
 
uint get_random()
{
    m_z = 36969 * (m_z & 65535) + (m_z >> 16);
    m_w = 18000 * (m_w & 65535) + (m_w >> 16);
    return (m_z << 16) + m_w;  /* 32-bit result 
}
*/

void setup()
{
  Serial.begin(115200);
}

void loop()
{
  Serial.println(getRandom());
  //long x = getRandom();
}


// An example of a simple pseudo-random number generator is the 
// Multiply-with-carry method invented by George Marsaglia.
// two initializers (not null)
unsigned long m_w = 1;
unsigned long m_z = 2; 

unsigned long getRandom()
{
    m_z = 36969L * (m_z & 65535L) + (m_z >> 16);
    m_w = 18000L * (m_w & 65535L) + (m_w >> 16);
    return (m_z << 16) + m_w;  /* 32-bit result */
}

What do you mean by bloat issue?

If you #include a library BUT do not use it, the compiler will remove the reference and the code-size (flash) and memory requirements (SRAM) will not change. When you reference the library functions, some or all of the library is included, depending upon how well the library is written (software architecture.)

So, if lots of non-used functions are added even when you only use one function, I call that code-bloat... kind of an all or nothing implementation.

If the library is granular, functions are included as are needed (based upon dependencies.)

Ray

Couldn't wait how fast it was...

uint32_t total = 0;
float count = 0;

void setup()
{
  Serial.begin(115200);
}

void loop()
{
  uint32_t start = micros();
  uint32_t x = getRandom();
  uint32_t stop = micros();
  count++;
  total += stop - start;
  Serial.println(total/count, 2);
  Serial.println(x);
}

on average ~14 usec

but the random() function takes as much as 130 µS per call

so that is almost a factor 10 ...

update: the Arduino random function takes : 101.67 on my UNO
Still a factor 7

Look at standard C random functions

Just Google Random in C

http://zygomorphic.com/arduino-tiny/?p=78

Much faster and good quality...
http://zygomorphic.com/arduino-tiny/?p=26
https://code.google.com/p/arduino-tiny/source/browse/cores/tiny/tc_random_XorShift.cpp?repo=core2

Very much faster but very poor quality (good choice for blinkies; bad choice for games of chance)...
http://zygomorphic.com/arduino-tiny/?p=62
(let me know if you want the source code)

Give the multiplexing code priority. I did this by using a timer interrupt. The ISR actually contains the multiplexing code. Human interface gets the priority!

robtillaart:
might try another random generator, please time this one for the records

/*

An example of a simple pseudo-random number generator is the
Multiply-with-carry method invented by George Marsaglia. It is
computationally fast and has good (albeit not cryptographically
strong) randomness properties.[7] (note that this example is not
thread safe):

m_w = ;    // must not be zero
m_z = ;    /* must not be zero

uint get_random()
{
    m_z = 36969 * (m_z & 65535) + (m_z >> 16);
    m_w = 18000 * (m_w & 65535) + (m_w >> 16);
    return (m_z << 16) + m_w;  /* 32-bit result
}
*/

void setup()
{
  Serial.begin(115200);
}

void loop()
{
  Serial.println(getRandom());
  //long x = getRandom();
}

// An example of a simple pseudo-random number generator is the
// Multiply-with-carry method invented by George Marsaglia.
// two initializers (not null)
unsigned long m_w = 1;
unsigned long m_z = 2;

unsigned long getRandom()
{
    m_z = 36969L * (m_z & 65535L) + (m_z >> 16);
    m_w = 18000L * (m_w & 65535L) + (m_w >> 16);
    return (m_z << 16) + m_w;  /* 32-bit result */
}

This one is working great for me. Thanks! Much faster!

after the last row just switch of the leds, then do other work, like comms, random etc, and then do a scan again of your leds, now the leds will be off a little longer.

shooter:
after the last row just switch of the leds, then do other work, like comms, random etc, and then do a scan again of your leds, now the leds will be off a little longer.

Shooter,
You nailed it. I discovered this a couple days ago. Evens out the PWM.

Also, this is a very helpful read concerning good random number generation and offers one that is even better called JKISS which I will reproduce here
http://www0.cs.ucl.ac.uk/staff/d.jones/GoodPracticeRNG.pdf

static unsigned int x=123456789,y=987654321,z=43219876,c=6543217; /* Seed variables */
unsigned int JKISS()
{
unsigned long long t;
x=314527869*x+1234567;
y^=y<<5;
y^=y>>7;
y^=y<<22;
t =4294584393ULL*z+c;
c= t>>32;
z= t;
return x+y+z;
}

bwinter88:

Also, this is a very helpful read concerning good random number generation and offers one that is even better called JKISS which I will reproduce here
http://www0.cs.ucl.ac.uk/staff/d.jones/GoodPracticeRNG.pdf

static unsigned int x=123456789,y=987654321,z=43219876,c=6543217; /* Seed variables */

unsigned int JKISS()
{
unsigned long long t;
x=314527869x+1234567;
y^=y<<5;
y^=y>>7;
y^=y<<22;
t =4294584393ULL
z+c;
c= t>>32;
z= t;
return x+y+z;
}

Note that the unsigned ints should be unsigned long for Arduino …

JKISS32 is a better choice for AVR processors.
http://zygomorphic.com/arduino-tiny/?p=39