Implementations of power in Clojure

powpow.clj

(defn create-power
  "Takes a positive power-of implementation and returns a function that uses
  it plus the logic for y==0 and y<0"
  [implementation]
  (fn [x y]
    (cond
      (> y 0) (implementation x y)
      (< y 0) (/ 1 (implementation x (Math/abs y)))
      :else 1)))


; Implementations...

(defn power-reduce-pos
  "Reduce solution, O(y)"
  [x y]
  (reduce * (repeat y x)))
(def power-reduce (create-power power-reduce-pos))


(defn power-recurs-pos
  "Recursive solution, O(y)" ; Is this TCO'd?
  [x y]
  (if (= y 1)
    x
    (* x (power-recurs-pos x (- y 1)))))
(def power-recurs (create-power power-recurs-pos))


(defn power-tco-pos
  "Recursive / TCOd, O(y)"
  ([x y] (power-tco-pos x y nil))
  ([x y a]
  (if (= y 1)
    (or a x)
    (recur x (- y 1) (* (or a x) x)))))
(def power-tco (create-power power-tco-pos))


(defn power-logn-pos
  "Recursive solution, O(logy)"
  [x y]
  (if (= (int y) 1) x
  (let [half (power-logn-pos x (Math/floor (/ y 2)))]
    (* half half (if (odd? (int y)) x 1)))))
(def power-logn (create-power power-logn-pos))


(defn power-shift-pos
  "Recursive power multiplication, O(logy)"
  [x y]
  (reduce *
    (loop [idx 1 candidates []]
      (if (> idx y)
        candidates
        (recur
          (bit-shift-left idx 1)
          (if (not (= (bit-and idx y) 0))
            (concat
              candidates
              (list (reduce * (repeat idx x))))
            candidates))))))
(def power-shift (create-power power-shift-pos))


(defn power-factor-pos
  "Recursive power using factoring, O(logy)"
  [x y]
  (
    reduce
    *
    (map
      #(reduce * (repeat % x))
      (filter ; take only the factors present in y
        #(not (= 0 (bit-and % y)))
        (take-while ; take all powers of 2 smaller or equal to y
          #(<= % y) ; i.e. the factors of y
          (map #(bit-shift-left 1 %) (range)))))))
(def power-factor (create-power power-factor-pos))


; Tests...

(use 'clojure.test)


(deftest power-reduce-test
  (is (= (power-reduce 2 0) 1))
  (is (= (power-reduce 2 2) 4))
  (is (= (power-reduce 5 2) 25))
  (is (= (power-reduce 2 -2) 1/4)))

(deftest power-recurs-test
  (is (= (power-recurs 2 0) 1))
  (is (= (power-recurs 2 2) 4))
  (is (= (power-recurs 5 2) 25))
  (is (= (power-recurs 2 -2) 1/4)))

(deftest power-tco-test
  (is (= (power-tco 2 0) 1))
  (is (= (power-tco 2 2) 4))
  (is (= (power-tco 5 2) 25))
  (is (= (power-tco 2 -2) 1/4)))

(deftest power-logn-test
  (is (= (power-logn 2 0) 1))
  (is (= (power-logn 2 2) 4))
  (is (= (power-logn 5 2) 25))
  (is (= (power-logn 2 -2) 1/4)))

(deftest power-shift-test
  (is (= (power-shift 2 0) 1))
  (is (= (power-shift 2 2) 4))
  (is (= (power-shift 5 2) 25))
  (is (= (power-shift 2 -2) 1/4)))

(deftest power-factor-test
  (is (= (power-factor 2 0) 1))
  (is (= (power-factor 2 2) 4))
  (is (= (power-factor 5 2) 25))
  (is (= (power-factor 2 -2) 1/4)))

(run-tests)


; Benchmark...

(time (dotimes [_ 1000] (power-reduce 1 1000)))
(time (dotimes [_ 1000] (power-recurs 1 1000)))
(time (dotimes [_ 1000] (power-tco    1 1000)))
(time (dotimes [_ 1000] (power-logn   1 1000)))
(time (dotimes [_ 1000] (power-shift  1 1000)))
(time (dotimes [_ 1000] (power-factor 1 1000)))