Beer in the Evening - Intel Fastercity Event

Intel are hosting a freebie beer in the evening event. Looks like it will be fun - I plan to attend.

Nigel Woodward of Intel writes:

A quick reminder about the FasterCity community event featuring: industry panel, discussion and Chief Wine Officer™ reception on the 2^nd of July 2007, registrations begin at 5pm after which the conference is set to commence at 5.30pm – the venue is Savoy Place WC2R 0BL.

The many bottles of excellent fine wine are waiting to be tasted, and the chef has prepared a canapé menu specifically to complement the wine. Peter McCombie will host the event (www.petermccombie.com) and you will hopefully leave entertained, educated and possibly with a prize or award.

I look forward to meeting you on the night.

Nigel Woodward

Head of Financial Services

Intel Corporation

Dir: 020 7614 8600

Web:www.intelfasterfs.com/fastertrading

A Lesson in Simplification: Heuristic methods, Genetic Algos and NP Complete Problems

It's rare to find an intriguing and difficult task in investment banking - mostly our work involves straight forward computational work. I was asked to write a program for a guy who was manually sorting spreadsheets which contained totals of net asset values for exchange traded funds from Reuters. He was trying to find out which flags had been used by Reuters to calculate the total.

My initial reaction was that this would be a simple iterative algorithm which would be easy to implement. After consulting two quantitative analysts I know, I was informed that I'd come across the Postage Stamp problem (a.k.a. the Money Changing problem) which could only be solved using a brute force approach. Technically, the problem is N-P Complete. There was no known algorithm for this so he suggested I go through all the subsets as outlined in this article on Generating Partitions. At this point I felt like giving up but I persevered, and read some interesting articles which related the problem to Frobenious so I found some code which implements this though didnt get particulary far with this as it produced a (to me at least) meaningless series of numbers. I did find this McNuggets Problem analogy from Wolfram useful in explaining the problem in Joe six-pack terms. I also found a candidate algorithm which looked good for the job - The Diophantine Linear Equation.

A young turk here, Darryl Stein, was itching to help so we both worked on candidate solutions. He adopted a GA approach based on a C# GA library from those lovely people at Google - Aforge.NET - this was efficient and reasonably accurate on the data we had - but being c# - it couldnt' work on the unix platform so was not really feasible as this had to be done server side (the data was coming out of Vhayu).

So we ended up coding a version of the Diophantine equation which did pretty much what the guy was doing with the spreadsheet - ie - starting with the biggest number, then the next until the limit was breached then sieving through the permutations until you get a hit or not. Darryl beat me to it with a neatly coded recursive solution which did the job.

LSE Electronic Trading

The Wall Street Journal Europe is reporting that the LSE has unveiled a new electronic trading system that will allow a trade to be booked and confirmed within 10ms, 130ms faster than previously.

The London Stock Exchange on Monday unveiled a new electronic-trading platform, TradElect, which promises to trade a share in 10 milliseconds -- 30 times faster than the blink of an eye and a speed that could help decide the fate of Europe's biggest exchange by market capitalisation of its listed companies.

The system cuts the time from placing an order to final confirmation to an average of 10 milliseconds from 140 milliseconds. It can handle 3,000 orders a second, up from 600 under the LSE's old system, known as SETS, a number the LSE said it has approached on several occasions in recent months.

By comparison, it takes 110 milliseconds for a trade to make its way through the main trading platform of NYSE Euronext's New York Stock Exchange. The Big Board intends to cut that to 10 milliseconds.

Another way of putting this is that someone can make 11 trades on the LSE while you are waiting for your NYSE transaction to complete.

How much XML can you process in 10ms?

XML versus ASN.1

I don't know how widely the ASN.1 Packed Encoding Rules (PER) are used but here's an example of how much more verbose XML can be than PER.

Here's a simple ASN.1 definition:

FooBaz {1 2 0 0 6 3} DEFINITIONS ::=
 BEGIN
    T1 ::= INTEGER (25..30)

    Test1 ::=
       SEQUENCE {
          first  T1,
          second T1
       }
  
    Test2 ::=
       SEQUENCE {
          first2  [0] T1 OPTIONAL,
          second2 [1] T1 OPTIONAL
       }
  
    Integer11 ::= INTEGER (0..32000)    
  
    Test3 ::=
       SEQUENCE {
          first  T1,
          second T1,
          third Integer11,
          fourth Integer11
       }
 END

Here's an encoding using XML:

<Test3>
   <first>29</first>
   <second>30</second>
   <third>63</third>
   <fourth>31000</fourth>
</Test3>

Here's the PER. Note that it fits into 36 bits so the last 12 are irrelevant.

9401 ff91 8000

I make that 36 bits for PER and 112*8 = 896 bits for XML, a ratio of 1:25.