TravelinMax
Posts: 25
Joined: Mon Nov 26, 2012 3:46 am
Location: Michigan, USA

Coin Toss Simulator

Wed Jul 10, 2013 3:51 am

I'm writing a small program in C++ that simulates a large number of coin tosses. I would like any input on it. My main concern is that I read that entropy is like a "limited resource" so I worry that by doing so many simulations in a short period of time (1.25 million in the time it takes to loop through them) I run out of true random values. Any and all pointers will be appreciated.

Here is the code:

Code: Select all

#include <fstream>
#include <random>

using namespace std;

int main()
{

  ofstream outFile;

  outFile.open("coinflip.txt");

  random_device rd;

  for(int l = 1; l <= 10000; l++)
  {

    for(int k= 1; k <= 5; k++)
    {

      for(int j = 1; j <= 5; j++)
      {

        for(int i=1; i <=5; i++)
          {
            outFile << rd() % 2;
          }
        outFile << "     ";
      }
      outFile << endl;
    }
    outFile << endl;
  }

  outFile.close();

  return 0;
}
Next I am writing a program to look through the results and count the longest streak of heads or tails. I got the idea from my stats class; knowing that there is an approximate chance of 0.195% of ten straight tosses being all heads or all tails, I want to find out how many coin tosses I need to throw to consistently get at least one streak of 10 straight. Yes I know I can calculate this by hand, but it's a much more fun idea to code.

Thanks

User avatar
AndyD
Posts: 2333
Joined: Sat Jan 21, 2012 8:13 am
Location: Melbourne, Australia
Contact: Website

Re: Coin Toss Simulator

Wed Jul 10, 2013 12:08 pm

Hi,
TravelinMax wrote:I'm writing a small program in C++ that simulates a large number of coin tosses. ... I worry that by doing so many simulations in a short period of time (1.25 million in the time it takes to loop through them) I run out of true random values.
According to this website (and the freely available last draft of C++11), if the entropy() method of the random_device class returns 0.0, then the implementation uses a pseudo-random number generator. I did a quick test on my raspberry pi (latest wheezy/up to date) and sure enough entropy() returns 0.0. So it won't matter how quickly you read them as they are pseudo-random. You could read from /dev/random to get random numbers. However according to Wikipedia, /dev/random will block if you ask for more random data than is available in the bits of noise in the entropy pool. Another quick test (cat /dev/random) confirms this behavior.

PiGraham
Posts: 3679
Joined: Fri Jun 07, 2013 12:37 pm
Location: Waterlooville

Re: Coin Toss Simulator

Wed Jul 10, 2013 12:41 pm

TravelinMax wrote: Next I am writing a program to look through the results and count the longest streak of heads or tails. I got the idea from my stats class; knowing that there is an approximate chance of 0.195% of ten straight tosses being all heads or all tails, I want to find out how many coin tosses I need to throw to consistently get at least one streak of 10 straight. Yes I know I can calculate this by hand, but it's a much more fun idea to code.

Thanks
What do you mean by "consistently get at least one streak of 10 straight". There are no guarantees of any particular pattern occurring in random data. That's why it's called random.

User avatar
AndyD
Posts: 2333
Joined: Sat Jan 21, 2012 8:13 am
Location: Melbourne, Australia
Contact: Website

Re: Coin Toss Simulator

Thu Jul 11, 2013 12:04 am

PiGraham wrote:... There are no guarantees of any particular pattern occurring in random data. That's why it's called random.
True, but as he is simulating 1.25 million coin tosses, the probability that he will get no runs of 10 heads or 10 tails is extremely low!

TravelinMax
Posts: 25
Joined: Mon Nov 26, 2012 3:46 am
Location: Michigan, USA

Re: Coin Toss Simulator

Thu Jul 11, 2013 4:41 am

AndyD wrote:Hi,
TravelinMax wrote:I'm writing a small program in C++ that simulates a large number of coin tosses. ... I worry that by doing so many simulations in a short period of time (1.25 million in the time it takes to loop through them) I run out of true random values.
According to this website (and the freely available last draft of C++11), if the entropy() method of the random_device class returns 0.0, then the implementation uses a pseudo-random number generator. I did a quick test on my raspberry pi (latest wheezy/up to date) and sure enough entropy() returns 0.0. So it won't matter how quickly you read them as they are pseudo-random. You could read from /dev/random to get random numbers. However according to Wikipedia, /dev/random will block if you ask for more random data than is available in the bits of noise in the entropy pool. Another quick test (cat /dev/random) confirms this behavior.
Thanks!

Is /dev/random populated by the random number generator on the chip? I am running the standard Raspian Wheezy OS.

I'm now considering writing a version of my program that pulls from /dev/random and waits a set amount of time before the next "toss" (to allow time to more entropy to be acquired). Eventually I would like to get a second Pi and make the 2 work together. This would be a great scenario because I will be able to generate coin tosses as 2x the amount.

User avatar
AndyD
Posts: 2333
Joined: Sat Jan 21, 2012 8:13 am
Location: Melbourne, Australia
Contact: Website

Re: Coin Toss Simulator

Thu Jul 11, 2013 6:15 am

TravelinMax wrote:Is /dev/random populated by the random number generator on the chip? I am running the standard Raspian Wheezy OS.
I am not sure how the random number of /dev/random are generated. I am running standard Raspbian too.
TravelinMax wrote:... waits a set amount of time before the next "toss" (to allow time to more entropy to be acquired).
You don't need to wait, as your read from /dev/random will block until there are enough random bits.

I have had a try at modifying your code to use /dev/random. I will post it here after I have a chance to mess with it.

PiGraham
Posts: 3679
Joined: Fri Jun 07, 2013 12:37 pm
Location: Waterlooville

Re: Coin Toss Simulator

Thu Jul 11, 2013 8:23 am

You could make a hardware RNG:
Image
http://www.cryogenius.com/hardware/rng/

User avatar
topguy
Posts: 6063
Joined: Tue Oct 09, 2012 11:46 am
Location: Trondheim, Norway

Re: Coin Toss Simulator

Thu Jul 11, 2013 8:44 am

Also remember that each byte you read from "/dev/random" is 8 cointosses not just one.

User avatar
AndyD
Posts: 2333
Joined: Sat Jan 21, 2012 8:13 am
Location: Melbourne, Australia
Contact: Website

Re: Coin Toss Simulator

Thu Jul 11, 2013 9:41 am

AndyD wrote:I have had a try at modifying your code to use /dev/random. I will post it here after I have a chance to mess with it.
Here it is, but the speed is a little disappointing!

Code: Select all

#include <cstdlib>
#include <ctime>
#include <fstream>
#include <iostream>

using namespace std;

//-----------------------------------------------------------------

class CoinToss
{
public:

    CoinToss();

    bool toss();

    bool good() const { return _random.good(); }

private:

    ifstream _random;

    int _bit;
    char _byte;

};

//-----------------------------------------------------------------z

CoinToss::CoinToss()
:
    _random("/dev/random", ios::in | ios::binary),
    _bit(0),
    _byte(0)
{
}

//-----------------------------------------------------------------

bool CoinToss::toss()
{
    if (_bit == 0)
    {
        _random.read(&_byte, 1);
    }

    bool result((_byte >> _bit) & 1);

    _bit = (_bit + 1) % 8;

    return result;
}

//-----------------------------------------------------------------

int main()
{
    CoinToss coinToss;

    if (!coinToss.good())
    {
        cerr << "Coin toss failed" << endl;
        exit(EXIT_FAILURE);
    }

    ofstream outFile("coinflip.txt");

    for(int l = 0 ; l < 10000 ; ++l)
    {
        time_t now(time(0));
        struct tm* local_now = localtime(&now);
        char time_string[20];

        strftime(time_string, sizeof(time_string), "%H:%M:%S", local_now);

        cout << l << " " << time_string << endl;

        for(int k = 0 ; k < 5 ; ++k)
        {
            for(int j = 0 ; j < 5; ++j)
            {
                for(int i = 0 ; i <=5; ++i)
                {
                    outFile << coinToss.toss();
                }

                outFile << "     ";
            }

            outFile << endl;
        }

        outFile << endl;
    }

    outFile.close();

    return 0;
}
Here is the output of the run so far ...

Code: Select all

0 19:31:41
1 19:31:41
2 19:31:57
3 19:32:27
4 19:32:45
5 19:33:02
6 19:33:30
7 19:33:48
8 19:34:08
9 19:34:38
10 19:34:55
11 19:35:15
12 19:35:44
13 19:36:04
14 19:36:23
15 19:36:53
So 15 (out of 10000) iteration has taken over 5 minutes. A quick calculation show that it would take over two days to complete.

PiGraham's link to a hardware RNG is looking good.

jamesh
Raspberry Pi Engineer & Forum Moderator
Raspberry Pi Engineer & Forum Moderator
Posts: 24655
Joined: Sat Jul 30, 2011 7:41 pm

Re: Coin Toss Simulator

Thu Jul 11, 2013 9:52 am

Seems a bit odd it is that slow. Code looks sane. Is it a debug build?

I can only assume that reading from the random device is exceptionally slow - can you fake the read to just be a constant (dont do the read) and see how fast it is then. After all, the inner loop is only to 5*5*5 = 125, so 15 looks of 125 in 5 minutes is hopeless.
Principal Software Engineer at Raspberry Pi (Trading) Ltd.
Contrary to popular belief, humorous signatures are allowed. Here's an example...
“I own the world’s worst thesaurus. Not only is it awful, it’s awful."

scrapheap
Posts: 20
Joined: Wed Feb 13, 2013 5:13 pm

Re: Coin Toss Simulator

Thu Jul 11, 2013 10:13 am

Have you tried using /dev/urandom instead of /dev/random?

/dev/random will block when your entropy pool is empty and so can cause slowness if repeated called. /dev/urandom won't block when the entropy pool is empty, but is theoretically predictable (though I have never seen anyone actually do so).

For simulating coin tosses /dev/urandom will be fine; For generating cryptographic keys to protect your highly valuable information, probably best to look elsewhere for your randomness.

User avatar
AndyD
Posts: 2333
Joined: Sat Jan 21, 2012 8:13 am
Location: Melbourne, Australia
Contact: Website

Re: Coin Toss Simulator

Thu Jul 11, 2013 10:15 am

jamesh wrote:Seems a bit odd it is that slow. Code looks sane. Is it a debug build? I can only assume that reading from the random device is exceptionally slow - can you fake the read to just be a constant (dont do the read) and see how fast it is then. After all, the inner loop is only to 5*5*5 = 125, so 15 looks of 125 in 5 minutes is hopeless.
The code may be sane, it doesn't mean that I am. No not debug ... but doesn't really matter as the limiting factor is reading from /dev/random. If I change the code to use /dev/urandom the code finishes in 6 seconds.
Last edited by AndyD on Thu Jul 11, 2013 10:24 am, edited 1 time in total.

User avatar
AndyD
Posts: 2333
Joined: Sat Jan 21, 2012 8:13 am
Location: Melbourne, Australia
Contact: Website

Re: Coin Toss Simulator

Thu Jul 11, 2013 10:23 am

scrapheap wrote:Have you tried using /dev/urandom instead of /dev/random?
Yes, see above
scrapheap wrote:/dev/random will block when your entropy pool is empty and so can cause slowness if repeated called. /dev/urandom won't block when the entropy pool is empty, but is theoretically predictable (though I have never seen anyone actually do so).

For simulating coin tosses /dev/urandom will be fine; For generating cryptographic keys to protect your highly valuable information, probably best to look elsewhere for your randomness.
Yes, agree. Even using rand() and seeding with the current time would be fine. This was only an experiment in trying to achieve the OP's objectives.

TravelinMax
Posts: 25
Joined: Mon Nov 26, 2012 3:46 am
Location: Michigan, USA

Re: Coin Toss Simulator

Sat Jul 13, 2013 4:26 pm

AndyD wrote:
AndyD wrote:I have had a try at modifying your code to use /dev/random. I will post it here after I have a chance to mess with it.
Here it is, but the speed is a little disappointing!

Code: Select all

#include <cstdlib>
#include <ctime>
#include <fstream>
#include <iostream>

using namespace std;

//-----------------------------------------------------------------

class CoinToss
{
public:

    CoinToss();

    bool toss();

    bool good() const { return _random.good(); }

private:

    ifstream _random;

    int _bit;
    char _byte;

};

//-----------------------------------------------------------------z

CoinToss::CoinToss()
:
    _random("/dev/random", ios::in | ios::binary),
    _bit(0),
    _byte(0)
{
}

//-----------------------------------------------------------------

bool CoinToss::toss()
{
    if (_bit == 0)
    {
        _random.read(&_byte, 1);
    }

    bool result((_byte >> _bit) & 1);

    _bit = (_bit + 1) % 8;

    return result;
}

//-----------------------------------------------------------------

int main()
{
    CoinToss coinToss;

    if (!coinToss.good())
    {
        cerr << "Coin toss failed" << endl;
        exit(EXIT_FAILURE);
    }

    ofstream outFile("coinflip.txt");

    for(int l = 0 ; l < 10000 ; ++l)
    {
        time_t now(time(0));
        struct tm* local_now = localtime(&now);
        char time_string[20];

        strftime(time_string, sizeof(time_string), "%H:%M:%S", local_now);

        cout << l << " " << time_string << endl;

        for(int k = 0 ; k < 5 ; ++k)
        {
            for(int j = 0 ; j < 5; ++j)
            {
                for(int i = 0 ; i <=5; ++i)
                {
                    outFile << coinToss.toss();
                }

                outFile << "     ";
            }

            outFile << endl;
        }

        outFile << endl;
    }

    outFile.close();

    return 0;
}
Actually I like this better. Unfortunately I don't understand your code all that well because I haven't learned classes or anything yet. I could let this run continuously, save the results into a database, and then when I learn PHP (is PHP even necessary for this?) write a webpage to auto update and calculate stats on the fly. This way I will still benefit when I get a second Pi because I will still have a reason to double entropy.

As for PiGraham's hardware rng, I don't understand what it is saying at all!

PiGraham
Posts: 3679
Joined: Fri Jun 07, 2013 12:37 pm
Location: Waterlooville

Re: Coin Toss Simulator

Sat Jul 13, 2013 5:07 pm

TravelinMax wrote:As for PiGraham's hardware rng, I don't understand what it is saying at all!
It was just something Google threw up.
The idea is to use electronic noise as the source of randomness.
To use it with a Pi you could sample the output once for each bit of a random number. If you want a 32 bit random number read the RGN 32 times and assemble those bits into a 32 bit value.

For your heads or tails case simply sample the signal once for each toss. You will read either 0 or 1, heads or tails.

It uses shott noise which is random. Any high gain circuit could pick up signals that may be patterned, or they may oscillate. In either case your result is less random. If the circuit works well it could be a good source for your experiments.

technion
Posts: 238
Joined: Sun Dec 02, 2012 9:49 am

Re: Coin Toss Simulator

Mon Jul 15, 2013 11:06 pm

[quote="TravelinMax"][/quote]

How random does random need to be?

rand() can be predictable enough - if for no other reason than the srand() seed is 32-bit, which can be brute forced in seconds. It also has patterns that will emerge after enough calls.

A major requirement of a cryptographic cipher is that any patterns in the input don't reflect on the output. If you can obtain a secure seed and start state, you can forever run AES(key, seed++) to produce a random looking string. A well known and accepted RNG named "Yarrow" is based upon this principle.

Is this cryptographically strong? "It depends", because if that key and seed are compromised once, all subsequent data is. For the majority of purposes, I would say yes.

The "blocking" issue of /dev/random is surely a security issue itself - someone can effectively exhaust the entropy pool then cause your app to hang - a denial of service bug.

So a high strength algorithm might look a bit like this:

1. Pull 2048bit from /dev/urandom
2. Compress that to 256bit with SHA256
3. That value becomes "key"
4. Repeat above process to generate "seed"
5. Let seed = AES(key, seed)

Now every time you desire entropy, use the AES(key, seed++) function. For added security, every x number of calls, regenerate the seed as per step 5.

If you'd really like to make this heavily cryptographically secure:

Run the algorithm twice
Obtain SHA256 of the output
This provides 256 coin tosses
Run this as many times as required
Test the results against expected distribution. Google "chi-square" test.

scrapheap
Posts: 20
Joined: Wed Feb 13, 2013 5:13 pm

Re: Coin Toss Simulator

Thu Jul 18, 2013 11:55 am

Just stumbled across a post about the Raspberry Pi's hardware random number generator (http://scruss.com/blog/2013/06/07/well- ... generator/), which could be a good solution to try. I suspect that its performance will be somewhere between /dev/random and /dev/urandom.

TravelinMax
Posts: 25
Joined: Mon Nov 26, 2012 3:46 am
Location: Michigan, USA

Re: Coin Toss Simulator

Mon Aug 05, 2013 6:01 pm

PiGraham wrote:
TravelinMax wrote:As for PiGraham's hardware rng, I don't understand what it is saying at all!
It was just something Google threw up.
The idea is to use electronic noise as the source of randomness.
To use it with a Pi you could sample the output once for each bit of a random number. If you want a 32 bit random number read the RGN 32 times and assemble those bits into a 32 bit value.

For your heads or tails case simply sample the signal once for each toss. You will read either 0 or 1, heads or tails.

It uses shott noise which is random. Any high gain circuit could pick up signals that may be patterned, or they may oscillate. In either case your result is less random. If the circuit works well it could be a good source for your experiments.
I get the general idea, but I don't understand enough to create it (I'm starting to regret blowing off Physics II). It's a neat idea though so thanks
technion wrote:
TravelinMax wrote:
How random does random need to be?

rand() can be predictable enough - if for no other reason than the srand() seed is 32-bit, which can be brute forced in seconds. It also has patterns that will emerge after enough calls.

A major requirement of a cryptographic cipher is that any patterns in the input don't reflect on the output. If you can obtain a secure seed and start state, you can forever run AES(key, seed++) to produce a random looking string. A well known and accepted RNG named "Yarrow" is based upon this principle.

Is this cryptographically strong? "It depends", because if that key and seed are compromised once, all subsequent data is. For the majority of purposes, I would say yes.

The "blocking" issue of /dev/random is surely a security issue itself - someone can effectively exhaust the entropy pool then cause your app to hang - a denial of service bug.

So a high strength algorithm might look a bit like this:

1. Pull 2048bit from /dev/urandom
2. Compress that to 256bit with SHA256
3. That value becomes "key"
4. Repeat above process to generate "seed"
5. Let seed = AES(key, seed)

Now every time you desire entropy, use the AES(key, seed++) function. For added security, every x number of calls, regenerate the seed as per step 5.

If you'd really like to make this heavily cryptographically secure:

Run the algorithm twice
Obtain SHA256 of the output
This provides 256 coin tosses
Run this as many times as required
Test the results against expected distribution. Google "chi-square" test.
scrapheap wrote:Just stumbled across a post about the Raspberry Pi's hardware random number generator (http://scruss.com/blog/2013/06/07/well- ... generator/), which could be a good solution to try. I suspect that its performance will be somewhere between /dev/random and /dev/urandom.
Yes! This is exactly what I am looking for!

Return to “C/C++”