49 lines
945 B
Plaintext
49 lines
945 B
Plaintext
(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]
|
|
(cond
|
|
(= b 0) 0
|
|
(= b 1) a
|
|
(even? b) (double (mul-iter a (halve b)))
|
|
(+ a (mul-iter a (- b 1)))))
|
|
(mul-iter a b))
|
|
|
|
# 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)
|