Plan for Today CS 594 Spring 2003 Lecture 5 Computer Arithmetic and Cache u u Talk about computer arithmetic Begin Cache discussion Jack Dongarra Computer Science Department University of Tennessee 2 1 Defining Floating Point Arithmetic A Little History u u Representable Von Neumann and Goldstine 1947 u u u Turing 1949 Motivated search for industry wide standard beginning late 1970s First implementation Intel 8087 ACM Turing Award 1989 to W Kahan for design of the IEEE Floating Point Standards 754 binary and 854 decimal 3 Nearly universally implemented in general purpose machines IEEE Floating Point Arithmetic Standard 754 Normalized Numbers Nonzero Representable Numbers Macheps Machine epsilon 2 operation significand bits 1 d d x rexp arithmetic x how to round result to fit in format comparison conversion between different formats short to long FP numbers FP to integer exception handling what to do for 0 0 2 largest number etc binary decimal conversion for I O when radix not 10 Hard to write portable and reliable software u Normalized x u Operations Rediscovered in 1961 by Wilkinson and publicized Starting in the 1960s many papers doing backward error analysis of various algorithms Many years where each machine did FP arithmetic slightly differe ntly Both rounding and exception handling differed u d d d sign bit radix r usually 2 or 10 sometimes 16 significand d d d how many base r digits d exponent exp range others Carrying d digits is equivalent to changing the input data in t he d th place and then solving Ax b So if A is only known to d digits the answer is as accurate as the data deserves Backward Error Analysis u numbers Scientific notation Can t expect to solve most big n 15 linear systems without ca rrying many decimal digits d 8 otherwise the computed answer would be com pletely inaccurate WRONG u Language library support for these operations 4 IEEE Floating Point Arithmetic Standard 754 Denorms 2exp u Denormalized Numbers 0 d d x 2min exp sign bit nonzero significand minimum exponent relative error in each Fills in gap between UN and 0 OV overflow threshold largest number u Underflow Exception occurs when exact nonzero result is less than underflow threshol d UN UN underflow threshold smallest number Ex UN 3 Format bits significand bits macheps exponent bits exponent range Single 32 23 1 2 24 10 7 8 2 126 2127 10 38 Double 64 52 1 2 53 10 16 11 2 1022 21023 10 308 Double 80 64 2 64 10 19 15 2 16382 216383 10 4932 Extended 80 bits on all Intel machines 5 return a denorm or zero u Why bother Necessary so that following code never divides by zero if a b then x a a b 6 1 IEEE Floating Point Arithmetic Standard 754 Infinity IEEE Floating Point Arithmetic Standard 754 NAN Not A Number uNAN uInvalid u Infinity Sign bit zero significand maximum exponent uOverflow Exception occurs when exact result not a well defined real number 0 0 occurs when exact finite result too large to represent accurately Ex 2 OV sqrt 1 infinity infinity NAN 3 return infinity uDivide infinity infinity 0 infinity NAN 3 Return a NAN in all these cases by zero Exception return infinity 1 0 uTwo sign of zero important uAlso Sign bit nonzero significand maximum exponent Exception kinds of NANs Quiet propagates without raising an exception Signaling generate an exception when touched return infinity for 3 infinity 2 infinity infinity infinity Result is exact not an exception good for detecting uninitialized data 7 8 Error Analysis uBasic Backward error error formula u fl a op b a op b 1 d where op one of d macheps u u assuming no overflow underflow or divide by zero uExample adding 4 numbers u fl x1 x2 x 3 x 4 x 1 x 2 1 d 1 x 3 1 d 2 x 4 1 d 3 x 1 1 d1 1 d2 1 d 3 x 2 1 d1 1 d2 1 d3 x 3 1 d2 1 d3 x 4 1 d3 x 1 1 e1 x 2 1 e2 x 3 1 e3 x 4 1 e4 x where each ei 3 macheps get exact sum of slightly changed summands x i 1 ei Problem is insensitive or well conditioned if relative change in input causes commensurate relative change in solution u Problem is sensitive or ill conditioned if relative change in solution can be much larger than that in input data u u Consider problem of computing cosine function for arguments near p 2 Let x p 2 and let h be small perturbation to x Then absolute error cos x h cos x h sin x h relative error h tan x 8 Cond Relative change in solution Relative change in input dat a f x f x f x x x x u u f Forward error f x 10 Sensitivity 2 Examples cos p 2 and 2 d System of Equations u u Problem is sensitive or ill conditioned if cond 1 When function f is evaluated for approximate input x x h instead of true input value of x Absolute error f x h f x h f x Relative error f x h f x f x h f x f x f x f x Sensitivity and Conditioning u f Backward error Backward Error Analysis algorithm called numerically stable if it gives the exact result for slightly changed inputs 9 Numerical Stability is an algorithm design goal u Approximate solution is exact solution to modified problem How large a modification to original problem is required to give result actually obtained How much data error in initial input would be required to explain all the error in computed results Approximate solution is good if it is exact solution to nearby problem u u u 11 So small change in x near p 2 causes large relative change in cos x regardless of method used cos 1 57079 0 63267949 x 10 5 cos 1 57078 1 64267949 x 10 5 Relative change in output is a quarter million times greater than relative change in input 12 2 Example Polynomial Evaluation Using Horner s Rule Sensitivity 2 Examples cos p 2 and 2 d System of Equations u u Consider problem of computing cosine function for arguments near p 2 Let x p 2 and let h be small perturbation to x Then absolute error cos x h cos x h sin x h relative error h tan x 8 u u u u So small change in x near p 2 causes large relative change in cos x regardless of method used cos 1 57079 0 63267949 x 10 5 cos 1 57078 1 64267949 x 10 5 Relative change in output is a quarter million times greater than relative change in input uHorner s rule to evaluate p ck x k n 1 k 0 p c n for k n 1 down to 0 p x p c k uNumerically uApply Stable to x 2 9 x 9 18 x8 512 29 x …
View Full Document
Unlocking...