# Phillip Trelford's Array

## POKE 36879,255

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))
{
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
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 
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)

• #### pete w

11/30/2009 8:29:33 AM |

Very interesting indeed! I've been working in C++/C#/F#, and these comparisons are spot on with my experiences as well.
I am particularly surprised by the C#/C++ performance numbers.

• #### Frocka

11/30/2009 10:00:51 AM |

• #### Bryan O'Sullivan

11/30/2009 9:15:29 PM |

• #### Nigel Findlater

12/1/2009 12:59:30 AM |

Hallo,

We have just been looking into using intel compilers because they optimize the machine code to use features of the Intel procesor. We measured a 100 times improvment of speed over the MS C++ compiler. The code had a lot of floating point operations that the HPO compiler could easily vectorize, so I am not sure that you will get the same kind of speed up. But it's worth a go.

have fun...

• #### Frocka

12/1/2009 7:51:14 AM |

HELLO SIR WE ARE PATIENTLY WAITING FOR HASKELL TIME

• #### Don Stewart

12/1/2009 8:24:16 PM |

www.serpentine.com/.../

• #### Wamiduku

12/2/2009 5:07:52 AM |

I'm surprised to see that C++ and C# have the same execution time. Is that C++ compiled into native machine code, or is it managed .NET C++?

• #### Phil

12/3/2009 1:10:53 AM |

Thanks everybody for all the comments.

Haskell timing: Unfortunately Matt is away this week, so I'm afraid a reliable time for Haskell won't be till next week, but don't expect it to be any faster than the other languages.

C++ timing: the C++ was compile into native code, i.e. unmanaged. Remember that the C# and F# code is Just In Time (JIT) compiled to native code before execution.

• #### Eddie Freddie

2/1/2010 3:46:16 PM |

> HELLO SIR WE ARE PATIENTLY WAITING FOR HASKELL TIME

Be patient, it's still running..