Random int

Projects General Guidance
7

raschemmel:
This function is from the second link posted by BillHo

 void getRandomNo() {

int rand = random(10,13);
  if(rand == previousNo) {
    getRandomNo();
  } else {
    randomNumber = rand;
    previousNo = randomNumber;
  }





(SNIPPET from second link posted by BillHo

This is a very dangerous solution as

  • it is a recursive function which will randomly eat the complete heap/stack (chance it will repeat is 1 in 3, that is fairly big.)
  • it can continue indefinitely (in theory) causing deadlock

non recursive version 1:

void getRandomNo() 
{
  int rand;
  do 
  {
    rand = random(10,13);
  }
  while (rand == previousNo) ;
  randomNumber = rand;
  previousNo = randomNumber;
}

This variation will not eat the stack but can still run indefintely (livelock).

non recursive version 2, constant time, no livelock.

void getRandomNo() 
{
  // all possible values
  int ar[3] = { 10, 11, 12 };  

  // remove previous random value from the array 
  for (int i=0; i< 2; i++)
    if (ar[i] == previousNo)  
    {
      ar[i] = ar[2];
      break;
    }

  // make a selection from the remaining values
  int idx = random(2);  // note the 2 instead of 3.
  randomNumber = ar[idx];
  previousNo = randomNumber;
}

Yes, although this seems to work it has a new drawback that it does not scale very well
(assume you need a random number 0..20000 => the array won't fit in memory)

version 3:

// the [] and <>  and () in the comments are 3 scenarios...
void getRandomNo() 
{
  int min = 10;
  int max = 13;
  int rangeSize = max - min;  // == 3

  int rand = random(rangesize) + min  // (10)  [10]  <12>
  if (rand == previousNo)    //  (false)  [true] <true>
  {
    int offset = random(rangeSize -1) + 1;   //   { 1.. rangeSize-1 }   [1]    <2>
    rand = rand + offset;  //    [11]  <14>
    if (rand >= max) rand = rand - max + min; // wrap if needed //  [11] is OK  <14> ==>  <11>
  }
  randomNumber = rand;  //  (10) [11] <11>  
  previousNo = randomNumber;
}

This version is

  • not recursive, will not eat stack
  • will not livelock as there are no loops
  • the runtime depends only on the 'collision' with the previous random number, longest path = ~2x short path
  • scales up for any continuous range,
  • no large footprint -> hold no array of values.

For non continuous ranges a solution needs a more complex range administration (left as homework :slight_smile: