|
|
15292
SPRING 2020
|
Charles Babbage's Difference Engine computed the values of a polynomial f(x) of up to degree 7 using the method of finite differences. For example, if f(x) = x2 + 3x + 4, then Δf(x) = 2x + 4 and Δ2f(x) = 2. So the initial settings of the columns of the machine (when x = 0) would be:
4 4 2 0 0 0 0 0
If the machine is cranked three times, then the results in the columns would be
22 10 2 0 0 0 0 0
This shows that f(3) = 22 which you can confirm if you plug 3 into the original f(x) above.
Write a computer program that asks the user for the initial settings for each of the 8 columns of the machine (one for the function value and 7 for the difference functions of order 1 through 7, as discussed in class. These input values should represent the values of the respective functions evaluated at x = 0. Note that you are not inputting the original function nor its difference functions. You may assume all inputs are non-negative.
The program should then ask the user how many times the machine should be cranked. One "crank" represents a complete cycle of the machine that advances the machine from f(x) to f(x+1). The results of the columns should be displayed VERTICALLY, as they would have appeared on the real machine.
Your program must use the method of finite differences to compute the results, as Babbage's machine would have done once it was set to its initial values.
IMPORTANT: Your input must follow the formatting shown below exactly for full credit, including prompts and spacing, since we will essentially do a UNIX diff of your output and ours to see if they match for various test cases. User input in the example below is in red italics for clarity only. Your input does not need to be red nor in italics.
Enter f(0): 4 Enter delta f(0): 4 Enter delta2 f(0): 2 Enter delta3 f(0): 0 Enter delta4 f(0): 0 Enter delta5 f(0): 0 Enter delta6 f(0): 0 Enter delta7 f(0): 0 Enter number of cranks: 3 Final machine results: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 2 0 2 0 0 0 0 0
(The first column shows f(3) = 22, the second column shows Δf(3) = 10, and the third column shows Δ2f(3) = 2.)
Note that for the machine results, each column is one digit wide, columns are separated by 3 spaces, and the last column has NO extra space to its right. Each line of the machine results should end with a newline character, including the LAST line. You may assume that the output will never be more than 5 digits per column for this assignment.
You are allowed to use Python 3, Java, or C for your code, and it should run on the Andrew server cluster. You should include a README.txt file that gives instructions on how to compile, run, and interact with your program on the command line, and explain what each file does if you include more than one file.
Zip up all file(s) that are required to run your program and hand in to Autolab (on andrew). You do not need to hand in any library files that are standard to the language you are using. If you're not sure, ask. Your submission should be a zip file ending in the suffix .zip . Autolab will NOT autograde your program; you are only using Autolab to hand in your code. You may submit as many times as you wish, but we will grade your last submission only.
Assignments will be graded out of 100 points. Ten points will be reserved for program style. In this assignment, there is a lot of potential repetition and code reuse, so well-written programs will receive more points than poorly written ones. Programs may be submitted up to one lecture late with a 20% penalty.
Assignments that do not meet the input and output specification will be penalized, so please be careful when you're writing this program. Test your program on the example above and compare it using "diff" on the Andrew server with this sample program run or this sample program run to make sure that your formatting is correct. Then test a number of examples to be sure your program is working correctly.