University of Delaware CISC 108: Introduction to Computer Science I Fall 2016
Goals:
Lab 11
0. Goals and Instructions
• designing functions using accumulators • analyzing memory-e ciency.
Instructions: Work with your partner. Using Sakai, turn in a file lab11.rkt containing all code and documentation for this assignment; turn in a separate file project2-start.rkt for the last question. Both partners’ names must be listed in a comment at the top of each file.
1. Memory consumption
Recall that computer scientists are interested in two very important issues regarding the relative
e ciency of the programs that they write:
(1) How much time will it take?
(2) How much physical computer memory (“space”) will it take?
Recall the function slow-expt from Lab 10? It consumes a number b (the base) and a natural number n (the exponent) and computes bn (b raised to the n-th power). The definition uses the standard natural number template to perform n multiplications:
(define (slow-expt b n) (cond [(zero? n) 1]
[else (* b (slow-expt b (sub1 n)))]))
In Lab 10, you observed (using the Stepper), that in the course of evaluating a call to slow-expt, the multiplications “stack up”. For example, the evaluation of (slow-expt 2 5) goes through a series of stages that look like this:
(slow-expt 2 5) --> (* 2 (slow-expt 2 4)) --> (* 2 (* 2 (slow-expt 2 3))) --> (* 2 (* 2 (* 2 (slow-expt 2 2)))) --> (* 2 (* 2 (* 2 (* 2 (slow-expt 2 1))))) --> (* 2 (* 2 (* 2 (* 2 (* 2 (slow-expt 2 0)))))) --> (* 2 (* 2 (* 2 (* 2 (* 2 1))))) --> (* 2 (* 2 (* 2 (* 2 2)))) --> (* 2 (* 2 (* 2 4))) --> (* 2 (* 2 8)) --> (* 2 16) --> 32
Imagine if you were doing this computation with pen and paper. What a waste of ink and paper! There is no reason to write out all those “* 2”s. If you were computing 2 to the one-million this way, your paper would need to be wide enough to hold one million *s and 2s. But there is no reason to be so wasteful. A more sane computation would look something like this:
1
2
25 =1⇤25 =2⇤24 =4⇤23 =8⇤22
=16⇤21 =32⇤20
=32
This way, the “width” of the stages is constant: at each point you just have to keep track of two numbers: the current accumulated product (1, 2, . . . , 32) and the remaining exponent (5, 4, . . . , 0).
Like paper and ink, computer memory is a valuable resource. The memory required to evaluate a call to (slow-expt b n) is proportional to n. We say this function uses O(n) memory, or that it uses “linear memory.” The definition follows the natural “linear recursive” template.
You should aim to design functions that use as little memory as possible. This is one motivation for writing functions in accumulator style.
2. Problems
Problem 1. Design a function iter-expt that raises b to the n-th power. Instead of using the
natural (linear recursive) template on n, use an accumulator with an auxiliary function as follows:
(define (iter-expt b n) (local
[ ; ie-aux: NatNum Number -> Number
(define (ie-aux counter product) ...)
]
(ie-aux n 1)))
Function ie-aux is a recursive function. It consumes a natural number counter, and a product (the accumulator). If the counter is 0, then ie-aux returns the product. Otherwise, ie-aux makes a recursive call, decrementing the counter and multiplying the base times the product. This is similar to our natural recursion, but the part about updating product to (* base product) is quite di↵erent. Some examples:
(ie-aux 0 product) --> product (ie-aux counter product) --> (ie-aux (sub1 counter) (* base product))
In this case, the multiplication and decrementing of the counter both occur before the recursive call. If you’ve written programs in a traditional imperative programming language, this is equivalent to something like a “for loop”.
for counter = start downto 0 {
counter <- counter - 1; // new counter is subtract one from the old counter
product <- product * base; // new product is multiply the current product by the base
}
After you have developed and tested the function, copy and paste the definition and (iter-expt 2 5) into a temporary Dr.Racket document. Evaluate in the Stepper. Notice anything di↵erent??? This is called tail recursion. Enter as a comment in your main file an explanation of what you observed and how it di↵ers from the linear recursive solution. How much memory (big-O) does the tail recursive algorithm require?
Note that the amount of time required by slow-expt and iter-expt is the same: O(n) (“linear time”) in both cases.
You do not have to turn in the temporary file.
Problem 2. Design a function linear-sum which consumes a natural number n and returns the sum of the natural numbers up to and including n. This function should follow the standard “linear recursive” template. Then design a function accum-sum which does the same thing but uses accumulator style and is “tail-recursive”.
Problem 3. The following formula, which provides a way to compute ⇡ based on an infinite series, is due to Madhava of Sangamagrama (1340-1425); see https://en.wikipedia.org/wiki/ Madhava_of_Sangamagrama:
⇡ = 4 X1 ( 1)i+1 i=1 2i 1
= 4(1/1 1/3+1/5 1/7+…).
(Note: Dr.Racket also has an approximate value of ⇡ stored in a constant called pi.)
Design a tail-recursive function pi-approx which consumes a natural number n and returns the approximation to ⇡ obtained using the first n terms of this series. Because Dr.Racket’s exact numbers are very expensive (in terms of time and memory), you should convert the intermediate result to an inexact number at each stage using exact->inexact. Once you have done this correctly, you should be able to call the function on n = 10000000 (ten million). What is the result? (Put the answer in a comment.)
Problem 4.
(a) Following the linear-recursive template, design a function called partition/template that accepts as input a predicate (i.e., a function that accepts an X and produces a Boolean) and a list of X and produces as output a list of two elements. The first element should be a list containing the elements of the given list that satisfy the predicate (in the same order as the given list) and the second element should be a list containing the elements of the given list that do not satisfy the given predicate (in the same order as the given list). For example:
(check-expect (partition/template positive? (list -2 -1 0 1 2))
(list (list 1 2) (list -2 -1 0)))
(check-expect (partition/template even? (list -2 -1 0 1 2))
(list (list -2 0 2) (list -1 1)))
In a comment, indicate the abstract memory usage and abstract runtime of partition/template.
(b) Create a copy of partition/template called partition/local. Using local, refactor partition/local to reduce its execution time. In a comment, indicate the abstract memory usage and abstract run-
time of partition/local.
3
4
(c) Develop an accumulator-style, tail recursive version of partition/template called partition/accumulator. In a comment, indicate the abstract memory usage and abstract runtime of partition/accumulator.
Problem 5. Turn in a separate file, project2-start.rkt, with your initial project code for Lab 11. We expect to see at least an outline of your solution and data definitions and examples for the most important types.
3. Extra Credit
Problem 6. Develop iter-fast-expt, that is, a function that uses both the fast-expt log n time trick from Lab 10, and the iter-expt iteration constant space trick. The built-in expt function in Racket (and most other languages) uses both of these tricks.