Feeds:
Posts
Comments

Posts Tagged ‘loops’

Loops in Ocaml

Following on from my look at basic looping syntax in various languages I thought I’d take a look at various methods of looping in Ocaml to make amends for the Ocaml solution.

gcd is the same as in the previous post.

let rec gcd a b =
  if b = 0 then a
  else gcd b (a mod b);;

Using one function for one loop is nicer than cramming both into one which felt too much like coding using if and goto.

Most of the solutions use the following recursive function.

let count_for_denom denom =
  let rec loop num count =
    if num >= (denom/2+1) then count
    else loop (num+1) (count + if gcd num denom = 1 then 1 else 0)
  in
    loop (denom/3+1) 0;;

The first solution is a pure recursive function. This is really just mental masturbation – needlessly exchanging loops for more verbose recursion.

let solve_it max_denom =
  let rec loop denom count =
    if denom > max_denom then count
    else loop (denom+1) count+count_for_denom denom
  in
    loop 5 0;;

Printf.printf "%d solutions\n" (solve_it 10000);;

$ time ./a.out
XXX solutions

real    0m1.138s
user    0m1.108s
sys     0m0.000s

Functional programming includes a bunch of higher level functions such as map and fold. In a strict language it would be wasteful to construct a list before iterating over it with one of these higher-order functions.

How about a fold-like function that folds over a range of numbers?

let collector s e acc f =
  let rec loop s acc =
    if s > e then acc
    else loop (s+1) (f acc s)
  in loop s acc;;

Printf.printf "%d solutions\n"
  (collector 5 1000 0 (fun acc denom -> acc+count_for_denom denom));;

Here is one with a reference and a for next loop. I think this is quite nice – I like that Ocaml is a pragmatic language and includes this kind of stuff.

let count = ref 0 in
  for i = 5 to 1000 do
    count := !count + count_for_denom i
  done;
  Printf.printf "%d solutions\n" !count;;

And finally the pure nested for loop solution which is about 20% faster than the recursive versions.

let count = ref 0 in
  for i = 5 to 10000 do
    for j = (i/3+1) to (i/2) do
      if gcd i j == 1 then count := !count + 1
    done
  done;
  Printf.printf "%d solutions\n" !count;;

$ time ./a.out
XXX solutions

real    0m0.934s
user    0m0.928s
sys     0m0.004s

So, is there anything I missed? What other types of loops are there in Ocaml?

Read Full Post »

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 »

Follow

Get every new post delivered to your Inbox.