CMPS 251 Homework Assignment 2 Solution, Fall 2015

CMPS 251 Assignment 2-Solution Problem 1 Code function y=dec2binfull(x) if (x>32767) error('The input number is larger than the maximum allowed'); end y=zeros(1,30); integer=floor(x); decimal=x-floor(x); count=15; while integer >= 1 y(count)=mod(integer,2); integer=floor(integer/2); count=count-1; end count=16; while sum(decimal~=[0 1])>1 && count<=30 decimal=decimal*2; y(count)=floor(decimal); decimal=decimal-y(count); count=count+1; end % to represent as a string y=[num2str(y(1:15)) '.' num2str(y(16:30))]; Example >> dec2binfull(52.234375) ans = 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0.0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 Problem 2 Part 1 a) Using six significant digits, cos(0.007)=0.999976 and sin(0.007)=0.00699994. Thus, f(0.007)=(1-0.999976)/0.00699994= 0.00342860. b) Using Matlab, the value is as follows >> format long >> f=(1-cos(0.007))/sin(0.007) f = 0.00350001429173 The relative error is then error = |0.00350001429173 − 0.00342860| 0.00350001429173 = 0.0204 c) Computing the function f near 0 causes a problem due to the cancellation error that occurs when subtracting two nearly equal numbers (cos(0.0...) and 1). To rearrange the function f, we multiply the numerator and denominator by 1+cos(x) as follows 𝑓(𝑥) = 1 − cos(𝑥) sin(𝑥) ⋅ 1 + cos(𝑥) 1 + cos(𝑥) = 1 − cos2(𝑥) sin(𝑥) + sin(𝑥) cos(𝑥) = sin2(𝑥) sin(𝑥) (1 + cos(𝑥)) = sin (𝑥) 1 + cos (𝑥) Using the values of sin(0.007) and cos(0.007) in part (a) with the reformulated function yields f(0.007)=0.00350001 for a relative error of 1.22 × 10−6 Part 2 The function f clearly causes overflow for large values of x and y. The technique to follow while dealing with such problems is to bound the result for large values of x and y. One way to reformulate the function is as follows 𝑓(𝑥, 𝑦) = √𝑥2 + 𝑦2 = { |𝑦|√1 + (𝑥 𝑦) 2 if 0 ≤ |x| ≤ |y| |𝑥|√1 + (𝑦 𝑥) 2 if 0 ≤ |y| ≤ |x| Depending on the values of x and y, the selected ratio is less than 1 and the magnitude of the results is close to that of |x| or |y|. The remaining issues would be when x and y cannot be represented using the machine floating point representation. Problem 3 The derivation for the error in the FunkyRound scheme uses the same approach that was employed in class. The calculations are shown for the absolute error. The relative error can be calculated using the minimum bound on x 1-For dt+1<β/2 For this case, and in contrast to the normal rounding, we are rounding up. The maximum error occurs when all the digits 𝑑𝑖, 𝑖 = 𝑡 + 1, ⋯ , ∞ have a value of zero |𝑥 − fl(𝑥)| < | ∑ 𝑑𝑖𝛽−𝑖 ∞ 𝑖=𝑡+1 − 𝛽−𝑡| ⋅ 𝛽𝑒 = 𝛽−𝑡 ⋅ 𝛽𝑒 2-For dt+1>β/2 For this case, rounding down is done. The maximum error occurs when all remaining digits take the highest value which is β-1 Hence, the absolute error is given as |𝑥 − fl(𝑥)| < (𝛽 − 1) ∑ 𝛽−𝑖 ∞ 𝑖=𝑡+1 ⋅ 𝛽𝑒 = (𝛽 − 1) ( 1 1 − 1 𝛽 − 1 − (1 𝛽) 𝑡+1 1 − 1 𝛽 ) ⋅ 𝛽𝑒 = 𝛽−𝑡 ⋅ 𝛽𝑒 3- For dt+1=β/2 For this case, we round by setting dt to 0 and removing the remaining decimal digits. The maximum error in this case occurs when dt=β-1, dt+1=β/2 and the remaining digits take the maximum value of β-1. The error is then given as |𝑥 − fl(𝑥)| < ((𝛽 − 1) ⋅ 𝛽−𝑡 + 𝛽 2 ⋅ 𝛽−𝑡−1 + (𝛽 − 1) ∑ 𝛽−𝑖 ∞ 𝑖=𝑡+2 ) ⋅ 𝛽𝑒 = ((𝛽 − 1) ⋅ 𝛽−𝑡 + 1 2 ⋅ 𝛽−𝑡 + 𝛽−𝑡−1) ⋅ 𝛽𝑒 = ((𝛽 − 1/2) ⋅ 𝛽−𝑡 + 𝛽−𝑡−1) ⋅ 𝛽𝑒 = (𝛽 − 1 2 + 1 𝛽) 𝛽−𝑡 ⋅ 𝛽𝑒 2𝛽2 − 𝛽 + 2 2𝛽 𝛽−𝑡 ⋅ 𝛽𝑒 The factor 2𝛽2−𝛽+2 2𝛽 is bigger than 1 for any base, hence the last case yields the largest error for this fictitious rounding scheme. Problem 4 Part 1 1- +0 2- -0 3- +ꝏ 4- -ꝏ 5- (1.0)2 . 21-127=2-126=1.1755 x 10-38 6- (1.011)2. 2129-127=(101.1)2=5.5 7- (1.0)2. 2127-127=1 8- (1.10011001100110011001100)2. 2123-127=(0.000110011001100110011001100)2 =0.099999994039536 ≈0.1 Part 2 [C705A700] Binary: 1 10001110 00001011010011100000000 Decimal: -34215 [45607000] Binary: 0 10001010 11000000111000000000000 Decimal: 3591 [494F96A0] Binary: 0 10010010 10011111001011010100000 Decimal: 850282 Calculations: Sign bit 0  + Exponent: (10010010)2=146  exponent =2146-127 =219. 1.f: (1.10011111001011010100000)2 Number: (1.10011111001011010100000)2 x 219=(011 001 111 100 101 101 010)2=(3174552)8 =850282 Part 3 64.37109375 Binary: 1000000.01011111=(1.00000001011111) x 26 Exponent: c-127=6  c=133 = (10000101)2 Sign bit: 0 Single precision representation: 0 10000101 00000001011111000000000 [4280BE00]16 0.234375 Binary: 0.001111 =1.111 x 2-3 Exponent: c-127=-3  c=124 = (0111 1100)2 Single precision representation: 0 01111100 11100000000000000000000 [3E700000]16 -9876.54321 Binary: 10011010010100.10001011000011111100111 (non-terminating) =(1.00110100101001000101100)2 x 213 since next bit is 0 Exponent: c=140 =(10001100)2 Sign bit : 1 Single precision representation: 1 10001100 00110100101001000101100 [C61A522C]16 Since the value is not exact, we calculate the relative error as 9876.54321 − 9876.54296875 9876.54321 = 2.44 × 10−8 Problem 5 fl(fl(a+b)+c) a = 0.23371258× 10−4 = 0.00000023371258× 102 b=0.33678429× 102 a+b=0.33678452371258× 102 Since we have an 8-decimal digit precision fl(a+b)=0.33678452× 102 Now fl(fl(a+b)+c)=fl(0.33678452× 102 −0.33677811 × 102) = fl(0.00000641× 102)) =0.64100000× 10-3 fl(a+fl(b+c)) fl(b+c)=fl(0.33678429× 102-0.33677811 × 102) =fl(0.00000618× 102) =0.61800000× 10-3 a = 0.23371258× 10−4 =0.023371258× 10−3 fl(a+fl(b+c))=fl(0.61800000× 10-3+0.023371258× 10−3 ) =fl(0.641371258× 10−3) = 0.64137126× 10−3 Looking at the two results we can see that the second operation has 8 significant digits and a precision equal to the machine precision. The first operation resulted in an accuracy of 3 significant digits (not counting the spurious zeros) and thus a loss of significance of 5 digits. This is due to the cancellation error in adding the sum of a and b to c. Now we consider machine number a,b, and c and neglecting higher order terms in δ fl(fl(𝑎 + 𝑏) + 𝑐) = ((𝑎 + 𝑏)(1 + 𝛿1) + 𝑐)(1 + 𝛿2) ≈ 𝑎 + 𝑏 + 𝑐 + (𝑎 + 𝑏)𝛿1 + (𝑎 + 𝑏 + 𝑐)𝛿2 fl(𝑎 + fl(𝑏 + 𝑐)) = ((𝑏 + 𝑐)(1 + 𝛿3) + 𝑎)(1 + 𝛿4) ≈ 𝑎 + 𝑏 + 𝑐 + (𝑏 + 𝑐)𝛿3 + (𝑎 + 𝑏 + 𝑐)𝛿4 Now finding the relative error for both cases |𝑎 + 𝑏 + 𝑐 − (𝑎 + 𝑏 + 𝑐 + (𝑎 + 𝑏)𝛿1 + (𝑎 + 𝑏 + 𝑐)𝛿2) 𝑎 + 𝑏 + 𝑐 | ≤ | 𝑎 + 𝑏 𝑎 + 𝑏 + 𝑐 𝜖 + 𝜖| = | 𝑎 + 𝑏 𝑎 + 𝑏 + 𝑐 + 1| 𝜖 |𝑎 + 𝑏 + 𝑐 − (𝑎 + 𝑏 + 𝑐 + (𝑏 + 𝑐)𝛿3 + (𝑎 + 𝑏 + 𝑐)𝛿4) 𝑎 + 𝑏 + 𝑐 | ≤ | 𝑏 + 𝑐 𝑎 + 𝑏 + 𝑐 𝜖 + 𝜖| = | 𝑏 + 𝑐 𝑎 + 𝑏 + 𝑐 + 1| 𝜖 Finally, we can note that when |𝑏 + 𝑐| < |𝑎 + 𝑏|, the second operation is better than the first one.