How to improve the precision of the result due to the lack of precision in C++ division

Question

I am working on the leibniz question as indicated https://www.hackerrank.com/challenges/leibniz here. which computes 1-1/3+1/5-1/7+1/9+... Each element in the sequence can be defined as a(i)=(-1)^i/(2*i+1) start i from 0.

The question requires that to add from the first term to the nth term and output the result. My program passes the basic test cases. But it fails in other cases.

I guess my program fault is due to the precision when the number is large enough.

Can anybody provide a way to improve the precision of the result?

double leibnitz(int n) {
    double res = 0.0;
    for (int i = 1; i <= n; i++) {
        res += 1.0 / (2 * i - 1) * (i % 2 == 1 ? 1.0 : -1.0);
    }
    return res;
}

Whats the fault? You haven't mentioned what exactly goes wrong, or what kind of input triggers such wrong behavior. — Borgleader, Jul 07 '13 at 04:09
this could be helpful http://stackoverflow.com/questions/14637621/c-calculating-more-precise-than-double-or-long-double?rq=1 — Nick Maroulis, Jul 07 '13 at 04:14
You forgot to ask your question. What question do you want us to answer? — user2357112, Jul 07 '13 at 04:43
I wanna ask how could I improve the precision of the result of my code — witrus, Jul 07 '13 at 05:00
@witrus `printf("%.15f\n"):` a) this colon should be a semi-colon b) it will always print 0.0 because you forgot to add `, res` after the string pattern. it should be: `printf("%.15f\n", res);` — Borgleader, Jul 07 '13 at 05:02
I don't understand why this is being blocked / downvoted. Looks like a legitimate question to me. It could be improved by providing an example or examples of the actual and expected input / output, though. — Stefan Haustein, Jul 07 '13 at 07:51

Stefan Haustein · Answer 1 · 2013-07-07T21:31:32.113

2

Start the loop with n and count down.

The reason is that small numbers around 0 can be added with higher precision because leading zeroes will be represented in the exponent part of the floating point number (hence the name "floating point"), making more of the mantissa available. So you may be able to approach 1 with a more precise sum of the smaller parts.

The loop should look like this:

for (int i = n; i >= 1; i--) {
    res += 1.0 / (2 * i - 1) * (i % 2 == 1 ? 1.0 : -1.0);
}

Jsfiddle with a simpler problem to illustrate that ordering may make a difference here:

http://jsfiddle.net/smt56/1

BTW: You should be able to shorten the expression to

res += ((i % 2) * 2 - 1) / (2.0 * i - 1)

edited Jul 07 '13 at 21:31

answered Jul 07 '13 at 04:50

Stefan Haustein

18,427
3
36
51

I really appreciate your help.It seems to improve precision in this way. But when n is extremely large like when n equals to 10^7 it still fails to give enough accurate answer.So it still fails in the submission. – witrus Jul 08 '13 at 01:04
Did you try using long double? – Stefan Haustein Jul 08 '13 at 02:01
What about combining terms pairwise, as suggested in the wikipedia article? http://en.wikipedia.org/wiki/Leibniz_formula_for_%CF%80 – Stefan Haustein Jul 08 '13 at 02:14

How to improve the precision of the result due to the lack of precision in C++ division

1 Answers1

Linked