Freesteel Blog » 2007 » November

Wednesday, November 28th, 2007 at 2:10 pm - - Machining 1 Comment »

The subset of the 1-dimensional real line is an important model in computational geometry because it can be defined accurately in terms of an even-sized array of floats, and because it can be used as a building block for more sophisticated geometric structures.

The diagram below shows illustrates such a subset, A which happens to have 3 components and could be expressed by the array:

   size(A) = 6;
   A[0] = 0.5;  A[1] = 1.7;  A[2] = 2.9;
   A[3] = 4.1;  A[4] = 5.8;  A[5] = 6.0;

which means it lies inside the interval [0.0, 6.0].

For convenience, subsets are assumed to be closed, which means they contain the endpoints of their connected segments. A contains(x) function could be written as:

bool contains(A, x)
{
    for (i = 0; i < size(A); i += 2)
    {
        if (A[i] <= x) and (x <= A[i + 1])
            return True;
    }
    return False;
}

It's easy to calculate the compliment A' of this subset within an interval using the following routine:

complement(A, lo, hi)
{
    if (size(A) == 0) or (A[size(A) - 1] != hi)
        A.append(hi);
    else
        A.eraseAt(size[A] - 1);
    
    if (size(A) == 0) or (A[0] != lo)
        A.insertAt(0, lo);
    else
        A.eraseAt(0);
}

The (size(A) == 0) condition is superfluous, because after the first paragraph size(A) will not be even, so cannot be 0.

(There’s no generally accepted pseudocode for array handling, but knowing what needs to be done should make it possible to understand what it means. The statements len(A), count(A), A.size(), and size(A) all mean the same thing.)

This function is not strictly the complement set, because if A' (drawn on the lower half of the above diagram) is the value of A after this function has been executed, then its intersection with A is non-empty because it contains five boundary points.

There are a lot of other problems with this representation, which I once wrote up in a sixty page chapter of a book I began on computational geometry before I got the current work. But one of the good things about it is it’s a self-inverting function. That is, if you apply compliment() twice, you come back to the value you started out with.

I have constructed a representation of a 2-dimensional subset of the plane using two arrays of these 1-dimensional subsets by arranging them in a weave, like so:

The area is broken down into these square cells between the 1-dimensional lines with the endpoints of the subsets connected up in the obvious manner. As you can see, this approximates the area bounded by the polygonal model (the triangle drawn with a green dotted line), which in this case has been placed in the most inconvenient way possible — one of its edges has been perfectly aligned with a horizontal 1-dimensional subset.

As you would expect, it’s pretty rare for this to happen; if the spacing between the lines is a random-looking value, like 1.928374746, then the odds of hitting one of the edges of the polygon are pretty low. However, when it does, things shouldn’t go particularly wrong…

Unless you try making the complement of the area.

There is an important consistency requirement with regards to these area models, which in my code are called “weaves” (the 1-dimensional subsets are known as “fibres”). It is that the crossing points are consistent. That is, for any vertical fibre A aligned with value x = a, and any horizontal fibre B aligned with the value y = b, then:

    contains(A, b) == contains(B, a)

This condition is satisfied by the diagram above. Up till now I had implicitly found the complement of the area by applying complement() to each fibre in turn. This worked nearly always, and I had never suspected that there was a problem. Unfortunately, when you do it for such an instance where endpoints of subset segments lie exactly on a cross-fibre, the consistency requirement fails, and the rest of the algorithm which depends on this requirement being true breaks down in catastrophic and unpredictable ways.

Some of these failures were recovered from by additional code later on. However, once we began running our fancy algorithms on multi-processor machines, these fixes stopped working. I am therefore in a bit of a pickle.

Of course, the quick fix would be to ensure that there always is a good fudge factor to prevent the polygon (or any of its offsets) becoming perfectly aligned with one of the fibres. Multiplying the weave spacing by 0.999928376 would almost certainly make any given bug instantly disappear, whilst leaving the underlying design flaw in place.

For most people this would the best course of action, because they didn’t write the algorithm, they don’t understand it, more invasive fixes are likely to make things worse, and it’s not their code anyway. If they’re a very good programmer, they will have moved on up the company before it reappears. Workload tends to be pretty constant all the time, so there is nothing to be gained from fixing a very marginal problem absolutely given all the costs it entails.

That’s assuming you’re sure it is a marginal problem, and not just hoping it is. However, I do note that it is unusual for a programmer, unless he is young and naive, to believe he has a stake in the software to the extent that he expects that if it goes wrong in 20 years time it will still be his problem. It might not be true, but if he believes it, his results will be different.

So I better stop blogging and continue fixing this now-known issue now, having discussed it with the world (even if no one in the world understands it; it helps to talk it through). It’s not going very easily; it’s going to get slower before it gets faster because have to leave some duplicate calculations floating around before I work out how to avoid them. I hope everyone understands.

Friday, November 23rd, 2007 at 1:18 pm - - Whipping 1 Comment »

I am not an accountant. Not many of us down among the non-owning-sharedealing-banking classes are. So there’s no one looking out for our interests when people at the top loot the public treasury and saddle the state with highly ill-conceived projects that are nevertheless very profitable.

Remember, it’s about money. And nothing else. If they get their hands on truck-load of snake-oil, it doesn’t matter what it can and cannot cure, they will do whatever it takes to sell it. Even if it means we have to build a police state.

What I’m saying is that the money-grubbing going on over the sale of QinetiQ matters. It’s a sign of what our politics is all about. QinetiQ is about weapons, programmable CCTV cameras, ID equipment, and dumb-ass airplane seat detectors that are supposed to tell from the shiftiness of your body whether you are a terrorist or already dead. They’ll think of something. It could be worse. If they were invested in a medical company, we we could have been infected with smallpox vaccines, as opposed to an invasive infestation of security cameras and fingerprinting equipment. After some wikipedia background hacking, it was good to see how the current CEO connected back to previous knowledge I had about a PR firm whose New Zealand office battled for the eradication of old growth forests, as documented in this book, which made quite an impression on me.

So what’s the deal here? The sale of these valuable state assets — whose value becomes much greater after the snake-oil sale campaign is in full swing — to an extremely well-connected business was transparently undervalued. Disappointingly, the Government Ministers have had a habit of covering it up. They mess with your mind because all the evidence of serious corruption gets inverted. No wonder we never understand. You see, the three-fold increase in value shortly after sale is not because someone we were ripped off; it’s merely a sign of how excellent the directors were at managing the company! The bigger the discrepancy, the better their qualities! It’s like seeing someone in a stolen Jaguar, and concluding that, dang, he must get paid well for his job. Let’s hire him. The Secretary of State for Bombing told us two years ago that the National Audit Office decision to investigate the situation was purely routine. No one had reason to suspect anything. Why do politicians even bother to lie like that?

Luckily, the NAO report, which got published today, was useless. It’s all misleading numbers, confusing statements, technical history, and no account anywhere that people had lied.

My favourite moment is on page 17:

1.21 The opening balance sheet of QinetiQ is set out in Figure 5 overleaf. This was prepared in line with accepted practice and as such the value of shares in joint ventures that were commercially exploiting intellectual property did not reflect their potential to generate future revenue. The Department held share capital with a book value of £346 million and long-term loans amounting to £156 million.

And here’s the table from Figure 5

Tangible fixed assets: £548million
Current assets: £240million
Current liabilities: -£230million
Provisions: -£56million
Long term loans: -£156million

Total share capital: £346million

As I said, I am not an accountant, but I think most people who read paragraph 1.21 would have subtracted the £156million from £346million and imagined a net value of £190million, although the £156million had already been taken away once to get that number.

Boring, isn’t it?

Numbers and accounts are so naturally confusing that it’s relatively easy to put people off from understanding them if you want to. Not only was the £346million an under-valuation (excluding all the inventions in the pipeline), those who were arranging the purchase wanted to sell it even cheaper than that.

But first, a few words on this value. The deal was sweetened by the transfer of a lot of government land that had been obtained by the Ministry of Defence during the second world war. The net worth is easy to guess. In 2002, the MoD was willing to divulge some figures when asked in Parliament. By 2006, when asked about this formerly publically owned land, the Secretary of State told whoever asked to go jump in a lake, by giving the corporate address of the CEO, knowing that he was going to say that it was none of anyone’s business.

But of this under-estimated value, the civil-servants concerned were determined to ensure that their future benefactors (the Carlysle Group) was not going to pay a fair price even for this. Some MPs noticed: Carlysle was paying £42million for 31% of something which accountants had valued at more than £300million. In a Select Committee meeting on 21 January 2003, we read:

Gerald Howarth MP: Mr Youngkin told us a moment ago, as you heard, that his group is paying £42 million for a third of the equity. If I can ask you the question that they were not able to persuade us of the answer to. If the net assets of the company are £312 million, that is net of liabilities, which presumably includes the £140 million owed to you under those loan notes, therefore the free capital, if you like, is £312 million, can you explain to us as laymen why is Carlyle paying £42 million for a third stake in a company which has a capital value net of debt of £312 million?

Colin Balmer: Can I take this question in two parts. First, Carlyle will be paying us in the order of £40million, as I said the exact figure will depend on the completion accounts, but they are also allowing us to be repaid by the company the debt that I have described, so Carlyle are in effect paying us £140 million to £150 million but they are not having to provide cash from their own shareholders for all of that. The company will be worth less because we have taken our money out. As regards the balance sheet value of the assets—

Gerald Howarth MP I am sorry, I am going to stop you there because they will not have taken their money out because the figure of £312 million is net of the debt, the liabilities are in the accounts at £251 million as creditors falling due in one year, so that is already accounted for, is it not? We know that the company has been valued at £500 million but after you deduct the liabilities, of which the £140 million to £150 million due to you in the loan notes is a part, the net result is that we have still got assets on the books of £300 million where you have got two-thirds of the action and Carlyle, plus the employees with their, in my view, rather small stake in privatisation, they have got the rest. Therefore, they have paid £42 million for assets worth £117 million.

Colin Balmer The asset values on the books are recorded in the company’s accounts. From the figures you have correctly quoted and as was disclosed by the Minister in a Parliamentary question the net asset value is £312.5 million as at 31 March last year, those are the closing accounts for the company at that stage. The directors of the company made clear in a note to those accounts that the valuation of the assets was done on a depreciated replacement cost basis, a perfectly normal process, which is not the open market value of the assets. Had an attempt been made to assess the open market value of those assets the director’s view was that the assets would have been worth substantially less than that, by more than £100 million. The view at that point in time of the net assets of the company was £312.5 million less a substantial amount if you tried to sell the assets in the market place. That is the asset position. What Carlyle have done—

Gerald Howarth MP That is phoney accounting, is it not?

Colin Balmer: No, that is perfectly normal accounting and those were the notes disclosed by the company in its accounts and passed by their auditors. The figure for the opening balance sheet that year had previously been agreed by the National Audit Office but the closing accounts were agreed by the company’s new auditors KPMG. The figures have all passed normal audit processes. The question about what Carlyle or whoever we sold these shares to should pay is a different question. Clearly an asset value is one consideration that one would take into account. Other things to take into account, and this will clearly weigh very heavily with Carlyle are: What happens to this company in the future? What will the future performance be? What future requirements are there going to be for capital investment? What future liabilities might arise in other circumstances and what cash can the asset base be expected to generate in normal trading? The amount of cash that the company should generate over a longer period discounted back to today’s value is a more normal way of valuing companies at a point of sale and our own advisers suggested that is probably how Carlyle or anybody else would have valued the company. I do not know what value Carlyle did put on any of those calculations, that is their business, they simply gave me the enterprise value at a figure of about £500 million on the assumption there was neither debt or cash in the company. The underlying value is about £500 million. Clearly there was a mixture of debt and overdraft and cash holding so at any point in time the working capital movements would mean that the actual value would be less or more than £500 million, probably less than £500 million taking account of those liabilities. If you work that calculation through and you take account of what we think the working capital balance will be and we take account of the debt the company owes that is how we get down to a number which generates a flow to us of about £140 to £150 million.

Gerald Howarth MP You start off by saying there is an underlying value of £500 million, the balance sheet shows net assets of £312.5 million but you say that the directors reckon that an open market would be about 100 million less.

Colin Balmer More than £100 million less, they actually said £113 million.

Colin Balmer was a Finance Director at the Ministry of Defence. Now he is the Managing Director of the Cabinet Office at “the centre of government, making government work better.”

For whom?

Tuesday, November 20th, 2007 at 1:35 am - - Whipping

Allow me to propose the a Wikipedia citation template for referring to an email document, as follows:

{{Email document| 
    From= Adam Smith |
    From_Organization= Bristol City Council|
    To= Beth Smith |
    Date= 2007-10-10 09:35
    Subject= Re: FOI request for contract

    document_dump_location= MySociety|
    document_id= 883746
}}

The template would do a #switch on the value of “document_dump_location” and expand it to a URL, such as

    http://www.foiarchive.org.uk/emails.php?id=883746

and the text would be laid out suitably for a footnote in a wikipedia article. In the event of the mySociety email archive melting down, you have two other repositories for the email, the sender and the receiver, such that there is still a chance it could be dug out, or at least obtained by a subpoena.

As some of you know, mySociety is in the process of building a Freedom of Information Archive, including a User Interface for people who don’t know how to make and follow up such requests.

The primary way in which this Free Information and its requests thereof are transmitted is via emails. These are going to be archived somewhere central, and the structure of what is a request, what is a reply, and what is a denial is going to be built within some kind of complex database.

Unfortunately, the design of the database is non-obvious, and no matter how well you try to set it up, there will always be missing cases. Possibly very important ones.

In the real world, difficult software is a process, not a finished product. It’s no good hoping for it to be great when it is complete, because it won’t ever be complete, therefore a design which allows the system to perform at various stages of incompleteness is going to be necessary if you are to avoid disappointment.

Now, it would be true to say that my theories of software design go against the prevailing practice. To me, databases exist only to make software run quicker, and generally provide a hindrance to the design and experimentation process. If premature optimization is the root of all evil, then databases are the devil’s post-it notes.

As it happens, the way the archive is initially scheduled to work will be as a series of dynamic web-pages, forms, drop-down address lists, exemption tick-boxes, log-in systems, and comment streams. At every stage of development before it is entirely complete (if that is indeed possible), there will be large gaps in the system. When you are faced with one of these gaps, your options are either to give up, or wait for the system to be redesigned to handle it, or, more often than not, drop out and complete the process by hand, thus starving the system of participation. Things that are created in your own records and email accounts will fail to get archived in public where we will ultimately all benefit.

My own design calls for the establishment of an email database with accessibility through the above Wikipedia template, combined with a copy of MediaWiki that makes everything possible by hand on Day 1.

Each request is made on its own page with an attractive info-box, with use made of the Category system. By hand, or using Wikipedia:Bots, categories of Pending Requests, Satisfied Requests, Denied Requests, Overdue Requests, and Appealed Requests could be maintained. Categories would also be for the Authority, Sender (if an institution), and according to Exemption.

The fluid structure of the InfoBox and the email templates therein are easy to hack about and scan using text-based scripts. A block of text with this structured data is equivalent to a database entry, but with one of the columns representing “everything else we haven’t thought of yet”. Except this way it’s hand-editable, quickly viewable, immediately functional, and suitable for experimentation. Think of it as a dynamic prototype we can all work with and show off different configurations using. And, most importantly, it works for everything from Day 1, so you never need to leave it.

Then, with this as the platform, you can start discussing and coding up a working user interface system for more novice users to access.

There is a precedence for this style of development. A while ago all User Interfaces were designed in programming languages like C++. Only later did we start to get graphical tools for designing these User Interfaces; and what they did was automatically generate the C++. This meant that they were built on top of a known-to-be-working layer, and when it turned out not to be able to do everything necessary, the programmer had the option of dropping down into the lower level to finish the job off in C++, if they chose to. It’s not compulsory to go into the hard stuff, but it remains there as a potential work-around, which is better than having no means of working around it at all when you hit a limitation.

Luckily, I have nothing to do with this project, so all this can be safely ignored. I am, however, a potential user, and have submitted the entirety of my Bristol City Council case as emails to them as data in the hope that the system will at least be able to handle all of that.

Hopefully an email archive component gets up and running at some point, with all these emails loaded into it. Then I can make my own Wiki page documenting the case and put all the above theory into practice.

Meanwhile, the mySociety crew will put together their proper database, web-form filling design however they like, and get lots of users into the system doing wonderful things. Speeches will be made. Awards will be given. And another amazing success story will be chalked up with the ease of something whose correct solution was completely obvious from the start.

Tuesday, November 20th, 2007 at 12:32 am - - UN, Whipping 9 Comments »

Sometime after the discovery of the International Year of the Potato, there was a late night vote of 1 to 0 with 0 abstentions to put the www.undemocracy.com project on strike, because nobody loves it.

The UN_document wikipedia template has been diverted to the UN Documentation Centre. The front page links to this blog post. And the full output of the parser, which will still continue to run, remains in this directory.

If there is an objective measure of respect for a website, it can be expressed by the number and quality of links that come into it. Aside from the couple hundred structured wikipedia links which I did myself, now harmlessly disabled, the exhaustive list of links to www.undemocracy.com is as follows:

  • A large handful from my blog and another blog which I write for
  • A spam report page on wikipedia
  • A link most of the way down on the Cambridge University Model United Nations Society research page which doesn’t even work
  • Two [1] [2] references from blogs about Hack Day in June
  • A minor note at the bottom of someone else’s blog post in July
  • One minuscule sentence somewhere lost in a blog posting in September
  • The page for my scheduled talk at Pycon 2007
  • A talk by “net-political troublemaker extraordinaire” Stefan Magdalinski in October where he mentioned the site in detail (I know because I went down to London especially), but where the write-up links to everything else but it
  • A link I put in for BarcampUKGovweb under my own name
  • er…
  • That’s it.

Clearly, in spite of my best efforts (and I’ve left out all the blow-by-blow details), I’ve not got what it takes. And nobody who has what it takes has made themselves available.

This site stays down until further notice, except when I want to look at it, or I want to show it to someone, or I am on my way to barcamp, which I guess is the same thing. I wrote the whole original parser for theyworkforyou.com for no credit, which obviously matured into no social capital of the kind that can be used to influence people. This one is definitely sitting out in an unhappy place.

Feel free to contact me through the comment system on this blog post, or email team@undemocracy.com, which so far has never used.

Messages I do not want to hear include:
(a) “You’re too impatient. You haven’t given this enough time+effort”;
(b) “You’re no good at connecting with people. Try a little more persuading and a little less ranting”;
(c) “You’re being completely unreasonable. You have no right to do this with the work of so many other people.”

Messages I would prefer to hear include:
(a) “It does seem odd and unfair how little has come out of it in six months, even though you have jumped at every opportunity you could think of”;
(b) “You have proven to be far less capable of generating publicity than at programming. I’m pretty good at doing publicity. Maybe there’s stuff I can do which doesn’t involve beginning with a lecture about all the things you’re doing wrong”;
(c) “I can see why you have been driven to go on strike. I thought I was quite interested in the project, but now I realize I have never once put a link to it on my blog or tried to get to know the project better. Frankly, I’m not sure why that is. And if can’t decode exactly why I’ve felt this apathetic, I don’t see why should be able to.”

Anything else remotely productive or encouraging will be gratefully received, although I am primarily looking for tangible offers from people who can convince me they will actually do something. I plan on this lasting at least a couple of months. Maybe a year. Or until I experience a change in mood. But, believe me, if I can get this far on what has basically been zero encouragement, my moods can be pretty stable over long periods.

Friday, November 16th, 2007 at 1:21 pm - - UN

Just when I have no time to spare, I get sucked into the nexus of undemocracy.com and Wikipedia, beginning with the Ustica Massacre and riding through the Category of Airliner Bombings, back to
Korean Air Flight 858
which I patched up extensively using some amazing transcripts from the Security Council documenting the North Korean terrorist agent Kim Hyon Hui’s confession. Prior to carrying the bomb on board, she had been shipped through several European cities pretending to be a Japanese tourist, having learnt Japanese while living in North Korea from a woman who had presumably been kidnapped from Japan.

You can’t make this sh*t up. I started the page for the book Shoot the Women First. And now it’s long past lunchtime. I was originally trying push the scraping of UN documents back to 1980 and the Ustica Massacre, but I only got as far as September 1985. I’ll need to come back when they’ve scanned some more, if that’s what they’re doing.