Lazy sequence or repetition for a mathematical function of power?

Question

As an exercise, I implemented a mathematical power function. After using recur:

(defn power [an] (let [multiply (fn [x factor i] (if (zero? i) x (recur (* x factor) factor (dec i))))] (multiply aa (dec n)))) user=> (time (dotimes [_ 10000] (power 2 512))) "Elapsed time: 1839.406746 msecs" 

And once with lazy-seq:

 (defn power [an] (letfn [(multiply [a factor] (lazy-seq (cons a (multiply (* a factor) factor))))] (nth (multiply aa) (dec n)))) user=> (time (dotimes [_ 10000] (power 2 512))) "Elapsed time: 2162.297827 msecs" 

Which implementation do you think is superior? I really do not know. (I would use recur because it was easier to understand.)

I read that lazy-seq is fast because it uses internal caching. But I do not see the possibility of caching in my example. Am I missing something?

Update
I posted timings with samples. It seems that recur here is a little faster.

Regular recursion is not too bad either:

 (defn power [an] (if (== n 1) a (* a (power a (dec n))))) user=> (time (dotimes [_ 10000] (power 2 512))) "Elapsed time: 1877.34521 msecs" 

Answer 1

First of all, the usual advice is to choose the right algorithm first , think about the implementation details later (if your code is actually performance sensitive or can be used in contexts).

Then there are aesthetic considerations. recur seems cleaner to me, simply because it's a completely natural way to solve a problem. Using sequences makes sense when they somehow enter the semantic picture or, otherwise, make the code much easier to write / understand / do the performer. It has nothing of the kind here.

Finally, I would definitely expect recur be faster overall, if only because it avoids unnecessary allocation and GC. This is confirmed by the initial timings. In fact, there is no way to capitalize on any kind of caching here because you generate your sequence from scratch whenever power is called and does not return to it after returning.

Answer 2

I have provided some lazy power functions to show how you can reuse lazy-seq from a function.

Each time you call my-simple-lazy-power with two numbers, it creates a lazy seq with powers of a certain number x and returns the nth element. Using this version is very expensive, because for each function call exactly one lazy seq is created. This is probably why the reference mine-lazy power is so slow. Since lazy-seqs caches its results, you probably want to reuse them. This is what my-lazy-power does: it creates lazy-seq for the number x and wraps around it a function that takes n as an argument. You can reuse the latter function to access cached results. (The function maintains a link to lazy-seq as long as the function exists, because it is "closed" to lazy-seq. That's why they call it closing.)

Another common way to cache function results is to use a memoized version of the function. Basically, memoize remembers the result for the arguments you pass, so the next time you pass the same arguments, it will return the result from the cache. See examples below. For comparison, I also timed your versions and their memoized versions.

 (defn my-simple-lazy-power [xn] (let [my-lazy-list ((fn my-lazy [y] (lazy-cat [y] (map #(* % x) (my-lazy y)))) x)] (nth my-lazy-list n))) (defn my-lazy-power [x] (let [my-lazy-list ((fn my-lazy [y] (lazy-cat [y] (map #(* % x) (my-lazy y)))) x)] (fn [n] (nth my-lazy-list n)))) (defn rec-power [an] (let [multiply (fn [x factor i] (if (zero? i) x (recur (* x factor) factor (dec i))))] (multiply aa (dec n)))) (defn lazy-power [an] (letfn [(multiply [a factor] (lazy-seq (cons a (multiply (* a factor) factor))))] (nth (multiply aa) (dec n)))) (def mem-my-simple-power (memoize my-simple-lazy-power)) (def mem-my-power (memoize my-lazy-power)) (def mem-rec-power (memoize rec-power)) (def mem-laz-power (memoize lazy-power)) (time (dotimes [_ 50] (my-simple-lazy-power 2 512))) "Elapsed time: 7138.346976 msecs" nil (time (let [my-pow-2 (my-lazy-power 2)] (dotimes [_ 10000] (my-pow-2 512)))) "Elapsed time: 854.717301 msecs" nil (time (dotimes [_ 10000] (rec-power 2 512))) "Elapsed time: 2726.559879 msecs" nil (time (dotimes [_ 10000] (mem-rec-power 2 512))) "Elapsed time: 4.775677 msecs" nil (time (dotimes [_ 10000] (lazy-power 2 512))) "Elapsed time: 3617.100209 msecs" nil (time (dotimes [_ 10000] (mem-laz-power 2 512))) "Elapsed time: 4.95887 msecs" nil 

PS: I had to write fn around the lazy-seq definition in my versions because let doesn't support recursive definitions, but fn does.

PS2: sorry for the indent, copying the paste from Emacs doesn't seem to save it ...

Answer 3

You have to do time tests, run both 1 m times and time. Typically, non-recursive functions execute faster, but when working with functional languages, recursion is the preferred transition method, since they usually use tail calls. Clojure is based on Java Clr, so I'm not right now if a tail call is supported, but if so, it should be as fast as a non-recursive call.

Answer 4

Adding the answer to Michael Marcik ...

You can reset the definition and call the multiply function in the loop :

 (defn power [an] (loop [xa, factor a, i (dec n)] (if (zero? i) x (recur (* x factor) factor (dec i))))) 

... but it does not work faster.

As M. wrote, it is important to choose the right algorithm. The one he suggested runs the example about twenty times faster than yours:

 (defn power [xn] (loop [acc 1, nn, factor x] (if (zero? n) acc (recur (if (even? n) acc (* acc factor)) (quot n 2) (* factor factor))))) 

You must invite the current Clojure to use BigInt , otherwise you will get an integer overflow:

 (time (dotimes [_ 10000] (power 2N 512))) 

Your mileage may vary.