This shows you the differences between two versions of the page.
Next revision | Previous revision | ||
haas:spring2017:cprog:projects:mbe1 [2015/09/28 09:38] – external edit 127.0.0.1 | haas:spring2017:cprog:projects:mbe1 [2017/03/07 19:42] (current) – [Output Specification] wedge | ||
---|---|---|---|
Line 9: | Line 9: | ||
=====Objective===== | =====Objective===== | ||
- | To implement a programmatic solution (ie simulation) of a real life process- the mental math trick of multiplying any one- through eight-digit number by eleven. | + | To implement a programmatic solution (ie simulation) of a real life process- the mental math trick of multiplying any two- through eight-digit number by eleven. |
=====Prerequisites/ | =====Prerequisites/ | ||
Line 24: | Line 24: | ||
=====Background===== | =====Background===== | ||
- | In the **mbe0** project, we commenced our exploration of this multiply by 11 mental math trick. Using it as a playground for better understanding the newly introduced conditional (ie **if**) statement, we explored the mental math solving of " | + | In the **mbe0** project, we commenced our exploration of this multiply by 11 mental math trick. Using it as a playground for better understanding the newly introduced conditional (ie **if**) statement, we explored the mental math solving of " |
We explored single digit additions, a nostalgic throwback to 2nd/3rd/4th grade math, where we learned how any addition results in a one-digit sum as well as a one-digit carry. The sum occupies a place value in our answer, where the carry is applied to the addition of the next highest place value. | We explored single digit additions, a nostalgic throwback to 2nd/3rd/4th grade math, where we learned how any addition results in a one-digit sum as well as a one-digit carry. The sum occupies a place value in our answer, where the carry is applied to the addition of the next highest place value. | ||
- | It is hoped that by accomplishing **mbe0**, you both got in some good practice with **if** statements, utilizing math to aid you in per-digit numeric manipulations, | + | It is hoped that by accomplishing **mbe0**, you both got in some good practice with **if** statements, utilizing math to aid you in per-digit numeric manipulations, |
I am referring to **loops** and **arrays** | I am referring to **loops** and **arrays** | ||
Line 275: | Line 275: | ||
====Multiplying a number (of varying digits) by 11==== | ====Multiplying a number (of varying digits) by 11==== | ||
- | In **mbe0**, we specifically looked at 3 usage cases for our mental math problem: | + | In **mbe0**, we specifically looked at 2 usage cases for our mental math problem: 2- and 3-digit |
- | Now that we have those down, we can now apply arrays and loops to optimize and enhance a solution, and to allow it to scale to a wider range of possibilities (why limit ourselves to just 1-, 2-, and 3-digit values? Once we see the pattern, we can apply this to 4-, 5-, 6-digit numbers and beyond). | + | Now that we have those down, we can now apply arrays and loops to optimize and enhance a solution, and to allow it to scale to a wider range of possibilities (why limit ourselves to just 2- and 3-digit values? Once we see the pattern, we can apply this to 4-, 5-, 6-digit numbers and beyond). |
===3-digits (review)=== | ===3-digits (review)=== | ||
Again, to review, let's look at a 3-digit example. 123 x 11: | Again, to review, let's look at a 3-digit example. 123 x 11: | ||
- | <code> | + | <cli> |
- | 123 x 11 = 1 | + | |
- | = (1 + 0) (3 + 0) 5 | + | = |
- | = 1 | + | = 1353 |
- | | + | </cli> |
- | </code> | + | |
And digit-based additions that generate a carry are similarly propagated. | And digit-based additions that generate a carry are similarly propagated. | ||
Line 293: | Line 292: | ||
567 x 11: | 567 x 11: | ||
- | <code> | + | <cli> |
- | 567 x 11 = 5 | + | |
- | | + | = 5 11 13 7 |
- | | + | = (5+1) (1+1) 3 7 |
- | | + | = |
- | </code> | + | = 6237 |
+ | </cli> | ||
- | When doing this, we need to evaluate the number from right to left (just as we would do it if we were to compute it purely mathematically by hand): | + | Some things of note: |
* We know the last digit (1s place) of 567 x 11 right off the bat: 7 | * We know the last digit (1s place) of 567 x 11 right off the bat: 7 | ||
Line 314: | Line 314: | ||
4567 x 11: | 4567 x 11: | ||
- | <code> | + | <cli> |
- | 4567 x 11 = 4 | + | 4567 x 11 = |
- | = (4)+1 (9)+1 (11)+1 (13)+0 7 the numbers outside are the carry | + | = 4 |
- | = 5 | + | = 4 (9+1) (1+1) |
- | = 50237 | + | = |
- | </code> | + | = (4+1) 0 2 |
- | + | = | |
- | Remember, we are processing this from right to left (so that the carry values can properly propagate). While there is no initial carry coming in, we'll add one anyway (0), so we see 13+0 (which is simply 13)... but because we're interested in place values, this is actually a sum of 3, carry of 1... and that one gets sent over to the next place (which has an 11)... so 11+1 will be 12, or sum of 2, carry 1... that carry will propagate to the next position to the left (the 9)... so there' | + | = 50237 |
+ | </cli> | ||
Can you see how "the same" this process for 4-digit numbers is when comparing to the process for 3-digit numbers? And how the same comparison can be made for 2-digit, and 5-digit, 6-digit, etc.? Please take some time, working through some examples (by hand) to identify and notice the pattern, or essence, of this process. You need to see how it doesn' | Can you see how "the same" this process for 4-digit numbers is when comparing to the process for 3-digit numbers? And how the same comparison can be made for 2-digit, and 5-digit, 6-digit, etc.? Please take some time, working through some examples (by hand) to identify and notice the pattern, or essence, of this process. You need to see how it doesn' | ||
Line 327: | Line 328: | ||
That " | That " | ||
- | (Also, the potential exception here would possibly be 1-digit values... if you cannot easily find a way to make 1-digit numbers work with greater-than-1-digit numbers, that's where an if-statement would come into play-- if 1-digit, do this specific process, else do the regular process). I'm not saying one universal solution isn't possible, but at this stage of your structured programming development, | ||
=====Program===== | =====Program===== | ||
- | It is your task to write an optimized version of your multiply by eleven program that will use arrays and loops to enable you to enhance and expand the functional capabilities of your program. No longer will you be limited by 1-, 2-, or 3-digit numbers, but you will be able to input up to 8-digit numbers and have your program successfully determine the result (and 8 is merely an arbitrary value I picked, you should easily be able to up it to even more and experience no change in functionality) -- actually, our 8-digit limit is considering a data type limitation... the maximum size of an int: **signed int**s can have a maximum value of 2.4 billion, so unless we change to a different data type (or different method of inputting the source number), this will be our limitation. | + | It is your task to write an optimized version of your multiply by eleven program that will use arrays and loops to enable you to enhance and expand the functional capabilities of your program. No longer will you be limited by 2-, or 3-digit numbers, but you will be able to input up to (and including!) |
Your program should: | Your program should: | ||
* obtain its input from STDIN. | * obtain its input from STDIN. | ||
- | * input should be in the form of a single integer value | + | * input should be in the form of a single |
- | * determine the number of digits | + | * take this input, and split it up into individual |
- | * perform the correct algorithm against the input | + | * you may want to put the one's place in the right-most, or last, array position. |
- | * propagate any carries | + | * hint: you will want to make your arrays larger than the specified input number digit length. Why is this? What would that quantity of array elements be? |
- | * use an array (**digit**) to store individual digits from the number input | + | * perform the correct algorithm against the input: |
- | * use another | + | * generate carry values in an unsigned char **carry** array |
- | * hint: you will want to make the **result** array one element larger. Why is this? | + | * propagate carry values against the sum values in the **sum** array |
+ | * repeat until there are no further carry values to process | ||
* Display output showing aspects of the process (see example execution below) | * Display output showing aspects of the process (see example execution below) | ||
- | | + | |
+ | * Output | ||
=====Execution===== | =====Execution===== | ||
Line 351: | Line 353: | ||
lab46: | lab46: | ||
Enter value: 31415926 | Enter value: 31415926 | ||
- | Digits detected: 8 | + | 31415926 x 11 = |
- | + | | |
- | Obtaining unique digits, storing in array... | + | = 3 |
- | digit[0] | + | = 3 4 |
- | digit[1] = 2 | + | = 345575186 |
- | digit[2] = 9 | + | |
- | digit[3] = 5 | + | |
- | digit[4] = 1 | + | |
- | digit[5] = 4 | + | |
- | digit[6] = 1 | + | |
- | digit[7] = 3 | + | |
- | + | ||
- | Applying process... | + | |
- | result[0] = 6 + 0 + 0 (sum of 6, carry out of 0) | + | |
- | result[1] = 2 + 6 + 0 (sum of 8, carry out of 0) | + | |
- | result[2] = 9 + 2 + 0 (sum of 1, carry out of 1) | + | |
- | result[3] = 5 + 9 + 1 (sum of 5, carry out of 1) | + | |
- | result[4] | + | |
- | result[5] = 4 + 1 + 0 (sum of 5, carry out of 0) | + | |
- | result[6] | + | |
- | result[7] = 3 + 1 + 0 (sum of 4, carry out of 0) | + | |
- | result[8] = 3 + 0 + 0 (sum of 3, carry out of 0) | + | |
- | + | ||
- | Displaying result... | + | |
- | 31415926 x 11 = 345575186 | + | |
lab46: | lab46: | ||
</ | </ | ||
Line 384: | Line 366: | ||
lab46: | lab46: | ||
Enter value: 7104 | Enter value: 7104 | ||
- | Digits detected: 4 | + | 7104 x 11 = 7 (7+1) (1+0) (0+4) 4 |
- | + | = | |
- | Obtaining unique digits, storing in array... | + | = 78144 |
- | digit[0] = 4 | + | |
- | digit[1] = 0 | + | |
- | digit[2] = 1 | + | |
- | digit[3] | + | |
- | + | ||
- | Applying process... | + | |
- | result[0] = 4 + 0 + 0 (sum of 4, carry out of 0) | + | |
- | result[1] = 0 + 4 + 0 (sum of 4, carry out of 0) | + | |
- | result[2] = 1 + 0 + 0 (sum of 1, carry out of 0) | + | |
- | result[3] | + | |
- | result[4] = 7 + 0 + 0 (sum of 7, carry out of 0) | + | |
- | + | ||
- | Displaying result... | + | |
- | 7104 x 11 = 78144 | + | |
lab46: | lab46: | ||
</ | </ | ||
Line 409: | Line 377: | ||
lab46: | lab46: | ||
Enter value: 56789 | Enter value: 56789 | ||
- | Digits detected: | + | 56789 x 11 = 5 (5+6) (6+7) (7+8) (8+9) 9 |
+ | = | ||
+ | = (5+1) (1+1) (3+1) (5+1) | ||
+ | = | ||
+ | = 624679 | ||
+ | lab46: | ||
+ | </ | ||
- | Obtaining unique digits, storing in array... | + | The execution of the program is short and simple- obtain the input, do the processing, produce the output, and then terminate. |
- | digit[0] = 9 | + | |
- | digit[1] = 8 | + | |
- | digit[2] = 7 | + | |
- | digit[3] = 6 | + | |
- | digit[4] = 5 | + | |
- | Applying process... | + | ====Output Specification==== |
- | result[0] | + | As you can see, there' |
- | result[1] | + | |
- | result[2] | + | |
- | result[3] | + | |
- | result[4] | + | |
- | result[5] = 5 + 1 + 0 (sum of 6, carry out of 0) | + | |
- | Displaying | + | < |
- | 56789 x 11 = 624679 | + | Enter value: 967 |
+ | 967 x 11 = | ||
+ | = | ||
+ | = (9+1) (5+1) | ||
+ | = 10 | ||
+ | = | ||
+ | = | ||
+ | = 10637 | ||
+ | </ | ||
+ | |||
+ | With the exception of the final (packed together) 10637, everything is displayed to STDERR (that final 10637 is the **only** thing to display to STDOUT). | ||
+ | |||
+ | Some important things of note: | ||
+ | * The input value should be //right justified// in an 8 space allocated location to just before the " x 11". | ||
+ | * The equal sign has a space padding it on each side: " = " | ||
+ | * The output is calibrated for working with 5 digits. If there are no digits in those further left places, blanks must be displayed instead (in the 10637 example above, the first four lines are only dealing with 4 digits, until a carry propagates over to a 5th digit). | ||
+ | * Each digit of output needs to be calibrated to potentially display an addition operation, wrapped in parenthesis (as you see in the above example: (9+1) | ||
+ | * if only a single value is being displayed, it must appear where the ' | ||
+ | * if the number to display is a 2-digit number (10-19), its one's place needs to line up with the ' | ||
+ | * each digit space has a single space separating it from the next digit space. | ||
+ | * The final digit column (which should never have a carry) has a newline immediately following it (no trailing spaces). | ||
+ | * At the beginning, the leftmost and rightmost digits are displayed, with the additions visualized on the inner digits, according to the length. | ||
+ | * If there are any additions, the next line needs to show the result | ||
+ | * Following any result, carries should be checked for. If any carries are generated, a new line visualizing the additions must be displayed, then another line with the result. This process needs to propagate as many times as needed. | ||
+ | * Obviously, if the problem resolves sooner, it does, without needing to display those extra lines. Study the other execution examples, they demonstrate this. | ||
+ | |||
+ | You will probably find some application for selection statements, gaining further experience with them and likely deploying them with more sophisticated relational conditions (even compound ones). | ||
+ | |||
+ | Output formatting is still an important aspect to keep in mind. The computer needs to be told exactly what to do, and our default habits would likely be to do " | ||
+ | |||
+ | Another aspect of the output requirements is that they will force a focus on the individual steps of processing using this algorithm. This should help add exposure to developing good habits of ceasing to automatically read between the lines, and to identify and focus on the discrete steps needed to accomplish the task at hand. | ||
+ | |||
+ | =====Verification===== | ||
+ | Following are some procedures you can follow to verify if your program' | ||
+ | |||
+ | ====STDOUT verification of answer==== | ||
+ | As the final answer (and ONLY the answer) is to be output to STDOUT, your can run the following to check to see if this is the case with your program: | ||
+ | |||
+ | ===3-digit result=== | ||
+ | < | ||
+ | lab46: | ||
+ | 704 | ||
lab46: | lab46: | ||
</ | </ | ||
- | The execution | + | ===4-digit result=== |
+ | < | ||
+ | lab46: | ||
+ | 5632 | ||
+ | lab46: | ||
+ | </ | ||
+ | |||
+ | ===5-digit result=== | ||
+ | < | ||
+ | lab46: | ||
+ | 10197 | ||
+ | lab46: | ||
+ | </ | ||
+ | |||
+ | ====Total output comparison==== | ||
+ | If you'd like to check if the entirety | ||
+ | |||
+ | I have saved sample (correct) outputs on the system that you can check against. The following commands will let you do so: | ||
+ | |||
+ | ===First, save your output to a file=== | ||
+ | |||
+ | I have saved program | ||
+ | * 78 | ||
+ | * 143 | ||
+ | * 2600 | ||
+ | * 31337 | ||
+ | * 191919 | ||
+ | * 8763243 | ||
+ | * 31415926 | ||
+ | |||
+ | If you run your program with one of these same inputs, you can compare your results for correctness. | ||
+ | |||
+ | In the below example, I do this for an input value of 37: | ||
+ | |||
+ | < | ||
+ | lab46: | ||
+ | lab46: | ||
+ | </ | ||
+ | |||
+ | What we have done is fed in the input via a here string (form of STDIN redirect), and then output both STDERR and STDOUT into a common file (appending STDOUT, after the STDERR output). | ||
+ | |||
+ | You should now have a file called **output.78** in your current directory. | ||
+ | |||
+ | ===Next, check it against mine=== | ||
+ | I have these files (by the same names), saved in the CPROG Public Directory (under the **mbe1** directory). | ||
+ | |||
+ | By using the **diff** command, you can see differences, | ||
+ | |||
+ | < | ||
+ | lab46: | ||
+ | lab46: | ||
+ | </ | ||
+ | |||
+ | If you see output, that means there are differences, | ||
+ | |||
+ | You can repeat this for the other data files (output.78 for an input of 78, etc.) | ||
+ | |||
+ | ===Isolate just the STDOUT or the STDERR=== | ||
+ | Additionally, | ||
+ | |||
+ | To do this, you can do the following. | ||
+ | |||
+ | To isolate STDOUT and STDERR into separate files, you can do the following: | ||
+ | |||
+ | < | ||
+ | lab46: | ||
+ | lab46: | ||
+ | </ | ||
+ | |||
+ | You can then compare those particular collections of information against my copies (located in the **mbe1** subdirectory of the CPROG Public Directory, by the same file names). | ||
+ | |||
+ | ====automated verification==== | ||
+ | I have rigged up **pchk** to work for this project; it will check for differences and compare MD5sum hashes for stderr, stdout, and total (combined) output. | ||
+ | |||
+ | Once you have everything complete, this is a good final check to do to ensure everything is in order. | ||
+ | |||
+ | < | ||
+ | lab46: | ||
+ | ===================================================== | ||
+ | = mbe1 output validation check = | ||
+ | ===================================================== | ||
+ | |||
+ | | ||
+ | [78] | ||
+ | | ||
+ | |||
+ | | ||
+ | [143] stdout diff: MATCH stdout md5sum: MATCH | ||
+ | | ||
+ | |||
+ | | ||
+ | [2600] | ||
+ | | ||
+ | |||
+ | | ||
+ | [31337] | ||
+ | | ||
+ | |||
+ | | ||
+ | [191919] | ||
+ | | ||
+ | |||
+ | | ||
+ | [8763243] | ||
+ | | ||
+ | |||
+ | | ||
+ | [31415926] stdout diff: MATCH stdout md5sum: MATCH | ||
+ | | ||
+ | ===================================================== | ||
+ | = matches: 42, mismatches: | ||
+ | ===================================================== | ||
+ | lab46: | ||
+ | </ | ||
+ | |||
+ | Since your project submission will be evaluated in part by compliance to output specifications, | ||
=====Submission===== | =====Submission===== | ||
Line 437: | Line 557: | ||
* Code must compile cleanly (no warnings or errors) | * Code must compile cleanly (no warnings or errors) | ||
+ | * I will be compiling as follows: gcc -Wall --std=c99 -o mbe1 mbe1.c | ||
* Output must be correct, and resemble the form given in the sample output above. | * Output must be correct, and resemble the form given in the sample output above. | ||
* Code must be nicely and consistently indented (you may use the **indent** tool) | * Code must be nicely and consistently indented (you may use the **indent** tool) | ||
Line 457: | Line 578: | ||
You should get some sort of confirmation indicating successful submission if all went according to plan. If not, check for typos and or locational mismatches. | You should get some sort of confirmation indicating successful submission if all went according to plan. If not, check for typos and or locational mismatches. | ||
+ | |||
+ | What I'll be looking for: | ||
+ | |||
+ | < | ||
+ | 78: | ||
+ | *: | ||
+ | *: | ||
+ | *: | ||
+ | *: | ||
+ | *:mbe1:sum array used appropriately in processing [8/8] | ||
+ | *: | ||
+ | *: | ||
+ | *: | ||
+ | *: | ||
+ | *: | ||
+ | *:mbe1:no negative compiler messages for code [3/3] | ||
+ | *:mbe1:code is pushed to lab46 repository [4/4] | ||
+ | </ |