Lab 22: Generating Numbers

Implement this lab with the Intermediate Student Language with Lambda.

Make sure you follow The Style we use for the {B,I,A}SL{,+} languages in this class.

Choose the initial Head and Hands, and get started!

Special Numbers

Each number Fibn in the Fibonacci sequence is the sum of the two previous numbers Fibn-1 and Fibn-2. The first two Fibonacci numbers Fib0 and Fib1 are 0 and 1.

Ex 1: Design the function fib that, given a number n, returns Fibn.

Ex 2: Design a function fibs that given a natural n, returns the list of all Fibonacci numbers less than or equal to n.

A Natural n is prime if it has no divisors other than 1 and itself.

Ex 3: Design a function prime? that returns #true only if the given natural number n is prime. To do so, build a list of all naturals greater than 1 and less than n and test each to see if any numbers in the list is a factor of n.

Ex 4: Re-implement your prime? function to take advantage of the fact that only trial factors less than (sqrt n) need be considered.

Ex 5: Design a function primes that given a natural n, returns the list of all prime numbers less than or equal to n.

Out, Out, Brief Candle

Below is a description of a simple function a implemented with addition and subtraction. It is not implemented with the standard structural recursion over the naturals.

Ex 6: Design the function a. Keep your tests small: the result of (a 4 2) is a number with 19,729 digits and will take a bit too long to calculate during this lab.

Ex 7: Does the function a terminate on all possible inputs? Discuss this with your partner and come up with an argument in one direction or the other.

Hint: Structural recursion always terminates because we’re always making progress toward the base case. With generative recursion, progress can be a bit more obscure. Does the function a always make progress toward some base case when called recursively?

If you finish early...

Try to improve the speed of prime? by implementing a faster prime number test.