Archive for the ‘Computers’ Category

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

Using F# to minimise a function

Thursday, August 22nd, 2013

Finding the minimum of functions is at the heart of optimisation. Mathematicians, engineers and programmers have come up with a large number of approaches to solving this problem, including differentiation, genetic algorithms and even exhaustive search.

Consider a quadratic function such that could be written in F# as

let f x = (x ** 2.0) - (2.0 * x) + 1.0

Finding the minimum means finding the input value for the function that returns to lowest value. If we plot the curve, then the minimum is the lowest point of the curve.

One way to find this is find the derivative of the function:

(2.0 * x) - 2.0

and solve the equation where the derivative is equal to 0, which is when x is 1. This probably the best way to solve this problem in practice.

However, not all functions have derivatives that are easy to find. Therefore, an alternative way to minimise a function is an exhaustive search of the inputs in some range. This is not an elegant or generally efficient solution, but it works.

In F#, we might proceed as follows.

We define the range that we want to search and the step between candidate inputs:

let min = 0.0
let max = 10.0
let step = 0.01

We know where to start searching- with the lowest candidate input:

let firstCandidate = f min, min

This creates a tuple of two floats, the first being the output and the second being the lowest candidate input.

We also want a sequence of tuples of two floats that are the remaining candidate solutions:

let remainingCandidates = seq { for c in min + step .. step .. max do yield f c, c }

Note that at this point the sequence has not been enumerated and the function has not been run with each of the candidate inputs. Because sequences are evaluated lazily, the function will not be run for each of the candidate inputs until it is asked for.

We are trying to minimise the function, therefore we need a function that can compare the first elements of two candidate solutions:

let findMin currentMinSln candidateSln =
    match fst currentMinSln < fst candidateSln with
    | true -> currentMinSln
    | false -> candidateSln

Running this code in fsi shows its type to be:

val findMin : 'a * 'b -> 'a * 'b -> 'a * 'b when 'a : comparison

The F# compiler can infer that the function takes in two tuples, each with two elements. The tuples must be of the same type and the first element of each tuple must be comparable. Way to go, type inference!

Everything has been set up at this point. We just need to run the code:

let minSln = Seq.fold findMin firstCandidate remainingCandidates

The fold function is to reduce a sequence to a single value, starting with a given accumulator. In this case, the first candidate solution that we created earlier is our starting point. The output of the function for each candidate input is compared to that accumulator.

Running the code finds the same answer (1) that we found with calculus.

This code runs pretty quickly, but this approach is generally slow. Our range is only 10 wide and the step is 0.01, so there are only 1000 candidate inputs. Increasing the size of the range or decreasing the step would increase the number of inputs. More worryingly, the size of the search space increases exponentially as the number of inputs to the function increases. So a function that took two inputs for the same range for each input would have a million candidate inputs, three inputs would take a billion and so on.

However, it is also quite straightforward to parallelise this approach. The sequence of candidate solutions could be split up into partitions and each partition could be sent off to a different computer. Each batch would find a local minimum for the range it was given. Finding the minimum for the whole of our range of inputs is simply a matter of find the minimum in the returned list.

The complete code for this can be found here:

https://github.com/robert-impey/CodingExperiments/blob/master/F%23/Loose/MinimiseQuadratic.fs

Finding the Nearest Tube Station with LINQ

Tuesday, August 20th, 2013

I recently wrote a little command line program in C# that can tell you the name of the nearest tube station. I’ve put the program on GitHub in my Coding Experiments repository:

https://github.com/robert-impey/CodingExperiments/tree/master/C%23/NearestTube

The interface is very simple- this more of an experiment than something that I intend for mass consumption! You enter a location via the command line as the latitude and longitude:

Nearest Tube CLI

The starting point of the program was to calculate the distances between points. To do this I adapted some JavaScript code that John D. Cook wrote:

http://www.johndcook.com/lat_long_distance.html

Mathematical code looks very similar in many languages, and the translation from JavaScript to C# was trivially simple as the languages are very similar in this case. This code is part of the Point class:

        /// <summary>
        /// Porting JavaScript code from
        /// http://www.johndcook.com/lat_long_distance.html
        /// </summary>
        /// <param name="that"></param>
        /// <returns></returns>
        public double Distance(Point that)
        {
            // Compute spherical coordinates
 
            double rho = 6373;
 
            // convert latitude and longitude to spherical coordinates in radians
            // phi = 90 - latitude
            double phi1 = (90.0 - this.Latitude) * Math.PI / 180.0;
            double phi2 = (90.0 - that.Latitude) * Math.PI / 180.0;
            // theta = longitude
            double theta1 = this.Longitude * Math.PI / 180.0;
            double theta2 = that.Longitude * Math.PI / 180.0;
 
            // compute spherical distance from spherical coordinates
            // arc length = \arccos(\sin\phi\sin\phi'\cos(\theta-\theta') + \cos\phi\cos\phi')
            // distance = rho times arc length
            return rho * Math.Acos(
                    Math.Sin(phi1) * Math.Sin(phi2) * Math.Cos(theta1 - theta2)
                    + Math.Cos(phi1) * Math.Cos(phi2)) * 1000;
        }

Once I was able to calculate the distances between points on the map, I needed to be able to sort the tube stations of London by distance from the given point. This is the sort of code that LINQ to objects handles very naturally. In the SequentialTubeStationFinder class, I have the following method:

        public TubeStation FindNearestTubeStation(Point point)
        {
            return (from tubeStation in tubeStations
                    orderby tubeStation.Point.Distance(point)
                    select tubeStation).First();
        }

tubeStations is a generic list of TubeStation objects. Each has a Point property that is used to sort the tube stations and find the nearest one to our location.

The declarative style of programming that LINQ uses is much easier to read (and therefore maintain) than the equivalent code written with a for loop.

One liner to show logs without Rotated Backup files

Friday, May 25th, 2012

I’ve been looking at the Apache log files on a web server this morning. There are many virtual hosts on the machine and the log rotation scripts have created many numbered backup files of the logs. To make the directory listing more readable, I have been using the following one-liner:

ls -l /var/log/apache2 | grep -Ev -e '[[:digit:]]+(\.gz)?$'

This will only display the current log files, assuming that /var/log/apache2 is the directory in which you store your Apache logs and that you do not store any other files there.

I hope it helps.

Decimal to Binary

Friday, April 13th, 2012

In order to prepare for teaching computing, I’ve been reading Introduction to Computing by David Evans.

In the first chapter there is an excellent explanation of binary numbers using binary search trees. You can build a bitstring for the binary representation of a number by starting at the root (highest node on the tree) and comparing the number to the midpoints of a range of numbers that you are searching. If you answer a question with “yes” append “1” to your bitstring, otherwise append “0”.

The number 6 would be “Yes”, “Yes”, “No” or 110.

I decided to implement the logic of this binary tree in Java.

private static String decimalToBinary(int input) {
    if (input < 0 || input > 7) {
        throw new IllegalArgumentException();
    }
 
    StringBuilder result = new StringBuilder();
 
    if (input >= 4) {
        result.append('1');
        if (input >= 6) {
            result.append('1');
            if (input == 7) {
                result.append('1');
            } else {
                result.append('0');
            }
        } else {
            result.append('0');
            if (input == 5) {
                result.append('1');
            } else {
                result.append('0');
            }
        }
    } else {
        result.append('0');
        if (input >= 2) {
            result.append('1');
            if (input == 3) {
                result.append('1');
            } else {
                result.append('0');
            }
        } else {
            result.append('0');
            if (input == 1) {
                result.append('1');
            } else {
                result.append('0');
            }
        }
    }
 
    return result.toString();
}

This works for converting decimal numbers to binary strings. I think that writing a program like this might work as an exercise for secondary school students for learning about conditional statements in programming and binary numbers.

However, the range of inputs is severely limited (0 to 7 inclusive). I wrote another method and a recursive helper method that can take arbitrary non-negative decimals in the range of Java ints and return the corresponding binary number:

private static String decimalToBinaryRecursive(int input) {
    if (input < 0) {
        throw new IllegalArgumentException();
    }
 
    if (input == 0) {
        return "0";
    }
 
    if (input == 1) {
        return "1";
    }
 
    // Find how many bits we need.
    int bits = (int)(Math.log(input) / Math.log(2)) + 1;
 
    // Find the greatest number that can be represented with this many bits.
    int max = (int)Math.pow(2, bits);
 
    // We want to know how much to change this value by to search from the mid point.
    int delta = max / -2;
 
    StringBuilder result = new StringBuilder();
 
    return decimalToBinaryRecursiveHelper(input, max, delta, result);
}
 
private static String decimalToBinaryRecursiveHelper(int input, int previousMidpoint, int delta, StringBuilder result) {
    if (delta == 0) {
        return result.toString();
    }
 
    int midpoint = previousMidpoint + delta;
 
    if (input >= midpoint) {
        result.append('1');
        return decimalToBinaryRecursiveHelper(input, midpoint, Math.abs(delta) / 2, result);
    } else {
        result.append('0');
        return decimalToBinaryRecursiveHelper(input, midpoint, Math.abs(delta) / -2, result);
    }
}

The recursive method is considerably more complex and would be much harder for a secondary school student to write. The mathematics might be unfamiliar for most secondary school students, particularly the code to do with logarithms. You could simplify the mathematics of that code with a while loop that compared increasing powers of 2 to the input. It might be a possible extension task for a gifted and talented student. It could also be a task for a lesson on recursive methods.

I can see that teaching computing will present challenges. There are an enormous number of toy programs that we can get students to create in order to learn about programming. However, in order to extend any of these tasks to make them more practical and interesting, it is very easy to set challenges that are rely on outside skills, knowledge and understanding that many secondary school students do not have.

The whole program with a main method for testing looks like this:

package decimaltobinary;
 
/**
 * @author Robert Impey
 */
public class DecimalToBinary {
    public static void main(String[] args) {
        System.out.println("Simple Approach");
        for (int i = 0; i <= 7; i++) {
            System.out.printf("%d\t%s\n", i, decimalToBinary(i));
        }
 
        System.out.println("Recursive Approach");
        int bits = 8;
        for (int i = 0; i <= Math.pow(2, bits) - 1; i++) {
            System.out.printf("%d\t%s\n", i, decimalToBinaryRecursive(i));
        }
    }
 
    private static String decimalToBinary(int input) {
        if (input < 0 || input > 7) {
            throw new IllegalArgumentException();
        }
 
        StringBuilder result = new StringBuilder();
 
        if (input >= 4) {
            result.append('1');
            if (input >= 6) {
                result.append('1');
                if (input == 7) {
                    result.append('1');
                } else {
                    result.append('0');
                }
            } else {
                result.append('0');
                if (input == 5) {
                    result.append('1');
                } else {
                    result.append('0');
                }
            }
        } else {
            result.append('0');
            if (input >= 2) {
                result.append('1');
                if (input == 3) {
                    result.append('1');
                } else {
                    result.append('0');
                }
            } else {
                result.append('0');
                if (input == 1) {
                    result.append('1');
                } else {
                    result.append('0');
                }
            }
        }
 
        return result.toString();
    }
 
    private static String decimalToBinaryRecursive(int input) {
        if (input < 0) {
            throw new IllegalArgumentException();
        }
 
        if (input == 0) {
            return "0";
        }
 
        if (input == 1) {
            return "1";
        }
 
        // Find how many bits we need.
        int bits = (int)(Math.log(input) / Math.log(2)) + 1;
 
        // Find the greatest number that can be represented with this many bits.
        int max = (int)Math.pow(2, bits);
 
        // We want to know how much to change this value by to search from the mid point.
        int delta = max / -2;
 
        StringBuilder result = new StringBuilder();
 
        return decimalToBinaryRecursiveHelper(input, max, delta, result);
    }
 
    private static String decimalToBinaryRecursiveHelper(int input, int previousMidpoint, int delta, StringBuilder result) {
        if (delta == 0) {
            return result.toString();
        }
 
        int midpoint = previousMidpoint + delta;
 
        if (input >= midpoint) {
            result.append('1');
            return decimalToBinaryRecursiveHelper(input, midpoint, Math.abs(delta) / 2, result);
        } else {
            result.append('0');
            return decimalToBinaryRecursiveHelper(input, midpoint, Math.abs(delta) / -2, result);
        }
    }
}

This post contains content that was released with the following license:
http://creativecommons.org/licenses/by-nc-sa/3.0/us/
and is published with the same license.

GHCN Monthly and MS Access

Sunday, December 4th, 2011

For some of the last few evenings, I have been learning about MS Access’s data import functionality in order to interrogate the data of the Global Historical Climatology Network-Monthly dataset. This dataset holds records of temperature readings dating back to the beginning of the eighteenth century from more than seven thousand stations around the globe.

GHCN Monthly

The data are in text files with a fixed width format. It’s very straightforward to set up the import format (although there are many columns!) and save the import specification so that future datasets can be imported as they are released with ease. The largest data files have almost half a million rows, yet Access can import the data in a few seconds. The resulting table of readings of average, minimum and maximum temperatures for each month for each station has more than one million rows. I have not experimented with adding indexes yet but, in spite of this, I can run queries that are not painfully slow.

Now that I have the data into an Access database, I hope to start analysing the data. I have produced a couple of charts for a single station but am yet to run any serious calculations. I have read of a similar project at:

A Quick and Dirty Analysis of GHCN Surface Temperature Data

The algorithm that caerbannog (the blogger) uses in his C++ program to smooth the data and calculate averages is fairly simple. Something similar should be possible (or even easy) using the MS Office tools.

Ultimately, my aim for this is to make this the basis of an ICT lesson or project. As caerbannog notes “Never in history has science been more accessible to the general public than it is now.” The quantities of data that can be accessed for free are as enormous as the power of the computers that are now cheaply available. I hope that my students will be inspired to look deeply into the issue and this will help develop their sense of empirical curiosity.

Generics in VB.Net

Tuesday, June 14th, 2011

Taking a lead (again) from Java generic types for beginners, I decided to experiment with generic types in VB.Net. The ICT Cool blog covers the idea behind generics and the MSDN documentation on generic types in VB.Net gives more details on the topic, so I won’t repeat what has been explained elsewhere.

My code shows how generics can make code more robust by enforcing compile time type checking. The type safety of the various objects can be checked in Visual Studio by hovering the mouse over any of the variables in the code. This brings up a pop up that says the type of the object. Many of the lines of the main sub have been commented out because the project would not build otherwise. Try uncommenting them to see the errors that the IDE finds.

The code also shows that generic types allow coders to build and use type safe, polymorphic collections. Put simply, we can create a list (for example) that will only allow us to add an object of any type, so long as it implements an interface given at the time of construction.

GenericsInLists

String Manipulation with the Decorator Pattern

Sunday, June 12th, 2011

Inspired by the Java program to sort and reverse a string at ICTCool.com, I decided to try to solve the problem using Java and the Decorator Pattern.

StringDecoratorDemo.tar.gz

My solution required considerably more lines of code than the code at ICT Cool. For a problem as simple as this, using the Decorator Pattern is probably overkill. However, the advantage of this pattern is that multiple decorators can be stacked up at run time in any order that we choose. Also, if we wanted to add more operations later, we simply add a new class, which is cleanly separate from the other operations.

I’ve written the program using NetBeans, which creates quite a few files other than the source files, which are in src. To run the program, cd to the dist directory and type java -jar StringDecoratorDemo.jar.

Percidae

Saturday, March 6th, 2010

For the last few weeks I have been looking for a job as a programmer. One of the jobs that interests me involves writing VB.net. Many of my friends who are also programmers have howled with anguish at the mere mention of this technology.

In order to get a better idea of how the language works, I’ve written a small program for editing the PATH environment variable on Windows machines:

http://code.google.com/p/percidae/

I find myself editing this variable on various Windows machines pretty regularly. Every time, I also am annoyed by the small text box in the dialog in the Control Panel.

So far I’ve enjoyed the experience of writing with Visual Basic and can’t see what all the fuss is about. Having written PHP for years, I’m used to ignoring the comments of language purists. I’m much more interested in getting something working than any imagined superiority of different languages.

How not to fight global warming

Monday, May 4th, 2009

http://www.guardian.co.uk/technology/2009/may/03/internet-carbon-footprint

Above is a link to an article on the carbon footprint of the internet. In the comments, we can find the normal luddite opinions. If only people didn’t like the modern world, we could live in pre-industrial simplicity.

It seems embarrassingly obvious to me that if we have any hope of survival, it is in moving forward, rather than backwards. If we think that we can solve the world’s environmental problems by rejecting technology, then we’re sunk. Do the troglodyte commenters on the Guardian really think that the world is going to be able to implement the sort of engineering projects that are going to be necessary for a revolution in the world’s energy industry without the internet? How do they imagine engineers study and design things like solar panels, wind turbines or smart electricity grids? Using pencils, recycled paper and 30 year old text books?