Saturday, August 10, 2019

SICP in Clojure: Chapter 1, Exercise 16

This is my Clojure solution to Chapter 1, Exercise 16:

(ns sicp.ch1.ex16)

(defn square
  [n]
  (* n n))

(defn fast-expt
  [b n]
  (cond (zero? n) 1
        (even? n) (square (fast-expt b (/ n 2)))
        :else (* b (fast-expt b (dec n)))))

(defn fast-expt-iter
  ([b n]
   (fast-expt-iter 1 b n))
  ([a b n]
   (cond (zero? n) a
         (even? n) (fast-expt-iter a (square b) (/ n 2))
         :else (fast-expt-iter (* a b) b (dec n)))))

(fast-expt 2 8) ; => 256

(fast-expt 2 9) ; => 512

(every? #(= (fast-expt 2 %) (fast-expt-iter 2 %))
        (range 10)) ; => true


No comments: