Programming Praxis – Emirps

In today’s Programming Praxis, our task is to enumerate all the non-palindrome prime numbers that are still prime when their digits are reversed. Let’s get started, shall we?

Since we are to focus on maximum speed, the obvious choice is to use a library.

import Data.Numbers.Primes

I tried a couple different versions, and settled on a simple filter. This version can calculate all the emirps under one million in about 650 ms. One other version where the isPrime test was replaced by first putting all the primes in a Set and doing membership testing was a fraction faster (about 10 ms), but it is about twice as long and requires specifying the maximum up front, which is less convenient then the current infinite stream. I also tried to make it faster via parallelism, but I could only get it to go slower, so it looks like the benefits of doing everything in parallel don’t weigh up against the additional overhead. Or maybe I’m just not using the library right.

emirps :: [Integer]
emirps = [p | p <- primes, let rev = reverse (show p)
            , isPrime (read rev), show p /= rev]

All that’s left is to print all the emirps under a million.

main :: IO ()
main = print $ takeWhile (< 1000000) emirps

As mentioned, just evaluating the list takes about 650 ms, which is about the same as the Scheme version.

About these ads

Tags: , , , , , , ,

3 Responses to “Programming Praxis – Emirps”

  1. Grégory LEOCADIE Says:

    Hi,
    You use the Data.Numbers.Primes package, but if you did your own prime numbers generation, would the bench be horrible ?

    ++ greg

  2. Remco Niemeijer Says:

    That would depend on the algorithm used. Obviously a naive algorithm, like the one I used in the previous exercise, is going to be pretty slow. I tried using the basic wheel factorization method from http://bonsaicode.wordpress.com/2009/05/08/programming-praxis-%E2%80%93-wheel-factorization/ (Data.Numbers.Primes also relies on wheel factorization, albeit a more complex version) and it calculates the whole list in about 1.5 seconds. That’s on a different computer than the original solution though, so the two aren’t directly comparable. Still, it’s not too far off and that’s with an algorithm that hasn’t exactly been optimized for speed (for instance, my primes function was simply 2 : filter isPrime [3,5..]). So the short answer is no, it wouldn’t be a whole lot worse. But why bother reinventing the wheel (factorization)? :)

  3. Grégory LEOCADIE Says:

    I was looking for comments/tips about an efficient implementation of the prime numbers generation, and you answered it well.
    And I agree, no need to reinvent the wheel :D (good one ;))
    Thanks again
    Greg

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: