QUIZ: Implement rand3 with rand2

[Tadeas]

This is not a question (as I know an answer, though there might be several), but rather a quiz, you might be interested in.

Suppose we have a function "rand2" that returns truly random 0 or 1. Now we are asked to implement "rand3", that returns truly random 0, 1 or 2. The statistical probability must be the same for all options (i.e. solutions that return 0 and 1 with 25% probability and 2 with 50% probability are not sufficient).

How would you solve it? Of course it doesn't matter which language you use, or pseudo-code.

Enjoy !

[tomazzi]

You know that in reality there is no such thing like "truly random" numbers right?
So I would not use some artificial rand() function to produce even more artificial results, but instead I would try to use fast fourier transformation (FFT) on white noise sample -> if I would really need randomness - otherwise it doesn't make much sense - and to me it looks like a ... homework.

regards.

[DominiqueM]

I would ask peoples:

Code: Select all

echo "Write an integer number between 0 and 2 and press Enter:"
read RANDOM

[Tadeas]

You know that in reality there is no such thing like "truly random" numbers right?

That's where the magical word 'suppose' comes into the game. Anyway, the interesting question is to find the algorithm.

and to me it looks like a ... homework.

Actually, we ask this on job interviews for software engineers.

[tomazzi]

Actually, we ask this on job interviews for software engineers.

Ok, I uderstand,
just out of curiosity: how much time do You give them to find the algorithm and to proove its correctness?
(so I may test myself whether I'm good enough to get the job in Your company... )

edit:
I did a short reconnaissance over the net to get an overview of how others are solving such problems, but there's nothing especially interresting (maybe excluding this: http://stackoverflow.com/questions/1377 ... m-15-to-17).
So, here's my solution:
<fprintf(sderr, ) does immediate fflush, so it's a bit more thread-safe and I just get used to it >

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int rand3(unsigned int *rndmem) {
   unsigned int mrnd = *rndmem;

   mrnd <<= 1;
   mrnd |= rand() % 2; //rand2()
   *rndmem = mrnd;
   return mrnd %3;
}

int main() {
   unsigned int rnd, rndmem, it, itmax;
   unsigned int stat0, stat1, stat2;

   //init
   itmax = 1000000;
   stat0 = stat1 = stat2 = 0;
   srand (time(NULL));
   rndmem = rand();

   fprintf(stderr, "rand_test:\n");

   for(it=0; it<itmax; it++) {
      rnd = rand3(&rndmem);
      //sequence check, every 1/1024 turns,
      if( (it%(itmax>>10)) == 0 ) fprintf(stderr, "@%d, rnd=%u\n", it, rnd);

      if(rnd == 0) {stat0++ ; continue;}
      if(rnd == 1) {stat1++ ; continue;}
      stat2++ ;
   }

   fprintf(stderr, "\n--> stats:\nstat0=%d, stat1=%d, stat2=%d\nend.\n", \
      stat0, stat1, stat2);

    return 0;
}

example result for itmax=1000000 :

Code: Select all

stat0=333141, stat1=333502, stat2=333357

...so what do You think?

<edit: fixed: tab gives incorrect indentations>

[drl]

Hi.

You know that in reality there is no such thing like "truly random" numbers right? ...

I occasionally use http://www.random.org/ and http://random.irb.hr/ ... cheers, drl

[saulgoode]

C

Code: Select all

int rand3() {
 int x;
 while (! (x = rand2() << 1 | rand2()))
  ;
 return --x;
 }

EDITED: Fixed syntax errors (been doing too much Scheme programming lately).

[tomazzi]

drl: ...and that's why mentioned white noise, which has flat distribution of power on any bandwidth - in other words, it's true source of randomness

Ok, I have horrible wather outside the window - so I've decided to take a closer look at the problem:
Ver2 of the above solution - the only difference is that this time we get much more statistical info:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

unsigned int rand3(unsigned int *rndmem) {
   unsigned int mrnd = *rndmem;

   mrnd <<= 1;
   mrnd |= rand() % 2; //rand2()
   *rndmem = mrnd;
   return mrnd %3;
}

int main() {
   unsigned int rnd, rndmem, it, itmax;
   unsigned int dist0, dist1, dist2;
   unsigned int rndlast;
   unsigned int longser[3], serlast;
   unsigned int totsers[3], singles[3];

   //init
   itmax = 1000000;
   dist0 = dist1 = dist2 = 0;
   it = 0;
   longser[it++] = 0; longser[it++] = 0; longser[it] = 0;
   it = 0;
   totsers[it++] = 0; totsers[it++] = 0; totsers[it] = 0;
   it = 0;
   singles[it++] = 0; singles[it++] = 0; singles[it] = 0;
   srand (time(NULL));
   serlast = 0;
   rndlast = rand() % 2; //rand2()

   #ifdef MOD
      fprintf(stderr, "rand_mod_3 (nturns = %u):\n", itmax);
   #else
      fprintf(stderr, "rand3 (nturns = %u):\n", itmax);
   #endif

   for(it=0; it<itmax; it++) {

      #ifdef MOD
         rnd = rand() % 3;
      #else
         rnd = rand3(&rndmem);
      #endif
      //fprintf(stderr, "%u", rnd);
      //sequence check
      if(rnd == rndlast) {
         serlast++;
      } else {
         serlast++ ;
         if(serlast > 1) {
            //fprintf(stderr, "_ series[%u] len = %u\n", rndlast, serlast);
            totsers[rndlast]++ ;
         } else  {
            singles[rndlast]++ ;
         }
         if(serlast > longser[rndlast]) longser[rndlast] = serlast;
         serlast = 0;
      }
      rndlast = rnd;

      if(rnd == 0) {dist0++ ; continue;}
      if(rnd == 1) {dist1++ ; continue;}
      dist2++ ;
   }

   fprintf(stderr, "--> overall distribution:\n    dist_0=%u, dist_1=%u, dist_2=%u\n", \
      dist0, dist1, dist2);
   fprintf(stderr, "--> single hits:\n    hits_0=%u, hits_1=%u, hits_2=%u\n", \
      singles[0], singles[1], singles[2]);
   fprintf(stderr, "--> longest series:\n    long_0=%u, long_1=%u, long_2=%u\n", \
      longser[0], longser[1], longser[2]);
   fprintf(stderr, "--> total num of series:\n    nser_0=%u, nser1=%u, nser_2=%u\nend.\n", \
      totsers[0], totsers[1], totsers[2]);

    return 0;
}

results for original rand()%3:

Code: Select all

cmd> ./rand_mod3 && sleep 1 && ./rand_mod3 && sleep 2 && ./rand_mod3

Code: Select all

rand_mod_3 (nturns = 1000000):
--> distribution:
    dist_0=333180, dist_1=333737, dist_2=333083
--> single hits:
    hits_0=147851, hits_1=147927, hits_2=147817
--> longest series:
    long_0=14, long_1=11, long_2=12
--> total num of series:
    nser_0=74080, nser1=74354, nser_2=74094
end.
rand_mod_3 (nturns = 1000000):
--> distribution:
    dist_0=333303, dist_1=333522, dist_2=333175
--> single hits:
    hits_0=148079, hits_1=148670, hits_2=148255
--> longest series:
    long_0=11, long_1=14, long_2=11
--> total num of series:
    nser_0=74001, nser1=73844, nser_2=73933
end.
rand_mod_3 (nturns = 1000000):
--> distribution:
    dist_0=333084, dist_1=333754, dist_2=333162
--> single hits:
    hits_0=148196, hits_1=147981, hits_2=148596
--> longest series:
    long_0=15, long_1=13, long_2=14
--> total num of series:
    nser_0=73807, nser1=74321, nser_2=73842
end.

results for rand3:

Code: Select all

cmd> ./rand3 && sleep 1 && ./rand3 && sleep 2 && ./rand3

Code: Select all

rand3 (nturns = 1000000):
--> distribution:
    dist_0=334418, dist_1=333247, dist_2=332335
--> single hits:
    hits_0=83890, hits_1=187465, hits_2=187378
--> longest series:
    long_0=17, long_1=8, long_2=10
--> total num of series:
    nser_0=83461, nser1=62545, nser_2=62322
end.
rand3 (nturns = 1000000):
--> distribution:
    dist_0=333749, dist_1=332629, dist_2=333622
--> single hits:
    hits_0=83441, hits_1=187554, hits_2=187460
--> longest series:
    long_0=17, long_1=8, long_2=12
--> total num of series:
    nser_0=83545, nser1=62245, nser_2=62664
end.
rand3 (nturns = 1000000):
--> distribution:
    dist_0=333591, dist_1=333370, dist_2=333039
--> single hits:
    hits_0=83619, hits_1=187127, hits_2=187032
--> longest series:
    long_0=19, long_1=8, long_2=11
--> total num of series:
    nser_0=83306, nser1=62648, nser_2=62626
end.

Conclusion: overall distribution of probability is useless in testing such algorithms - the examples above are proving, that despite nearly ideal results in ver1, reality is quite different.

Tadeas: can You show corresponding statistics for Your algorithm? ...or is it classified :B

Regards.

[Tadeas]

saulgoode, that's a very nice solution!

tomazzi's solution is actually almost the same, but the need for an external variable is not very nice. My solution uses it as well, though .

I implemented it like this:

Code: Select all

def rand3():
    global aux
    for _ in range(2):
        aux += rand2()
   
    return aux % 3

I'll do the statistic stuff later, once I actually decipher what exactly you are doing (it's monday morning and that's a crisis time always ).

just out of curiosity: how much time do You give them to find the algorithm and to proove its correctness?

We don't limit it. But this is not like a paper and pencil test, it's more of an informal chat about interesting tech stuff . Some people sit down with a paper for a while, some start to draw on a whiteboard some say that they would think it up, but they don't have that much time right now etc. Anyway, we don't want them to write it, just saying the main idea is enough.

EDIT: I see that my solution is not random. It gives uniformly distributed 0, 1, 2, but it can be predicted, knowing the previous result. Fortunately it's not me, who ask this question on the interviews, but my colleague .
I'll think about some more robust solution.

EDIT2: This is truly random, but it can loop forever. When I think about it, it's basically a variation on saulgoode's solution.

Code: Select all

def rand3():
    x = 0
    while not x:
        x = 2*rand2() + rand2()
    
    return x - 1

[tomazzi]

tomazzi's solution is actually almost the same, but the need for an external variable is not very nice

well, that's because it should be rand3_r() implemented with rand2_r() beeing a special case of rand_r()

[tomazzi]

OK, here's ver3, which seems to work even better than the original rand()%3:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

unsigned int rand3(unsigned int *rndmem) {
   unsigned int mrnd = *rndmem;

   mrnd ^= rand() % 2; //rand2()
   mrnd++ ;
   *rndmem = mrnd;
   return mrnd %3;
}

int main() {
   unsigned int rnd, rndmem, it, itmax;
   unsigned int dist0, dist1, dist2;
   unsigned int rndlast, seed;
   unsigned int longser[3], serlast;
   unsigned int totsers[3], singles[3];

  //uninitialized vars here ;)
  seed = dist2<<8 ^ dist1<<4 ^ dist0;
  fprintf(stderr, "unitialized seed = 0x%08X):\n", seed);
   seed *= time(NULL);
   srand (seed);

   //init
   itmax = 1000000;
   dist0 = dist1 = dist2 = 0;
   it = 0;
   longser[it++] = 0; longser[it++] = 0; longser[it] = 0;
   it = 0;
   totsers[it++] = 0; totsers[it++] = 0; totsers[it] = 0;
   it = 0;
   singles[it++] = 0; singles[it++] = 0; singles[it] = 0;
   serlast = 0;
   rndlast = rndmem =  rand() % 2; //rand2()

   #ifdef MOD
      fprintf(stderr, "rand_mod_3 (nturns = %u, seed(time) = 0x%08X):\n", itmax, seed);
   #else
      fprintf(stderr, "rand3 (nturns = %u, seed(time) = 0x%08X):\n", itmax, seed);
   #endif

   for(it=0; it<itmax; it++) {

      #ifdef MOD
         rnd = rand() % 3;
      #else
         rnd = rand3(&rndmem);
      #endif
      //fprintf(stderr, "%u", rnd);
      //sequence check
      if(rnd == rndlast) {
         serlast++;
      } else {
         serlast++ ;
         if(serlast > 1) {
            //fprintf(stderr, "_ series[%u] len = %u\n", rndlast, serlast);
            totsers[rndlast]++ ;
         } else  {
            singles[rndlast]++ ;
         }
         if(serlast > longser[rndlast]) longser[rndlast] = serlast;
         serlast = 0;
      }
      rndlast = rnd;

      if(rnd == 0) {dist0++ ; continue;}
      if(rnd == 1) {dist1++ ; continue;}
      dist2++ ;
   }

   fprintf(stderr, "--> distribution:\n    dist_0=%u, dist_1=%u, dist_2=%u\n", \
      dist0, dist1, dist2);
   fprintf(stderr, "--> single hits:\n    hits_0=%u, hits_1=%u, hits_2=%u\n", \
      singles[0], singles[1], singles[2]);
   fprintf(stderr, "--> longest series:\n    long_0=%u, long_1=%u, long_2=%u\n", \
      longser[0], longser[1], longser[2]);
   fprintf(stderr, "--> total num of series:\n    nser_0=%u, nser1=%u, nser_2=%u\nend.\n", \
      totsers[0], totsers[1], totsers[2]);

    return 0;
}

I've also added some code to mess up the seed value and to get totally differen seeds for consecutive runs.
Here are example results:
rand()%3:

Code: Select all

unitialized seed = 0x5337FCBD):
rand_mod_3 (nturns = 1000000, seed(time) = 0xC00D4CFC):
--> distribution:
    dist_0=333260, dist_1=333686, dist_2=333054
--> single hits:
    hits_0=148074, hits_1=148254, hits_2=147947
--> longest series:
    long_0=12, long_1=14, long_2=15
--> total num of series:
    nser_0=74047, nser1=74295, nser_2=74031
end.
unitialized seed = 0x5337FCBD):
rand_mod_3 (nturns = 1000000, seed(time) = 0x7B045EE1):
--> distribution:
    dist_0=333119, dist_1=333961, dist_2=332920
--> single hits:
    hits_0=147690, hits_1=148249, hits_2=147839
--> longest series:
    long_0=13, long_1=12, long_2=12
--> total num of series:
    nser_0=74219, nser1=74245, nser_2=74061
end.

rand3:

Code: Select all

unitialized seed = 0x922B489D):
rand3 (nturns = 1000000, seed(time) = 0xDE1E937B):
--> distribution:
    dist_0=334986, dist_1=332263, dist_2=332751
--> single hits:
    hits_0=209609, hits_1=208474, hits_2=208812
--> longest series:
    long_0=12, long_1=16, long_2=14
--> total num of series:
    nser_0=41825, nser1=41144, nser_2=41419
end.
unitialized seed = 0x922B489D):
rand3 (nturns = 1000000, seed(time) = 0x6F78D863):
--> distribution:
    dist_0=333380, dist_1=333241, dist_2=333379
--> single hits:
    hits_0=207711, hits_1=207780, hits_2=207720
--> longest series:
    long_0=16, long_1=16, long_2=16
--> total num of series:
    nser_0=41816, nser1=41802, nser_2=41869
end.

As You can see, orginal rand()%3 produces more series (more chains of the same value), than ver3.


Regards.

[Tadeas]

Wow.. XOR . This is starting to look really cool ! Anyways, nice idea (and nice results).

[Roken]

Personally, for something truly random, I'd wget a dynamic, user content heavy website, grep the first dynamic entry and calculate the random number on the basis of the first character returned (or 5th character, or 10th - or whatever works with that website).

Haven't wrote the code, because I can't be bothered hunting for a suitable website, but it should work.

EDIT: For clarity the site would have to inject the html code, rather than simply use javascript to display it.