On Mon, Oct 1, 2012 at 4:45 PM, Grant Rettke <gret...@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.
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@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+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
