In this problem we wish to make an application of polynomial arithmetic to do representations of decimal values in an arbitrary base as well as converting arbitrary base representations to decimal values. Springer and Friedman, in Section 5.4 of the text, show that converting a base b representation to a decimal value is just a matter of evaluating the polynomial whose coefficients are the corresponding digits of the base b representation at the value x = b.

For example, if we consider the base 3 value 1 2 1, this value determines a polynomial

x² + 2x + 1

which we evaluate at x = 3 to produce a decimal value of 16.

Similarly, if we start with the decimal value of 16, and wish to produce a 3 digit base three representation of 16, then we perform the following steps:

(1) Divide 16 by 3 producing a quotient of 5 and a remainder of 1. The least significant digit of the 3 digit base 3 representation of 16 is this remainder.

(2) Divide the previous quotient 5 by 3 producing a quotient of 1 and a remainder of 2. The next least significant digit of the 3 digit base 3 representation of 16 is this remainder.

(3) Divide the previous quotient 1 by 3 producing a quotient of 0 and a remainder of 1. The next least significant digit of the 3 digit base 3 representation of 16 is this remainder.

Next, we notice that we can undo the above process to produce a more efficient conversion from a base b representation to a decimal value. This process, which is illustrated in the following example, is called Horner's method for evaluating a polynomial.

To convert the base 3 value 1 2 1 to decimal, perform the following steps:

(1) Start with the most significant digit, 1, and multiply by the base 3; then add the next least sigficant digit 2 producing a value of 5.

(2) Multiply the previous term, 5, by the base 3 and add the next least significant digit 1, producing a value of 16.

Write two functions having the following form:

(define representation

(lambda (base-list decimal-value)

...))

(define base-value

(lambda (base-list digit-list)

...))

which provide an efficient implementation of the above two algorithms. For example:

(representation '(3 3 3) 16) ==> (1 2 1)

(base-value '(3 3 3) '(1 2 1)) ==> 16

Notice that these two functions are mathematical inverses of the other function.

(representation '(3 3 3) (base-value '(3 3 3) '(1 2 1))) ==> (1 2 1)

(base-value '(3 3 3) (representation '(3 3 3) 16))

==> 16

Analyze the performance of your functions. Next, consider what happens if the values in the base-list are not all the same value. Describe an application of the case where the base-list values are not all the same.