(defn mul [a b]
  (if (= b 0)
    0
    (+ a (mul a (- b 1)))))

(defn fast-mul [a b]
  (defn even? [n]
    (= (mod n 2) 0))
  (defn double [n]
    (* n 2))
  (defn halve [n]
    (/ n 2))
  (defn mul-iter [a b s]
    (cond
      (= b 0) s
      (even? b) (mul-iter (double a) (halve b) s)
      (mul-iter a (- b 1) (+ a s))))
  (mul-iter a b 0))

(defn fast-mul2 [a b]
  (defn even? [n]
    (= (mod n 2) 0))
  (defn double [n]
    (* n 2))
  (defn halve [n]
    (/ n 2))
  (defn mul-iter [a b s]
    (cond
      (= b 0) s
      (= a 0) s
      (even? b) (mul-iter (double a) (halve b) s)
      (mul-iter (double a) (halve (- b 1)) (+ s a))))
  (mul-iter a b 0))

# Similar to exercise 1.16 the procedure is again split into two cases:
# case 1: b even?
#   f(a,b) = f(2a,b/2)
# case 2: b uneven?
#   f(a,b) = a+f(a,b-1)
# given:
#   f(a,0) = 0
#   f(a,1) = a
#   f(a,2) = 2a
#   f(a,n) = na
# prove (for n > 1):
#   f(a, 2*n) = f(2a, n)
#   f(a, 2*n-1) = a + f(a,2*n-2)
# solution:
#   2*n*a = 2*a*n
#   (2*n - 1) * a = a + (2*n - 2)*a
#   2*n*a - a = a + 2*n*a - 2a
#   2*n*a - a = 2*n*a - a

(def k 100)
(defn lo [n]
  (cond
    (= n k) (printf "%d %f" n (fast-mul 10 n))
    (do
      (printf "%d %f" n (fast-mul 10 n))
      (lo (+ n 1)))))

(lo 0)

(def k 100)
(defn lo2 [n]
  (cond
    (= n k) (printf "%d %f" n (fast-mul2 10 n))
    (do
      (printf "%d %f" n (fast-mul2 10 n))
      (lo2 (+ n 1)))))

(lo2 0)

(def k 100)
(defn lo3 [n]
  (cond
    (= n k) (printf "%d %f" n (fast-mul2 n 10))
    (do
      (printf "%d %f" n (fast-mul2 n 10))
      (lo3 (+ n 1)))))

(lo3 0)