Re: Which power function is right for Clojure?
On Mon, Oct 1, 2012 at 7:13 PM, Andy Fingerhut andy.finger...@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. -- 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
Re: Which power function is right for Clojure?
On Mon, Oct 1, 2012 at 8:29 PM, Mark Engelberg mark.engelb...@gmail.com wrote: On Mon, Oct 1, 2012 at 4:45 PM, Grant Rettke gret...@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. -- 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
Re: Which power function is right for Clojure?
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 On Oct 1, 2012, at 4:45 PM, Grant Rettke wrote: (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 -- 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 -- 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
Re: Which power function is right for Clojure?
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).) -- 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
Re: Which power function is right for Clojure?
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
Re: Which power function is right for Clojure?
On Mon, Oct 1, 2012 at 6:29 PM, Mark Engelberg mark.engelb...@gmail.comwrote: (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. -- 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
