Okay, this post is going to be quite long. I’m going to start with a basic problem I was solving in emacs lisp. From there I’ll segue into thinking about looping syntax and finally I’ll do a bit of benchmarking as I’ve got the code already and people seem to like that (the scheme, ocaml, c++ speed comparison is by far the most popular post on this blog followed by this).

Futzing around with Project Euler is something I do for fun. Most recently I was looking at problem 73 – count the reduced proper fractions with a denominator less than or equal to 10,000 between 1/3 and 1/2.

### Emacs Lisp Solution

Emacs Lisp is usually my default language for doing this kind of thing as I’m already in my text editor and there is a REPL to experiment with.

First of all, it is clear that I’m going to need a function to calculate the greatest common divisor. I found an imperative Pascal implementation of Euclid’s algorithm here. A brief aside – I searched for Pascal deliberately as I generally find it very clear. Does anyone else do that?

(defun gcd (a b)
(while (not (= b 0))
(let ((tmp b))
(setq b (% a b))
(setq a tmp)))
a)

Thinking ahead, I’ll probably know what the gcd is before we call make-fraction as only fractions with a gcd of 1 will be actually counted amongst the solutions. I’ve therefore made gcd an optional parameter as a nod to efficiency.

(defsubst make-fraction (num denom &optional gcd)
(unless gcd (setq gcd (gcd num denom)))
(cons (/ num gcd) (/ denom gcd)))

I like the flexibility that lisp-like languages give you to name your functions too.

(defsubst more-than-1/3 (frac)
(let ((num (car frac))
(denom (cdr frac)))
(> (* num 3) denom)))
(defsubst less-than-1/2 (frac)
(let ((num (car frac))
(denom (cdr frac)))
(< (* num 2) denom)))
(defsubst within-range (frac)
(and (more-than-1/3 frac) (less-than-1/2 frac)))

We only check fractions between 1/3 and 1/2 as to do all fractions with a denominator <= 10,000 would take far too long.

(defun solve-it (max-denom)
(insert (format-time-string "\n\nStarted at: %H:%M:%S\n\n"))
(let (num denom frac max gcd solutions)
(setq solutions 0)
(setq denom 2)
(while (<= denom max-denom)
(setq num (/ denom 3))
(setq max (1+ (/ denom 2)))
(while (<= num max)
(setq gcd (gcd num denom))
(when (= gcd 1)
(setq frac (make-fraction num denom gcd))
(when (within-range frac)
;; (insert (format "%s\n" frac))
(incf solutions)))
(incf num))
(incf denom)
(when (= (% denom 50) 0)
(insert (format "Denom: %d Solutions: %d\n" denom solutions)))
(sit-for 0))
(insert (format "\n%d solutions\n" solutions))
(insert (format-time-string "Finished at: %H:%M:%S\n"))))

After I wrote this, I realised I didn’t need to construct and destruct my fraction type so simplified to the following:

(defun solve-it (max-denom)
(insert (format-time-string "\n\nStarted at: %H:%M:%S\n"))
(let (num denom frac max solutions)
(setq solutions 0)
(setq denom 5)
(while (<= denom max-denom)
(setq num (1+ (/ denom 3)))
(setq max (/ denom 2))
(while (<= num max)
(when (= (gcd num denom) 1)
(incf solutions))
(incf num))
(incf denom))
(insert (format "%d solutions\n" solutions))
(insert (format-time-string "Finished at: %H:%M:%S\n"))))
(solve-it 10000)
;; Started at: 22:14:35
;; 5066251 solutions
;; Finished at: 22:15:45

70 seconds. Okay.

The most annoying thing is the primitive looping constructs. `while`

is the basic and obvious built-in. It also has a slew of macros beginning with `doXXX`

including `dotimes`

and `dolist`

not to mention the mighty common lisp `loop`

macro.

I don’t know loop (but I’m going to learn it), but after messing about with `do*`

for a few minutes, I realised it wasn’t the looping construct for me.

(do* ((i 5 (if (> j 10) (+ i 1) i))
(j (+ i 1) (if (> j 10) (+ i 1) (+ j 1))))
((> i 10))
(insert (format "[%d %d]" i j)))

**Yuck.**

Now, the great thing about lisp is supposed to be that if you don’t like the syntax you can add your own with macros. Unfortunately, I haven’t got around to that yet as a bunch of people have already designed most of the syntax I like.

### Scheme Solution

When I read some of the earlier posts on this blog, it seems that *scheme* has got some nice generator syntax (aka eager comprehensions) for handling nested loops.

There are a nice set of posts on eager comprehensions here.

I took `print-ln`

from the portable scheme post and `gcd`

from SICP.

#lang scheme/base
(require srfi/42)
(define (print-ln . args)
(for-each display args)
(newline)
(flush-output))
(define (gcd a b)
(if (= b 0) a
(gcd b (remainder a b))))
(define (solve-it max-denom)
(sum-ec (:range denom 2 (+ max-denom 1))
(:range num (+ (floor (/ denom 3)) 1) (ceiling (/ denom 2)))
(if (= (gcd num denom) 1) 1 0)))
(print-ln "There are " (solve-it 10000) " solutions")

Yikes, mzscheme is much quicker than emacs-lisp. That surprised me. A factor of 10 I would have expected, a factor of 50 not so much.

$ time mzscheme frac.scm
There are XXX solutions
real 0m1.413s
user 0m1.404s
sys 0m0.004s

### Perl Solution

use strict;
use warnings;
use POSIX qw(floor ceil);
sub gcd
{
my ($n1, $n2) = @_;
until ($n2 == 0) {
my $tmp = $n2;
$n2 = $n1 % $n2;
$n1 = $tmp;
}
return $n1;
}

The nested loop actually looks okay to me in perl although not as nice as the srfi-42 eager comprehensions.

sub solve_it
{
my $max_denom = $_[0];
my $solutions = 0;
foreach my $denom (5..$max_denom) {
my $max = ceil($denom / 2) - 1;
foreach my $num ((1 + floor($denom / 3))..$max) {
if (gcd($num, $denom) == 1) {
++$solutions;
}
}
}
return $solutions;
}
printf "There are %d solutions\n", solve_it(10000);

The performance of my perl is pretty bad too.

$ time perl frac.pl
There are XXX solutions
real 0m47.026s
user 0m46.963s
sys 0m0.008s

### Ocaml Solution

let rec gcd a b =
if b = 0 then a
else gcd b (a mod b);;
let solve_it max_denom =
let rec loop num denom solutions =
if denom > max_denom then solutions
else if num >= (denom/2+1) then
loop ((denom+1)/3+1) (denom+1) solutions
else begin
if gcd num denom = 1 then begin
(* Printf.printf "%d/%d\n" num denom; *)
loop (num+1) denom (solutions+1)
end else
loop (num+1) denom solutions
end
in
loop ((5/3)+1) 5 0;;
Printf.printf "There are %d solutions\n" (solve_it 1000);;

Oh dear, I seem to have an awful accent when programming ocaml. I’ll need to work on that.

$ time ./a.out
There are XXX solutions
real 0m1.071s
user 0m1.060s
sys 0m0.004s

### So, Conclusions

For this particular task (looping and integer math) Emacs Lisp is slow, but not that slow compared with another scripting language. I really like the scheme looping constructs and mzscheme is surprisingly quick (again, just for this tiny thing), not too far from the ocaml – although again I should emphasise that the ocaml is a terrible hack. And finally, I need to learn how to use `loop`

properly.

All comments welcome.

Read Full Post »