QUIZ: Implement rand3 with rand2

Need help with C, C++, perl, python, etc?

QUIZ: Implement rand3 with rand2

Postby Tadeas » 2013-08-29 21:40

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 :) !
Because let’s face it, the unfortunate aspect of software development is that it involves humans. Mewling, disorganized, miserably analog humans. Sometimes they smell bad.
User avatar
Tadeas
 
Posts: 1017
Joined: 2008-09-22 09:11
Location: Prague

Re: QUIZ: Implement rand3 with rand2

Postby tomazzi » 2013-08-30 18:26

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.
Odi profanum vulgus
tomazzi
 
Posts: 730
Joined: 2013-08-02 21:33

Re: QUIZ: Implement rand3 with rand2

Postby DominiqueM » 2013-08-30 19:08

I would ask peoples:
Code: Select all
echo "Write an integer number between 0 and 2 and press Enter:"
read RANDOM
DominiqueM
 
Posts: 40
Joined: 2013-08-30 10:08

Re: QUIZ: Implement rand3 with rand2

Postby Tadeas » 2013-09-01 08:05

tomazzi wrote: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.
tomazzi wrote:and to me it looks like a ... homework.

Actually, we ask this on job interviews for software engineers.
Because let’s face it, the unfortunate aspect of software development is that it involves humans. Mewling, disorganized, miserably analog humans. Sometimes they smell bad.
User avatar
Tadeas
 
Posts: 1017
Joined: 2008-09-22 09:11
Location: Prague

Re: QUIZ: Implement rand3 with rand2

Postby tomazzi » 2013-09-02 09:06

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/137783/expand-a-random-range-from-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>
Odi profanum vulgus
tomazzi
 
Posts: 730
Joined: 2013-08-02 21:33

Re: QUIZ: Implement rand3 with rand2

Postby drl » 2013-09-02 17:19

Hi.
tomazzi wrote: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
["Sure, I can help you with that." -- USBank voice recognition system.
( Mn, 2.6.x, AMD-64 3000+, ASUS A8V Deluxe, 3 GB, SATA + IDE, NV34 )
Debian Wiki | Packages | Backports | Netinstall
User avatar
drl
 
Posts: 434
Joined: 2006-09-20 02:27
Location: Saint Paul, Minnesota, USA

Re: QUIZ: Implement rand3 with rand2

Postby saulgoode » 2013-09-02 18:23

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).
Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it. -- Brian Kernighan
User avatar
saulgoode
 
Posts: 1545
Joined: 2007-10-22 11:34

Re: QUIZ: Implement rand3 with rand2

Postby tomazzi » 2013-09-02 18:25

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.
Odi profanum vulgus
tomazzi
 
Posts: 730
Joined: 2013-08-02 21:33

Re: QUIZ: Implement rand3 with rand2

Postby Tadeas » 2013-09-02 20:05

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 :) ).


tomazzi wrote: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
Because let’s face it, the unfortunate aspect of software development is that it involves humans. Mewling, disorganized, miserably analog humans. Sometimes they smell bad.
User avatar
Tadeas
 
Posts: 1017
Joined: 2008-09-22 09:11
Location: Prague

Re: QUIZ: Implement rand3 with rand2

Postby tomazzi » 2013-09-02 21:34

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() ;)
Odi profanum vulgus
tomazzi
 
Posts: 730
Joined: 2013-08-02 21:33

Re: QUIZ: Implement rand3 with rand2

Postby tomazzi » 2013-09-05 10:07

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.
Odi profanum vulgus
tomazzi
 
Posts: 730
Joined: 2013-08-02 21:33

Re: QUIZ: Implement rand3 with rand2

Postby Tadeas » 2013-09-05 18:48

Wow.. XOR :) . This is starting to look really cool :) ! Anyways, nice idea (and nice results).
Because let’s face it, the unfortunate aspect of software development is that it involves humans. Mewling, disorganized, miserably analog humans. Sometimes they smell bad.
User avatar
Tadeas
 
Posts: 1017
Joined: 2008-09-22 09:11
Location: Prague

Re: QUIZ: Implement rand3 with rand2

Postby Roken » 2013-09-07 10:14

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.
Roken
 
Posts: 87
Joined: 2011-02-06 01:12


Return to Programming

Who is online

Users browsing this forum: No registered users and 3 guests

fashionable