Yesterday a colleague asked me how a function to calculate the nth left-truncatable prime might look in F# for comparison against a C++ implementation, so lets start with the definition from Wikipedia:

In number theory, a

left-truncatable primeis a prime number which, in a given base, contains no 0, and if the leading ("left") digit is successively removed, then all resulting numbers are prime. For example 9137, since 9137, 137, 37 and 7 are all prime. Decimal representation is often assumed and always used in this article.

The following is the F# implementation, using recursion, coded up on the train home last night (the function takes about 5ms to calculate the 1000th left-truncatable prime, just 2ms off very close to the optimized C++ time):

let IsPrime n = if n = 1 then false else let max = n |> float |> sqrt |> int let rec Test = function | x when x > max -> true | x -> if (n % x) = 0 then false else Test (x+1) Test 2 let NthLeftTruncatedPrime index = let rec Find digit factor primes primes' count acc = match digit, primes' with | 10, _ -> let primes = List.rev acc Find 1 (10*factor) primes primes count [] | _, [] -> Find (digit+1) factor primes primes count acc | _, prime::tail -> let k = (digit * factor) + prime let count, acc = if IsPrime k then count+1, k::acc else count, acc if count = index then k else Find digit factor primes tail count acc let primes = [2;3;5;7] if index <= 4 then List.nth primes (index-1) else Find 1 10 primes primes 4 []

Initially the comparison was intended to be simply on readability, where the F# code was unsurprisingly found to be shorter, and the imperative style (lots of for loops) of the C++ code more familiar to some.

Just out of curiosity I ran a quick performance check to see whether performance was in the same order of magnitude, fully expecting the C++ to faster. In fact initially the C++ was half the speed of the F# code (i.e. the C++ took twice as long). After a little head scratching, I tried a few teaks on the C++, for example giving the STL vector an initial capacity which increased performance by about 20%. Then I spotted that the C++ was using Int64 underneath and the F# Int32. Making the C++ use Int32 brought comparable performance to the F# code give or take a millisecond. At no point did I bother trying to optimize the F# code (except for running the function once before doing the timing to ensure the code had been just-in-time (JIT) compiled).

At the time of first posting this entry it was thought that the C++ was a couple of milliseconds faster. Actually later in the day it was found that there was an error in the calculation of the C++ result and in fact there was no discernable difference between the performance of the C++ and F# code. There are further algorithmic optimizations that could be applied to both implementations but I will leave that as an exercise for the reader.

This is quite interesting, it really does show that you can *NOT* assume that writing code in unmanaged C++ will intrinsically make it faster than code written in managed languages like C# and F#.