Why isn't this running in constant space (and how do I make it so it does)?

Question

I'm doing Project Euler to learn Clojure.

The purpose of this function is to calculate the lcm of the set of integers from 1 to m.

(lcm 10) returns 2520

This is a rather brute-force way of doing this. In theory, we go through each number from m to infinity and return the first number for which all values 1 through m divide that number evenly.

If I understand what 'lazy' means correctly (and if I am truly being lazy here), then this should run in constant space. There's no need to hold more than the list of numbers from 1 to m and 1 value from the infinite set of numbers that we're looping through.

I am, however, getting a java.lang.OutOfMemoryError: Java heap space at m values greater than 17.

 (defn lcm [m]
  (let [xs (range 1 (+ m 1))]
  (first (for [x (iterate inc m) :when 
          (empty? 
              (filter (fn [y] (not (factor-of? y x))) xs))] x))))

Thanks!

Answer 1

While I accept that this is acknowledged to be brute force, I shiver at the idea. For the set of consecutive numbers that runs up to 50, the lcm is 3099044504245996706400. Do you really want a loop that tests every number up to that point to identify the lcm of the set?

Other schemes would seem far better. For example, factor each member of the sequence, then simply count the maximum number of occurrences of each prime factor. Or, build a simple prime sieve, that simultaneously factors the set of numbers, while allowing you to count factor multiplicities.

These schemes can be written to be highly efficient. Or you can use brute force. The latter seems silly here.

Answer 2

As far as I can tell, your code is in fact lazy (also in the sense that it's in no hurry to reach the answer... ;-) -- see below), however it generates piles upon piles upon piles of garbage. Just consider that (lvm 17) amounts to asking for over 1.2 million lazy filtering operations on (range 1 18). I can't reproduce your out-of-memory problem, but I'd tentatively conjecture it might be an issue with your memory & GC settings.

Now although I realise that your question is not actually about algorithms, note that the production of all that garbage, the carrying out of all those filtering operations etc. not only utterly destroy the space complexity of this, but the time complexity as well. Why not use an actual LCM algorithm? Like the one exploiting lcm(X) = gcd(X) / product(X) for X a set of natural numbers. The GCD can be calculated with Euclid's algorithm.

(defn gcd
  ([x y]
     (cond (zero? x) y
           (< y x)   (recur y x)
           :else     (recur x (rem y x))))
  ([x y & zs]
     (reduce gcd (gcd x y) zs)))

(defn lcm
  ([x y] (/ (* x y) (gcd x y)))
  ([x y & zs]
     (reduce lcm (lcm x y) zs)))

With the above in place, (apply lcm (range 1 18)) will give you your answer in short order.

Answer 3

Michal is correct about the problem. A sieve will be a little bit faster, since no gcd calculations are needed:

EDIT: This code is actually horribly wrong. I've left it here to remind myself to check my work twice if I have such a hangover.

(ns euler (:use clojure.contrib.math))

(defn sieve 
  ([m] (sieve m (vec (repeat (+ 1 m) true)) 2))
  ([m sieve-vector factor] 
       (if (< factor m) 
       (if (sieve-vector factor)
           (recur m 
              (reduce #(assoc %1 %2 false)
                  sieve-vector
                  (range (* 2 factor) (+ 1 m) factor))
              (inc factor))
           (recur m sieve-vector (inc factor)))
       sieve-vector)))

(defn primes [m] (map key (filter val (seq (zipmap (range 2 m) (subvec (sieve m)  2))))))

(defn prime-Powers-LCM [m] (zipmap (primes m) (map #(quot m %) (primes m))))

(defn LCM [m] (reduce #(* %1 (expt (key %2) (val %2))) 1 (seq (prime-Powers-LCM m))))

Answer 4

I'm getting the same OutOfMemoryError on Clojure 1.1, but not on 1.2.

I imagine it's a bug in 1.1 where for holds on to more garbage than necessary.

So I suppose the fix is to upgrade Clojure. Or to use Michal's algorithm for an answer in a fraction of the time.