ProjectEuler problem 1 in C, Groovy, Lisp, Perl, Python, and Ruby
By Seth Schroeder
Apr 29, 2008
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:
- Runtime environment
- Results
- Code (alphabetically by language)
- Big O(rly)?
- Wrap up
- 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 | 10**1 | 10**2 | 10**3 | 10**4 | 10**5 | 10**6 | 10**7 | Comments |
|---|---|---|---|---|---|---|---|---|
| first.c | 5 | 5 | 5 | 5 | 11 | 65 | 648 | |
| first.groovy | 928 | 929 | 1065 | 1643 | 2155 | 7998 | 52732 | |
| second.groovy | 920 | 1004 | 1189 | 1353 | 1806 | 3243 | 19620 | |
| third.groovy | 914 | 880 | 936 | 1181 | 1421 | 2545 | 12835 | |
| first.pl | 8 | 8 | 10 | 26 | 192 | 1886 | 18845 | |
| second.pl | 8 | 8 | 8 | 11 | 36 | 378 | 3062 | |
| first.py | 22 | 22 | 23 | 35 | 160 | 1506 | 14939 | |
| second.py | 147 | 22 | 21 | 24 | 53 | 422 | 4242 | |
| third.py | 22 | 22 | 22 | 24 | 51 | 405 | 4081 | |
| fourth.py | 21 | 22 | 21 | 22 | 26 | 156 | 1580 | Credit goes to Pete below |
| first.rb | 9 | 8 | 9 | 20 | 134 | 1420 | 14288 | |
| second.rb | 9 | 8 | 9 | 17 | 100 | 1075 | 10818 | |
| first.el | 20141 | 10^1...6 not available | ||||||
| second.el | 8172 | Actually first.elc | ||||||
| instant.rb | 8 | 8 | 8 | 8 | 8 | 8 | 8 |
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?