Problem 10 states: "Find the sum of all primes less than 2,000,000".

After finding out that it's only necessary to check for divisors less than the square root of the number, I blatantly stole this version from the Haskell Wiki:

If this doesn't give you a nerdgasm, I don't know what will. It creates an infinite list of primes by filtering an infinite list of odd numbers with the isPrime function. This function, in turn, uses the primes list itself to look for potential divisors. So basically, the list is defined recursively.

The solution then boils down to getting all primes smaller than two million from the infinite list, summing them and outputting the result.

Anyway, this beautiful solution got me wondering how the perl version would look. Here is my first attempt:

Ugh. I mean, it's not

*that*bad, it has some interesting things going on like having an infinite stream of primes, but after being embelished by the Haskell version, this seems uninspired at best.

But then I thought that being CPAN (and not syntax) Perl's strength, I should take a look there. After no more than 30 seconds of searching, I found Math::Primality. Look how the Perl 5 version looks now:

This put a smile on my face. Perl may not be the most beautiful language around, but it has a JFDI attitude that I have yet to find elsewhere.

Is there a speed difference?

ReplyDeleteall The images are broken :-(

ReplyDeleteah, nm, github's back. (Another reason why gists are annoying :-)

ReplyDeleteWith J:

ReplyDelete+/x:p:i._1 p:2000000

I win. What was the point anyway?

(See http://www.reddit.com/r/programming/comments/a7rey/baby_haskell_and_good_old_perl/c0g8lri too.)

If I understand it right the Haskell version uses primes recursively in it's own definition (and thus speeding the scanning a bit). If you want to make it interesting - add that to the Perl version :)

ReplyDelete@frew: the haskell version (compiled without any flags) runs in little over 2 secs, while both the Perl versions run in ~ 40 secs on my laptop. However, as zby++ noted, the comparison is not exactly fair since the priming algorithm in my Perl version doesn't use previously calculated primes to search for possible factors, it just scans the whole list (it doesn't even filter out odd numbers).

ReplyDelete@lasts: That's cool, I've heard nice things about J.

ReplyDeleteAnd it isn't a contest, so sorry, I don't have a price for you.

The point of the blogpost (if there is a point) was to just show why, despite some warts that Perl might have, it's still current thanks to the community behind it (CPAN being a product of that).

*prize

ReplyDeleteprimes = 2 : filter isPrime [3,5..]

ReplyDeleteisPrime n = not . any (`isDiv` n) . takeWhile (\x -> x^2 <= n) $ primes

isDiv a b = b ` | mod` a == 0

context: http://r6.ca/blog/20081116T213644Z.html

Oops, typo, the last line is:

ReplyDeleteisDiv a b = b `mod` a == 0

nubBy divides [2..]

ReplyDeletewhere divides x y = x `mod` y == 0

Your comment box is really broken on Firefox. On two different machines I can't paste or even use the arrow keys.

ReplyDelete#!/usr/bin/env perl

ReplyDelete#

# revised.pl

#

# if doing this with just core Perl, here is

# a more elegant program and it's faster

#

# apologies for lack of decent indentation in

# the final comment

use Modern::Perl;

use List::Util qw/sum first/;

my $limit = shift @ARGV;

my @primes;

sub check_prime {

my $n = shift;

return if $n <= 1;

for my $p ( @primes ) {

last if $p**2 > $n;

return if ! ( $n % $p );

}

push @primes, $n;

}

check_prime($_) for 2 .. $limit;

say sum @primes;

__END__

$ time perl original.pl 2000000

142913828922

real 0m47.097s

user 0m45.820s

sys 0m0.190s

$ time perl revised.pl 2000000

142913828922

real 0m11.704s

user 0m11.600s

sys 0m0.060s

@dagolden: I like your version a lot! It actually uses the same algorithm that the haskell version, and it's pretty clear and concise.

ReplyDeleteSo the Haskell version runs in 2.5 seconds, and yours in 10.5 (on my laptop). Not too bad for a dynamic language, eh?

It's a bit of a cheat, since first() and sum() are implemented in XS/C. Still dynamic, but avoids some extra overhead. And it's not quite the Haskell algorithm, since it's not a stream, which would add more overhead. But for the task, it suffices.

ReplyDeleteHi Zeroth Order! I should note that I posted a follow-up to your post on my blog. I'll be happy to hear any comments.

ReplyDelete