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.