How to do exponentiation in clojure?

Question

How can I do exponentiation in clojure? For now I'm only needing integer exponentiation, but the question goes for fractions too.

Solution 1

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)

Solution 2

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

Solution 3

You can use java's Math.pow or BigInteger.pow methods:

(Math/pow base exponent)

(.pow (bigdec base) exponent)

Solution 4

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

Solution 5

user=> (.pow (BigInteger. "2") 10)
1024
user=> (.pow (BigInteger. "2") 100)
1267650600228229401496703205376

View more solutions

Comments

[Peter]

+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?

[DaVinci]

Clojure is built arround the java libraries, it does not attempt to fix what is not broken and Math/pow works just fine. Why do you need to care for doubles or integers? You could also use this richhickey.github.com/clojure-contrib/…

[sepp2k]

@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 than math-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.

[Peter]

@Da vinci : strange remark, it's a language of it's own, and has a lot of functions that are in Java (like stringreverse)

[Peter]

@sepp : It is indeed about big nummers (project euler like stuff)

[sepp2k]

@Peter: For bigints you can use java's BigInteger.pow instance method.

[mikera]

+1 for this answer since it handles all the Clojure exact (i.e. BigDecimal / BigInteger) arithmetic correctly.

[mikera]

I 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.....

[TJ Trapp]

but seems to max out at 2^63... def not capable of 2^200

[user1568901]

Probably 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.

[mikera]

I think it's now in "clojure.math.numeric-tower" as of 1.3 (since clojure.contrib got broken up into individual libraries)

[noisesmith]

also you can use the literal notation for this: (.pow 2M 100)

[KIM Taegyoon]

Their types are different. user=> (type 2M) java.math.BigDecimal user=> (type (BigInteger. "2")) java.math.BigInteger

[Karl Rosaen]

see fully iterative version of sneaky solution below stackoverflow.com/a/22977674/231589

[Brad Koch]

"Note - the contrib libs have moved to individual repos under Clojure org"; this link only answer is now misleading.

[Brad Koch]

"Note - the contrib libs have moved to individual repos under Clojure org"; this answer is outdated.

[Daniel Gruszczyk]

imo best solution, showr, using existing libraries, and including handling of bigint. +1

[Zaz]

For me (Math/pow Math/E x) does the trick (replacing Math/E with the base of your choice).

[alvaro g]

Clojure.contrib.math is now deprecated, see Math.Numeric-Tower

[Pointo Senshi]

The second suggestion (tail recursive) has integer overflow for n < 0.

[Daniel Szmulewicz]

Fantastic answer. Here's how to do with it with a macro: (defmacro exp [x n] `(* ~@(take n (repeat x))))

[loxaxs]

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))

[johncip]

I'm getting No matching method pow ... for class clojure.lang.BigInt -- shouldn't it be (.pow (biginteger base) exponent)?

[Andrew Koster]

None of the answers that involve importing an existing function work (including the (require 'clojure.contrib.math) in this answer). But (defn exp [x n] (reduce * (repeat n x))) works great, and is easy to understand!

[David Tonhofer]

Clojure has no "tail recursion" (or rather, "tail-call optimization") because Java does have it. A loop, however, is a loop.

[David Tonhofer]

Added "reminder about package installation" to allay user frustration.