Sample Problem Design the function power, which computes the first number to the power of the second number using multiplication.

; power : Nat Nat -> Nat

; Compute n^m using '*'

(check-expect (power 2 5) 32)

(check-expect (power 3 2) 9)

(define (power n m)

(cond [(zero? m) 1]

[else (* n (power n (sub1 m)))]))

Sample Problem Design power-fast which uses a method of repeated squaring to calculate the answer to the same problem. The basic rules of repeated squaring are:

• X2Y = (XY)*(XY)

• X2Y+1 = X*(X2Y)

; power-fast : Nat Nat -> Nat

; Compute n^m using rules of repeated squaring

(check-expect (power-fast 2 5) 32)

(check-expect (power-fast 3 2) 9)

(define (power-fast n m)

(cond [(zero? m) 1]

[(zero? (modulo m 2))

(local [(define halfpower (power-fast n (/ m 2)))]

(* halfpower halfpower))]

[else (* n (power-fast n (sub1 m)))]))

; digit->string : Nat -> String

; Turn a single digit number into a single char string

(check-expect (digit->string 5) "5")

(check-expect (digit->string 0) "0")

(define (digit->string n)

(string (integer->char (+ 48 n))))

Exercise 1 Design the function num->string that returns the string representation of a natural number. What is the base case for this function? What can we do to get from one digit to the next? Here are some tests for num->string:

(check-expect (num->string 0) "0")

(check-expect (num->string 5) "5")

(check-expect (num->string 1234) "1234")

(check-expect (num->string 4321) "4321")