Feeds:
Posts

## Looping Syntax in Various Languages

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 = \$_;
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.

### 11 Responses

1. on May 28, 2009 at 15:24 trimtab

For 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.

2. on May 28, 2009 at 15:41 Porges

```main = print solve

solve::Int
solve = sum [1|
denom <- [5..10000::Int],
num <- [1+floor(fromIntegral denom/3)..ceiling(fromIntegral denom/2)-1],
gcd num denom == 1]
```

3. on May 28, 2009 at 19:35 Jisang Yoo

What 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?

4. on May 28, 2009 at 20:26 Jared

@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.

5. on May 28, 2009 at 22:16 Jonathan Creekmore

Compiling 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.

6. on May 29, 2009 at 08:13 Jared

Wow, 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.

7. on May 29, 2009 at 11:22 stuart

I 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?

8. on May 29, 2009 at 22:38 Jared

Hi 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.

9. on June 3, 2009 at 15:14 Liang

I profile perl version. Three statements in until block in gcd function take most of time.

10. on June 4, 2009 at 21:52 Jared

Hi 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.

11. on February 19, 2014 at 12:12 Andrew Phillips

Your perl version will likely run faster if you move the variable declarations (my \$max, my \$tmp) out of the loops.