The elements of programming: primitive arithemetic operations, combining them, abstracting them. Focus now on common patterns of usage.
A procedure is a pattern for the local evolution of a computational process. Want to make statements about the global behavior of the process. Difficult in general but can describe some typical patterns.
Consider the factorial function. Many ways to compute, here's one:
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
(factorial 5) ; => 120Using the substitution model, can see that this creates a kind of "triangular-shaped" process. Here's another way:
(define (factorial n)
(fact-iter 1 1 n))
(define (fact-iter product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count)))
(factorial 5) ; => 120Using the substitution model, can see the "shape" of this process is the same width the whole time. Both processes do the same thing.
In the first case, the expansion occurs as the process builds up a chain of deferred operations, then contraction occurs as the operations are performed. This is called a recursive process. The interpreter needs to keep track of operations to be performed later, so the amount of information needed to keep track of grows linearly with n. Such a process is called a linear recursive process.
Second process is an iterative process. One whose state can be sumarized by a fixed number of state variables, with a rule that describes how they should be updated, and an optional end test. the number of required steps grows linearly with n. Called a linear iterative process.
In the iterative process, the variables provide a complete description of the state at any point. With the recursive process, there is some additional "hiddden" information which indicates "where the process is" in the chain of deferred operations.
Must be careful not to confusion the notion of a recursive process with the notion of a recursive procedure. A recursive procedure means that the procedure definition refers to the procedure itself. In the case of a process, we are speaking about how the process evolves, not the syntax of how it is written.
This distinction can be confusing because in most common languages the interpretation of any recursive procedure consumes an amount of memory that grows with the number of calls, even when the process described is iterative.To describe iterative processes they must use looping constructs (do, repeat, until, ...). Scheme executes an iterative process in constant space, even if it is described by a recursive procedure. Called tail-recursive.
Each of the following two procedures defines a method for adding two positive integers in terms of the procedures inc, which increments its argument by 1, and dec, which decrements its argument by 1.
(define (+ a b)
(if (= a 0) b (inc (+ (dec a) b))))
(define (+ a b)
(if (= a 0) b (+ (dec a) (inc b))))Using the substitution model, illustrate the process generated by each procedure in evaluating (+ 4 5). Are these processes iterative or recursive?
The first is recursive and the second is iterative.
(+ 4 5)
(inc (+ (dec 4) 5))
(inc (+ 3 5))
(inc (inc (+ (dec 3) 5)))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9(+ 4 5)
(+ (dec 4) (inc 5))
(+ 3 6)
(+ (dec 3) (inc 6))
(+ 2 7)
(+ (dec 2) (inc 7))
(+ 1 8)
(+ (dec 1) (inc 8))
(+ 0 9)
9The following procedure computes a mathematical function called Ackermann’s function.
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1) (A x (- y 1))))))What are the values of the following expressions?
(A 1 10)
(A 2 4)
(A 3 3)Consider the following procedures, where A is the procedure defined above:
(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))
(define (k n) (* 5 n n))Give concise mathematical definitions for the functions computed by the procedures f, g, and h for positive integer values of n. For example, (k n) computes 5n^2.
(A 1 10) ; => 1024 (2^10)(A 2 4) ; => 65536 (reduced to (A 1 16) = 2^16)(A 3 3) ; => 65536 (reduced to (A 2 4))(f n) computes 2n
(g n) computes 2^n
(h n) computes 2^(2^(2^(...^2)))Wikipedia tells me this last one is called tetration.
Another common pattern of computation: tree recursion. Consider the Fibonacci sequence. Can immediately transform the definition into a recursive procedure:
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
(fib 10) ; => 55In general, the evolved process looks like a tree. The branches split into two at each level. Reflects the fact that fib calls itself twice each time it is invoked.
This is a terrible way to compute Fibonacci numbers because it does so much redundant computation. The number of leaves in the tree (aka times (fib 1) or (fib 0) will be computed) is exactly Fib(n+1). The value of Fib(n) grows exponentially with n.
In general, the number of steps required by a tree-recursive process will be proportional to the number of nodes in the tree. The space required will be proportional to the maximum depth.
Can formulate an iterative process for Fibonacci numbers. Initialize a and b to Fib(1) = 1 and Fib(0) = 0, and repeatedly apply:
a <- a + b
b <- bAs a procedure:
(define (fib n)
(fib-iter 1 0 n))
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))
(fib 10) ; => 55Difference in number of steps for the two methods is huge (linear vs Fib(n)), even for small inputs.
Tree-recursive processes are still useful when operating on hierarchical data, instead of just numbers. And although the first fib procedure is less efficient, it is more straightforward.
How many different ways can we make change of $1.00, given half-dollars, quarters, dimes, nickles, and pennies? Can we write a procedure to compute the number of ways to change any given amount of money?
Simple recursive procedure solution: arrange the types of coins available in some order, then the number of ways to change amount a using n kinds of coins is:
a using all but the first kind, plusa - d using all n kinds of coins, where d is the denomination of the first kind of coinWe can use this to describe an algorithm if we specify the following degenerate cases:
a is exactly 0, count that as 1 way to make changea is less than o, count that as 0 ways to make changen is 0, count that as 0 ways to make change(define (count-change amount) (cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination
kinds-of-coins))
kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))To answer the original question about changing a dollar:
(count-change 100) ; => 292This generates a tree-recursive process, similar to first implementation of fib. But it is not obvious how to design a better algorithm.
A function f is defined by the rule that
f(n) = { n if n < 3, else f(n-1) + 2f(n-2) + 3f(n-3)Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.
Here's a recursive one:
(define (f n)
(cond ((< n 3) n)
(else (+ (f (- n 1))
(* 2 (f (- n 2)))
(* 3 (f (- n 3)))))))
(f 10)And here's an iterative one:
(define (g n)
(define (g-iter a b c count)
(cond ((= n 0) 0)
((= n 1) 1)
((= n 2) 2)
((= n count) (+ c (* 2 b) (* 3 a)))
(else (g-iter b c (+ c (* 2 b) (* 3 a)) (+ 1 count)))))
(g-iter 0 1 2 3))
(g 10)The following pattern of numbers is called Pascal's triangle.
.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it. Write a procedure that computes elements of Pascal’s triangle by means of a recursive process.
(define (P r c)
(cond ((<= r 0) 1)
((<= c 0) 1)
((>= c r) 1)
(else (+ (P (- r 1) (- c 1))
(P (- r 1) c)))))
(P 4 2)Prove that Fib(n) is the closest integer to phi^n/sqrt(5), where phi = (1 + sqrt(5))/2. Hint: Let psi = (1 - sqrt(5))/2. Use induction and the definition of the Fibonacci numbers (see Section 1.2.2) to prove that Fib(n) = (phi^n - psi^n)/sqrt(5).
I took a stab at this two mornings in a row but I relented and referred to the solution here.
Previous examples illustrate processes can differ considerably in rates at which they consume resources. One way to describe the difference is notion of order of growth.
Let n be a parameter that measures the size of the problem, and let R(n) be the amount of resources the process requires for a problem of size n.
Say R(n) has order of growth theta(f(n)), if there are positive constants k_1 and k_2 independent of n such that k_1f(n) <= R(n) <= k_2f(n) for any sufficiently large n.
Remainder of section 1.2 will examine two algorithms whose order of growth is logarithmic (doubling problem size increases resources by constant amount).
Draw the tree illustrating the process generated by the count-change procedure of Section 1.2.2 in making change for 11 cents. What are the orders of growth of the space and number of steps used by this process as the amount to be changed increases?
I drew the tree out on paper in 5 minutes, then I spent 45 minutes trying format it in ASCII here but I gave up.
I also totally botched the analysis. I should have been able to get that the space is O(n) (the max height of the tree). Apparently the time complexity is O(n^5) but I'm having trouble following that computation.
The sine of an angle (specified in radians) can be computed by making use of the approximation sin x ~= x if x is sufficiently small, and the trigonometric identity
sin x = 3 * sin(x/3) - 4 * sin^3(x/3)to reduce the size of the argument of sin. (For purposes of this exercise an angle is considered "sufficiently small" if its magnitude is not greater than 0.1 radians.) These ideas are incorporated in the following procedures:
(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
(if (not (> (abs angle) 0.1))
angle
(p (sine (/ angle 3.0)))))a. How many times is the procedure p applied when (sine 12.15) is evaluated?
b. What is the order of growth in space and number of steps (as a function of a) used by the process generated by the sine procedure when (sine a) is evaluated?
(sine 12.15)By substitution, it's easy to see p is applied 5 times.
I had trouble computing the complexity here as well. Initially I thought O(n) for each but they're actually O(log n), I could probably have gotten there if I really applied myself but I find myself not that motivated to solve these "mathy" problems as opposed to the "coding" ones (valuable as the skill may be). I plan on coming back to try these ones again.
Consider computing the exponential of a number. Would like a procedure that takes a base b and a positive integer exponent n and computes b^n. One way is via the recursive definition:
b^n = b * b^(n-1)
b^0 = 1which translates to the procedure
(define (expt b n)
(if (= n 0)
1
(* b (expt b (- n 1)))))
(expt 2 5) ; => 32This is linear recursive, requires O(n) steps and O(n) space. Can formulate an equivalent linear iteration:
(define (expt b n)
(expt-iter b n 1))
(define (expt-iter b counter product)
(if (= counter 0)
product
(expt-iter b
(- counter 1)
(* b product))))
(expt 2 5) ; => 32Requires O(n) steps and O(1) space.
We can compute exponentials in fewer steps with successive squaring.
(define remainder mod)
(define (square x) (* x x))
(define (fast-expt b n)
(cond ((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))
(define (even? n)
(= (remainder n 2) 0))
(fast-expt 2 5) ; => 32This process grows logarithmically with n in space and steps. The difference between O(log n) and O(n) becomes striking as n becomes large.
Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt.(Hint: Using the observation that (b^n/2)^2=(b^2)^n/2, keep, along with the exponent n and the base b, an additional state variable a, and define the state transformation in such a way that the product ab^n is unchanged from state to state. At the beginning of the process a is taken to be 1, and the answer is given by the value of a at the end of the process. In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerfulway to think about the design of iterative algorithms.)
Here's what I got. If we have variables a, b, and n, and we initialize a to 1, I think we should update:
a <- a * b^n if n even, else a * b
b <- b
n <- n/2 if n even, else n - 1Naively giving this algoritm:
(define (fast-expt-iter a b n)
(cond ((= n 0) a)
((even? n)
(fast-expt-iter (* a (fast-exp-iter 1 b (/ n 2))) b (/ n 2)))
(else (fast-expt-iter (* a b) b (- n 1)))))The problem is I'm using exponentiation in my update definition. So I think I lose tail recursion, and thus my algorithm is not iterative. Now I'm stuck.
Here's a correct answer:
(define (fast-expt-iter a b n)
(cond ((= n 0) a)
((even? n)
(fast-expt-iter a (b * b) (/ n 2)))
(else (fast-expt-iter (* a b) b (- n 1)))))Add it to the list of problems to revisit.
The exponentiation algorithms in this section are based on performing exponentiation by means of repeated multiplication. In a similar way, one can perform integer multiplication by means of repeated addition. The following multiplication procedure (in which it is assumed that our language can only add, not multiply) is analogous to the expt procedure:
(define (* a b)
(if (= b 0)
0
(+ a (* a (- b 1)))))This algorithm takes a number of steps that is linear in b. Now suppose we include, together with addition, operations double, which doubles an integer, and halve, which divides an (even) integer by 2. Using these, design a multiplication procedure analogous to fast-expt that uses a logarithmic number of steps.
(define (multiply2 a b)
(cond ((= b 0) 0)
((even? b) (multiply2 (double a) (halve b)))
(else (+ a (multiply2 a (- b 1)))))Using the results of Exercise 1.16 and Exercise 1.17, devise a procedure that generates an iterative process for multiplying two integers in terms of adding, doubling, and halving and uses a logarithmic number of steps.
The above is almost there.
(define (multiply3 a b)
(mult-iterative a b 0))
(define (mult-iterative a b n)
(cond ((= b 0) n)
((even? b) (mult-iterative (double a) (halve b) n))
(else (mult-iterative a (- b 1) (+ n a)))))There is a clever algorithm for computing the Fibonacci numbers in a logarithmic number of steps. Recall the transformation of the state variables a and b in the fib-iter process of Section 1.2.2: a <- a + b and b <- a.Call this transformation T, and observe that applying T over and over again n times, starting with 1 and 0, produces the pair Fib(n+1) and Fib(n). In other words, the Fibonacci numbers are produced by applying T^n, the nth power of the transformation T, starting with the pair (1, 0). Now consider T to be the special case of p = 0 and q = 1 in a family of transformations T_pq, where T_pq transforms the pair (a, b) according to a <- bq + aq + ap and b <- bp+aq. Show that if we apply such a transformation T_pq twice, the effect is the same as using a single transformation T_p′q′ of the same form, and compute p′ and q′ in terms of p and q. This gives us an explicit way to square these transformations, and thus we can compute T^n using successive squaring, as in the fast-expt procedure. Put this all together to complete the following procedure, which runs in a logarithmic number of steps:
(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
<??> ; compute p'
<??> ; compute q'
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))p' = p^2 + q^2
q' = 2qp + q^2
Here's the completed code:
(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))
(+ (* 2 q p) (* q q))
(/ count 2)))
(else
(fib-iter (+ (* b q)
(* a q)
(* a p))
(+ (* b p)
(* a q))
p
q
(- count 1)))))
(fib 10) ;=> 55The GCD of two integers a and b is the largest integer that divides both with no remainder. One way to find it is factor them and search for common factors, but there is a famous, more efficient algorithm.
Idea: If r is the remainder when a is divided by b, then the common divisors of a and b are the same as of b and r. Can successively reduce the problem to smaller pairs of integers. Eventually one is zero and the other is the GCD. Called Euclid's Algorithm.
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
(gcd 45 100) ; => 5Generates an iterative process, whose steps grow as the log of the numbers involved. This bears an interesting relation to Fibonacci numbers.
Lame's Theorem: If Euclid's algorithm requires k steps to compute the GCD of some pair, then the smaller number in the pair must be greater than or equal to the k^th Fibonacci number.
Can use this to get an order of growth estimate. O(log n).
The process that a procedure generates is of course dependent on the rules used by the interpreter. As an example, consider the iterative gcd procedure given above. Suppose we were to interpret this procedure using normal-order evaluation, as discussed in Section 1.1.5. (The normal-order-evaluation rule for if is described in Exercise 1.5.) Using the substitution method (for normal order), illustrate the process generated in evaluating (gcd 206 40) and indicate the remainder operations that are actually performed. How many remainder operations are actually performed in the normal-order evaluation of (gcd 206 40)? In the applicative-order evaluation?
This ones of good re-test of whether I actually understand normal vs applicative order.
(gcd 206 40)
(gcd 40 (rem 206 40))
(gcd (rem 206 40) (rem 40 (rem 206 40)))
(gcd (rem 40 (rem 206 40)) (rem (rem 206 40) (rem 40 (rem 206 40))))
(gcd (rem (rem 206 40) (rem 40 (rem 206 40))) (rem (rem 40 (rem 206 40)) (rem (rem 206 40) (rem 40 (rem 206 40)))))
(rem (rem 206 40) (rem 40 (rem 206 40)))
(rem 6 (rem 40 6))
(rem 6 2)
2Every step we compute the remainder of b to see if its zero, so 14 times on the first 6 lines, and then to actually compute the answer we call it another 4 times.
In applicative order we only call remainder 4 times.
Two methods for checking the primality of an integer n, one with order of growth O(sqrt(n)) and a "probabalistic" algorithm with order of growth O(log n).
One way to test if a number is prime is to find the divisors.
(define (smallest-divisor n) (find-divisor n 2))
(define (find-divisor n test-divisor)
(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))
(smallest-divisor 10) ;=> 2A number is prime if and only if it is its own smallest divisor.
(define (prime? n)
(= n (smallest-divisor n)))
(prime? 7) ; => trueNumber of steps in this case is order O(sqrt(n)).
Fermat's Little Theorem: If n is a prime number and a is any positive integer less than n, then a raised to the n^th power is congruent to a modulo n.
Two numbers are congruent modulo if they have the same remainder when divided by n.
If n is not prime, most numbers a < n will not satisfy the relation. Leads to the following algorithm: given a number n, pick a random number a < n and compute the remainder of a^n modulo n. If the result is not equal to a then n is not prime. If the result is equal to a, chances are good. By trying more and more values of a, can increase confidence in the result. Known as the Fermat test.
To implement, need a procedure that computes the exponential of a number modulo another number:
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder
(square (expmod base (/ exp 2) m))
m))
(else
(remainder
(* base (expmod base (- exp 1) m))
m))))Like fast-exp in Section 1.2.4. The number of steps grow logarithmically with the exponent.
Can use random to return a non-negative integer less than its input:
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))We run the test a given number of times, the value is true if the test succeeds every time, and false otherwise.
(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)))Fermat test differs in character from familiar algorithms, the answer is only probably correct (if n passes the test).
There do exist numbers that fool the test: numbers n that are not prime but have the property that a^n is congruent to a modulo n for all integers a < n. Such numbers are extremely rare, so the Fermat test is reliable in practice.
There are variations that cannot be fooled (see Exercise 1.28). The existence of tests for which one can prove the chance of error becomes arbitrarily small has sparked interest in probabilistic algorithms.
Use the smallest-divisor procedure to find the smallest divisor of each of the following numbers: 199, 1999, 19999.
Maybe the point is to trace these out but it doesn't say that so I just did it in the repl.
199 => 199, 1999 => 1999, 19999 => 7
Most Lisp implementations include a primitive called runtime that returns an integer that specifies the amount of time the system has been running (measured, for example, in microseconds). The following timed-prime-test procedure, when called with an integer n, prints n and checks to see if n is prime. If n is prime, the procedure prints three asterisks followed by the amount of time used in performing the test.
(define (timed-prime-test n)
(newline)
(display n)
(start-prime-test n (runtime)))
(define (start-prime-test n start-time)
(if (prime? n)
(report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
(display " *** ")
(display elapsed-time))Using this procedure, write a procedure search-for-primes that checks the primality of consecutive odd integers in a specified range. Use your procedure to find the three smallest primes larger than 1000; larger than 10,000; larger than 100,000; larger than 1,000,000. Note the time needed to test each prime. Since the testing algorithm has order of growth of O(sqrt(n)), you should expect that testing for primes around 10,000 should take about sqrt(10) times as long as testing for primes around 1000. Do your timing data bear this out? How well do the data for 100,000 and 1,000,000 support the O(sqrt(n)) prediction? Is your result compatible with the notion that programs on your machine run in time proportional to the number of steps required for the computation?
Pretty straightforward to extend the given code to loop through a range.
(define (search-for-primes start end)
(cond ((<= start end)
(timed-prime-test start)
(search-for-primes (+ start 2) end))
(else (newline))))Note that you have to make sure start is an odd number, I should probably add some handling for that.
The first 3 primes over 1000 are found to be 1009, 1013, 1019. Which all take 1-3 ms to find.
The first 3 over 10,000 are 10007, 10009, and 10037, which take 3-5ms.
The first 3 over 100,000 are 100,003, 100,019, and 100,043, which take 11-14ms.
The first 3 over 1,000,000 are 1,000,003, 1,000,033, and 1,000,037, which take 38-45ms.
We can see that this roughly bears out our prediction that our order of growth will be O(sqrt(n)). The square root of 10 is about 3 and every 10x increase in input takes about 3x as long. This is compatible with the notion that programs run in time proportional to the number of steps.
The smallest-divisor procedure shown at the start of this section does lots of needless testing: After it checks to see if the number is divisible by 2 there is no point in checking to see if it is divisible by any larger even numbers. This suggests that the values used for test-divisor should not be 2, 3, 4, 5, 6, ..., but rather 2, 3, 5, 7, 9, ...
To implement this change, define a procedure next that returns 3 if its input is equal to 2 and otherwise returns its input plus 2. Modify the smallest-divisor procedure to use (next test-divisor) instead of (+ test-divisor 1).With timed-prime-test incorporating this modified version of smallest-divisor, run the test for each of the 12 primes found in Exercise 1.22. Since this modification halves the number of test steps, you should expect it to run about twice as fast. Is this expectation confirmed? If not, what is the observed ratio of the speeds of the two algorithms, and how do you explain the fact that it is different from 2?
(define (next n)
(if (= n 2) 3 (+ n 2)))1009, 1013, and 10019, all still take 1-3 ms to find. Weirdly when running just timed-prime-test with these a single arg (instead of calling it from the search-for-primes loop),
the first time to find each takes ~10ms, but as you run it 3 or 4 times in the repl it drops to
1-3. I don't know why that is.
10007, 10009, and 10037 still take 3-5 ms, no observed speedup.
100,003, 100,019, and 100,043 take 7-11ms, so some speedup.
1,000,003, 1,000,033, and 1,000,037 take 21 -25ms.
As the input increases, we get closer to the predicted twice as fast speedup. I think that at lower numbers other factors like the time to print to the screen are a bigger factor, and the timer is probably less accurate.
Modify the timed-prime-test procedure of Exercise 1.22 to use fast-prime? (the Fermat method), and test each of the 12 primes you found in that exercise. Since the Fermat test has O(logn) growth, how would you expect the time to test primes near 1,000,000 to compare with the time needed to test primes near 1000? Do your data bear this out? Can you explain any discrepancy you find?
I'm not sure exactly what to set the number of tries to for the fermat test. Wikipedia seems to say that 1 is usually enough, I notice a couple false positives when doing that so I'm going to try 2.
1009, 1013, and 10019, all still take 1-3 ms to find. No observed speeed up.
10007, 10009, and 10037 take 2-4 ms.
100,003, 100,019, and 100,043 take 2-3ms.
1,000,003, 1,000,033, and 1,000,037 take 2-3ms.
When we say the fermat test has O(n) growth the n is referring to the number of iterations, which is fixed at 2 in my above test. So we would expect my above prime test to have a constant time complexity, any number I test will take the same amount of time. The trade off obviously is that there's a small chance of a false positive. But it's a pretty remarkable algorithm.
Alyssa P. Hacker complains that we went to a lot of extra work in writing expmod. After all, she says, since we already know how to compute exponentials, wecould have simply written
(define (expmod base exp m)
(remainder (fast-expt base exp) m))Is she correct? Would this procedure serve as well for our fast prime test? Explain.
I think the answer here is basically explained in footnote 46. Using the fast-exp version of exp-mod works for small numbers, but very quickly the exponential numbers we are dealing with are too large to represent accurately and we start failing to identify primes. The exp-mode version introduced in the text takes the modulo every step and so our numbers never grow much larger than m.
I think the problem here is that by multiplying explicitly we are creating a recursive tree and that will grow at O(n^2), cancelling out our O(log n) gains.
The function returns true for primes and for Carmichael numbers.
(define (carmichael-test n)
(define (fermat-test x y)
(= (expmod y x x) y))
(define (full-prime-test num count)
(cond ((= count 0) #t)
((fermat-test num count) (full-prime-test num (- count 1)))
(else #f)))
(full-prime-test n (- n 1)))I must confess I was unable to solve this one. I banged my head against it two mornings in a row but couldn't get a good understanding of the math going on. I think if I had sat down and worked the algorithm by hand with a bunch of numbers maybe I could have got there, but in the interest of keeping my momentum going I referred to the Codology solution here. I guess this is why I didn't go to MIT.