SICP

Exercise 2.96. a.    Implement the procedure  pseudoremainder-terms , which is just like  remainder-terms  except that it multiplies the dividend by the integerizing factor described above before calling  div-terms . Modify  gcd-terms to use  pseudoremainder-terms , and verify that  greatest-common-divisor  now produces an answer with integer coefficients on the example in exercise  2.95 . b.    The GCD now has integer coefficients, but they are larger than those of  P 1 . Modify  gcd-terms  so that it removes common factors from the coefficients of the answer by dividing all the coefficients by their (integer) greatest common divisor. SOLUTION The code is here: Exercise 2.96 pseudoremainder Both part a and b of the exercise are verified in the tests. The final result is equal to polynomial P1 from exercise 2.95.

Exercise 2.95.   Define  P 1 ,  P 2 , and  P 3  to be the polynomials Now define  Q 1  to be the product of  P 1  and  P 2  and  Q 2  to be the product of  P 1  and  P 3 , and use  greatest-common-divisor  (exercise  2.94 ) to compute the GCD of  Q 1  and  Q 2 . Note that the answer is not the same as  P 1 . This example introduces noninteger operations into the computation, causing difficulties with the GCD algorithm. 61  To understand what is happening, try tracing  gcd-terms  while computing the GCD or try performing the division by hand. SOLUTION See here: SICP Exercise 2.95 You can see from the result that the gcd algorithm is not working properly. The result is just a number which is clearly wrong. The 'print-poly' procedure came in very handy here. I could print the various stages of polynomials in a readable format.

Exercise 2.94.    Using  div-terms , implement the procedure  remainder-terms  and use this to define  gcd-terms  as above. Now write a procedure  gcd-poly  that computes the polynomial GCD of two polys. (The procedure should signal an error if the two polys are not in the same variable.) Install in the system a generic operation  greatest-common-divisor  that reduces to  gcd-poly  for polynomials and to ordinary  gcd  for ordinary numbers. As a test, try (define p1 (make-polynomial 'x '((4 1) (3 -1) (2 -2) (1 2)))) (define p2 (make-polynomial 'x '((3 1) (1 -1)))) (greatest-common-divisor p1 p2) and check your result by hand. SOLUTION The implementation is here: SICP Exercise 2.94 This problem was straightforward.

Exercise 2.93.   Modify the rational-arithmetic package to use generic operations, but change  make-rat  so that it does not attempt to reduce fractions to lowest terms. Test your system by calling  make-rational  on two polynomials to produce a rational function (define p1 (make-polynomial 'x '((2 1)(0 1)))) (define p2 (make-polynomial 'x '((3 1)(0 1)))) (define rf (make-rational p2 p1)) Now add  rf  to itself, using  add . You will observe that this addition procedure does not reduce fractions to lowest terms. SOLUTION The solution is here: SICP Exercise 2.93

Exercise 2.92.   By imposing an ordering on variables, extend the polynomial package so that addition and multiplication of polynomials works for polynomials in different variables. (This is not easy!) SOLUTION It was long overdue but I moved all my code to github. The solution to this problem is here: SICP Exercise 2.92 (I plan to modularize my code now that it is in github. This will allow me to maintain reusable code and hopefully no clones.) This problem was quite hard and took me several days to solve correctly. Right in the beginning, I decided to write a 'convert' procedure that 'casts' a polynomial in one variable to the same polynomial in a different variable by re-arranging the terms. In this procedure I needed to account for the fact that the coefficients of a polynomial can themselves be polynomials. This 'polynomials inside a polynomial' can go to any depth. The hardest part was to find a clean, generic way to do the multiplying and re-...