Archive for September, 2016

Have you celebrated Baegil yet?

Sunday, September 25th, 2016

A Korean friend asked my wife if our son had celebrated Baegil or 100 days yet. Not being familiar with the celebration, we said that we hadn’t kept track of the days since his birth. I decided to write a little program in Go in order to check what day of one’s life one is currently on.

The program should take the subject’s date of birth as a string from the first command argument. This was simple enough for me to decide against using the flags package and check the command line arguments directly:

if len(os.Args) == 1 {
    os.Stderr.WriteString("Please tell me your date of birth!\n")
} else {
...
}

I wanted to save programming effort and avoid reinventing the square wheel by using a library for handling the dates. The time package from the standard library can represent times and parse strings to time structs.

The time package has a peculiar (but easy to grok) way of specifying date layouts for formatting. Rather than %Y, %h, %s and so on from the standard C library and its descendants, in Go a fixed date where days are 1 and months are 2 and so on is used. So, to parse dates such as “2016-06-20” or “1980-10-28”, we need:

var layout = "2006-01-02"
var dateOfBirth, dOBParseError = time.Parse(layout, os.Args[1])

Full details can be found on this blog post:

https://pauladamsmith.com/blog/2011/05/go_time.html

Of course, a user of the program might not enter a parseable date string, so we need a little bit more error handling:

if dOBParseError != nil {
    fmt.Fprintf(os.Stderr, "Unable to parse your date of birth: %s\n", dOBParseError)
} else {
...
}

Once we have a date of birth, we can perform our arithmetic. The time package has a Since(...) method that can give you the duration of time since a given time struct:

var age = time.Since(dateOfBirth)

For a simple program like this, methods like Since are more convenient than creating a date object of the current time and comparing the given time to it. However, this does create an issue when testing code that does anything to do with time. If your code makes direct use of the system’s clock, your functions are impure as the same input won’t always return the same output. How do you test that a given input produces the correct output? Such tests would only pass at specific times on a given date. The purely functional way to do this is to write your business logic handling functions to accept all the used time objects already created, so that appropriate mocks can be passed in during tests without calling any methods that get data from the system’s clock. Another approach is the override the methods that call the system’s clock so that they return a set time in the test. This is called monkey patching. I’ve heard of people even setting the system clock during the test, but this is likely to have unforeseen consequences, especially on a shared build server.

The time package defines an Hours function for Duration structs but not one for days. A quick and dirty solution to this is the divide the number of hours by 24 and floor the result:

var ageInDays = math.Floor(age.Hours() / 24)

This makes the assumption that every day has exactly 24 hours. What about leap seconds? A person might have a few leap seconds during a lifetime. What if this program is run within a few seconds of midnight? The result might be different from the true result. As we are not using the precise time of birth and are flooring the number of days anyway, this is not too much of a concern. However, if really precise maths is needed or you using the components of one time struct to create a new time struct, inaccuracies can creep into your code. The fun really begins when you need to handle issues like leap years, time zones and seasonal time adjustments. If I ran this code in San Francisco in Winter for someone who was born in Sydney during Daylight Saving Time, would the result be accurate? A more fully developed version of this program would probably use a library to handle the mind boggling complexity of time tracking in the real world.

Another issue to consider is off by one errors. I’m flooring the number of days in order to say, “days since”. If I enter today’s date, I will get 0 as the subject’s age has not reached one day yet. This might be confusing to someone expecting 1 on the first day and so on. How ages are reckoned changes among different cultures. How Koreans consider their ages is surprising to many foreigners.

https://en.wikipedia.org/wiki/East_Asian_age_reckoning#Korean

Koreans celebrate Baegil on the 100th day, so we would expect the program to return 99 on the appropriate day. A programmatic solution to this might be add 1 to the result and change the wording. Programmers need to consider the audience of their programs carefully and gather requirements fully.

Obviously, you can’t be born in the future and still use the program, so we need a bit more user input checking:

if ageInDays < 0 {
    os.Stderr.WriteString("Wow! I must be talking to a foetus!\n")
} else {
    ...
}

If we’ve made it this far, we can now print the age in days:

fmt.Printf("Days old: %.0f\n", ageInDays)

Putting it all together, this is my program:

package main
 
import (
    "fmt"
    "math"
    "os"
    "time"
)
 
func main() {
    if len(os.Args) == 1 {
        os.Stderr.WriteString("Please tell me your date of birth!\n")
    } else {
        var layout = "2006-01-02"
        var dateOfBirth, dOBParseError = time.Parse(layout, os.Args[1])
 
        if dOBParseError != nil {
            fmt.Fprintf(os.Stderr, "Unable to parse your date of birth: %s\n", dOBParseError)
        } else {
            var age = time.Since(dateOfBirth)
            var ageInDays = math.Floor(age.Hours() / 24)
 
            if ageInDays < 0 {
                os.Stderr.WriteString("Wow! I must be talking to a foetus!\n")
            } else {
                fmt.Printf("Days old: %.0f\n", ageInDays)
            }
        }
    }
}

Entering my son’s date of birth, I see that we still have a couple of days to go:

$ ./daysOld 2016-06-20
Days old: 97

The source code can be found at:

https://github.com/robert-impey/CodingExperiments/blob/master/Go/daysOld.go

Coin Flips with Go

Thursday, September 15th, 2016

Following on from my little experiment with flipping coins millions of times, I thought that it would be interesting to write the same program in Go for comparison.

func main() {
    rand.Seed(time.Now().UTC().UnixNano())
 
    var competitionSize, runs int
    flag.IntVar(&competitionSize, "competitionSize", 10, "The size of each coin tossing competition.")
    flag.IntVar(&runs, "runs", 10, "The number of runs of the competition")
 
    flag.Parse()
 
    fmt.Println("heads, tails, flips")
    for i := 0; i < runs; i++ {
        countHeads := 0
        for j := 0; j < competitionSize; j++ {
            countHeads += rand.Intn(2)
        }
 
        fmt.Printf("%d, %d, %d\n", countHeads, competitionSize-countHeads, competitionSize)
    }
}

The basic idea of how to write the program is unchanged in this language. The output showed a similar distribution to the C# program.

However, Go has straightforward command line arguments parsing built into the standard library (like Python or Perl). In C#, there are a number of third party libraries that do this that can be installed via NuGet. I went with Command Line Parser.

To use this, I needed to add a class with properties with attributes to describe my expected options:

class Options
{
    // Taken from http://www.bbc.co.uk/news/politics/eu_referendum/results
    [Option('s', "competitionSize", DefaultValue = 33551983, HelpText = "The size of each coin tossing competition.")]
    public int CompetitionSize { get; set; }
 
    [Option('r', "runs", DefaultValue = 1000, HelpText = "The number of runs of the competition")]
    public int Runs { get; set; }
}

The command line arguments are then parsed in the main method:

var commandLineArgs = new Options();
if (Parser.Default.ParseArguments(args, commandLineArgs))
{
    var runs = commandLineArgs.Runs;
    var flips = commandLineArgs.CompetitionSize;
    ...
}
else
{
    WriteLine("Unable to parse the command line arguments!");
}

While this is not difficult to understand, it is more complicated than it needs to be and requires quite a bit more typing than in the Go program.

10 runs of the referendum simulation in both programs on Windows 10 with an Intel i7 4500U running at 1.8GHz took 7 seconds for the C# program and 13 seconds for the Go program. I wouldn’t take such simple programs very seriously for drawing conclusions about the relative speed of these languages.

The updated C# program and the complete Go program are on GitHub:
https://github.com/robert-impey/CodingExperiments/blob/master/C-Sharp/CoinFlipsAreRandom/CoinFlipsAreRandom/Program.cs
https://github.com/robert-impey/CodingExperiments/blob/master/Go/coinToss.go

Was the EU Referendum Random?

Monday, September 5th, 2016

One of the claims that I saw on social media in the aftermath of the recent EU referendum here in the UK was that the result (52% to 48%) was so close that it was little different from tossing a coin.

Without getting bogged down in the politics of that referendum, or the various campaigns that led up to it; I want to consider whether this claim holds any water. How similar to millions people each tossing a coin and voting accordingly was the result?

According to the BBC, there were 17,410,742 votes to leave and 16,141,241 votes to remain, giving a total of 33,551,983 votes. If we were to make each of these people toss a coin and count up the results, the ratio of heads/tails or remains/leaves could be anywhere between all heads and all tails. However, we would expect the counts to be about equal if the coins were all fair. Of course, any ratio is possible, but if we were to run the coin tossing game repeatedly, we would expect to mean ratio to converge on 1:1. How likely would a 52:48 ratio be?

The leave side got a share of the vote equal to 0.51891842. Therefore, their absolute deviation from the expectation (the mean, or 0.5) is 0.01891842. The difference between the two counts is 1,269,501. Would we expect to see a deviation of this magnitude in a coin tossing competition?

Being a computer programmer rather than a mathematician, I’m going to look at this using a simple program.

WriteLine("heads, tails, flips, heads share");
 
var runs = 1000;
 
// Taken from http://www.bbc.co.uk/news/politics/eu_referendum/results
var flips = 33551983;
 
var randomNumberGenerator = new Random();
 
for (var run = 0; run < runs; run++)
{
    var heads = 0;
 
    for (var coinToss = 0; coinToss < flips; coinToss++)
    {
        var toss = randomNumberGenerator.Next(2);
 
        if (toss > 0)
        {
            heads++;
        }
    }
 
    WriteLine($"{heads}, {flips - heads}, {flips}, {(0.0 + heads) / flips}");
}

This program simulates 1,000 coin tossing competitions with 33,551,983 players and writes the counts as comma separated values.

Putting the output into Excel, the largest deviation was 0.000275081 (or a difference between counts of 18,459) and the smallest was 1.49022E-08 (which was 16,775,992 heads and 16,775,991 tails. This happened twice in 1,000 runs!) The largest difference between heads and tails was 69 times smaller than the result from the referendum.

Plotting the shares in decreasing order, we see how quickly larger deviations fall off:

deviation

Putting the deviations into bins and counting the competitions by deviation from the expectation, we see that smaller deviations are more common:

bins

Whatever else we might say about the result, we cannot seriously claim that the result was random.

The full program can be found here:

https://github.com/robert-impey/CodingExperiments/blob/master/C-Sharp/CoinFlipsAreRandom/CoinFlipsAreRandom/Program.cs

The Excel file can be found here:
http://www.reversing-entropy.com/wp-content/uploads/2016/09/EuRef.xlsx