-
Notifications
You must be signed in to change notification settings - Fork 0
/
1-16.rkt
49 lines (39 loc) · 1.21 KB
/
1-16.rkt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#lang racket
(define (assert-eql actual expected)
(if (not (= expected actual))
(error "Does not match condition, expected: "
expected " actual: " actual)
true))
(define (expt b n)
(if (= n 0)
1
(* b (expt b (- n 1)))))
(assert-eql (expt 10 0) 1)
(assert-eql (expt 5 3) 125)
(define (expt-iter b n)
(define (expt-iter-inner a counter)
(if (= counter 0)
a
(expt-iter-inner (* a b) (- counter 1))))
(expt-iter-inner 1 n))
(assert-eql (expt-iter 10 0) 1)
(assert-eql (expt-iter 5 3) 125)
(define (fast-expt b n)
(define (square x) (* x x))
(cond ((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))
(assert-eql (fast-expt 10 0) 1)
(assert-eql (fast-expt 5 3) 125)
;; 1.16
(define (fast-expt-iter b n)
(define (square x) (* x x))
(define (fast-expt-inner a b counter)
(cond ((= counter 0) a)
((even? counter) (fast-expt-inner a (square b) (/ counter 2)))
(else (fast-expt-inner (* a b) b (- counter 1)))))
(fast-expt-inner 1 b n))
(assert-eql (fast-expt-iter 10 0) 1)
(assert-eql (fast-expt-iter 2 2) 4)
(assert-eql (fast-expt-iter 5 3) 125)
(assert-eql (fast-expt-iter 5 5) 3125)