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.

on May 28, 2009 at 15:24trimtabFor Common Lisp, you might be interested in the Iterate package in lieu of Loop.

http://common-lisp.net/project/iterate/

More expressive, extensible, and Lispy! There are others still (e.g. Series), but Iterate seems to be the most powerful.

on May 28, 2009 at 15:41PorgesA direct translation of your algorithm into Haskell yields:

on May 28, 2009 at 19:35Jisang YooWhat does (sit-for 0) do in the first solve-it defun? Accoding to its describe-function, it redisplays. But why redisplay in the middle of the loop?

on May 28, 2009 at 20:26Jared@trimtab – iterate looks nice, but I’m looking for a looping mechanism to improve my emacs coding. I just thought I’d do a quick comparison with looping in other languages while I was messing around.

@Porges – thanks for that – it looks similar in spirit (if a bit different in syntax) to the scheme. How long does it take to run on your machine?

@Jisang – sit-for does redisplay as the manual says. If I don’t add it then the screen does not redraw until the loop has finished executing, which took around 5 minutes in my first effort. I added the sit-for so I could check on the progress.

Thanks for the comments.

on May 28, 2009 at 22:16Jonathan CreekmoreCompiling your solve-it function with compile-defun sped up Emacs-Lisp for me a lot. The uncompiled version of solve-it completed in 56 seconds for me. After compiling it, the time shrank to 9 seconds. That is closer to your expected MzScheme time and I believe that MzScheme will byte-compile things behind the scenes for you.

on May 29, 2009 at 08:13JaredWow, byte-compiling made a big difference.

(This is a different machine than my other tests).

before:

Started at: 08:07:17

XXX solutions

Finished at: 08:08:39

After:

Started at: 08:10:54

XXX solutions

Finished at: 08:11:11

And yes, I think that mzscheme has a JIT. However, I’m still surprised that it beats Perl by so much.

on May 29, 2009 at 11:22stuartI don’t understand why you are comparing emacs lisp to scheme. I would not have considered emacs lisp a fast implementation of lisp. Wouldn’t it make more sense to compare sbcl (or clisp or clozure or even Clojure) with scheme?or emacs lisp with a common lisp implementation?

on May 29, 2009 at 22:38JaredHi Stuart,

Basically the process was the following:

1. I implemented my solution in emacs lisp using (while …) and (setq …)

I didn’t like it so I had a look at looping in other languages.

2. I liked the look of eager comprehensions so I tried those and I’m possibly interested in learning Ocaml so I tried that. I added the Perl as a reference.

3. I added the benchmarks as I thought other people might be interested (and it looks like I was right – it has had the third most number of visitors in the last 30 days and its only been 2 days). I don’t really care that much.

I guess what came across most strongly was the benchmarking, but what I was most interested in was the various syntaxes for looping.

Hopefully that makes sense.

on June 3, 2009 at 15:14LiangI profile perl version. Three statements in until block in gcd function take most of time.

on June 4, 2009 at 21:52JaredHi Liang,

That makes sense as the gcd is the only piece that actually does any work (although obviously it is best to measure to be sure – thanks!). The other part is just iterating around some loops.

on February 19, 2014 at 12:12Andrew PhillipsYour perl version will likely run faster if you move the variable declarations (my $max, my $tmp) out of the loops.