Question: It is an algorithm question for computer science, please HELP.... The problem of accurately summing a set S of n floating-point numbers, S = {x_1,

It is an algorithm question for computer science, please HELP....
The problem of accurately summing a set S of n floating-point numbers, S = {x_1, x_2, ..., x_n}, on a real-world computer is more challenging than might first appear. For example, using the standard accumulating-sum algorithm to compute the harmonic numbers, H_n = Sigma^n _i = 1 1, in floating-point produces a sequence that converges to a constant instead of growing to infinity as a function close to In n. This phenomenon is due to the fact that floating-point addition can suffer from round-off errors, especially if the two numbers being added differ greatly in magnitude. Fortunately, there are several useful heuristic summation algorithms for dealing with this issue, with one of them being the following. Let x_i and x_j be two numbers in S with smallest magnitudes. Sum x_i and x_j and return the result to S. Repeat this process until only one number remains in S, which is the sum. This algorithm will often produce a more accurate sum than the straightforward summation algorithm, because it tends to minimize the round-off errors of each partial sum. Describe how to implement this floating-point summation algorithm in O(n log n) time
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
