How can I do exponentiation in clojure? For now I'm only needing integer exponentiation, but the question goes for fractions too.
118
votes
As 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.
- Mars
well 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
- jm0
I 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 Aspden
13 Answers
151
votes
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)
79
votes
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
66
votes
13
votes
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
8
votes
6
votes
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.
4
votes
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)))
2
votes
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))
2
votes
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)))))))
1
votes
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.
