A new method of forecasting has been brought to my attention: Paul. Paul is an English-born octopus, currently living in Germany, and has been predicting with high accuracy the results of the German soccer team, by picking between two boxes marked with the flag of the two competing teams:
How unlikely is it that Paul would have such a string of correct forecasts? Pretty unlikely. If you assume that Paul’s picks were completely random, with a 50% chance of correctly calling the winner, the probability of making 11 good calls out of 12 comes down to 0.29%. Does this mean Paul is the next big thing in forecasting? It’s possible, but I don’t think so (this said with all due respect to Paul and his skills). Leonard Mlodinow, in his excellent book, The Drunkard’s Walk, makes the following comment:
This example illustrates an important point: even with data significant at, say, the 3 percent level, if you test 100 nonpsychic people for psychic abilities […], you ought to expect a few people to show up as psychic.
In other words, if a phenomenon is random, you should typically see the “average” case regularly, but you should also see highly unlikely cases happen from time to time – observing such a rare occurrence doesn’t contradict the randomness of the phenomenon. Or, in the words of the French poet Mallarmé, Un Coup de Dés Jamais N’Abolira Le Hasard (A throw of the Dice will Never Abolish Chance).
In our last post, we saw how to use F# to read historical stock quotes from Yahoo. Today we’ll take the raw response, which is a big block of text, and break it up into a list of individual quotes.
Breaking up the response into lines
The function we wrote last time, GetResponse, receives one chunk of text from the web service, formatted like this:
Date,Open,High,Low,Close,Volume,Adj Close
2010-03-08,28.52,28.93,28.50,28.63,39414500,28.50
2010-03-05,28.66,28.68,28.42,28.59,56001800,28.46
2010-03-04,28.46,28.65,28.27,28.63,42890600,28.50
What we need to do now is break up this into individual lines of text, and parse them to read individual quotes. The first part is straightforward: the function BreakIntoLines calls String.Split(), using char(10), the code for line break, as a delimiter, and returns an Array of strings.
Note the type annotation on the function argument: without context, F# cannot infer the type of “response”, and we need to specify that this function expects a string argument.
Parsing valid lines into Quote records
The second part is a bit more complex. We need to break each line into 7 components (date, open, etc…), deal with lines that are not valid, like the header, and store the result in an appropriate structure.
We will store individual quotes into records. A Record is a data type somewhat similar to the C# struct. It has named fields, which makes it more expressive than Tuples, and is less involved than a class. Here is the declaration for our Quote record – concise, and pretty self-explanatory:
A client asked me recently a fun probability question, which revolved around figuring out the probability of success of a research program. In a simplified form, here is the problem: imagine that you have multiple labs, each developing products which have independent probabilities of succeeding – what is the probability of more than a certain number of products being eventually successful?
Let’s illustrate on a simple example. Product A has a 30% probability of success, and product B a 60% probability of success. Combining these into a probability tree, we work out that there is an 18% chance of having 2 products successful, 18% + 12 % + 42% = 72% chance of having 1 or more products succeed, and 28% chances of a total failure.
It’s not a very complicated theoretical problem. Practically, however, when the number of products increases, the number of outcomes becomes large, fairly fast – and working out every single combination by hand is extremely tedious. Fortunately, using a simple trick, we can generate these combinations with minimal effort. The representation of integers in base 2 is a decomposition in powers of 2, resulting in a unique sequence of 0 and 1. In our simplified example, if we consider the numbers 0, 1, 2 and 3, their decomposition is
0 = 0 x 2^2 + 0 x 2^1 –> 00
1 = 0 x 2^2 + 1 ^ 2^1 –> 01
2 = 1 x 2^2 + 0 x 2^1 –> 10
3 = 1 x 2^2 + 1 x 2^2 –> 11
As a result, if if consider a 1 to encode the success of a product, and a 0 its failure, the binary representation of integers from 0 to 3 gives us all possible outcomes for our two-products scenario.
Lately I have spent time on a pet project, which requires access to historical financial data. Mads Kristensen has a nice post where he shows how to read stock quotes from Yahoo finance using C#, which was very helpful to get started. I figured it would be interesting to try out a conversion to F# and see what the result looked like.
Mads focus is on getting quasi real-time updates of a quote; my interest is in an easier problem: retrieving historical data. Fortunately, Yahoo provides a free service for that, too. Given a quote symbol and two dates, it returns a comma-separated file list of all the values for the quote between these 2 dates.
So what do we need to do? Given a valid symbol and 2 dates, we want to create the WebRequest to send to Yahoo, retrieve the response, break it into lines, and parse each line into a quote, which will be added to a list. The core of the resulting program will be the ReadQuotes function, which will look like this:
A, B, C are the start month, day and year, the month being coded in base 0 (i.e. January is 0)
D, E, F are the end month, day and year, the month being coded in base 0 (i.e. January is 0)
For instance, replacing S with MSFT, A with 0, B with 1, C with 2010, D with 1, E with 15, F with 2010, will return all the available quotes for Microsoft between January 1 and February 15, 2010.
Let’s start by creating a Console application, by selecting new F# project > F# Application, and typing in the following code:
In my last post I explored how ExcelDNA can be used to write high-performance UDFs for Excel, calling .Net code without the overhead of VSTO. Using .Net instead of VBA for intensive computations already yields a nice improvement. Still, I regretted that ExcelDNA supports .Net up to 3.5 only, which puts the Task Parallel Library off limits – and is too bad because the TPL is just totally awesome to leverage the power of multi-cores.
This isn’t a pressing need of mine, so I thought I would leave that alone, and wait for the 4.0 version of ExcelDNA. Yeah right. Between my natural curiosity, Ross McLean’s comment (have fun at the Excel UK Dev Conference!), and the fact that I really want to know if I could get the Walkenbach test to run under 1 second, without too much of an effort, I had to check. And the good news is, yep, it works.
Last time we saw how to turn an average PC into a top-notch performer; let’s see how we can inject some parallelism to get a smoking hot calculation engine.
