ProjectEuler problem 1 in C, Groovy, Lisp, Perl, Python, and Ruby

Updated 2008-05-02: new Python implementation using sum() -- thanks Pete!

My blog post about the first problem in Project Euler went strange places. I was just trying to learn Python by solving a barely non-trivial problem. Maybe it was a full moon, not sure, but it wound up in a tangle of gcc, groovyc, and .elc. Happily, some good performance improvements were suggested and I've tried to incorporate them below.  

This is a really long post. Here's the skeleton:

1. Runtime environment
2. Results
3. Code (alphabetically by language)
   1. C
   2. Groovy
   3. Lisp
   4. Perl
   5. Python
   6. Ruby
4. Big O(rly)?
5. Wrap up
6. Extras

Runtime environment

• Machine: Powerbook Pro, 10.5.2, 2x 2.16 GHz Core 2 Duo
• Userspace programs: Finder, Terminal
• Battery conservation mode: Better Performance (plugged in)
• C: GCC 4.0.1 (Apple Inc. build 5465)
• Groovy: 1.5.5 JVM: 1.5.0_13-119
• Lisp: GNU Emacs 22.1.1
• Perl: v5.8.8, built for darwin-thread-multi-2level
• Python: 2.5.1
• Ruby: 1.8.6 (2007-09-24 patchlevel 111) [universal-darwin9.0]

Results

No cheesy graphs this time, just better organized numbers. Each row has one implementation of the problem. The 10**x columns show how many milliseconds it took the implementation to sum the multiples of three and five less than that number. Each implementation was run seven times for each column, and the average runtime is shown below. A test harness was written to execute the scripts automatically; I disabled the screensaver, started the tests, and went to bed.

Code

C

#include <stdio.h>
#include <math.h>

#define multiple_of(a, b) ((a == 0 || b == 0) ? 0 : a % b == 0)

int main(int argc, char** argv)
{
    int exp = atoi(argv[1]);
    double sum = 0;
    int i;

    for (i = 3; i < pow(10, exp); i++)
        if (multiple_of(i, 3) || multiple_of(i, 5))
            sum += i;

    printf("%0.0f\n", sum);

    return 0;
}

Groovy

// first.groovy
exp = Integer.parseInt(args[0])

mof = { val, test -> val && test && test % val == 0 }
mof3 = mof.curry(3)
mof5 = mof.curry(5)

sum = 0 as BigDecimal

(3..<(10**exp)).each {
    if (mof3(it) || mof5(it)) {
        sum += it
    }
}

println sum

// second.groovy
def exp = Integer.parseInt(args[0])

def mof = { val, test -> val && test && test % val == 0 }
def mof3 = mof.curry(3)
def mof5 = mof.curry(5)

def sum = 0 as BigInteger

(3..<(10**exp)).each {
    if (mof3(it) || mof5(it)) {
        sum += it
    }
}

println sum

// third.groovy
def exp = Integer.parseInt(args[0])

def sum = 0 as BigInteger

for (int i = 3; i < 10 ** exp; i++)
    if (i % 3 == 0 || i % 5 == 0)
        sum += i

println sum

Lisp

; first.el
(defun multiple_of (a b)
  (= 0 (% a b))
)

(defun val-to-add (val)
  (cond
   ((multiple_of val 3) val)
   ((multiple_of val 5) val)
   (0)
   )
  )

(defun sum-of-3or5-multiples (exp)
  (let ((num 3) (sum 0.0))
    (while (< num (expt 10 exp))
      (setq sum (+ sum (val-to-add num)))
      (setq num (1+ num))
      )
    sum
    )
  )

(sum-of-3or5-multiples 7)

Perl

#!/usr/bin/env perl -w
# first.pl
use strict;

my $exp = $ARGV[0];
my $sum = 0;

sub multiple_of {
    my ($val, $tgt) = @_;
    return $val % $tgt == 0;
}

for my $i (3 ... 10 ** $exp - 1) {
    if (multiple_of($i, 3) || multiple_of($i, 5)) {
        $sum += $i
    }
}

print "$sum\n"

#!/usr/bin/env perl -w
# second.pl

use strict;

my $exp = $ARGV[0];
my $sum = 0;

for my $i (3 ... 10 ** $exp - 1) {
    if ($i % 3 == 0 || $i % 5 == 0) {
        $sum += $i
    }
}

print "$sum\n"

Python

# first.py
import sys

def multiple_checker(val):
    return lambda test: test and val and test % val == 0

mof3 = multiple_checker(3)
mof5 = multiple_checker(5)

sum = 0

for i in range(10 ** int(sys.argv[1])):
    if mof3(i) or mof5(i):
        sum = sum + i

print sum

# second.py
import sys

exp = int(sys.argv[1])
sum = 0

for mof3or5 in set(range(3, 10**exp, 3)) | set(range(5, 10**exp, 5)):
    sum = sum + mof3or5

print sum

# third.py
import sys

exp = int(sys.argv[1])
sum = 0

for mof3or5 in set(xrange(3, 10**exp, 3)) | set(xrange(5, 10**exp, 5)):
    sum = sum + mof3or5

print sum

# fourth.py
import sys

exp = int(sys.argv[1])
total = sum(xrange(3, 10**exp, 3)) + sum(xrange(5, 10**exp, 5)) - sum(xrange(15, 10**exp, 15))

print total

Ruby

# first.rb
exp = ARGV[0].to_i
sum = 0

def is_mult(large, small)
  large % small == 0
end

for i in 3..(10 ** exp - 1)
  next unless is_mult(i, 3) or is_mult(i, 5)
  sum = sum + i
end

puts sum

# second.rb
exp = ARGV[0].to_i
sum = 0

for i in 3..(10 ** exp - 1)
  next unless i % 3 == 0 or i % 5 == 0
  sum = sum + i
end

puts sum

Big O(rly)?

Well... sigh... all of the code above works correctly but is slow and naïve. All of the approaches above take more time as the largest multiple increases. I was ignorantly, happily tweaking code down this road until fortunately Bob clued me in. The best approach takes the same amount of time as the largest multiple increases. Why? There's a simple equation for this, calculating an arithmetic series.  

# instant.rb
ceil = 10 ** ARGV[0].to_i - 1

def series_of_multiples(val, ceiling)
  diff = val
  vals = ceiling / val
  last_val = val + diff * (vals - 1)
  (val + last_val) / 2.0 * vals
end

def som(v, c) series_of_multiples(v, c).to_i end

puts som(3, ceil) + som(5, ceil) - som(15, ceil)

Wrap up

• I got a lot more out of this than a quick glance at Python. It was good to calculate a series or two, but much better to build a little test harness.
• Groovy performance tested out well here. I would avoid using some of its features in tight loops. I'm confident that Monsieur LaForge et son amis will optimize that concern away eventually.
• I thought I could love it, I really wanted to love it, it's loved by many for many good reasons, but Python started to chafe me. It's so hard to nail down exactly why... it's chock full of goodness, but just seems to need more Kool-Aid than Groovy and especially Ruby. Perl's Kool-Aid threshold is a well-known constant, at least until the Parrot changes things drastically.
• Cosine similarity + arithmetic series = it's good to work with a friendly, helpful PhD. in math. Thanks Bob :-)

Extras

The Python test harness. Probably needs tweaking for Wintel boxes.

import sys
import re
from datetime import timedelta, datetime
from os import system

#
# prefix used to run scripts. Trailing whitespace matters!
#
vms = { 
        'el':           'emacs --script ',
        'elc':          'emacs --script ',
        'groovy':       'groovy ',
        'out':          './',
        'pl':           'perl ',
        'py':           'python ',
        'rb':           'ruby '
        }

# Configurable parameters
# 
DEFAULT_MIN = 1
DEFAULT_MAX = 7
min = DEFAULT_MIN       # min "max" val = 10 ** min
max = DEFAULT_MAX       # max "max" val = 10 ** max
reps = 7                # times to repeat each test, then average the results


# Helper method
def td_to_ms(delta):
    val = delta.microseconds / 1000.0
    val = val + delta.seconds * 1000
    val = val + delta.days * 24 * 60 * 60 * 1000
    return val

#
# "main"
#
for script in sys.argv[1:]:
    ext = script.split('.').pop()
    if not ext in vms:
        print 'ignoring', script, 'unrecognized extension'
        continue

    vm = vms[ext]

    # the lisp files hardcode the max values :(
    if re.search('^el', ext):
        max = min
    else: # reset to defaults, needed when running multiple types of tests
        max = DEFAULT_MAX
        min = DEFAULT_MIN

    # gotta like list comprehensions
    runs = [0 for x in range(max - min + 1)]

    for rep in xrange(reps):
        for exp in xrange(min, max + 1):
            start = datetime.now()
            system('%s%s %s >/dev/null' % (vm, script, exp))
            end = datetime.now()
            runs[exp - min] = runs[exp - min] + td_to_ms(end - start)

    for i in xrange(len(runs)):
        runs[i] = int(runs[i] / reps)

    print script.split('/').pop(), runs

    # see, isn't it strange how python leaves you hanging at the end
    # of the last scope in the file?