# How to do exponentiation in clojure?

ClojureExponentiation## Clojure Problem Overview

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

## Clojure Solutions

## Solution 1 - Clojure

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

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

You can use java's `Math.pow`

or `BigInteger.pow`

methods:

```
(Math/pow base exponent)
(.pow (bigdec base) exponent)
```

## Solution 4 - Clojure

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

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

## Solution 6 - Clojure

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.

## Solution 7 - Clojure

I think this would work too:

```
(defn expt [x pow] (apply * (repeat pow x)))
```

## Solution 8 - Clojure

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

## Solution 9 - Clojure

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

## Solution 10 - Clojure

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

## Solution 11 - Clojure

A simple one-liner using reduce:

```
(defn pow [a b] (reduce * 1 (repeat b a)))
```

## Solution 12 - Clojure

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.

## Solution 13 - Clojure

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.

## Solution 14 - Clojure

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.