Phillip Trelford's Array

POKE 36879,255

C++ vs C# vs F# vs Haskell

Since I first posted an F# solution to Left-Truncatable Primes, C# and Haskell have entered the frame, and although this is not a good problem for a serious comparison of languages, I think it is still interesting.

So lets start at the beginning, Dominic Penfold initially posed the problem and gave an efficient algorithm implemented in C++ (39 lines):

bool IsPrime(int num)
{
    int sqrt = 1 + sqrtf(num);
    for (int i=2; i<sqrt; i++)
    {
        if (num % i == 0)
            return false;
    }
    return true;
}
 
int NthLeftTruncatablePrime(int target)
{
    std::vector<int> PrimeRoots;
    PrimeRoots.push_back(2);
    PrimeRoots.push_back(3);
    PrimeRoots.push_back(5);
    PrimeRoots.push_back(7);
    int start = 0;
    int tens = 10;    
    while(true)
    {
        int end = PrimeRoots.size();
        for (int i=1; i<10; i++)
        {
            for (int pos = start; pos< end; pos++)
            {
                int newprime = tens * i + PrimeRoots[pos];
                if (IsPrime(newprime))
                {
                    PrimeRoots.push_back(newprime);
                    if (PrimeRoots.size()==target)                                      
                        return newprime;                    
                }
            }
        }
        start = end;
        tens *= 10;
    }
}

 

Performance was considerably faster when 32-bit integers were switched for 64-bit integers.

The C++ code is very easily converted into C# (35 lines):

static bool IsPrime(int num)
{
    int sqrt = 1 + (int ) System.Math.Sqrt(num);
    blue">for (int i = 2; i < sqrt; i++)
    {
        if (num % i == 0)
            return false;
    }
    return true;
}

static int NthLeftTruncatedPrime(int target)
{
    var primeRoots = new List<int>() { 2, 3, 5, 7};               
    int start = 0;
    int tens = 10;
    while (true)
    {
        int end = primeRoots.Count;
        for (int i = 1; i < 10; i++)
        {
            for (int pos = start; pos < end; pos++)
            {
                int newprime = tens * i + primeRoots[pos];
                if (IsPrime(newprime))
                {
                    primeRoots.Add(newprime);
                    if (primeRoots.Count == target)
                        return newprime;
                }
            }
        }
        start = end;
        tens *= 10;
    }
}

 

Conversion to F# is only slightly trickier as there is no equivalent return statement, but similar behavior can be accomplished using yield (30 lines):

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 NthLeftTruncatablePrime n =
    let oneDigitPrimes = [2;3;5;7]          
    seq {            
        let primes = ref oneDigitPrimes        
        for tens = 1 to 8 do
            let acc = ref []
            for i=1 to 9 do 
                let newPrime = i * pown 10 tens                
                let primes' = ref !primes
                while (!primes').Length > 0 do                            
                    let x = newPrime+(!primes').Head
                    if IsPrime x then 
                        acc := x :: !acc
                        yield x
                    primes' := (!primes').Tail                    
                done                                     
            done         
            primes := !acc |> List.rev    
        done            
    }
    |> Seq.append oneDigitPrimes
    |> Seq.nth (n-1)

 

The extra overhead of generating a sequence can be avoided using instead recursion (25 lines including IsPrime function):

let NthLeftTruncatablePrime 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 []

 

Later Matt Curran (coincidentally another ex-games developer) got in on the act with a Haskell version (17 lines including a comment – although the lines are a little dense):

isPrime :: Int -> Bool
isPrime 1 = False
isPrime x = null $ take 1 [n | n <- [2..upperBound x], 0 == mod x n]
    where
        upperBound = floor . sqrt . fromIntegral

-- list of all left truncatable primes
ltps :: [Int]
ltps = ps 1 [0]
    where
        ps _ []      = []
        ps m prevMag = thisMag ++ (ps (m*10) thisMag)
            where
                thisMag = primes [x*m | x <- [1..9]] prevMag
                    where
                        primes [] _ = []
                        primes (m:mgs) bases = 
                            (filter isPrime [m+x | x <- bases]) ++ (primes mgs bases)

 

Results Breakdown by language

Language Lines of code Performance(ms)
C++ 39 5.213
C# 35 5.332
F# sequence 30 14.075
F# recursive 25 5.412
Haskell 17 ?

Note: the time is to generate the 1000th prime, and the same computer was used for all tests, as was release mode. Haskell time coming soon.

LeftTruncatablePrime.cpp (1.45 kb)

LeftTruncatablePrime.cs (1.58 kb)

LeftTruncatablePrime_seq.fs (1.53 kb)

LeftTruncatablePrime_rec.fs (1.36 kb)

This article has been translated to Serbo-Croatian language by WHGeeks .

Left-Truncatable Primes

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

F# Rational64 implementation

The F# Power Pack includes an arbitrarily large Rational type called BigNum, which in turn uses the arbitrarily large BigInt type for the numerator and denominator. The BigInteger type has recently moved into .Net 4.0 under the System.Numerics namespace, It would be nice if BigNum could join it there.

What if you want a fixed size Rational implementation that can be used from any .Net language? The following is a sample F# implementation using Int64 for the numerator and denominator values:

open System

type Rational64 (numerator:Int64,denominator:Int64) =
    do if denominator = 0L && numerator <> 0L then
        raise (new DivideByZeroException())
    let rec gcd x y =    
        match y with
        | 0L -> x
        | _ -> gcd y (x % y)
    let norm =
        let u = int64 (sign denominator) * numerator
        let v = abs denominator     
        let d = gcd (abs u) v     
        if denominator <> 0L then u / d, v / d
        else numerator, denominator
    let numerator, denominator = norm    
    static let zero = Rational64(0L,1L)
    static let Op f (a:Rational64,b:Rational64) = 
        let x,y = a.Numerator, a.Denominator
        let u,v = b.Numerator, b.Denominator
        f x y u v
    static let Add = Op (fun x y u v -> new Rational64(x * v + u * y, y * v))
    static let Sub = Op (fun x y u v -> new Rational64(x * v - u * y, y * v))
    static let Mul = Op (fun x y u v -> new Rational64(x * u, y * v))
    static let Div = Op (fun x y u v -> new Rational64(x * v, y * u))        
    static let Eq = Op (fun x y u v -> x * v = u * y)
    static let Lt = Op (fun x y u v -> x * v < u * y)
    static let Le = Op (fun x y u v -> x * v <= u * y)
    static let Gt = Op (fun x y u v -> x * v > u * y)
    static let Ge = Op (fun x y u v -> x * v >= u * y)
    static let Compare (a:Rational64,b:Rational64) =
        if Lt (a,b) then -1
        else if Gt (a,b) then 1
        else 0
    new(numerator:Int64) = Rational64(numerator,1L)                  
    member this.Numerator = numerator 
    member this.Denominator = denominator
    static member Zero = zero
    member this.ToDecimal() =
        decimal this.Numerator / decimal this.Denominator
    member this.ToDouble() =
        double this.Numerator / double this.Denominator
    override this.ToString() =
        match numerator, denominator with
        | n, 1L -> n.ToString()
        | n, d -> sprintf "%d/%d" n d                             
    static member ( + ) (a,b) = Add (a,b)
    static member ( - ) (a,b) = Sub (a,b)
    static member ( * ) (a,b) = Mul (a,b)
    static member ( / ) (a,b) = Div (a,b)
    static member op_Equality (a,b) = Eq (a,b)
    static member op_Inequality (a,b) = not (Eq (a,b))
    static member op_LessThan (a,b) = Lt (a,b)
    static member op_LessThanOrEqual (a,b) = Le (a,b)
    static member op_GreaterThan (a,b) = Gt (a,b)
    static member op_GreaterThanOrEqual (a,b) = Ge (a,b)
    interface IComparable with
        member this.CompareTo (x) = Compare (this, x :?> Rational64)                 
    static member Equals(a,b) = Eq(a,b)
    override this.Equals x = this = (x :?> Rational64) 

 

Finally specific for F# by implementing a NumericLiteralX module it is possible to declare Rational64 literals like so (Q for Quotient):

module NumericLiteralQ =
    let FromZero () = Rational64(0L)
    let FromOne () = Rational64(1L)
    let FromInt32 (x) = Rational64(int64 x) 
    let FromInt64 (x:Int64) = Rational64(x) 

module Test = 
    let x = 42Q

 

Rational64.fs (4.90 kb)

Rational64Test.cs (4.74 kb)