/* CS 341 Spring 2002 */ /* Note segment 8 */ /* 26-March-2002 */ /* Taken by Apostolos Paul Pantazis */ --> More on floating point --> How C++ code gets compliled into assembler. Assume that NASA hired you to write a program that adds Vectors of standard 64-bit numbers. Add them as accurately as possible. Ideas: -->Take as input a list of numbers , sort them and add them. Y1, ..., Yn == SORT(x1, ...,xn) , try to add numbers of nearly same size. a0 = y1 ai = asub(i-1) + y1 an = answer. | |--> if number was about equals to sum of all smaller numbers this would be a very good algorithm. -- How much error would you introduce adding 2 numbers (floating points) together. Lets say the numbers are a and b. a+b is the desired operation. Lets say they are base 2 with an m-bit mantissa. * * * * * a = asub(m)*2^(a*e) a<= asub(m) < 2, m bits of binary precision. asub(m) = d.dddd asubm = 1.dddd .... (1^(th))/(2^(m)) The in-accuracy is: Note: ~ on top is true asub(m), ^ is error asub(m). asub(m) = asub(m) + asub(m) (1) (2) (1) = ~ (2) = ^ The (1) and (2) style is valid for rest of note. asub(m) = (1)/(2^(m)) (1) a = asub(m) * 2^(a*e) (1) on the a. a = asub(m) * 2^(a*e) = (2^(a*e))/(2^(m)) = 2^((a*e) - m)). Note: asub(m) stands for a subscript m. The result above is the "big deal" with floating point numbers. How many digits do you chop off when 2 nums have different exponents. a = asub(m) * 2^(a*e) b = bsub(m) * 2^(b*e) | |--> the number of digits you chop off is the difference of exponents. Ex. 1.aaaa * 2^(a*e) be <= ae 1.bbbb * 2^(b*e) 1.aaaa | be = asube -3 1.b|bbb [digits choped off..] -- effectively m-bit mantissa becomes m-|ae - be| mantissa. This gives us an accuracy precision of 1 part in 2^(m). Process of compilation. * 2 ways to speed up a computer 1. hardware 2. software Tricks for compilers Strength reduction. e-mail me at maximus@cs.unm.edu for strength reduction example or web references on the subject.