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 prime is 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#.