Which power function is right for Clojure?

[Grant Rettke]

(ns power.examples)

(defn non-acc-pow [base exp]
(if (zero? exp)
1
(* base (non-acc-pow base (dec exp)))))

(defn acc-pow [base exp]
(letfn [(loop [base exp acc]
(if (zero? exp)
acc
(recur base (dec exp) (* base acc))))]
(loop base exp 1)))

(defn lazy-pow [base exp]
(letfn [(loop [cur]
(cons cur (lazy-seq (loop (* cur base)))))]
(nth (take exp (loop base)) (dec exp))))

(defn iter-pow [base exp]
(nth (take exp (iterate (partial * base) base)) (dec exp)))

(defn apply-pow [base exp]
(apply * (repeat exp base)))

(= 16
(non-acc-pow 2 4)
(acc-pow 2 4)
(lazy-pow 2 4)
(iter-pow 2 4)
(apply-pow 2 4))

Originally posted here:
http://www.wisdomandwonder.com/article/6430/which-power-function-is-right-for-clojure

--
((λ (x) (x x)) (λ (x) (x x)))
http://www.wisdomandwonder.com/
ACM, AMA, COG, IEEE

[Andy Fingerhut]

It depends.

Are you trying to optimize for speed? Teaching a particular style of programming? Code size? Range of input values handled correctly? Time to write it?

Something else?

Andy

> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en

[Jean Niklas L'orange]

Numeric tower has implemented pow (named expt in the library), so you could have a look at their implementation:

https://github.com/clojure/math.numeric-tower/blob/master/src/main/clojure/clojure/math/numeric_tower.clj#L64

(It utilizes exponentiation by squaring to get the running time from O(n) to O(log n).)

[Mark Engelberg]

On Mon, Oct 1, 2012 at 4:45 PM, Grant Rettke <gre...@acm.org> wrote:

(ns power.examples)

(defn non-acc-pow [base exp]
  (if (zero? exp)
    1
    (* base (non-acc-pow base (dec exp)))))

This is not ideal for Clojure.  The exponent will be limited by the stack size in Java.
 

(defn acc-pow [base exp]
  (letfn [(loop [base exp acc]
            (if (zero? exp)
              acc
              (recur base (dec exp) (* base acc))))]
    (loop base exp 1)))

This naming of a helper function to "loop" is non-idiomatic, because there is a built-in construct "loop", which works somewhat like named let in Scheme (without the name), allowing you to combine the function definition and the initial values at once.  Idiomatic version of this would be:

defn acc-pow [base exp]
  (loop [base base,
         exp exp,
         acc 1]
    (if (zero? exp)
      acc
      (recur base (dec exp) (* base acc)))))

There's a subtle concern here though.  Clojure, by default, uses longs.  If you try to do something large, like (acc-pow 2 500), you'll get an overflow error.  One easy fix is to change the 1 to 1N, and then you'll get boxed numerics.  Another option is to change * to *'.

Notice that it is perfectly idiomatic to bind the local "base" to the function input "base" and so on.  You don't have to do that, though.
 

(defn lazy-pow [base exp]
  (letfn [(loop [cur]
            (cons cur (lazy-seq (loop (* cur base)))))]
    (nth (take exp (loop base)) (dec exp))))

This is just an overly convoluted version of what comes next.
 

(defn iter-pow [base exp]
  (nth (take exp (iterate (partial * base) base)) (dec exp)))

This is an improvement, but the "take exp" is totally unnecessary.  Try:

(defn iter-pow [base exp]
  (nth (iterate (partial * base) base) (dec exp)))

(defn apply-pow [base exp]
  (apply * (repeat exp base)))

This is the most concise, and perfectly reflects what you want to do.  This is certainly good Clojure, and arguably the best of all of these (again, think about whether you want * or *')

(= 16
   (non-acc-pow 2 4)
   (acc-pow 2 4)
   (lazy-pow 2 4)
   (iter-pow 2 4)
   (apply-pow 2 4))

Finally, here's an efficient version:

(defn efficient-pow [base pow]
  (loop [n pow, y 1, z base]
    (let [t (even? n), n (quot n 2)]
      (cond
       t (recur n y (*' z z))
       (zero? n) (*' z y)
       :else (recur n (*' z y) (*' z z))))))
 
This is essentially how I coded it in clojure.math.numeric-tower.

[Mark Engelberg]

On Mon, Oct 1, 2012 at 6:29 PM, Mark Engelberg <mark.en...@gmail.com> wrote:

(defn efficient-pow [base pow]

  (loop [n pow, y 1, z base]
    (let [t (even? n), n (quot n 2)]
      (cond
       t (recur n y (*' z z))
       (zero? n) (*' z y)
       :else (recur n (*' z y) (*' z z))))))
 
This is essentially how I coded it in clojure.math.numeric-tower.

I should clarify that in clojure.math.numeric-tower, this is a helper function called when the power is known to be positive, so this doesn't work for a power of 0, for example.

It's written a little oddly because the variable names and branching structure are meant to reflect the algorithm as presented by Knuth.

[Grant Rettke]

On Mon, Oct 1, 2012 at 7:13 PM, Andy Fingerhut <andy.fi...@gmail.com> wrote:
> It depends.
>
> Are you trying to optimize for speed? Teaching a particular style of
> programming? Code size? Range of input values handled correctly? Time
> to write it?
>
> Something else?

The most "Clojury" way of doing it. Perhaps it was too trivial a problem.

[Grant Rettke]

On Mon, Oct 1, 2012 at 8:29 PM, Mark Engelberg <mark.en...@gmail.com> wrote:
> On Mon, Oct 1, 2012 at 4:45 PM, Grant Rettke <gre...@acm.org> wrote:
> This naming of a helper function to "loop" is non-idiomatic, because there
> is a built-in construct "loop", which works somewhat like named let in
> Scheme (without the name), allowing you to combine the function definition
> and the initial values at once. Idiomatic version of this would be:

Oh ok.

> There's a subtle concern here though. Clojure, by default, uses longs. If
> you try to do something large, like (acc-pow 2 500), you'll get an overflow
> error. One easy fix is to change the 1 to 1N, and then you'll get boxed
> numerics. Another option is to change * to *'.

Nice.

Thanks for the feedback everybody.