How can I do exponentiation in clojure? For now I'm only needing integer exponentiation, but the question goes for fractions too.
-
28As someone who doesn't know clojure, but is predisposed to like it (being a fan of lisps, functional programming, and having lots of handy libraries), I'm disappointed that this simple question has so many answers--or that it had to be asked at all. I would have thought that exponentiation would just be one of the basic functions provided without having to do anything at all special. I'm glad it was asked, though.– MarsCommented Sep 16, 2013 at 17:33
-
2well yes probably some version of it should be in the core... but i think that many answers is still a good sign. the "multiple paths to implementation" seems to be the reason a lot of these things aren't provided -- the user should know the details of the function they are using for efficiency's sake. for example (as is pointed out in the chosen answer) some ways may potentially blow the stack, others less likely to do so. maybe some are lazy, some eager... all details that need to be paid some attention in Clojure, which is why I feel most non-trivial libs aren't provided due to philosophy– jm0Commented Dec 22, 2013 at 9:39
-
4I think the reason there's not just an exp function in the core is because clojure's numeric tower is badly broken for efficiency reasons. So there are all sorts of different things you could mean by exponentiation. What should (exp 2 (exp 2 200)) be? An error or a huge integer that takes an age to calculate? If you just want the usual floating point exp, then the java one is built in. If you want a language where the numbers do their best to act like the reals, and hang the cost, use scheme instead of clojure.– John Lawrence AspdenCommented Apr 6, 2014 at 11:58
15 Answers
classic recursion (watch this, it blows stack)
(defn exp [x n]
(if (zero? n) 1
(* x (exp x (dec n)))))
tail recursion
(defn exp [x n]
(loop [acc 1 n n]
(if (zero? n) acc
(recur (* x acc) (dec n)))))
functional
(defn exp [x n]
(reduce * (repeat n x)))
sneaky (also blows stack, but not so easily)
(defn exp-s [x n]
(let [square (fn[x] (* x x))]
(cond (zero? n) 1
(even? n) (square (exp-s x (/ n 2)))
:else (* x (exp-s x (dec n))))))
library
(require 'clojure.contrib.math)
-
see fully iterative version of sneaky solution below stackoverflow.com/a/22977674/231589 Commented Apr 10, 2014 at 2:43
-
8Clojure.contrib.math is now deprecated, see Math.Numeric-Tower– alvaro gCommented Mar 14, 2016 at 17:23
-
1The second suggestion (tail recursive) has integer overflow for n < 0. Commented Oct 15, 2016 at 22:07
-
1Fantastic answer. Here's how to do with it with a macro: (defmacro exp [x n] `(* ~@(take n (repeat x)))) Commented Oct 27, 2016 at 22:53
-
Terminal recursion for the fast exponentiation algorithm:
(def exp (letfn [(rexp [x n r] (cond (zero? n) r (even? n) (recur (*' x x) (/ n 2) r) :else (recur (*' x x) (/ (dec n) 2) (*' x r))))] (fn [x n] (rexp x n 1))))
. It never blows the stack. Test(exp 1 (exp 2 30000))
– loxaxsCommented Mar 4, 2018 at 20:46
Clojure has a power function that works well: I'd recommend using this rather than going via Java interop since it handles all the Clojure arbitrary-precision number types correctly. It is in namespace clojure.math.numeric-tower.
It's called expt
for exponentiation rather than power
or pow
which maybe explains why it's a bit hard to find ... anyway here's a small example (note that use
works but better use require
):
(require '[clojure.math.numeric-tower :as math :refer [expt]]) ; as of Clojure 1.3
;; (use 'clojure.contrib.math) ; before Clojure 1.3
(expt 2 200)
=> 1606938044258990275541962092341162602522202993782792835301376
Reminder about package installation
You must first install the Java package org.clojure.math.numeric-tower
to make the Clojure namespace clojure.math.numeric-tower
accessible!
On the command line:
$ lein new my-example-project
$ cd lein new my-example-project
Then edit project.clj
and add [org.clojure/math.numeric-tower "0.0.4"]
to the dependencies vector.
Start a lein REPL (not a clojure REPL)
$ lein repl
Now:
(require '[clojure.math.numeric-tower :as math])
(math/expt 4 2)
;=> 16
or
(require '[clojure.math.numeric-tower :as math :refer [expt]])
(expt 4 2)
;=> 16
-
1Probably unknown because it doesn't appear to be part of standard Clojure. 1.3.0 tosses errors about not being able to locate the math.clj when I try to do it this way. Commented Dec 21, 2011 at 18:40
-
9I think it's now in "clojure.math.numeric-tower" as of 1.3 (since clojure.contrib got broken up into individual libraries)– mikeraCommented Dec 22, 2011 at 9:36
-
1Added "reminder about package installation" to allay user frustration. Commented Jan 28, 2020 at 10:28
You can use java's Math.pow
or BigInteger.pow
methods:
(Math/pow base exponent)
(.pow (bigdec base) exponent)
-
1+1, though I know you can interop with java libs; however, 1) Math.pow works with doubles, I need Integers, can you give an example? 2) Do you really have to use interop for sth. simple as powers?– PeterCommented Feb 20, 2011 at 12:43
-
1@Peter: 1) Unless your powers are so large that they can't be accurately represented by doubles anymore, there really is no problem with just casting the result to int. 2) I don't see how writing
Math/pow
is more complicated thanmath-pow
or whatever the name would be if there was a clojure equivalent. If there already is a simple java method that does what you want, there is no reason to recreate the functionality in clojure. Java interop is not inherently harmful.– sepp2kCommented Feb 20, 2011 at 12:52 -
4@Da vinci : strange remark, it's a language of it's own, and has a lot of functions that are in Java (like stringreverse)– PeterCommented Feb 20, 2011 at 12:53
-
4I think you are better using Clojure's clojure.contrib.math/expt if you want accurate biginteger powers. Probably does the same under the hood but much nicer than going via Java interop.....– mikeraCommented Feb 22, 2011 at 13:10
-
1I'm getting
No matching method pow ... for class clojure.lang.BigInt
-- shouldn't it be(.pow (biginteger base) exponent)
?– johncipCommented May 1, 2019 at 21:32
When this question was originally asked, clojure.contrib.math/expt was the official library function to do this. Since then, it has moved to clojure.math.numeric-tower
-
+1 for this answer since it handles all the Clojure exact (i.e. BigDecimal / BigInteger) arithmetic correctly.– mikeraCommented Feb 22, 2011 at 13:08
user=> (.pow (BigInteger. "2") 10)
1024
user=> (.pow (BigInteger. "2") 100)
1267650600228229401496703205376
-
6also you can use the literal notation for this:
(.pow 2M 100)
Commented Nov 9, 2013 at 1:53 -
1Their types are different. user=> (type 2M) java.math.BigDecimal user=> (type (BigInteger. "2")) java.math.BigInteger Commented Nov 14, 2013 at 5:53
-
imo best solution, showr, using existing libraries, and including handling of bigint. +1 Commented Jun 9, 2014 at 9:53
-
For me
(Math/pow Math/E x)
does the trick (replacingMath/E
with the base of your choice).– ZazCommented Nov 10, 2015 at 1:01
Since Clojure 1.11, clojure.math/pow
ships with the standard library, and works both for Clojure and ClojureScript.
If you really need a function and not a method you can simply wrap it:
(defn pow [b e] (Math/pow b e))
And in this function you can cast it to int
or similar. Functions are often more useful that methods because you can pass them as parameters to another functions - in this case map
comes to my mind.
If you really need to avoid Java interop, you can write your own power function. For example, this is a simple function:
(defn pow [n p] (let [result (apply * (take (abs p) (cycle [n])))]
(if (neg? p) (/ 1 result) result)))
That calculates power for integer exponent (i.e. no roots).
Also, if you are dealing with large numbers, you may want to use BigInteger
instead of int
.
And if you are dealing with very large numbers, you may want to express them as lists of digits, and write your own arithmetic functions to stream over them as they calculate the result and output the result to some other stream.
I think this would work too:
(defn expt [x pow] (apply * (repeat pow x)))
SICP inspired full iterative fast version of 'sneaky' implementation above.
(defn fast-expt-iter [b n]
(let [inner (fn [a b n]
(cond
(= n 0) a
(even? n) (recur a (* b b) (/ n 2))
:else (recur (* a b) b (- n 1))))
]
(inner 1 b n)))
Implementation of "sneaky" method with tail recursion and supporting negative exponent:
(defn exp
"exponent of x^n (int n only), with tail recursion and O(logn)"
[x n]
(if (< n 0)
(/ 1 (exp x (- n)))
(loop [acc 1
base x
pow n]
(if (= pow 0)
acc
(if (even? pow)
(recur acc (* base base) (/ pow 2))
(recur (* acc base) base (dec pow)))))))
Use clojure.math.numeric-tower
, formerly clojure.contrib.math
.
(ns user
(:require [clojure.math.numeric-tower :as m]))
(defn- sqr
"Uses the numeric tower expt to square a number"
[x]
(m/expt x 2))
Try
(defn pow [x n]
(loop [x x n n r 1]
(cond
(= n 0) r
(even? n) (recur (* x x) (/ n 2) r)
:else (recur x (dec n) (* r x)))))
for a tail-recursive O(log n) solution, if you want to implement it yourself (only supports positive integers). Obviously, the better solution is to use the library functions that others have pointed out.
I personally use:
(defn pow [x n] (reduce *' (repeat n x)))
Notice the apostrophe (') after the asterisk.
Works well for all sizes of integers.
Note: This might be a little slow for some implementations. (time (pow 2 200000)) took 1.2 seconds to resolve on my system.
How about clojure.contrib.genric.math-functions
There is a pow function in the clojure.contrib.generic.math-functions library. It is just a macro to Math.pow and is more of a "clojureish" way of calling the Java math function.
-
1"Note - the contrib libs have moved to individual repos under Clojure org"; this answer is outdated. Commented May 26, 2014 at 19:56