CSE 341 - Spring 2002 - Assignment 2 - Miranda continued

Due April 19, at the beginning of class. Please submit all of your function definitions in one code file and your testing output in a separate file. Use comments to clearly indicate which problem number each section of code/output matches.

Suggestion: you know enough already to do the first question -- do this one one now, and get it out of the way. We'll talk about the second question in lecture and quiz section, since it's more complex.

  1. A perfect number is a number n that is the sum of all of its divisors (excluding n itself). The first four perfect numbers are:

    6 = 1 + 2 + 3
    28 = 1 + 2 + 4 + 7 + 14
    496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248
    8128 = 1 + 2 + 4 + ... + 64 + 127 + ... + 4064

    Write and test a Miranda script to print the list of all perfect numbers. (It is conjectured that there are an infinite number of them, but this has not been proven. It is also not known whether there are any odd perfect numbers - although if there are, they are very large.)

    Strive for elegance and brevity in your script -- efficiency is not a consideration for this problem. (So it's fine if your script prints out the first 3 perfect numbers, and then sits computing for a long time until someone gets annoyed at you for hogging all the cycles on the instructional linux server. Type control-c at this point to terminate the computation and restore peace in the ugrad lab.) Hint: see the factors function in the lecture notes.

  2. Write and test a Miranda function multiply that multiplies two polynomials in x and returns the result. The two polynomials should be represented as strings. For example:
    multiply "x^3 + x^2 + x + 1"  "x - 1"    =>
    "x^4 - 1"
    
    Here are some polynomial pairs to test your function on:
    "x^3 + x^2 + x + 1"
    "x - 1"
    
    "-3*x^3 + x + 5"
    "0"
    
    "x - 1 + x^3"
    "-5"
    
    "-10*x^2 + 100*x + 5"
    "x^9999 - x^7 - x^5 + x + 3"
    

    In general each string representing a polynomial will consist of a series of terms, separated by + or - signs. Each term will have an integer coefficient (assumed to be 1 if absent), followed by the letter x, followed by the symbol ^, followed by an integer exponent. If the ^ is missing, the exponent defaults to 1. If the x and exponent are both missing, the term is a constant. The terms can occur in any order in the input. You don't have to check for bad inputs.

    For the output, you should print out the terms with the highest exponent first. Omit terms with a coefficient of 0. If the coefficient or exponent is 1, omit it. If the exponent is 0, omit the "x^0" and just print the coefficient, unless it's 0. However, if the entire polynomial is equal to 0, print a "0". For example, here are some correctly formatted output polynomials:

    -3*x^3 + x^2 - x + 1
    100
    0
    x^9999 - 5*x^7 + 4*x^5
    

    To help you get started, there is a skeleton program ~borning/miranda/poly.m on ceylon, which includes comments explaining what is there and what you need to add. You can use this if you like, or write your own solution from scratch. (Personally, I'd start with the skeleton program.)

    Hint: in either case, write your program incrementally, testing as you go. For example, if you start with the skeleton, first just run what's there and make sure you understand it. Also try the different pieces: try the polyscan and string2poly functions separately. Then write and test a poly2string function. For example, you could test it using expressions such as poly2string (string2poly "-3*x^3 + x + 5"). Finally, write the polymult function, and test the whole program.