Consider two possibilities for representing a rational number r in algorithms: either as a pair of integers (p, q) such that r =plq (the fractional format), or as a triple of strings of digits (a,b,c) such that r =a.b (the decimal format). The line above the last part means that it repeats forever. The band c parts are allowed to be the empty string (8) or start with zeros such as b = 00 and 7 = 00103; that's why I defined them as strings of digits instead of integers. We say (p, q) is reduced if gcd(p, q) 1. We say (a,b,c) is reduced if the last digit of b and c are distinct1. or Examples: one half is either (p, q) = (1,2) or (a,b,c) = (0,5,8), since 1/2 = 0.5 ; one third is either (p, q) = (1,3) (a,b,c) = (0,,3) since 1/3 = 0.3; while a quarter is either (p, q) = (1,4) or (a, b, c) = (0,25,8), since 1/4 = 0.25. One eleventh is either (p, q) = (1,11) or (a,b,c) = (0,8,09) since 1/3 = 0.09. As for the size of these representations, in the fractional format we define, |r| = |p|+ [9], while in the decimal format we define Ir= |a + b + c). uses at most Assume for this exercise the standard algorithms we know for long additions and long multiplications of integers x,y. Those algorithms are such that the running time of x + y uses at most o(\x] + [y]) operations, while the running time of x xy (1x1xlyl) operations. a) Given two rational numbers r1, r2 of sizes |ri|, |r2| in fractional format, figure out the worst case running time of computing r1 + r2 and r1 X r2. Express your answer using Big-O notation. b) Given two rational numbers r1, r2 of sizes Tril,r2| in decimal format, figure out the worst case running time of computing r + r2 and r1 X r2. Express your answer using Big-O notation. c) Explain why in reality we would definitely discard one of these two formats. Hint: consider the worst case size of the representation of a number r in (reduced) fractional format and compare it to the worst case size of the representation of the same number r in (reduced) decimal format. Consider two possibilities for representing a rational number r in algorithms: either as a pair of integers (p, q) such that r =plq (the fractional format), or as a triple of strings of digits (a,b,c) such that r =a.b (the decimal format). The line above the last part means that it repeats forever. The band c parts are allowed to be the empty string (8) or start with zeros such as b = 00 and 7 = 00103; that's why I defined them as strings of digits instead of integers. We say (p, q) is reduced if gcd(p, q) 1. We say (a,b,c) is reduced if the last digit of b and c are distinct1. or Examples: one half is either (p, q) = (1,2) or (a,b,c) = (0,5,8), since 1/2 = 0.5 ; one third is either (p, q) = (1,3) (a,b,c) = (0,,3) since 1/3 = 0.3; while a quarter is either (p, q) = (1,4) or (a, b, c) = (0,25,8), since 1/4 = 0.25. One eleventh is either (p, q) = (1,11) or (a,b,c) = (0,8,09) since 1/3 = 0.09. As for the size of these representations, in the fractional format we define, |r| = |p|+ [9], while in the decimal format we define Ir= |a + b + c). uses at most Assume for this exercise the standard algorithms we know for long additions and long multiplications of integers x,y. Those algorithms are such that the running time of x + y uses at most o(\x] + [y]) operations, while the running time of x xy (1x1xlyl) operations. a) Given two rational numbers r1, r2 of sizes |ri|, |r2| in fractional format, figure out the worst case running time of computing r1 + r2 and r1 X r2. Express your answer using Big-O notation. b) Given two rational numbers r1, r2 of sizes Tril,r2| in decimal format, figure out the worst case running time of computing r + r2 and r1 X r2. Express your answer using Big-O notation. c) Explain why in reality we would definitely discard one of these two formats. Hint: consider the worst case size of the representation of a number r in (reduced) fractional format and compare it to the worst case size of the representation of the same number r in (reduced) decimal format
