Foundations of Programming 2023-2024 Term-2 Assignment - Contains 100 points Introduction The following algorithm converts a decimal number x (with 0≤x≤ 1) into a string containing the representation of x

in another base b (with b one of {2,3,4,..., 16}): Base-Conversion ALGORITHM 1. Let x be the decimal number to be converted and b the base we are converting it to. 2. Lets be the string "0." (s contains the result which we are going to build, as follows): Repeat the following three steps, and stop only when x equals 0: 3. i) Let d = int(x * b) (i.e., be the integer part of the product of x by b) ii) Append d to the right of the current string s (but see note [*] below) iii) x = x - d [*]: in step 3.ii) above, if d is larger than 9, the character to be added to the string s is not d itself but the corresponding letter in the second row of the following table: Value of d Character to be added to s 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 A B C D E F Example - use the above algorithm to convert x = 0.875 (decimal) into its base- 14 equivalent representation. • Steps 1-2: Let x = 0.875, b = 14. Let s initially be the string "0." • Step 3: because currently x = 0, we execute steps i) — iii) once (1st iteration): i) d = int(0.875 x 14) = int(12.25) = 12 ii) Using the above table, we see that we should append C to s → The new s becomes "0.C" iii) x = x - d = (12.25 – 12) = 0.25 • Step 3: because currently x = 0, we execute steps i) — iii) again (2nd iteration): i) d= int(0.25 x 14) = int(3.5) = 3 ii) Using the above table, we see that we should append 3 to s → The new s becomes "0.C3" iii) x = x - d = (3.5-3) = 0.5 • Step 3: because x = 0, we execute steps i) — iii) again (3rd iteration): i) d = int(0.5 x 14) = int(7.0) = 7 ii) Using the above table, we see that we should append 7 to s → The new s becomes "0.C37" iii) x = x -d=(7.0-7)= 0 • Step 3: Because x is 0, we stop ➜ The final result is the current value of s (i.e, "0.C37") To conclude, 0.87510 = 0.C3714 P.T.O. PART A (30 points): Implement the "BASE CONVERSION" algorithm in Python, Version 3.7.x. Your code must stop after computing at most 20 digits after the decimal point of the result. You may assume that the float x the user enters includes up to 5 digits after the point. USER-INTERFACE SPECIFICATIONS Your program should ask the user to enter the number x to be converted and the base b to convert it to (in this order). It should then print the result and stop. No input validation is required: you may assume the user will enter valid values for x (a float such that 0≤x < 1) and for b (an integer such that 1< b < 17). Here is what a single run of your program should look like: Please enter a decimal number between 0 and 1: Please enter the new base b (between 2 and 16): 0.4375 (in base 10) = 0.61A7 (in base 14) Goodbye. Any violations of the above requirements will lead to a 40-marks penalty. PART A1 (30 points) Because the precision of physical calculators is necessarily limited, the standard Python installation (Ver. 3.7.x) comes with minute (yet non-negligible) approximation errors. E.g., typing the simple operation (1.6 – 1) on the command line of the Python shell (Ver. 3.7.x) produces the result 0.6000000000000001, instead of the correct value 0.6. Ensure that your code avoids such errors, so that, when run in Python Ver. 3.7.x, the result produced is correct up to (and including) the 20th digit after the decimal point. For example, converting 0.999 to its equivalent in base 8 should produce exactly "0.999 (base 10) = 0.77737166621320712601 (base 8)" and not, for example, "0.999 (base 10) = 0.77737166621320712600 (base 8)" or, analogously, 0.777371666213207126, both of which are correct only up to the 19th digit. It is your responsibility to ensure that your code works correctly in Python Ver. 3.7.x. You are strongly advised to check your code's results against those provided in the examples below (e.g, by testing it on a Computing-Lab machine) prior to submitting it. EXAMPLES (with correct responses) for TESTING your PART-A/A1 code: 0.25 (base 10) = 0.1 (base 4) = 0.2 (base 8) = 0.A (base 16) 0.625 (base 10) 0.4375 (base 10) 0.03125 (base 10) = 0.101 (base 2) = 0.61A7 (base 14) =0.046 (base 12) = 0.2343 (base 6) = 0.061A7 (base 14) 0.99 (base 10) 0.143 (base 10) 0.5001 (base 10) 0.49991 (base 10) = 0.CB4050BAA36826157892 (base 13) = 0.11115645706517676355 (base 8) = 0.33335115660113533135 (base 7) = 0.55542007223166010073 (base 11) = 0.ECB3B3B3B3B3B3B3B3B3 (base 15) = 0.01021202020000120022 (base 3) = 0.44451357148412886136 (base 9) = 0.22222102132441021324 (base 5) VERY IMPORTANT: The use of the import statement (i.e., of any Python module) is strictly FORBIDDEN. Using recursion is also FORBIDDEN. Violating either of these requirements will incur in a penalty of 80 MARKS. PART B (40 points) - Coping with periodic expansions The "Base Conversion” Algorithm on p. 1 suffers from a serious problem: it could continue forever. (In fact, this is the reason for requiring that your PART-A/A1 code stop after having produced a maximum of 20 digits after the decimal point). To understand why this can happen, consider the conversion of the float 0.01 into, e.g., its base-7 equivalent: Step 3, 1st iteration: x = 0, so we multiply x by the base b (7) and use the integer part of the result: Because 0.01 x 7 = 0.07, the first digit to be appended to s is 0, and the new value of x is 0.07 So far, 0.01 (base 10) = 0.0... (base 7) - Step 3, 2nd iteration: x = 0, so we multiply x by 7 and use the integer part of the result: Because 0.07 x 7 = 0.49, the second digit to be appended to s is 0 again, and the new x is 0.49 - So far, 0.01 (base 10) = .00... (base 7) Step 3, 3rd iteration: x = 0, so we multiply x by 7 and use the integer part of the result: Because 0.49 x 7 = 3.43, the third digit to be appended to s is 3, and the new x is 0.43 - So far, 0.01 (base 10) = .003... (base 7). Step 3, 4th iteration: x = 0, so we multiply x by 7 and use the integer part of the result: Because 0.43 x 7 = 3.01, the fourth digit to be appended to s is another 3, and the new x is 0.01 - So far, 0.01 (base 10) = .0033... (base 7) At this point x = 0.01, which is exactly what we had at the start (1st iteration). Hence, the next iteration (the 5th) would be identical to the 1st, the 6th to the 2nd, and so on and so forth. In sum, if we continued executing the algorithm, the above 4 iterations would repeat indefinitely, unchanged, as the value of x never becomes 0. Therefore, the sequence of digits "0033" produced by these four iterations would continue to be appended to the result s forever. This phenomenon is caused by the fact that decimal fractions having a finite number of digits in base 10 can have infinite expansions when expressed in another base. In this example, 0.01 (decimal) re-written in base 7 is the periodic number 0.00 3300 3300 330033_.... where the sequence of four digits 0033, called the “repetend”, is repeated ad infinitum. Change your Part-A /A1 code so that, if the result is a periodic number, the computation does not stop at 20 digits but continues until a repetend *of arbitrary length* is identified. When this happens, your code should print the result, the repetend, and stop. (You may assume that the float x the user enters contains up to 5 digits after the point). USER-INTERFACE SPECIFICATIONS The user interface should be analogous to that in PART A/A1 (see top of previous page), except that, after the result of the base conversion, the full repetend should be displayed. As in PART A/A1, any violations of the interface requirements will incur a 40-marks penalty. EXAMPLES (with correct responses) for TESTING your PART-B code: Note: all digits of both the result and repetend must be correct for a Part-B test to earn full marks: 0.2 (base 10) 0.13 (base 10) 0.005 (base 10) 0.01 (base 10) = 0.0121 (base 3) - Warning! Repetend: 0121 = 0.0440251 (base 6) - Warning! Repetend: 40251 = 0.000110132232 (base 4) - Warning! Repetend: 0110132232 = 0.0000001010001111010111 (base 2) - Warning! Repetend: 00001010001111010111 VERY IMPORTANT: The use of the import statement (i.e., of any Python module) is strictly FORBIDDEN. Using recursion is also FORBIDDEN. Violating either of these requirements will incur in a penalty of 80 MARKS.