Basildon Coder

Marshalling a Variable-Length Array From Unmanaged Code In C#

2009-03-31T20:03:00.000+01:00

I recently spent time working on some C# code to interact with a simple DNS-SD system. This requires using DNS TXT records, which are not supported in the System.Net.Dns class. After a few google searches failed to turn up a pure .Net client library that met my needs, I settled on an approach based around p/invoking the Win32 DnsQuery function.

And quickly ran into problems.

For DNS TXT records, DnsQuery returns a DNS_TXT_DATA structure in the Data field of the DNS_RECORD structure. DNS_TXT_DATA is declared like this:

typedef struct {
    DWORD dwStringCount;
    PWSTR pStringArray[1];
} DNS_TXT_DATA,
    *PDNS_TXT_DATA;

Using the very handy P/Invoke Interop Assistant, we see that this struct can be represented like this in managed code:

[StructLayout(LayoutKind.Sequential)]
public struct DNS_TXT_DATA {

    /// DWORD->unsigned int
    public uint dwStringCount;

    /// PWSTR[1]
    [MarshalAs(UnmanagedType.ByValArray,
            SizeConst=1,
            ArraySubType=UnmanagedType.SysUInt)]
    public IntPtr[] pStringArray;
}

There is a problem with pStringArray, unfortunately. The System.Runtime.InteropServices.Marshal class cannot marshal a variable length array, as it needs to know in advance how big the array is in order to allocate memory. That's why the managed structure needs SizeConst specified in the MarshalAs attribute.

However, if the DNS TXT record data contains multiple quoted strings separated by whitespace, DnsQuery will return a structure with a variable number of elements in pStringArray. Since SizeConst is set at compile-time, when we marshal this into the managed struct defined above, we only get the first element in our single-element array. Rats.

More googling turned up very little info on dealing with this, though I found indications that others had run into the same problem without finding a satisfactory conclusion. DnsQuery is not the only Win32 function that returns variable-length arrays, and p/invoking any of the others has the same issue.

Simply declaring SizeConst to be bigger than we need - "hey, I know I'll never get more than 10 or so strings back, so why not declare SizeConst to be 128?" - is inelegant (hardcoded upper limits, ugh) and doesn't work properly anyway. Since the struct layout is sequential the marshaller will copy over (e.g.) 128*sizeof(IntPtr) sequential bytes (a total of 512 bytes, in this case). That much memory was never allocated on the unmanaged side, so we end up with a load of junk in the tail of pStringArray, and more often than not the marshaller chokes on this junk and throws an AccessViolationException. Fun.

There IS a way to get round the problem, though. I'm not sure it's the best way, but it works and seems stable, so I thought I'd throw it out there in case anyone else can use it (or maybe explain to me why it's an unsafe stupid thing to do...)

Basically, since we're dealing with sequential memory, we can use Marshal.PtrToStructure to marshal the DNS_TXT_DATA structure as defined above, then use pointer arithmetic to gain access to any further data that needs marshalling.

Pointer arithmetic? Oh yes, even in the safe and secure world of managed code it's sometimes still necessary to get our hands dirty, and situations like this illustrate that it will always be valuable to have some hard-earned Assembly/C/C++ war wounds.

So, assuming we have valid p/invoke declarations and data structures (I've included a complete source program below), DnsQuery is called like so:

var pServers = IntPtr.Zero;
var ppQueryResultsSet = IntPtr.Zero;
var ret = DnsQuery(domain,
        DnsRecordType.TEXT,
        DnsQueryType.STANDARD,
        pServers,
        ref ppQueryResultsSet,
        IntPtr.Zero);
if (ret != 0)
    throw new ApplicationException("DnsQuery failed: " + ret);

If we examine the memory location of ppQueryResultsSet (Ctrl-Alt-M,1 or Debug->Windows->Memory->Memory1 in Visual Studio) we'll see something like the following (actual address locations may vary - just copy the int value of ppQueryResultsSet to the Address bar of the memory window):

0x049E0878  00 00 00 00  ....
0x049E087C  b8 09 9e 04  ¸.ž.
0x049E0880  10 00 20 00  .. .
0x049E0884  19 30 00 00  .0..
0x049E0888  00 00 00 00  ....
0x049E088C  00 00 00 00  ....
0x049E0890  06 00 00 00  ....
0x049E0894  b8 08 9e 04  ¸.ž.
0x049E0898  d8 08 9e 04  Ø.ž.
0x049E089C  f8 08 9e 04  ø.ž.
0x049E08A0  28 09 9e 04  (.ž.
0x049E08A4  68 09 9e 04  h.ž.
0x049E08A8  88 09 9e 04  ˆ.ž.

I've set the column size to 4 here, as most of the values we are dealing with are 4 bytes in size. This effectively shows one value per line.

The first 6 rows (24 bytes) correspond to the DNS_RECORD structure up until (but not including) the DNS_TXT_DATA structure in DNS_RECORD's Data union. We can marshal this first structure without problem:

var dnsRecord = (DnsRecord) Marshal.PtrToStructure(
        ppQueryResultsSet, typeof (DnsRecord));

The DNS_TXT_DATA structure starts at address 0x049E0890 in my example. Having already marshalled the DNS_RECORD structure, now I want a pointer to the DNS_TXT_DATA structure. I can do this by creating a new pointer at the address of ppQueryResultsSet plus 24 bytes, and marshalling again:

var ptr = new IntPtr(
        ppQueryResultsSet.ToInt32() + Marshal.SizeOf(dnsRecord));
var txtData = (DNS_TXT_DATA) Marshal.PtrToStructure(
        ptr, typeof (DNS_TXT_DATA));

Because of the definition of DNS_TXT_DATA, this only marshals 8 bytes - 4 bytes for dwStringCount, and 4 bytes for the single element in pStringArray (an IntPtr). Since we know the memory is sequential, however, this gives us everything we need - we now know how many strings have been received (6 in this case, as indicated at 0x049E0890), and the location of the pointer to the first string (0x049E0894).

With this info, we can marshal all the pointers into an array with a length of dwStringCount:

ptr = new IntPtr(ptr.ToInt32() + sizeof (uint)); // move to first
var ptrs = new IntPtr[txtData.dwStringCount]; // dest array
Marshal.Copy(ptr, ptrs, 0, ptrs.Length);

And finally we iterate through those pointers, marshalling the string pointed at by each:

var strings = new List();
for (var i = 0; i < ptrs.Length; ++i)
{
    strings.Add(Marshal.PtrToStringAnsi(ptrs[i]));
}

While the example I've presented here is specific to DnsQuery, the general approach should be applicable to any situation where you need to marshal a data structure containing a variable-length array.

Source code

Project Euler Problem 8

2009-02-09T19:30:00.000Z

Problem 8

"Find the greatest product of five consecutive digits in the 1000-digit number.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450"

The first step here is to find a representation for that fairly humungous number. Obviously it's not going to fit into a paltry 32-bit int...but then we don't need it to. The problem description requires us to think in terms of smaller (5-digit) numbers, not one giant 1000-digit number.

So, it is sufficient for us to consider the number as an enumerable stream of single digits, which we can conveniently represent as IEnumerable. I could use a macro to convert the number into a collection initialiser, but it's much easier to treat the string as an IEnumerable<char> and let LINQ do the heavy lifting.


var nums = Enumerable.AsEnumerable(
        "73167176531330624919225119674426574742355349194934" +
        "96983520312774506326239578318016984801869478851843" +

        // ..... etc etc ......

        "05886116467109405077541002256983155200055935729725" +
        "71636269561882670428252483600823257530420752963450"
        ).Select(x => Convert.ToInt32(x.ToString()));

This gives us an IEnumerable<int> containing every digit in the 1000-digit number. Now, the 'obvious' way to solve the problem is to iterate through the collection, and at each index multiply the value against the next four indexes. A simple loop should deal with it:


private static int SimpleSolver(int[] ints)
{
    int max = 0;
    for (int i = 0; i < ints.Length - 4; i++)
    {
        int tmp = ints[i] * ints[i + 1] * ints[i + 2]
            * ints[i + 3] * ints[i + 4];
        max = Math.Max(max, tmp);
    }

    return max;
}

As ever, though, that's pretty ugly - the loop condition and product calculation is tied to the sequence size of 5, and messing with an index variable is tedious.

An alternative approach is to take advantage of LINQ's Skip and Take methods to split the problem domain into overlapping 'slices'. Similar to the for loop above, the core of the approach is to iterate through the digits, and at each digit grab a number of subsequent digits and calculate the product.

Lets look at the 5-digit slices available from the first 10 digits:


  7   3   1   6   7   1   7   6   5   3
|       73167       |
    |       31671       |
        |       16717       |
            |       67176       |
                |       71765       |
                    |       17653       |

We can use Skip to progressively move the starting index forward, and Take to grab the 5 digits we need. So, starting with i=0, each successive slice can be sliced from the whole with:


var slice = ints.Skip(i++).Take(5);

To calculate the product of the digits in the slice, we can use the Aggregate operation:


slice.Aggregate(1, (curr, next) => curr*next);

We've met Aggregate before - it's basically a fold, which collapses a sequence to a single item by repeatedly applying an operation to an accumulating result.

This can all be wrapped up as an iterator block, like so:


private static IEnumerable EnumerateSlices(
        IEnumerable ints, int sliceSize)
{
    int i = 0;
    while (true)
    {
        var slice = ints.Skip(i++).Take(sliceSize);

        if (slice.Count() < sliceSize)
            yield break; // end

        yield return slice.Aggregate(1,
                (curr, next) => curr*next);
    }
}

Note the termination condition - when we have enumerated every slice, our next slice will contain only 4 elements (3, 4, 5, and 0 from the end of the sequence) - that's our cue to exit the loop.

Also note that this approach makes the algorithm trivial to parameterize - it will work just as well with slice sizes other than 5.

This iterator will produce an IEnumerable containing the products of all slices, so the final step is to select the largest:


var result = EnumerateSlices(nums, 5).Max();

Killing and Reviving an Aspire One

2009-02-08T21:01:00.000Z

I just spent 2 hours reviving my Aspire One netbook after inadvertently killing it whilst fiddling about configuring dropbox. I found the whole process unnecessarily fiddly and information on the interwebs to be a bit scarcer than I would have liked, so I'm documenting it here in case I need it in the future. Hopefully it'll be useful to someone else too.

So, the cause of death was a typo when trying to set up the dropboxd daemon to start automatically on boot. I'm not running nautilus so couldn't use one of the prepackaged releases, and it's completely my fault that I made a mess of installing the vanilla x86 build.

After making the fatal change and rebooting, the system would only boot up to a blank black screen with a default X mouse cursor. This is because the system was trying to run my broken command, failing, and therefore never getting to the main desktop.

In the world of normal linux, there's all sorts of ways of dealing with this, but despite plenty of googling I couldn't find a way to use run-level 2 or 3 on an Aspire One, and the Ctrl+Alt+F1-F6 key combos for switching away from X to a terminal don't work either. There seems to be no way of preventing the system following the same doomed process over and again if you break X.

Frustrated, I thought about using the restore disk, but that's a nuclear option - it re-paves the whole machine, so bye-bye data. That seemed a bit drastic when all I needed to do was edit a single text file to fix the system.

Ironically, this was happening as a result of me trying to install a file sync system as a simple backup. Grr.

Still, like countless thousands before me, I was saved by a live linux distro - in this case, a USB bootable one (since the Aspire One has no optical drive). Following the instructions^[1] at pendrivelinux I created a bootable Feather Linux USB drive, and booted the netbook from it by hitting F12 on the post screen and selecting to boot from the USB stick.

At the boot prompt, I used 'knoppix 3' to boot the system up to a command line, mounted /dev/hdc1 as an ext2 filesystem, and fixed my typo. Reboot, and tada! Everything was working again (well, after hitting Fn-F7 to reenable the touchpad, which I had accidentally disabled whilst mashing the keyboard in frustration at the sight of a blank screen about an hour earlier, heh).

^[1] Note that I had to use a newer version of syslinux than the one referenced on pendrivelinux. This one worked for me.

Macros: You Oughta Know

2009-02-06T15:03:00.000Z

One of the most useful tools available in any decent text editor is the macro recorder, but it's criminally underused. It seems most people either don't know the functionality exists, or simply ignore it. This is a shame, since it's a great timesaver.

I don't know why macros are so underused. It might be a mindset thing - it can take a little while to develop the ability to spot repetitive editing tasks quickly (i.e. not when you're 75% of the way through thinking dang, I have to do this again?), so maybe many people never quite make the leap.

It's worth it though, because once you get your eye in you see chances to use macros everywhere.

I had a useful example just yesterday, in which I needed to make a change to a colossal switch statement (220 branches! Run the cyclomatic-complexity doohickey on THAT!) and had no unit tests to fall back on.

If I had to modify (and hopefully refactor) such a huge construct I wanted to be able to compare before-and-after test results, but I didn't much fancy hand-cranking a few hundred unit tests.

By recording a temporary macro, however, it took just a couple of minutes to cover every branch. I've decided to post a detailed walkthrough of the process here in the hopes that a fairly simple example will be illustrative for those that don't already lean heavily on macros.

Note that this is not an advanced tutorial. Please refrain from leaving snarky comments about how macros are so much more powerful than this - I'm just doing some introductory material here :-)

Here is a representative snippet of the C# source. It's part of a legacy permissioning system that, under certain circumstances, needs to check for the existence of a permission represented by an enum against a permission table containing a string-based hierarchy (application/role/permission). The code I was modifying did the appropriate conversion:


    case PermissionKey.SecurityParameterManagementAdd:
    {
        return new string[] {"Security", "ParameterManagement", "Add"};
    }
    case PermissionKey.SecurityRoleManagementAdd:
    {
        return new string[] {"Security", "RoleManagement", "Add"};
    }
    case PermissionKey.SecurityRoleManagementModify:
    {
        return new string[] {"Security", "RoleManagement", "Modify"};
    }
    case PermissionKey.SecurityUserManagementDelete:
    {
        return new string[] {"Security", "UserManagement", "Delete"};
    }
    case PermissionKey.SecurityPermissionManagementAdd:
    {
        return new string[] {"Security", "PermissionManagement", "Add"};
    }

I needed to add a couple of branches to this, but I also wanted to tidy up the code by removing the superfluous braces, as a precursor to converting it into something a bit more robust and maintainable. I wanted unit test coverage to give me confidence that I hadn't mucked up some logic and inadvertantly granted admin access to the helpdesk trainee role or something.

So, I copied the entire switch body into Notepad++ (well, vim really, but I'll pretend it's Notepad++ for the sake of making this post a bit more accessible) and set to work^[1].

Before recording my macro, I needed to do a bit of preprocessing to trim the code down to just the data I wanted to work with. The following steps show the 'find' regexes I used (in each case, the value of the replace field was empty, so these are effectively deletes), and the effect on the first switch branch from the list above:

1) Remove opening and closing braces from every switch branch:

^\s+[\{\}]$


    case PermissionKey.SecurityParameterManagementAdd:

        return new string[] {"Security", "ParameterManagement", "Add"};

2) Remove blanks - TextFX/Edit/Delete Blank Lines


    case PermissionKey.SecurityParameterManagementAdd:
        return new string[] {"Security", "ParameterManagement", "Add"};

3) Remove case statements and leading whitespace:

^\s+case\s+

PermissionKey.SecurityParameterManagementAdd:
PermissionKey.SecurityParameterManagementAdd:
        return new string[] {"Security", "ParameterManagement", "Add"};

4) Remove colon from end of case statement:

:$

5) Remove return statement and leading whitespace:

^\s+return new string\[\]\s*

I ended up with a sequence of couplets looking similar to this one:


PermissionKey.SecurityParameterManagementAdd
{"Security", "ParameterManagement", "Add"};

Now the fun starts - lets walk through the process.

We want to convert the first couplet into a simple unit test fixture, and record the process. This will be our macro - the instructions for converting one couplet into one unit test. We can then play the macro multiple times to convert all the others effortlessly.

Start by moving the cursor to the start of the line, before the 'P' of PermissionKey. This is the start point of the macro, so for the macro to be repeatable we must make sure that we finish recording the macro in perfect position to run it again, i.e. before the 'P' of PermissionKey for the next couplet (column 0 line 3). Hit Ctrl-Shift-R to start recording.

It is important not to use the mouse when editing - stick to the keyboard. It's also important not to record keystrokes that are too specific to one bit of code. For instance, don't use the arrow keys to move left and right character-by-character, because it won't work on longer or shorter lines.

Instead, use the Home and End keys to jump to the start or end of the line, and hold Ctrl whilst arrowing left or right to move a word at a time instead of a character at a time (this is one of the areas where vim's movement commands really differentiate it from wannabes like Notepad++...but I digress). See the 'Detailed Instructions' section below for more information.

Assume the original switch body is in a method called 'LookupEnumPermission'. The couplet should be edited to look like this (without the linewrap...):


[Test]
public void TestSecurityParameterManagementAdd()
{
    string[] result = LookupEnumPermission(
            PermissionKey.SecurityParameterManagementAdd);
    Assert.AreEqual("Security", result[0]);
    Assert.AreEqual("ParameterManagement", result[1]);
    Assert.AreEqual("Add", result[2]);
}

Make sure you finish by moving the cursor into position for the next couplet, and hit Ctrl-Shift-R again to stop recording.

Now, hit Ctrl-Shift-P to play back the macro. If you've done everything right, the next couplet should magically format itself into a unit test. Hit Ctrl-Shift-P again, and the next couplet will change too. Under the Macro menu, select 'Run a macro multiple times...' and you can enter a fixed number of iterations, or just apply the macro over and over again until the end of the file is reached.

Finally, you can copy the unit tests into a new or existing test fixture, and you're done! In much less time (hopefully) and with fewer errors than if the tests had been written one-by-one.

Detailed Instructions:

These are ley-by-key instructions in Notepad++, in case something in the description above is unclear. Visual Studio should be similar. Vim will be faster once you've learned how, but I'll assume if you use vim you're already au fait with this sort of editing :-)

Type [Test], and hit enter to start a new line.

Type 'public void Test' and hit Enter.

Type '{' and hit Enter, then Tab.

Hold Ctrl and tap the right arrow twice to jump over a couple of words and place the cursor at the start of the word SecurityParameterManagementAdd, then hold Ctrl-Shift and right arrow again to select the word. Ctrl-C to copy, then arrow up two lines and paste it after the word 'Test' to create the full function name TestSecurityParameterManagementAdd. Type () for the empty parameter list.

Arrow down two lines and hit Home to jump to the start of the line. Type 'string[] result = LookupEnumPermission(', then hit End to jump to the end of the line and type ');'.

Arrow down one line, hit Home, then Tab. Type 'Assert.Equals(' then hit Delete to remove the '{'. Hold Ctrl and move right three times (to move the cursor just past the comma) and type 'result[0]);' and hit Enter.

Repeat variations of step 7 a couple of times to convert the next two lines. Remember to use the correct indexes (result[1] and result[2]). Hit Enter after the last line and type '}' to close the function body.

Arrow down one line and hit Home to place the cursor at the correct start position for the next couplet, and end the macro by hitting Ctrl-Shift-R again.

^[1]I could have just done this in a new file in Visual Studio, but for some reason I find VS intolerably slow at running macros once recorded. So slow, in fact, that you can watch the cursor laboriously complete each step - I wind up thinking it would have been quicker to do it manually. That might just be something odd about my VS installation though, as no-one else seems to think it's slow.

OOD - The Second Coming?

2009-01-16T16:00:00.000Z

Over the last couple of months I've been burning up my free time on a pet project (hence the scarcity of posting here). This particular project is a web application, and since I've always been a desktop or middle-tier dude in my day job, it's a bit of a step out of my normal environment to grapple with browser compatibility and suchlike.

Still, I wanted it to be a decent learning experience, so after a brief dalliance with Rails I scrapped the idea of using any framework sorcery and decided to write everything in plain ol' PHP, and lean heavily on YUI and jQuery to sort out the browser stuff.

This probably isn't an approach I'd use in future projects, but I bet I'll appreciate those frameworks a lot more once I've encountered and understood the problems they attempt to solve.

So, having strayed from the comfort of Rails and its clones, I had to think about lots of things like security, validation, data access, and how to organise my code. Just because I'd abandoned the training wheels I had no intention of falling over all the time - I still wanted a nice, maintainable app with sensible abstractions, properly decoupled, and resilient to failure. Time to start reading articles and the odd open source project, obviously.

It's at this point I noticed something interesting. Since I regularly read plenty of development websites it could scarcely have escaped my notice that the trendy framework players (e.g. Rails, Django, Cake, ASP.NET MVC) strongly advocate the MVC pattern and class-based object-oriented design. What I hadn't really realised until now is how endemic that viewpoint had become.

In fact, beyond a few admirably out-there frameworks like Seaside, it's almost universal. OOD = good, EVERYTHING ELSE = bad. MVC = good, EVERYTHING ELSE = bad. No shades of grey, no room for dissenting opinion.

Go anywhere where best-practices are discussed and mention you're writing some procedural code, and watch the fireworks. It doesn't matter if your application has fewer lines of code than a newly-created Rails app has source files - if you haven't structured it with models, views, and controllers you may as well have written it in Visual Basic for all the bile you're going to have thrown at you.

If you say you're writing functional code, you might get away with it, since functional programming is still widely misunderstood and you'll likely be classified as some weird LISPer or Schemer doing something arcane and thus ignored.

Ironically, of course, if you grab a random Rails/Django/Cake app from github or Google Code, there's a pretty fair chance that what you'll find isn't particularly object-oriented anyway. Hint - usage of the 'class' keyword does not an object-oriented design make. And sweet zombie Jesus, I've never seen such abuse of the singleton pattern. That's a sure sign someone doesn't 'get' OO - the singleton pattern is evil and basically a way to shoehorn globals into an application without admitting it to your friends.

So, we have massive fanatical advocacy of a technique that will allegedly solve all your problems, coupled with large-scale real-world misunderstandings and misapplication. Does this remind anyone of anything? Say, for example, the last time OOD swept the world, panacea to all programming woes, about 20 or so years ago?

Don't get me wrong, I'm not arguing that class-based OO itself is just a fad - it deserves its place as a paradigm alongside procedural, functional, parallel, and numerous others. It's the heralding of OO as the one true way that seems faddish.

So, in the very best "bah, humbug" traditions I've written my app in unashamedly procedural PHP code. I don't mix my presentation and content. My data layer is decoupled and unit tested. Every bit of SQL is a parameterised query, to guard against injection. I don't have a single echo() statement containing any html tags. All my errors are exception based, and I don't have a single die() call anywhere. My average function size is about 10 lines, and my longest is about 20. I've no doubt that there's a legion of 15-year-old self-appointed geniuses ready to accuse me of inflicting yet more spaghetti code junk on the world just because "find . -iname '*php' | xargs grep class" comes up empty, but hey I'm OK with that.

I'm writing my next app in brainf*ck using ed.

Project Euler Problem 7

2008-10-26T21:58:00.000Z

Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6^th prime is 13.

What is the 10001^st prime number?

Ah, what a nice, straightforward, unambiguous spec! If only business software specifications were so precise.

Way back in problem 3, I took a bit of a wander off-topic and built a prime generator in .Net using the Sieve of Eratosthenes. Armed with this, problem 7 should be easy, right? The sieve implementation generates an IEnumerable, which is non-indexable (i.e. I can't just say Primes()[10001]), but I can take the first 10,001 and then ask for the last element, which will be the answer to the problem.

There's a problem with this, however. The sieve requires an upper bound during initialisation. This means it's great for solving problems like "generate all the primes less than 10,001", but not so great at answering questions like "what is the 10,001st prime number?", since it requires foreknowledge of the upper bound.

To illustrate the problem, I'll take a wild guess at the upper bound. I'm going to guess that the 10,001st prime number is less than 99,999. What happens?


var sieve = new SieveOfEratosthenes(99999);
var result = sieve.Primes().Take(10001).Last();

This generates an answer of 99,991. If I enter this into the Project Euler website, however, it tells me the answer is wrong. Gah! What went wrong? A simple test reveals the problem:


var sieve = new SieveOfEratosthenes(99999);
var primes = sieve.Primes().Take(10001);
var count = primes.Count();

There's only 9,592 primes generated! As the docs for Take() state (emphasis mine):

Take<TSource> enumerates source and yields elements until count elements have been yielded or source contains no more elements.

Damn. So, looks like my 99,999 guess was too small - with that as an upper bound, the sieve only finds 9,592 primes, and I need the 10,001st. OK, I'll bump it up by an order of magnitude:


var sieve = new SieveOfEratosthenes(999999);
var result = sieve.Primes().Take(10001).Last();

This gives me the correct answer. Not exactly a wonderful solution though; the idea of having to guess the upper bound is pretty horrendous, and if this was real code it wouldn't be particularly maintainable - what if the requirements changed and we had to find the nth prime, which happened to be >99,999? We'd have to guess again. Ugh.

Worse, the sieve algorithm precomputes all the primes up to the specified upper bound, meaning that in the above approach I've asked the sieve to generate primes up to 999,999 (all 78,498 of them!) despite only needing 10,001. Not very efficient.

Fortunately, the upper bound can be calculated separately. Where n>8601, as in this case, we can use the following equation:

p(n) < n (log_e n + log_e log_e n - 0.9427)

where p(n) is the nth prime number.

Alternatively, for flexibility in handling n<8601, we can use the less accurate

p(n) < n log_e log_e n

which works for n>5. We can easily precompute the answers for n<=5, or simply calculate on demand.

The formula can be implemented on the sieve class, with a factory method to help when we want to use it:


public static SieveOfEratosthenes
    CreateSieveWithAtLeastNPrimes(int n)
{
    return new SieveOfEratosthenes((long)
            Math.Ceiling(UpperBoundEstimate(n)));
}

private static double UpperBoundEstimate(int n)
{
    return n * Ln(n) + n * (Ln(Ln(n)));
}

private static double Ln(double n)
{
    return Math.Log(n, Math.E);
}

This leaves us with an overall solution like so:


var sieve = SieveOfEratosthenes.CreateSieveWithAtLeastNPrimes(10001);
var result = sieve.Primes().Take(10001).Last();

This generates a total 10,018 primes, cutting the wasted effort from almost 70,000 superfluous primes to just 17, and takes around 20ms to execute on my machine. Plenty fast enough, I think.

Look Before You Look Before You Leap

2008-10-24T15:32:00.000+01:00

Generally, I try to avoid turning this blog into some sort of snark-fest about other programmers or blogs. I've disagreed with Jeff Atwood once or twice though, and so by posting this I'm probably straying a little close to the edge...but what the hell.

A couple of days ago Coding Horror carried a fluff piece about how all developers should be marketers too. Predictably, the article soon got posted to proggit where it was ripped on by reddit's resident Jeff-haters, and even more predictably the comments were a mix of interesting insight and barely-concealed hate.

Apparently some of them got up Jeff's nose a bit, and today he responded. The core of his rebuttal seems to be that you shouldn't trust what you read on blogs, and should verify everything yourself. True enough, I guess, if perhaps a bit impractical given the sheer amount of information out there.

Then, however, Jeff goes on to give an example by referencing a compression benchmark he'd read on a blog and providing counter-analysis to show that the benchmark was wrong in claiming Deflate is faster than gzip. In doing so, much knowledge was gained.

Or so we are told.

The comment thread quickly becomes a goldmine of humour. Bugs in Jeff's benchmarking code (not resetting the stopwatch) meant that the durations were cumulative, not independent, with inevitable distortion of the results. Another commenter pointed out that gzip cannot possibly be faster than Deflate, since the gzip algorithm IS the Deflate algorithm plus some additional computation.

“gzip” is often also used to refer to the gzip file format, which is:

a 10-byte header, containing a magic number, a version number and a timestamp

optional extra headers, such as the original file name,

a body, containing a DEFLATE-compressed payload

an 8-byte footer, containing a CRC-32 checksum and the length of the original uncompressed data

http://en.wikipedia.org/wiki/Gzip

With the benchmarking code fixed, we see that Deflate is indeed slightly faster than gzip.

All of which leads to repeated quotations from Jeff about the community being smarter than him, and some drastic toning down of language in post-publication edits to the article. I read a cached version of the RSS feed, which is markedly different to the article currently live on codinghorror.com - "on my box, GZip is twice as fast as Deflate" becomes "on my box, GZip is just as fast as Deflate", "Deflate is way slower. It's not even close" becomes "Deflate is nowhere near 40% faster", etc.

Anyone who's tackled a major performance problem will likely agree that profiling is a tremendously valuable technique that should always be applied before attempting to optimise (i.e. look before you leap). I think this little episode has highlighted a couple of important things to bear in mind, however:

Profiling isn't a magic wand - if you use buggy profiling code, you are leading yourself up the garden path.

Profiling is less useful when you can reason (in the mathematical sense) about the code. That involves understanding the algorithms you are dealing with. Gzip is Deflate plus a bit more processing - so unless that extra processing has a negative duration gzip must necessarily take longer. You don't need a profiler to work that out. Look before you look before you leap.

Anyway, enough hatcheting from me, normal service will be resumed shortly.

Project Euler Problem 6

2008-08-14T01:00:00.000+01:00

Onwards to...

Problem 6

The sum of the squares of the first ten natural numbers is,
1² + 2² + ... + 10² = 385

The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Bit of a disappointment, problem 6; it's too easy. It's rated as the third-easiest, i.e. easier than problems 3, 4, and 5 which I've already covered. In fact, for my money it's easier than problem 2 as well. Ah well, the difficulty ramps up soon enough, trust me. Here's the very simple python solution:


sum_sq = sum([ x*x for x in xrange(1, 101)])
sq_sum = sum(xrange(1, 101)) ** 2

print sq_sum - sum_sq

As you can see, it's pretty intuitive. You sum the squares, square the sum, and calculate the difference. The answer is basically in the description, you just have to scale up a little.

There's not much else to say about this one. Even if I abandon the functional approach and write a straightforward imperative solution it's still very straightforward. In (deliberately non-idiomatic, so don't whine at me) ruby:


sum_of_squares = 0
sum = 0

1.upto 100 do |x|
    sum_of_squares += x * x
    sum += x
end

p (sum * sum) - sum_of_squares

Magic Numbers and Other Numerical Nightmares

2008-08-13T13:48:00.000+01:00

There are many coding practices that are near-universally regarded as 'bad', yet somehow keep cropping up over and over again. Conditional-branch abuse (including, yes, gotos). Deep nesting. Cryptic variable names. Global variables. Tight coupling. Entangled business/presentation logic. I could go on.

Why do we keep doing it? Convenience? Laziness? Tiredness? Is unreadable spaghetti code some sort of steady-state/equilibrium for code? Is it a natural consequence of the vague and squidgy limitations of our evolved monkey-brains? Or is well-designed code abhorred like a vacuum and naturally atrophies into the sort of shambles you dread seeing on your first day at a new job, unless well-intentioned and dedicated people actively work to clean and polish it, like the Forth Bridge?

I don't have the time or wit to give this subject the treatment it deserves, but I do want to rant a bit about another symptom of this disease, which has given me a couple of sleepless nights recently. I refer, as the title might suggest, to magic numbers.

Magic numbers are constants, unnamed in the most pathological cases, that represent an assumption or a limit in a piece of code. They often cause problems because soon they are forgotten about or their meaning is lost - and then something happens to invalidate the assumption, the code breaks, and all hell breaks loose.

Magic numbers, to stretch the definition a bit, can also be implicit. If you are using a 32-bit integer, your magic number is 2,147,483,647 - that's the biggest number you can store in that type. Often, movement up to and beyond these ranges can trigger long-dormant bugs that are no fun at all to diagnose.

Three times in recent history I've been bitten by bugs of this class, triggered by auto-incrementing sequences in database. These are they:

A table in a database had a 32-bit integer primary key. At the time this seemed like a perfectly reasonable default, but insanely fast growth in usage of the system meant that the ~2.1billion upper limit of that data type was quickly reached. The DB column was switched to a 64-bit integer, but some of the client applications reading that table were not identified as at-risk. When the sequence generator left the 32-bit range, those applications overflowed. This happened at 4:30pm on a Friday afternoon. Saturdays were peak-times for system usage. You can imagine the frantic hacking that ensued.

A sequence generator for a particular entity was started at 20,000,000, so as not to clash with the ID sequence of a related entity (that had started at 0 a good few years earlier). The similarity between the entities and the need to not have the IDs overlap had valid business justification, but the magic number was selected arbitrarily and promptly forgotten. Inevitably, the latter sequence surpassed that number, causing bizarre and difficult-to-trace entity relationship corruption that manifested as strangely-disappearing data on the front-end.

A stored procedure parameter was incorrectly declared as an OracleType.Float, when it should have been an OracleType.Int32. This resulted in the value being cast from an integer to a floating-point and back again. For the first 16,777,216 integers, this happens to work OK. For the value 16,777,217, however, the loss in precision means that the number changes during casting. This simple bit of (heavily contrived) code shows the problem:
```
static void Main(string[] args)
{
    for (int i = 0; i < 17000000; ++i)
    {
        if (i != (int)(float)i)
        {
            Console.WriteLine("{0} != {1}", i, (int)(float)i);
            break;
        }
    }
}
```
There are many numbers above 16,777,217 that have this characteristic; 16,777,217 just happens to be the first, for reasons you can probably divine if you think the IEEE floating-point spec is a riveting read. A couple of weeks after the launch of a fairly major internal application, this time-bomb exploded due to a sequence reaching the magic number. The bug was nothing to do with the new application, but of course fingers were pointed at it since a long-running and stable system had mysteriously choked very shortly after deployment of the new application.

Now, unquestionably, all these problems are avoidable, and a strong argument could be made that none of them should ever have been allowed to happen. Yet, for many reasons, they do. For example, first-mover advantage can mean the opportunity cost of taking the time to do things right first time is greater than the cost of fixing problems later.

Also, people make assumptions. The issue underlying the Millennium Bug hysteria was caused by well-meaning developers who knew that two-digit dates wouldn't work after 1999 (effectively another magic number), but assumed the software would have been replaced or upgraded by then. No doubt that seemed a totally reasonable assumption in the 1970s, and it had genuine technical benefits (storage space was so tight that every byte saved was a battle won).

Anyway, I don't have a magic bullet solution for this, I'm just venting spleen. Unit tests can help, but won't magically eliminate this class of bug (no matter what some of the more extreme TDD fanatics might tell you), so I suppose the lesson to take from this is the importance of being able to recognise and diagnose potential magic number issues. Pay close attention to data types, type conversions, and current values of sequences in your database. Keeping a sacrifical goat on hand might pay dividends too, in case any blood-thirsty deities with a head for binary arithmetic are watching.

Ubuntu, Xmonad, and an Ode to Apt

2008-08-10T23:34:00.000+01:00

This weekend I finally got around to updating my main Linux box from Ubuntu 7.10 to 8.04 (yes, I know, 4 months late - but moving fast!). The highly excellent xmonad has made it into the main Ubuntu repositories, so I discarded my own build and grabbed the packaged version - which promptly didn't work as expected on my dual-head setup. Gah.

A bit of googling suggested that the problem lay with the upstream debian package, which contained a build of libghc6-x11-dev that was compiled without xinerama support. This left me with a choice of either waiting for the package to get sorted out, or to do the build myself again. I decided to do my own build rather than live without xmonad, but rather than mucking about with tarballs I could at least now get the source from the package repository.

The appropriate steps, for anyone interested or having the same problem, are:

Make sure libxinerama-dev is installed

Recompile libghc6-x11-dev and install it

Recompile libghc6-xmonad-dev and libghc-xmonad-contrib-dev against the new X11 lib

The apt-get incantations are:


sudo apt-get install libxinerama-dev
cd /tmp
sudo apt-get source --compile libghc6-x11-dev
sudo dpkg -i libghc6-x11-dev_1.4.1-1_i386.deb
sudo apt-get build-dep libghc6-xmonad-dev
sudo apt-get source --compile libghc6-xmonad-dev
sudo dpkg -i libghc6-xmonad-dev
sudo apt-get build-dep libghc6-xmonad-contrib-dev
sudo apt-get source --compile libghc6-xmonad-contrib-dev
sudo dpkg -i libghc6-xmonad-contrib-dev_0.6-4_i386.deb

A quick alt-q restart, and all is well.

I only mention all this because it's so easy in this day and age to take something like apt for granted, and every so often it's worth taking a moment to appreciate just how spectacularly good it really is. Where I work, deployments are an endless source of headaches and grief, yet the complexity of those deployments absolutely pales against the task of updating literally millions of systems, all slightly different to each other, thousands of times a day. It's just a joy to be able to say to apt "hey, go get me everything I need to build package x, then build package x, then install it for me. And get it right first time!".

In most cases, it does just that. It's an astonishing piece of software.

Dynamic Async Batching with PFX

2008-08-08T17:41:00.000+01:00

The PFX Team blog has been posting some excellent articles recently on the subject of task batching using the June 2008 CTP release of the Task Parallel Library. It's really cool to see some of these techniques abstracted properly in .Net, and I hope it eventually becomes part of the core libraries.

I've been playing around a bit recently with the June CTP in the context of batching up web service calls, as that's something I do quite a lot. One particular problem that comes up occasionally is a two-stage series of requests to download a complete set of paged data. I might do this if I wanted to download an entire discussion thread, for instance, or a large account statement from my online bank.

Typically in this situation the web service will limit the number of records I can retrieve in one request, and allow me to specify start and count parameters to the request. The response will also include a total record count, so I know how much data there is.

The normal use case for this is to request the first page of data, and use the total record count to display a list of page links that my user can click on to navigate the data or jump to any page. In my case, however, I want ALL the data as quickly as possible.

So, imagine a situation where I am using a service that lets me download a maximum of 200 records per request. My first step is to request the maximum 200 records starting from index 0, i.e. the first page of data. In the response will be a total record count - if that number is equal to the number of records I got back (i.e. <= 200) I've got everything in one hit and can stop. But what if the total record count is, say, 1000? I need to make four more requests (since I've already got records 1-200, I have 800 more to get in batches of 200 each).

Naturally I want to do this asynchronously, using as few resources as I can. This means all webservice calls should be using the APM pattern (thus using IO completion ports, and not consuming worker threads from the thread pool or creating my own threads) and, preferably, not blocking anywhere except when I actually need some data before continuing.

The two-stage process can be successfully captured asynchronously by combining a future and a continuation. I encapsulate the initial request in a Future object (which is a subclass of Task), and handle the check-record-count-and-get-more-records-if-required logic in the continuation. The code for this basically looks as follows:


public Future<List<Item>> GetAllItemsAsync()
{
    var f = Create<GetItemsResponse>(
            ac => Service.BeginGetItems(0, ac, null),
            Service.EndGetItems);

    var start = 200;

    var resultFuture = f.ContinueWith(
        r =>
            {
                // Batch retrieval here...
            });

    return resultFuture;
}

In order to support the APM pattern neatly, I'm using the following method from the PFX blog:


private static Future<T> Create<T>(
        Action<AsyncCallback> beginFunc,
        Func<IAsyncResult, T> endFunc)
{
    var f = Future<T>.Create();
    beginFunc(iar =>
        {
            try
            {
                f.Value = endFunc(iar);
            }
            catch (Exception e)
            {
                f.Exception = e;
            }
        });
    return f;
}

This could be coded as an extension method, though I haven't bothered yet as I'm hopeful this immensely useful snippet will be integrated into the library itself.

Now I need to make a number of calls to get the rest of the data, so I loop until I've made the required number of async service calls:


var resultFuture = f.ContinueWith(r =>
    {
        var items = new ConcurrentQueue<Item>();
        var handles = new List<WaitHandle>();

        while (start < r.Value.TotalRecordCount)
        {
            var asyncResult = Service.BeginGetItems(200,
                ar => Service.EndGetItems(ar).Items
                    .ForEach(items.Enqueue), null);

            handles.Add(asyncResult.AsyncWaitHandle);
            start += 200;
        }

        handles.ForEach(h => h.WaitOne());
        return items.ToList();
    });

I'm about 85% happy with this as an approach. I'm not completely happy, however, because of the WaitOne calls, which mean that I'm blocking on a threadpool thread until all the calls complete. Given that this is all wrapped up in a future, I may not actually need to access the data until well after the calls have completed, in which case I am wastefully consuming a threadpool thread for some period of time. So the $64,000 question is, how do I get rid of it? I'm sure there's a way to do it, but my brain has gone on a protest march about all the time I'm forcing it to spend thinking about this stuff.

Comment Discontent

2008-07-30T17:01:00.000+01:00

There seems to have been a recent outbreak in blog posts about code commenting. As is so often the case with topics such as this, everyone has an opinion and they all seem to be different. It's quite an eye-opener seeing some of the explanations, justifications, and outright haranguing used in defence of all sorts of weird and wonderful stances.

I got a wry smile from stevey's post, as I recognise only too well the tendency to write narrative comments. I'm sure there's plenty of code from early in my career still floating around in various company codebases where the code/comment ratio is something embarrassing. I've mostly shaken that off now, though I sometimes have to fight my inner raconteur when writing something I think is neat or clever.

Jeff Atwood, as is so often the case recently, contradicted his own previous post on the matter (replacing the statement "comments can never be replaced by code alone" with "if your feel your code is too complex to understand without comments, your code is probably just bad") and endearingly veered wildly to and fro across a sensible medium^[1], without ever quite hitting it. Coding Horror, indeed.

So far, so blah; every time an argument on comments flares up we see the same thing. Something I've not noticed before though, either because I wasn't paying attention or because it's a new thing, is a trend amongst the I-don't-need-comments crowd to advocate very long and detailed method names as an alternative.

As neophyte coders we all have it drilled into us that we must use descriptive names. Programming gospel, as handed down in sacred tomes such as Code Complete, tell us not to use names like 'i' and 'tmp' except in very specific circumstances (e.g. loop indexes and tempfile handles). And, without question, this is good solid advice. Take heed, young Padawan, etc.

But can you take it too far? It's not something I've really come up against, but it seems to be increasingly popular. One response to Jeff's post suggested (only in passing, to be fair) using a function name like newtonRaphsonSquareRoot. A digg comment (OK, OK, not exactly the fount of all knowledge) vehemently defended the virtue of the frankly-scary

RunEndOfMonthReportsUnlessTheMonthStartsOnAFridayIn
WhichCaseRunTheWeeklyReportInstead

(!)

The argument is that with names like these, you don't need comments, since it is perfectly clear what the function does. Is it perfectly clear at the wrong level though? Function names like this, in my opinion, are so 'clear' that they leak. These are function names that violate the principle of encapsulation.

If I write a square root function, why do I need to burden all my clients with information about how I've implemented it? By naming it newtonRaphsonSquareRoot, that's exactly what I'm doing. Unless there are specific performance implications/requirements that favour Newton-Raphson, in most cases my clients just want a damn square root calculated to within a specified tolerance and don't care whether I used Newton's method or one of the army of alternatives. The implementation should be private to the method, and no-one else's business.

Worse, what if a requirements change means a switch to Walsh's fast reciprocal method? Uh-oh, now my method name is completely misleading, so I have to change it. Oops, now I have to change all the client code that calls it! I'd better hope no-one has exposed this with [WebMethodAttribute] since I wrote it, otherwise there could be thousands of client applications out there relying on it. My funky rename refactoring can't save me now.

If every tiny change propagates through the system requiring hundreds of source files to change, and possibly external apps as well, you may as well just copy 'n' paste the code everywhere it's needed and doing away with the function completely. Hell, who needs abstraction anyway?

We all do, of course, which is why I think names like this are a bad smell. The same goes for RunEndOfMonthReportsUnless... - what happens when the requirements change? This method name couples the public interface (method name) to the private implementation, which is exactly what you're not supposed to do. RunEndOfMonthReports is probably sufficient. Separate interface and implementation. This is programming 101, people, it shouldn't be beyond our grasp.

^[1]I agree with Dan Dyer that the best choice is as follows:


/**
 *  Approximate the square root of n, to within the specified
 *  tolerance, using the Newton-Raphson method.
 */
private double approximateSquareRoot(double n, double tolerance)
{
    double root = n / 2;
    while (abs(root - (n / root)) > tolerance)
    {
        root = 0.5 * (root + (n / root));
    }
    return root;
}

The function name is descriptive and clear whilst remaining general enough to allow an alternative implementation. Anyone who cares enough about the implementation (for performance reasons, or simply curiosity) can find enough information in the comment to start their investigation, without having the details jammed in their face every time they call it.

These...Are Not The Hammer

2008-07-20T23:40:00.000+01:00

So, yesterday saw the end of a weird week of Whedon wonderfulness when the third and final episode of Dr Horrible's Sing-Along Blog was released. All three episodes are now free to view until the end of the day, so run, don't walk, over there now. After all, how often do you get the chance to see a musical comedy about a supervillain who video blogs? With Doogie Howser and Malcolm Reynolds!

Lexical Closures in C# 3.0

2008-07-01T17:49:00.000+01:00

There's a slightly weird article up on Dobbs Code Talk this week, speculating that aggregate functions are "the next big programming language feature" after closures. The slight weirdness comes from the fact that both features have been around for decades, and not just in dusty academic languages either.

Still, there's some interesting discussion in the comments about whether .Net's closures are proper first-class lexically-scoped closures. The answer is yes - but with a fun twist.

The twist has been around for a long time - Brad Abrams blogged about it way back in 2004, for instance - but it's probably worth going over it again, since the recent arrival of LINQ and lambda syntax in C# 3.0 will presumably lead to more people being bitten by this as the use of closures becomes more mainstream.

A key thing to remember is that C# lambdas are just anonymous delegates in skimpy syntax. Behind the scenes the compiler turns them into classes - if you were looking at disassembled MSIL you wouldn't be able to tell whether the code was written with lambda syntax or anonymous delegate syntax. Therefore, the issue discussed by Brad has not gone anywhere.

Lets revisit the problem, with a 2008 sheen applied (i.e. I'll use lambda syntax rather than anonymous delegate syntax). What does the following code display?


Func<int>[] funcs = new Func<int>[10];
for (int i = 0; i < 10; ++i)
{
    funcs[i] = () => i * i;
}

funcs.ForEach(f => Console.WriteLine(f()));

If you answered something along the lines of "prints the square of every number between 0 and 9" you'd be...wrong. Really, try it out. See?

Now, a lexical closure is supposed to capture its environment, meaning that the lambda stored on the first loop would capture i when i==0, the second loop would capture i when i==1, and so on. If this happened, then executing all the lambdas would indeed result in the squares of the numbers 0-9 being printed. So what gives?

The problem stems from the fact that the lambda is binding itself to a variable that is accessible outside the closure, which is being changed in every iteration of the loop. The closure doesn't capture the value of i, it captures a reference to i itself, which is mutable.

You could actually make a case that this is bad code anyway, since it gives two responsibilities to the loop index - control the loop, and act as data in the closures. If we were being pedantic, we could split the responsibilities by creating a new variable, j, to be the closure data each iteration, and let i concentrate on being an index:


for (int i = 0; i < 10; ++i)
{
    int j = i;
    funcs[i] = () => j * j;
}

Lo and behold, the code now works! Pedantry rules! Take a look with Reflector or ildasm to see what's going on here. The executive summary is that the compiler captures the environment (i in the first example, j in the second) by creating a member variable within the class it generates for the closure. Previously, since the same instance of i lived for the entire duration of the loop, only one instance of the generated class was created and shared. Now, however, a new instance of the generated class is created in each iteration of the loop (since j is scoped within the loop body and thus we have a new j every time round). Thus, the data is not shared and we get the expected output.

There are two important points to consider here:

The problem goes away if you write code more declaratively. Do away with the clunky for loop and everything works OK.
```
Enumerable.Range(0, 10).Select(x => x * x);
```

It isn't always bad that multiple closures can capture a reference - since one closure can 'see' updates made to the shared data by another closure, you could use this as a coordination mechanism.

This is not an issue that's going to crop up every day - the example above is fairly contrived - but knowing about it will save some painful debugging sessions when inevitably you do run into it. The fix is always to take a local copy of the mutable data to coerce the compiler into generating code that creates multiple instances of the class generated to represent the closure.

Simple, yes? ;-)

Project Euler Problem 5

2008-06-10T12:47:00.000+01:00

On to the next Project Euler problem (after a bit of a hiatus)...

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

In common with many of the other Euler problems, there's a brute-force way to solve this, and a clean algorithmic way. And in common with my other Euler posts so far, I'll start with the brute-force way ;-)

This problem can be tackled head-on with the following approach: Start from n=1 and increment in a loop. Test each value of n by attempting to divide it by all numbers m from 1 to 20. The first number to pass the test (i.e. n mod m is 0 for all values of m) is the answer.


private static long BruteForceSolver()
{
    long result;
    for (result = 1; !Check(result); ++result)
        ;
    return result;
}

private static bool Check(long result)
{
    for (int i = 1; i <= 20; ++i)
    {
        if (result % i != 0)
            return false;
    }

    return true;
}

This works, but it takes >12 seconds to execute on my PC, so it's not what you'd call efficient (though it is well within the Euler execution time guidelines).

Some speed gains can be achieved by exploiting the information provided in the question itself. We are told that 2520 is the lowest number evenly divisible by all numbers from 1 to 10. Since the problem space (1 to 20) includes all these numbers, the answer must also be evenly divisible by 2520. This allows much bigger increments each loop - rather than incrementing by 1, why not increment by 2520? And since the answer must be greater than or equal to 2520, why not start the loop there instead of 1? Finally, since we already know that 1 to 10 divide evenly into 2520, each inner loop only needs to check numbers 11 to 20.

That should speed things up a bit:

private long BruteForceSolver()
{
    long result;
    for (result = 2520; !Check(result); result += 2520)
        ;
    return result;
}

private bool Check(long result)
{
    for (int i = 11; i <= 20; ++i)
    {
        if (result % i != 0)
            return false;
    }

    return true;
}

And indeed, on my machine this is now down to 150ms or so. It's still not a very nice way to tackle the problem, though.

Thinking about it from a different angle yields an altogether smarter approach. Imagine we are looking for the lowest number evenly divisible by the numbers 1 to 2.

[1, 2]

Well that's easy; since there are only two numbers we just find the lowest common multiple (LCM), which in this case is 2 (since 2 % 2 == 0, and 2 % 1 == 0). If we call this sequence s₁, we can say that LCM(s₁) = 2.

OK, now imagine we are solving the same problem for s₂, which contains the numbers 1 to 3.

[1, 2, 3]

You'll notice that s₂ contains s₁ in its entirety. LCM(s₂) must therefore be a multiple of LCM(s₁), so we can rewrite s₂ as [LCM(s₁), 3], or [2, 3] (since we know LCM(s₁) = 2). Now we are down to two numbers again, so we can calculate the LCM of 2 and 3, which is 6, so LCM(s₂) = 6.

OK, now we solve the problem for the first 4 numbers (s₃).

[1, 2, 3, 4]

This sequence contains s₂, therefore LCM(s₃) is a multiple of LCM(s₂). We can rewrite s₃ as [LCM(s₂), 4], or [6, 4]. Thus, LCM(s₃) = 12.

This can be repeated as many times as necessary. Generally, we have s_n = [LCM(s_n-1), n+1] where n > 0.

This looks recursive, but a better way to think of it is as an excellent example of a fold. A fold is one of the fundamental tools of functional programming. In fact, it is perhaps the most fundamental, since map, filter etc can be implemented as right folds^[1].

I won't inflict my pitiful Photoshop skills on anyone by trying to graphically represent a fold - try looking at this Wikipedia article if you want to try and visualise it.

Broadly, the behaviour of a fold is to apply a combining function to elements in a list (or other data structure) and accumulate the results. That's exactly what we want here - our combining function is LCM, and our accumulating value is the LCM of the whole list. Effectively, for list s₃ above, we have

LCM(s₃) = LCM(LCM(LCM(1,2),3),4) = 12

Note how the result of the innermost LCM (applied to values 1 and 2) becomes a parameter to the next LCM, which in turn becomes a parameter to the outermost LCM which returns the result we want.

By using a fold, we can generalise. In Haskell, the whole problem is a one-liner:


foldl lcm 1 [1..20]

The 1 passed in as a parameter represents the terminating value to use when the end of the list is reached. It is common for this value to be the first element of the list, so Haskell provides a convenience function that removes the need to specify it as a parameter:


foldl1 lcm [1..20]

Not all languages and platforms provide an LCM function right out of the box, so to take this neat Haskell solution and port it to .Net, the LCM function needs to be implemented. This is easily done in terms of the greatest common divisor (GCD) like so:

.Net doesn't provide a GCD function either, so I'll implement it using Euclid's Algorithm as an extension method on long ints:


public static long GCD(this long a, long b)
{
    while (b != 0)
    {
        long tmp = b;
        b = a % b;
        a = tmp;
    }

    return a;
}

With GCD defined, LCM can be implemented as above:


public static long LCM(this long a, long b)
{
    return (a * b) / a.GCD(b);
}

With this in place, it's a simple matter to use .Net's equivalent of fold - a method on IEnumerable called Aggregate - to get the answer^[2]:


return LongEnumerable.Range(1, 20)
    .Aggregate(1L, (curr, next) => curr.LCM(next));

And indeed, the same basic pattern can be used to solve the problem in a number of languages. In F#, given implementations of LCM and GCD as above, we have:


List.fold_left lcm 1 [1..20]

And in ruby:


require 'rational'
(1..20).inject { |c, n| c.lcm n }

Given that the right algorithm makes this problem a fairly trivial expression in all these languages, it's pretty hard to identify which is the nicest. I think overall I'll give the nod to Haskell, however, for not making me implement LCM and because I find ruby's 'inject' a less intuitive function name than foldr (but that's probably because I learned the technique in Haskell in the first place and am set in my ways...)

^[1]For example, in F#:


let filter p lst =
  List.fold_right (fun x xs -> if p x then x::xs else xs) lst []

let map f lst =
  List.fold_right (fun x xs -> f x :: xs) lst []

^[2]Note that in this code LongEnumerable is just a very simple partial reimplementation of Enumerable, using longs instead of ints

Project Euler Problem 4: Extra

2008-04-22T13:10:00.000+01:00

Couple of things to add to yesterday's post about problem 4. As is so often the case in life, no sooner had I finished the article than I realised there was an obvious additional step I could make, which I'd somehow failed to spot.

Regarding the C# solution, an easy win having implemented the Reverse extension method would be to add an IsPalindrome extension to the string class too. The implementation is straightforward:

public static bool IsPalindrome(this string s)
{
    return s == s.Reverse();
}

With this done, the where clause in the LINQ query is more readable, and we have a couple of handy reusable string extensions into the bargain.

var result = (from product in AllProducts.From(100).To(999)
              where product.ToString().IsPalindrome()
              select product).Max();

Also, Sol commented that the C code could have a direct implementation of a palindrome function, rather than messing about with strrev, since the implementations are very similar. Whilst this series isn't really focussed on the performance benefit of this approach, it does also make the code more expressive, so I'll include it:

int strpalindrome(char* s) {
    char *s1, *s2;

    s1 = s2 = s;
    while (*s2)
        s2++;

    while (s1 < s2) {
        if (*(s1++) != *(--s2))
            return 0;
    }

    return 1;
}

The loop now looks like this:

    for (i = 100; i < 1000; ++i) {
        for (j = i; j < 1000; ++j) {
            int sum = i * j;
            sprintf(s1, "%d", sum);
            if (strpalindrome(s1) && sum > largest) {
                largest = sum;
            }
        }
    }

If you are interested in the Project Euler problems but craving more detailed analysis, Joel Neely is working through at a similar rate to me, but focusing his efforts on Scala and studying each problem and its solution in greater depth rather than flitting from language to language. Highly recommended.

Project Euler Problem 4

2008-04-22T00:53:00.000+01:00

Problem 4 is as follows:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Bit of an easy one, this. The approach is pretty simple to understand - first calculate all the products of every pair of numbers between 100 and 999, then filter for the palindromic ones, and finally select the largest. The only even vaguely tricky bit is determining if the number is palindromic. The easiest check is to simply convert the number to a string, and check if the string is equal to itself when reversed.

To shake myself out of C#/python complacency, I decided to write my first attempt at this in good old C. I'm a bit rusty so this took a few goes to get right (the shame).

First, I need a string reverse function. For those of us that learned to program when C and C++ were king (before that upstart Java came long and ousted languages with pointers from classrooms up and down the land), this is bread and butter.

char* strrev(char* s) { 
    char *s1, *s2; 
    char c;                           

    s1 = s2 = s; 
    while (*s2) 
        s2++;                           

    while (s1 < s2) { 
        c = *(--s2); 
        *s2 = *s1; 
        *s1++ = c; 
    } 
    return s; 
}

If you can't read that, shame on you, go and pick up a copy of K&R and read it until you weep. In the meantime, basically what happens here is I set pointers to the start (s1) and end (s2) of the original string (s), then swap the pointed-to characters using a temporary variable (c) and move both pointers 1 character towards each other. Repeat until they meet in the middle.

In this day and age of immutable strings, this old friend now feels a little weird - although I retain (and eventually return) the original pointer, I have in fact modified the actual string that was passed in. Contrast this with C's trendy modern progeny, where you can't change a string at all and have to use a StringB[uilder|uffer] when mutating strings (unless lousy performance makes you smile, of course).

Still, now it is fairly simple to solve the problem. A nested for loop will let me calculate all the products, and then I just need to convert the results to strings and do the palindrome test. I keep track of the largest palindromic number found so far, and print it at the end.

int main() { 
    int i, j; 
    int largest = -1; 
    char s1[7]; 
    char s2[7];                           

    for (i = 100; i < 1000; ++i) { 
        for (j = i; j < 1000; ++j) { 
            int sum = i * j; 
            sprintf(s1, "%d", sum); 
            strcpy(s2, s1); 
            strrev(s2); 
            if (strcmp(s1, s2) == 0 && sum > largest) { 
                largest = sum; 
            } 
        } 
    }                           

    printf("%d\n", largest);                           

    return 0; 
}

Note I'm using the much-maligned strcpy function here (the cause of most of the buffer overflow attacks that were so endemic a few years back), but since I completely control the input it's no problem. Also note the use of sprintf to convert the int to a string, and I have to make a copy of the resulting string since my strrev function is destructive. The char arrays are of size 7, since the largest possible product in the problem space is 999*999=998001 which is 6 digits - plus 1 for the null terminator. Which I didn't forget about at all in my first attempt at this, nosirree.

To make the code a bit more 'modern' I could do the allocation and copy in the strrev function, so that the passed-in string remains unchanged and a new string gets returned, but without a garbage collector to rely on this potentially leads to memory leaks (since strrev allocates the memory but relies on the caller to free it - easy to forget!). Anyway, I'm wallowing in nostalgia here so who cares about modern idioms.

Whilst I chose C for this on a whim, it is (as always) enlightening to write a little C now and then, as it reminds you of the cost of things that are often taken for granted. Some people still don't understand why a StringBuilder offers better performance (trust me, I have interviewed more than a few of them), and are happy to write string manipulation code using immutable strings that results in countless allocations and destructions taking place, for no justifiable reason. Writing some string manipulation (or anything else) in C is a nice way to regain a bit of insight and perspective if you are spoiled by quad-core PCs and high-falutin' generational garbage collectors and smartass runtimes that don't let you write past the end of an array.

So, now we've got a nuts 'n' bolts reference implementation, let's look at some more exotic approaches.

As regular readers will have noticed by now, I'm fairly keen on LINQ - so it should be no surprise that C# is my next port of call. I was amused to recall that the .Net string class lacks a Reverse method so I had to write my own for this, about 20 minutes after I finished pontificating about the clean healthy virtue of doing so in C! (I didn't plan it this way, honest.)

There are of course many ways of writing a string reversal routine, but rather than attempt to mimic the fairly idiomatic C code above, I did the simple thing:


public static string Reverse(this string s) 
{ 
    char[] ch = s.ToCharArray(); 
    Array.Reverse(ch); 
    return new string(ch); 
}

Since the Array class contains a Reverse method, I can just convert my string to an array (of chars), reverse that, then create a new string from it. Done. Things to meditate on regarding this approach:

It relies on a char array. Strings may look like a native type these days, but I have to expose their dark and shameful lineage to get the job done here.

The throwback nature of this implementation does not, of course, extend as far as modifying the parameter. A new string is returned and the original remains intact. The garbage collector will take care of deallocation.

This is an extension method on System.String, so I can use it naturally on any string.

Whatever faults it may have, it's definitely easier to read than the C code, since the syntax is much closer to the problem domain. This is a recurring theme when looking at expressiveness. The C code has to specify the entire algorithm for reversing the string, whereas here the Array.Reverse method allows us to ignore the details of how the string is reversed. For the purposes of this problem, we don't really care how the string is reversed, just that it is reversed.

It's still warty, however, in that we have to know to turn the string into an array first, which may be completely non-intuitive to someone who's never tangled with C-style strings.

With this minor omission from the .Net libraries sorted, the problem can be solved with a single compound LINQ query:

return (from product in 
            ( 
             from i in Enumerable.Range(100, 900) 
             from j in Enumerable.Range(i, 1000 - i) 
             select i * j) 
        where product.ToString() == product.ToString().Reverse() 
        select product).Max();

I think that's pretty concise, and quite readable too. The main thing I don't like about it is the use of Enumerable.Range, which takes 'start' and 'count' parameters rather than 'from' and 'to', which would look more natural in this case.

Parameters aside, it's interesting to note the relative clumsiness of the twin calls to Enumerable.Range. Back when looking at problem 1, replacing a for loop with a more declarative alternative made the code considerably more expressive. In this case, however, I don't think it helps quite so much. Once again, it's to do with the nature of the problem domain - a nested for loop is quite a natural way to represent the process of generating the products, so the benefit of a declarative approach is less marked.

How to improve it? For fun, lets go the whole hog and make a simple fluent interface to improve readability of the LINQ query. This is what we want:

return (from product in AllProducts.From(100).To(999) 
        where product.ToString() == product.ToString().Reverse() 
        select product).Max();

Nifty, huh? Well actually I have my reservations about fluent interfaces, but it's quite the fashion these days so I thought I'd give it a chance. The example above is trivial to achieve. On a class called AllProducts we need a static method called From which acts as a factory method, and an instance method called To which returns an IEnumerable<int> for use in the LINQ query. The class looks like this:

class AllProducts 
{ 
    private int m_from; 
    private AllProducts(int @from) 
    { 
        m_from = @from; 
    }                    

    public static AllProducts From(int from) 
    { 
        return new AllProducts(@from); 
    }                    

    public IEnumerable<int> To(int to) 
    { 
        int inclusiveTo = to + 1; // to is inclusive                    

        return from i in Enumerable.Range( 
                   m_from, inclusiveTo - m_from) 
               from j in Enumerable.Range(i, inclusiveTo - i) 
               select i * j; 
    } 
}

Fluent interfaces are definitely this season's black. I heard about a guy who wrote a mocking library without using fluent interfaces for expectations, and 500 angry TDD advocates chased him out of the building with pitchforks.

I'm still a bit wary though, tweedy programmer as I am - I just get a bit nervous about writing hideously contorted classes with a mixture of static and instance methods, some returning the this ref, some returning arbitrary IEnumerables, some acting as factories - and all so the calling code can prance about in a tailored coat and a cool pair of shades. A noble goal, to be sure, but is the price too high? I guess we'll know in a year or two when some maintenance programmer has to try and debug it.

Enough of the lousy clothes metaphor. To finish up what turned out to be a longer post than expected, here's an F# solution I hacked together before getting sidetracked with the whole fluent thing. I read a blog post here about problem 4 (warning - also contains solution to problem 6) but didn't like it too much. It seems to be quite common when reading F# code on the web for there to be a reliance on Seq.unfold - I'm not sure it's always the right tool. Then again, my F# is sketchy at best for the moment, so maybe I should shut up. For balance, however, this is my solution without using unfold.

Note first that F#, as a .Net language, also lacks a built-in way to reverse strings. The implementation is extremely similar to the C# approach above:

let rev (s:string) = 
    let ch = s.ToCharArray() 
    let ra = Array.rev ch 
    let r = new string(ra) 
    r

The actual implementation involves two helpers: a small recursive function to produce all possible products of the numbers contained in two lists, and a simple check to see if a string is equal to itself reversed.

let Euler4 = 
    let rec allProducts l1 l2 = 
        let mul a lst = 
            List.map (fun x -> a * x) lst 
        match l1 with 
        | [] -> [] 
        | h::t -> (mul h l2) @ (allProducts t l2)               

    let isPalindrome x = 
        let str = Int32.to_string x 
        str = rev str

With the plumbing in place, we can use the very groovy forward pipe operator to chain together some very readable code. The only thing to note in here is the reverse ordering of the parameters in the call to compare - this is because we want the results in descending order, so that the largest is at the head of the list and easily accessible with List.hd.

    allProducts [100..999] [100..999] 
        |> List.filter isPalindrome 
        |> List.sort (fun x y = compare y x) 
        |> List.hd

Test-specific Shims in Production Code

2008-04-21T13:51:00.000+01:00

We're currently on a fairly major kick to increase automated test coverage of our software. This doesn't just mean 'get the unit test coverage up to scratch', it also means we are working towards full end-to-end integration testing using, amongst other tools, some front-end automation tools such as QTP and Selenium.

Of course, nothing is ever easy when trying to polish away the tarnish of ancient code. One particular problem we face regularly is patching up code that breaks the fragile expectations of some of these automation tools.

Some of our applications - including the one I am working to refactor - contain UI widgets that use a lot of custom painting routines and conceal data pretty well. One widget, for instance, needs to display data with a fast refresh rate and so uses a double-buffered approach to avoid flicker. The data it displays, however, is not stored anywhere; it is discarded as soon as it is rendered. And since the whole widget view is rendered as a bitmap and blitted to screen, there's no convenient hierarchy of panels, labels, text boxes, or any other standard controls.

This, the Automated QA folks tell me, causes a problem since QTP mainly works by reflecting on properties exposed by controls to get at their data. So, if QTP wants to read some data from a text box, it accesses the Text property of that text box. Simple. But this particular widget doesn't have the equivalent of a Text property.

This isn't really an oversight from a purely functional point of view, since no part of the actual application code ever needs to get data from the widget - it's a display mechanism only, not an interactive widget like a text box. Data is received from a web service, processed a bit, and dumped into the widget. The widget is the last object to do anything with the data - no other part of the app ever needs it again.

Since there are no properties on the widget exposing the data, QTP can't get at it.

Of course, there are ways to keep QTP happy. We can add a few properties to the widget and keep some data around in member variables, or we can write some extensions for QTP that allow it to access some of the widget's internals. The second way is probably the 'right' way since it keeps test-related code external to the application code - but it's more time-consuming, and also has a training cost since most developers aren't going to be familiar with QTP's API.

This leaves the first option. Traditionally I've always been a bit wary of having what is effectively test code (since it only exists for testing purposes) deployed with production code. Furthermore, doesn't it undermine the tests themselves, since they are dependent on code that never gets executed in production?

On the other hand, in some instances it may be the more pragmatic thing to do. It's difficult to justify spending a day or two writing a few hundred lines of QTP extension code when the same effect can be garnered by adding a single read-only property. It still doesn't quite sit right for me though, and I can't find much in the way of authoritative literature that argues one way or the other.

Bash History Spelunking

2008-04-14T14:50:00.000+01:00

Learned from Weiqi, who learned from KageSenshi, about a Fedora Planet shell history meme - post the results of running the following command on your linux box:


history | awk '{a[$2]++ } END{for(i in a){print a[i] " " i}}'|sort
-rn|head

I won't bother repeating the inevitable warning about the dangers of executing random shell scripts you find on the Internet, because I'm lazy and mean. Anyway, here's the results from my webhosting box:

231 ll
171 vim
132 cd
50 screen
43 cat
39 tail
34 ls
34 cls
32 exit
31 wget

'll' is an alias for 'ls -l', and 'cls' an alias for 'clear'. No real surprises otherwise - I use vim for development over ssh, I tail my logs occasionally, and live in GNU Screen.

Here's the output from my home box:

254 ll
181 cd
148 sudo
123 rm
123 ffmpeg
86 screen
83 ls
75 cls
72 vim
60 find

Quite similar actually, guess I'm set in my ways. The ffmpeg count is a bit of an anomaly, since I used it a lot recently to re-encode a bunch of Futurama rips for my mobile.

Not sure what to do with this remarkable intel, however. Perhaps I'll use the data to generate an Identicon and use it as a favicon? Or, perhaps not.

Evil = Important. Apparently.

2008-04-08T16:34:00.000+01:00

OK, I know I shouldn't even acknowledge spam blogs, but this one amused me. Some filthy credit-crunch link bait site took an extract from my previous post (this is obviously what happens when you say the phrase 'credit card' ... oops) and ran it though an automated word substitution program. The result is fascinating. It turned this:

… you buy something from Amazon, you are protected by the fact that evil black-hats can’t find the prime factors of your encryption key fast enough to steal your credit card number (OK, bit of a generalisation, but that’s the gist). …

into this:

… you take something from Amazon, you are secure by the fact that important black-hats can’t connexion the matureness factors of your writing key alacritous adequacy to advise your assign calculate sort (OK, discernment of a generalisation, but that’s the gist). …

Let's review the highlights. 'Buy' replaced with 'take', 'evil' replaced with 'important', 'steal' replaced with 'advise'? Someone's book of synonyms is bound in human hide with a skull on the front.

Project Euler Problem 3

2008-04-07T13:38:00.000+01:00

Next up in the list of Project Euler problems is this one:

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

This, obviously, is a factorisation problem. There is a colossal amount of material on the web for dealing with prime factorisation - a simple google search pulls up lots of information. Prime factorisation (and the difficulty of doing it with sufficiently large numbers) is at the heart of the cryptographic methods we currently use on the internet - every time you buy something from Amazon, you are protected by the fact that evil black-hats can't find the prime factors of your encryption key fast enough to steal your credit card number (OK, bit of a generalisation, but that's the gist).

One of the key phrases in the above paragraph is 'sufficiently large numbers'. For a computer, 600851475143 is not a particularly big number, so this problem can be brute-forced fairly easily. Of course, not all brute force approaches are created equal. The most naive algorithm would be something along the lines of a three-pass sweep - firstly test every single number between 2 and 600851475143 to see if it divides cleanly into 600851475143 (pass 1); then test each factor from pass 1 to see if it is prime (pass 2); and finally take the biggest of the pass 2 numbers to get your answer (pass 3).

This would work, but it sucks.

Fortunately, it's easy to optimise. Let the prime factors of our number N be f₁, f₂ ... f_n. If I start with the lowest prime number and work up from there looking for a factor, I know that the first factor I find will be prime (since if it wasn't prime, it would have factors of its own, which by definition would also be factors of our target number). This number is f₁. I can divide the target number by f₁ and then factorise the result to find f₂. Continuing this process will result in a list of prime factors, and then it's simply a case of selecting the largest.

I can optimise further by not resetting the factor to the lowest prime number each time - since having found f₁ I know that there aren't any smaller factors, so I don't have to waste time looking for them. Here's the implementation in python:

def primeFactors(n, factor):
    factors = []
    while (n % factor != 0):
        factor = factor + 1

    factors.append(factor)

    if n > factor:
        factors.extend(primeFactors(n / factor, factor))

    return factors

print max(primeFactors(600851475143, 2))

Note that in the recursive call the current factor is retained, so that the code doesn't repeat itself.

This executes pretty quickly, but it could be better. For a start, since 600851475143 is odd there's no need to start with the only even prime number (2). Instead, I could just start at 3, and in the while loop skip over even numbers. This would cut the number of tested numbers in half.

A more efficient trial division approach, however, would be to generate a list of primes, divide 600851475143 by each prime to find the prime factors, then simply select the largest. To use this solution, a prime number generator is needed.

This is an interesting diversion - I've peeked at some of the other Project Euler problems and know that prime numbers will pop up again, so it may prove useful to have a generator handy for when I get to those. Some languages, like Ruby, have library functions that can give you primes, but other languages don't. If you're not interested in generating primes and just want to know the answer to problem 3, execute the code above and you're free to get down from the table.

A Random Walk Off-Topic

The simplest way to generate primes is known as the Sieve of Eratosthenes after the Greek mathematician who invented it. In principle it's straightforward - take a list of all integers up to an arbitrary limit, then starting from 2 (the smallest prime), mark all the numbers that are multiples of 2. Then move to the next unmarked number (i.e. 3) and mark all the multiples of 3. Then you move to the next unmarked number (5, since 4 was marked as a multiple of 2) and mark all multiples. And so on, until you get to the end of your list. Whatever numbers remain unmarked are all the primes up to your arbitrary limit.

.Net lacks a built-in prime generator, so to demonstrate the algorithm I'll create a simple C# implementation. The list of numbers is represented as an array of booleans, all set to true by default except indexes 0 and 1 (since we aren't interested in evaluating those numbers as prime).

The other requirement for a funky contemporary .Net implementation is, of course, to expose the results with IEnumerable. This achieves two things - firstly, it lets the sieve class control enumeration and thus skip over the marked numbers (making the calling code cleaner), and secondly it lets me use LINQ to query it.

So, here's the code:


public class SieveOfEratosthenes
{
    private bool[] m_numbers;

    public SieveOfEratosthenes(long limit)
    {
        m_numbers = new bool[limit + 1];
        for (long l = 2; l < m_numbers.LongLength; ++l)
        {
            m_numbers[l] = true;
        }

        for (int i = 2; i != -1;
                i = Array.FindIndex(m_numbers, i + 1,
                    b => b == true))
        {
            for (int j = i * 2; j < m_numbers.Length; j += i)
                m_numbers[j] = false;
        }
    }

    public IEnumerable<long> Primes()
    {
        for (long i = 2; i < m_numbers.LongLength; ++i)
            if (m_numbers[i])
                yield return i;
    }
}

Fairly straightforward. Basically, I start by marking 2 as prime. Then, an inner loop sets all multiples of 2 to false, since no (other) even numbers are prime. Each time round the loop, we find the next true element of the array (which will have a prime index), and mark all multiples false as per the description above. The loop terminates when FindIndex fails to find any more true elements.

This results in an array where the only elements with a value of true are those with a prime index. This makes the actual IEnumerable generator very easy to write - it yield returns the index whenever it finds a true element.

There's a problem with this code, however, that makes it unusable with Euler problem 3 (at least in .Net - hence why I called it a 'diversion' earlier, rather than an alternative solution). In .Net, you can't create an array with 600851475143 elements, since an array with 600851475143 elements is way above the maximum array size limit of 2GB. Even if each element is only a single byte, 600851475143 bytes is about 560GB.

Therefore, you can't create a sieve big enough to solve the problem.

When using trial division it seems that it is enough to only generate primes up to the square root of N, though there are cases when this is not true (e.g. where N=15, sqrt(N) = ~3.873, but the largest prime factor of 15 is 5), and I don't have the maths (yet!) to know how big a fudge-factor is needed. I've seen a solution on the Project Euler forum that generates primes up to sqrt(N) + 10, which solves the example of N=15 above, but does it solve ALL cases? Another approach might be to generate the list of primes such that the largest prime in the list is the first prime > sqrt(N) - but now I'm completely guessing.

Still, for numbers that fit inside the 2GB limit, we can find the largest factor easily.

var sieve = new SieveOfEratosthenes(15);

Now I have my IEnumerable sieve, I can craft a LINQ query to find the largest factor. All I need to do is filter my list of primes for those which divide directly into 15 and call the Max() method:

return (from p in sieve.Primes()
        where 15 % p == 0
        select p).Max();

Done! And I have a handy reusable prime generator for later on.

The Lightbulb Moment

2008-03-25T18:06:00.000Z

Weiqi Gao has a post up today discussing the trials of grokking Scala. Scala is a language I want to take a much closer look at later this year, since I want to become current on the JVM again (having not been on talking terms with it since using J2SE 1.4 around the summer of 2003) without being particularly keen on tangling with the Java language itself.

One of the key features of Scala is the functional programming style it brings to the JVM. It's actually quite common to use certain functional idioms in Java - e.g. passing around a function as a parameter - but the syntax is clunky and verbose (unless and until closures get confirmed in 1.7, that is, and maybe even then).

For example, take a look at this very simple idiomatic code for spinning off a thread to perform an expensive operation:

new Thread (new Runnable() {
    public void run() {
        someObj.doExpensiveOperation();
    }
}).start();

Now that's not the most hideous code I've ever seen, but it's a bit...wordy. Compare it to this equivalent implementation in Java's closest mainstream relative, C#:

new Thread(x => someObj.DoExpensiveOperation()).Start();

I much prefer this syntax, even taking into account the throwaway lambda parameter that's only there to satisfy the ThreadStart signature. The Scala syntax is even nicer, however:

spawn({ someObj.doSomethingExpensive })

This is the sort of thing that piques my interest about the language - expressive syntax and a very funky concurrency model will get my attention, especially when running on something as mainstream as the JVM and with full interoperability with the frankly staggeringly-vast Java library ecosystem. I like F# on the CLR for similar reasons.

But I digress; what I wanted to talk about was a point made by Weiqi, when discussing the pattern-matching capabilities of Scala:

Pattern matching in Scala is exactly the point at which I would spend time trying to understand it, trying to master it, trying to learn to use it. I understand the syntax. I understand the explanation that the speakers in presentations gave. I do get to the part where I say "This is cool." But I never get to the point where I would see a problem and say "This problem is best solved with pattern matching, let me fire up Scala and code the solution."

This strikes a chord for me, as I have gone through that stage once or twice myself with other features in other languages and yet can't quite put my finger on how I get past it. I don't think it's something you consciously do - it's just something you keep grafting away at until suddenly you realise that the technique, whatever it is, has become part of your armoury.

Closures are an obvious example I can think of in my own background. I was raised as a straight-down-the-middle C++ man, way back in the early/mid-90s, cutting my teeth on Borland Turbo C++ 3 on Windows 3.1. When I first started to play with functional languages it took a long time for me to 'get it', and even when I understood what a closure was after a couple of weekends hacking around in OCaml, I couldn't envisage when I'd ever need one.

Soon after, whilst working on a Konfabulator widget in javascript, I noticed I was using them all the time. I suddenly had much more insight into what ruby blocks were doing. It wasn't so much that I noticed the lights go on - they'd been on for some time and I hadn't realised.

People commonly refer to the 'lightbulb moment' or 'the lights went on' as being the point where a flash of inspiration hits and everything suddenly makes sense. I don't like this metaphor. If I need to go to the bathroom in the middle of the night, when the lights go on I squint in pain and stagger around just as blindly as I did before. But then I acclimatise, and all becomes clear. And so it is, I think, with learning alien concepts - you need a bit of time to adjust to the dazzling light.

Project Euler Problems 1 and 2

2008-03-22T17:33:00.000Z

Browsing through Nate Hoellein's blog recently led me to Project Euler. This is a problem - I have a horrendous feeling I'm about to get addicted to it, to the cost of just about everything else that normally occupies my free time. Ack.

Still, at least it provides some blogging material. I'm going to start working my way through the list, and try to create idiomatic solutions in a number of languages. I won't always look for the most efficient solution, since I'm also interested in expressiveness (see here and here for previous posts on the subject).

To start with, here's some code and thoughts for problems 1 and 2.

Problem 1

Add all the natural numbers below 1000 that are multiples of 3 or 5.

This is generally regarded as the easiest Euler problem, so shouldn't present too many problems. Mainstream software development is still dominated by imperative languages and styles, so the most recognisable solution to this would be a straightforward for-loop. Here is an imperative C# solution:

int result = 0;
for (int i = 0; i < 1000; ++i)
{
    if (i % 3 == 0 || i % 5 == 0)
        result += i;
}

Simple enough, but as with all for-loops the guts are a little too visible. I have to explicitly declare and increment an accumulator variable as well as the loop counter. A functional style (Haskell in this case) allows a more declarative solution:

sum $ filter (\n -> n `mod` 3 == 0 || n `mod` 5 == 0) $ [1..999]

Or, with list comprehensions:

sum [n | n <- [1..999], n `mod` 3 == 0 || n `mod` 5 == 0]

In both cases, the loop is replaced by a list generated from Haskell's range operator. [1..999] creates a list containing every integer between 1 and 999 inclusive. The modulo test is basically the same, though Haskell lacks a modulo operator (% in most C-family languages) so the mod function is used instead.

Just for fun, here's an F# solution too:


let sum = List.fold_left (+) 0
let mod35 = fun x -> x % 3 = 0 || x % 5 = 0

List.filter mod35 [1..999] |> sum

This could be compressed into a one-liner like the Haskell solutions, but it would be a bit long for my taste. Also note F# is slightly hamstrung by the lack of a built-in sum function, so I have to define my own using fold. Another F# solution is here, but I prefer mine. There's a very nice snippet in the comments of that page, though, which I like even more:


Seq.fold1 (+) {for i in 1..999 when i % 3 * i % 5 = 0 -> i}

Interestingly, C# is gaining some fairly powerful functional techniques lately, in particular LINQ. I can use the new Enumerable class to mimic range syntax and filter functionality from other languages, and lambdas to keep the code concise.

Enumerable.Range(1, 999).Where(
        f => f % 3 == 0 || f % 5 == 0).Sum();

Note the similarity between F#/Haskell's lambda syntax and that of C#. It's very cool that a mainstream C-derivative language is getting this sort of syntax added to it.

Alternatively, I could use LINQ query expressions for a different approach:

var nums = from n in Enumerable.Range(1, 999)
           where n % 3 == 0 || n % 5 == 0
           select n;
nums.Sum();

Fun!

It should be noted that all the Project Euler problems I've seen so far have mathematical solutions, meaning if you are able to classify the problem correctly it is straightforward to work out the answer with pen and paper. In this case, the problem is based around an arithmetic progression, and there are powerful formulae for reasoning about those. If you're interested, check out the forum for problem 1.

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Ooh, Fibonacci. I've been here before. Using the Haskell code from that post makes problem 2 a snip:

fib = 0 : 1 : zipWith (+) fib (tail fib)
sum $ filter even $ takeWhile (<4000000) fib

Given the lazy Fibonacci generator in the first line, this just uses standard Haskell functions from the Prelude to do all the work - reading right to left, takeWhile pulls data from the fib sequence until the test fails (i.e. we've reached 4,000,000), filter even does exactly what it says on the tin, and sum does the business on the result.

C# could solve problem 1 very neatly - can it keep up the pace in problem 2? Actually, yes it can, after a fashion. The lazy Fibonacci generator can be implemented using the yield statement added in C# 2.0. This is much more efficient than the naive recursive solution I looked at in my previous post about Fibonacci sequences. Once I have the generator, the LINQ statement is very concise and quite similar to the Haskell code - C# 3.0 even has TakeWhile!

IEnumerable<long> Fibs()
{
    long a = 0, b = 1;

    while (true)
    {
        yield return b;

        b = a + b;
        a = b - a;
    }
}

Fibs().TakeWhile(f => f < 4000000).Where(f => f % 2 == 0).Sum();

The more I use C# 3.0, the more I like it - there's quite a bit of power in there.

As with problem 1, there are some fascinating mathematical tricks that can be utilised when solving problem 2, and I recommend you check out the forum. It's particularly cool to see how the Golden Ratio can be brought into play when working with Fibonacci sequences - I had no idea these techniques existed. So much to learn!

The P.G. Wodehouse Method Of Refactoring

2008-03-21T23:01:00.000Z

I am much given to ruminating on refactoring at the moment, as one of my current projects is a major overhaul of a fairly large (>31,000 lines) application which has exactly the kind of dotted history any experienced developer has learned to fear - written by many different people, including short-term contractors, at a time in the company's life when first-mover advantage was significantly more important than coding best-practice, and without any consistent steer on the subjects of structure, coding conventions, unit tests, and so on.

In other words, here be dragons.

In fairness, the application works and has been a critical part of a company that has gone from nothing to market-leading multinational in 7 years, so it has certainly pulled its weight. It is in desperate need of a spring-clean though, and my team volunteered to spend 3 months evicting the cobwebs and polishing the brasswork.

Yes, volunteered - it's a fascinating challenge, though perhaps not something you'd want to make a career of.

Now, the first mistake to avoid here is the compulsion to throw it away and rewrite from scratch. So often when confronted with a vast seething moiling spiritless mass of code a developer throws his hands into the air and declares it a lost cause. How seductive is the thought that 31,000 lines of code could be thrown away and replaced with ~15,000 lines of clean, well-designed, beautiful code?

Sadly, that's often a path to disaster. It's almost a rule of the game. jwz left Netscape because he knew their decision to rewrite from scratch was doomed. Joel Spolsky wrote a rant about the same decision - in fact, the Netscape rewrite is commonly cited as a major factor in Netscape losing the first browser war.

The problem is that warty old code isn't always just warty - it's battle-scarred. It has years of tweaks and bug-fixes in there to deal with all sorts of edge conditions and obscure environments. Throw that out and replace it with pristine new code, and you'll often find that a load of very old issues suddenly come back to haunt you.

So, a total rewrite is out. This means working with the old code, and finding ways to wrestle it into shape. Naturally, Working Effectively With Legacy Code now has an even more firmly established place on my 'critical books' bookshelf than it did before.

Inspiration came from a less well-known book, however. Buried in Chapter 10 of Code Reading is a single paragraph suggesting that it can be useful when working with unfamiliar code to paste it into a word processor and zoom out, getting a 'bird's eye' view.

One other interesting way to look at a whole lot of source code quickly under Windows is to load it into Microsoft Word and then set the zoom factor to 10%. Each page of code will appear at about the size of a postage stamp, and you can get a surprising amount of information about the code's structure from the shape of the lines.
(Spinellis, 2003)

The idea is that this lets you immediately identify potential trouble spots - if you see pages where the code is all bunched up on the right, it indicates massive nesting and over-long functions. If you see heavy congestion, it indicates dense code. It's also easy to spot giant switch statements and other crimes against humanity.

Of course, you don't actually need MS Word to do this - the Print Preview in Open Office is more than sufficient, and no doubt most office suites can do the same.

This 50,000ft view could be a useful tool in tracking progress. I mean sure, we can have our build system spit out cyclomatic complexity and code size metrics, but wouldn't it be neat if we could do a weekly bird's-eye printout of the source code and pin it up on the wall, giving a nice simple visual representation of the simplification of the code?

Except, of course, that with average page lengths of 45 lines we'd need almost 700 pages each time, and a hell of a lot of wall space.

A better solution would be to print a class per page. At the start of the project, the application had about 150 classes, and the refactoring effort is focussed on about 80 of those. Initially, gigantic classes would be an incomprehensible smudge of grey, but as the refactoring process starts tidying the code and factoring out into other classes, the weekly printout would start to literally come into focus, hopefully ending up with many pages actually containing readable code (which happens roughly when the class is small enough to fit on no more than 3 pages at normal size).

The first time we pinned up the printouts, I suddenly recalled a Douglas Adams foreword reprinted in The Salmon of Doubt. Adams was a great fan of P.G. Wodehouse, and explained Wodehouse's interesting drafting technique:

It is the next stage of writing—the relentless revising, refining, and polishing—that turned his works into the marvels of language we know and love. When he was writing a book, he used to pin the pages in undulating waves around the wall of his workroom. Pages he felt were working well would be pinned up high, and those that still needed work would be lower down the wall. His aim was to get the entire manuscript up to the picture rail before he handed it in.
(Adams, 2002)

Hmm, isn't redrafting a literary cousin of refactoring? In many ways, I think it is - so why not apply this technique to refactoring?

And we've made it so. We tied a piece of string horizontally across the wall - that's our 'picture rail'. Every week we reprint the classes we have been working on, and replace the old printouts. Then we move them up towards the string, in accordance with how happy we are with the view.

Obviously, this doesn't replace all the other tools we have for evaluating code quality - e.g. the aforementioned metrics, unit tests, manual QA, and so on. It does, however, make for a brilliant way of tracking our subjective satisfaction with the class. Software quality tools can never completely replace the gut instinct of a developer - you might have massive test coverage, but that won't help with subjective measures such as code smells. With Wodehouse-style refactoring, we can now easily keep track of which code we are happy with, and which code we remain deeply suspicious of.

As an added benefit, all those pages nicely cover up the hideous wall colour. Bonus!

Arthur C. Clarke, 16/12/1917 - 18/03/2008: Indistinguishable From Magic

2008-03-18T23:51:00.000Z

Sad news - the legendary Arthur C. Clarke has died. He'll be greatly missed; Clarke novels occupy a full shelf of my floor-to-ceiling bookcase, and Rendezvous With Rama stands proud as the finest sci-fi it has ever been my pleasure to read.

Aside from his very visible mastery of sci-fi, however, there is much to remember Clarke for. He is responsible for popularising the concept of geostationary orbit, which is very important for practical global telecommunications. When you watch the Olympics on TV this summer, you can thank Clarke for the fact that you haven't had to go to China to see it.

Perhaps best of all, though, is his now-infamous Third Law:

Any sufficiently advanced technology is indistinguishable from magic.

Clarke's Third Law has been quoted, referenced, and paraphrased copiously since he coined it, and it is almost axiomatic for many technologists. As a software engineer, I get a wry enjoyment from Gehm's Corollary, i.e. "any technology distinguishable from magic is insufficiently advanced" - a sobering thought when confidently hacking away on the next big thing!

If your users don't think your software is magic, then you have room for improvement. I believe Clarke would have approved of that sentiment. R.I.P.