Created
October 6, 2014 18:28
-
-
Save diezguerra/b894132d5fca3ee4e45b to your computer and use it in GitHub Desktop.
Implementations of power in Clojure
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(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))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment