The first procedure is recursive:
(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(int (inc (inc 6)))
(inc (inc 7))
(inc 8)
9
The second procedure is iterative:
(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9
1 ]=> (A 1 10)
;Value: 1024
1 ]=> (A 2 4)
;Value: 65536
1 ]=> (A 3 3)
;Value: 65536
The concise mathematical definitions for the functions computed by the procedures f, g, and h for positive integer values of \(n\):
Recursive:
(define (f n)
(cond ((< n 3) n)
(else (+ (f (- n 1))
(* 2 (f (- n 2)))
(* 3 (f (- n 3)))))))
Iterative:
(define (f n)
(define (f-iter count a b c)
(if (< count 0)
a
(f-iter (- count 1)
(+ a (* 2 b) (* 3 c))
a
b)))
(if (< n 3)
n
(f-iter (- n 3) 2 1 0)))
(define (pascal row col)
(cond ((> col row)
(error "invalid row-column"))
((or (= col 1) (= col row)) 1)
(else (+ (pascal (- row 1) (- col 1))
(pascal (- row 1) col)))))
Here is a well-explained proof, by Bill the Lizard.
The order of growth of the space is \(O(a)\).
The order of growth of the number of steps is \(O(n^2)\).
The expression (sine 12.15) is expanded as follows:
(sine 12.15)
(p (sine 4.05))
(p (p (sine 1.35)))
(p (p (p (sine 0.45))))
(p (p (p (p (sine 0.15)))))
(p (p (p (p (p (sine 0.05))))))
(p (p (p (p (p 0.05)))))
As we can see, the procedure p us applied 5 times.
The angle a is divided by 3 each time the procedure p is applied. For an arbitrary a, the number of steps n is the minimum value that satisfy the following formula:
Therefore, the order of growth in space and number of steps are both \(O(log{n})\).
(define (expt b n)
(define (expt-iter a b n)
(cond ((= n 0) a)
((even? n) (expt-iter a
(* b b)
(/ n 2)))
(else (expt-iter (* a b)
b
(- n 1)))))
(expt-iter 1 b n))
(define (* a b)
(cond ((= b 0) 0)
((even? b) (double (* a (halve b))))
(else (+ a (* a (- b 1))))))
(define (* a b)
(define (*-iter x a b)
(cond ((= b 0) x)
((even? b) (*-iter x (double a) (halve b)))
(else (*-iter (+ x a) a (- b 1)))))
(*-iter 0 a b))
The transformation \(T_{p\prime q\prime}\) can be easily calculated using matrix.
Therefore, \(p' = q^2 + p^2, q' = q^2 + 2pq\).
Our logarithmic Fibonacci procedure is as follows:
(define (fib n)
(fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
(cond ((= count 0) b)
((even? count)
(fib-iter a
b
(+ (* p p) (* q q)) ; compute p’
(+ (* q q) (* 2 p q)) ; compute q’
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))
The process of normal-order evaluation. It performs 18 remainder operations:
(gcd 206 40)
(if (= 40 0) ...)
(gcd 40 (remainder 206 40))
(if (= (remainder 206 40) 0) ...)
(if (= 6 0) ...)
(gcd (remainder 206 40) (remainder 40 (remainder 206 40)))
(if (= (remainder 40 (remainder 206 40)) 0) ...)
(if (= 4 0) ...)
(gcd (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
(if (= (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) 0) ...)
(if (= 2 0) ...)
(gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))
(if (= (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) 0) ...)
(if (= 0 0) ...)
(remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
The process of applicative-order evaluation. It performs 4 remainder operations:
(gcd 206 40)
(gcd 40 (remainder 206 40))
(gcd 40 6)
(gcd 6 (remainder 40 6))
(gcd 6 4)
(gcd 4 (remainder 6 4))
(gcd 4 2)
(gcd 2 (remainder 4 2))
(gcd 2 0)
2
The smallest-divisor procedure:
(define (smallest-divisor n) (find-divisor n 2))
(define (find-divisor n test-divisor)
(define (square x) (* x x))
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b) (= (remainder b a) 0))
Find the smallest divisor for thoese numbers:
> (smallest-divisor 199)
199
> (smallest-divisor 1999)
1999
> (smallest-divisor 19999)
7
The search-for-primes procedure:
(define (smallest-divisor n) (find-divisor n 2))
(define (find-divisor n test-divisor)
(define (square x) (* x x))
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b) (= (remainder b a) 0))
(define (prime? n)
(= n (smallest-divisor n)))
(define (timed-prime-test n)
(start-prime-test n (runtime)))
(define (start-prime-test n start-time)
(if (prime? n)
(report-prime n (- (runtime) start-time))))
(define (report-prime n elapsed-time)
(newline) (display n) (display " *** ") (display elapsed-time))
(define (search-for-primes first last)
(if (<= first last)
(if (odd? first)
(begin (timed-prime-test first)
(search-for-primes (+ first 1) last))
(search-for-primes (+ first 1) last))))
Let’s find the three smallest primes larger than 1000; larger than 10,000; larger than 100,000; larger than 1,000,000, respectively:
> (search-for-primes 1000 1019)
1009 *** 15
1013 *** 15
1019 *** 15
> (search-for-primes 10000 10037)
10007 *** 47
10009 *** 48
10037 *** 46
> (search-for-primes 100000 100043)
100003 *** 150
100019 *** 152
100043 *** 149
> (search-for-primes 1000000 1000037)
1000003 *** 470
1000033 *** 468
1000037 *** 469
As is mentioned in Community-Scheme-Wiki, computers today have become too fast to appreciate the time required for primality test on those small numbers. So we could perform tests with greater numbers (1e9 ~ 1e12)to get meaningful results:
> (search-for-primes 1000000000 1000000021)
1000000007 *** 14576
1000000009 *** 15021
1000000021 *** 13935
> (search-for-primes 10000000000 10000000061)
10000000019 *** 46108
10000000033 *** 47346
10000000061 *** 44855
> (search-for-primes 100000000000 100000000057)
100000000003 *** 146165
100000000019 *** 150204
100000000057 *** 143866
> (search-for-primes 1000000000000 1000000000063)
1000000000039 *** 472598
1000000000061 *** 460440
1000000000063 *** 474448
It can be easily observed that by increasing the tested number by a magnitude, the required time increases by approximately a factor of \(\sqrt{3}\). Therefore, the result is compatible with the notion that programs run in a time proportional to the numbers of steps required for the computation.
The modified program is as follows:
(define (smallest-divisor n) (find-divisor n 2))
(define (find-divisor n test-divisor)
(define (square x) (* x x))
(define (next n)
(if (= n 2) 3 (+ n 2)))
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (next test-divisor)))))
(define (divides? a b) (= (remainder b a) 0))
(define (prime? n)
(= n (smallest-divisor n)))
(define (timed-prime-test n)
(start-prime-test n (runtime)))
(define (start-prime-test n start-time)
(if (prime? n)
(report-prime n (- (runtime) start-time))))
(define (report-prime n elapsed-time)
(newline) (display n) (display " *** ") (display elapsed-time))
(define (search-for-primes first last)
(if (<= first last)
(if (odd? first)
(begin (timed-prime-test first)
(search-for-primes (+ first 1) last))
(search-for-primes (+ first 1) last))))
Let’s run those tests again:
> (search-for-primes 1000 1019)
1009 *** 10
1013 *** 10
1019 *** 10
> (search-for-primes 10000 10037)
10007 *** 42
10009 *** 31
10037 *** 26
> (search-for-primes 100000 100043)
100003 *** 86
100019 *** 80
100043 *** 80
> (search-for-primes 1000000 1000037)
1000003 *** 339
1000033 *** 268
1000037 *** 268
> (search-for-primes 1000000000 1000000021)
1000000007 *** 8613
1000000009 *** 8257
1000000021 *** 16954
> (search-for-primes 10000000000 10000000061)
10000000019 *** 29032
10000000033 *** 26263
10000000061 *** 31629
> (search-for-primes 100000000000 100000000057)
100000000003 *** 88494
100000000019 *** 85926
100000000057 *** 82583
> (search-for-primes 1000000000000 1000000000063)
1000000000039 *** 266821
1000000000061 *** 269202
1000000000063 *** 278392
The observed ratio of the speeds of the two algorithms is between 1.5 and 2. I think this is because although the number of test steps is halved, we are paying extra overhead for procedure next. Compared with the previous expression (+ test-divisor 1), which can be highly-optimized to register increment machine code, the procedure next surely introduce overhead of branch and function call.
The fast-prime? version:
(define (expmod base exp m)
(define (square x) (* x x))
(cond ((= exp 0)
1)
((even? exp)
(remainder
(square
(expmod base (/ exp 2) m))
m))
(else
(remainder
(* base
(expmod base (- exp 1) m))
m))))
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))
(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)))
(define (prime? n)
(fast-prime? n 12))
(define (timed-prime-test n)
(start-prime-test n (runtime)))
(define (start-prime-test n start-time)
(if (prime? n)
(report-prime n (- (runtime) start-time))))
(define (report-prime n elapsed-time)
(newline) (display n) (display " *** ") (display elapsed-time))
(define (search-for-primes first last)
(if (<= first last)
(if (odd? first)
(begin (timed-prime-test first)
(search-for-primes (+ first 1) last))
(search-for-primes (+ first 1) last))))
;;; tests
(timed-prime-test 1009)
(timed-prime-test 1013)
(timed-prime-test 1019)
(timed-prime-test 10007)
(timed-prime-test 10009)
(timed-prime-test 10037)
(timed-prime-test 100003)
(timed-prime-test 100019)
(timed-prime-test 100043)
(timed-prime-test 1000003)
(timed-prime-test 1000033)
(timed-prime-test 1000037)
Test output:
1009 *** 119
1013 *** 116
1019 *** 115
10007 *** 140
10009 *** 164
10037 *** 144
100003 *** 161
100019 *** 160
100043 *** 161
1000003 *** 182
1000033 *** 197
1000037 *** 183
We can observe that the time to test primes near 1,000,000 is nearly 2 times to that of primes near 1,000. However, because the selected primes is too small (for today’s computer), these results cannot clearly demonstrate the logarithmic growth of this algorithm.