Which way is more accurate?

Question

I need to divide a numeric range to some segments that have same length. But I can't decide which way is more accurate. For example:

double r1 = 100.0, r2 = 1000.0, r = r2 - r1;
int n = 30;
double[] position = new double[n];
for (int i = 0; i < n; i++)
{
    position[i] = r1 + (double)i / n * r;
    // position[i] = r1 + i * r / n;
}

It's about (double)int1 / int2 * double or int1 * double / int2. Which way is more accurate? Which way should I use?

Update

The following code will show the difference:

double r1 = 1000.0, r2 = 100000.0, r = r2 - r1;
int n = 300;
double[] position = new double[n];
for (int i = 0; i < n; i++)
{
    double v1 = r1 + (double)i / n * r;
    double v2 = position[i] = r1 + i * r / n;
    if (v1 != v2)
    {
        Console.WriteLine(v2 - v1);
    }
}

It seems to me that it should be equal. Why don't you try it out and see if there's any difference? — Tim S., Sep 05 '12 at 13:10
This is a great question. I believe there will be difference and it is domain dependent (the ranges of double, int1 and int2). The key word here is loss of significant digits. — amit, Sep 05 '12 at 13:22
@EFanZh: Unfortunately I am not sure which will be better and in each cases. It will be only a partial answer. Do you still want it? I think you should put a bounty on this one, might attract more viewers and better answers then the wrong ones originally supplied. — amit, Sep 06 '12 at 11:56
@amit If you are in the same situation, what will you do? And why? If there is something reasonable, I'll accept it. — EFanZh, Sep 06 '12 at 12:53
@EFanZh: I will try to wrap something up later today, I'll have to go back to my numerical analysis lectures and remember how it is expected to behave. (I promise to try). — amit, Sep 06 '12 at 13:06

score 1 · Answer 1 · answered Sep 05 '12 at 13:00

1

Neither is particularly faster, since the compiler or the JIT process may reorder the operation for efficiency anyway.

answered Sep 05 '12 at 13:00

akton

14,148
3
43
47

This is very true. You should check disassembly of NGen'd binary before you make these determinations. – Ani Sep 05 '12 at 13:02
1

are you sure that multiplication is comutative, just like in this post http://stackoverflow.com/questions/6430448/why-doesnt-gcc-optimize-aaaaaa-to-aaaaaa – Luka Rahne Sep 05 '12 at 13:04
@Ralu For two multiplicands only it is. If there were more terms, I would agree. – akton Sep 05 '12 at 13:06
OP asked about accuracy, not speed – Tom Sirgedas Sep 05 '12 at 17:49
@TomSirgedas You are correct. I meant to say both accuracy and speed but, by the time I realised I needed to correct my answer, Habib had already answered the question. I am a victim of my own typing speed once again. – akton Sep 06 '12 at 01:52
@akton: Habib answer is wrong, and so is this. You are both neglecting the fact that doubles are not real numbers. I really doubt the JIT will optimize it (tested in java, it did not), and it will definetly won't be "the same" as Habib suggests. – amit Sep 06 '12 at 12:01
@Habib You may well be right. It may be more informative for us all if you supplied an answer. – akton Sep 06 '12 at 13:12
@akton: I tried my best to explain the issue in an answer, but my numerical analysis really is rusty. I am certain I still miss some things. But the conclusion remains - which is more accurate is domain specific. – amit Sep 06 '12 at 18:36

score 1 · Accepted Answer · answered Sep 06 '12 at 18:34

Disclaimer: All numbers I am going to give as examples are not exact, but show the principle of what's happening behind the scenes.

Let's examine two cases:

(1) int1 = 1000, int2= 3, double = 3.0 The first method will give you: (1000.0 / 3) * 3 == 333.33333 * 3.0 == 999.999...
While the second will give (1000 * 3.0) / 3 == 3000 / 3 == 1000
In this scenario - the second method is more accurate.

(2) int1 = 2, int2 = 2, double = Double.MAX_VALUE
The first will yield (2.0 / 2) * Double.MAX_VALUE == 1 * Double.MAX_VALUE == Double.MAX_VALUE
While the second will give (2 * Double.MAX_VALUE) / 2 - which will cause (in Java) to be Infinity, I am not sure what the double standard says about this cases, if it might overflow or is it always infinity - but it is definetly an issue.
So, in this case - the first method is more accurate.

The things might go more complicated if the integers are longs or the double is float, since there are long values that cannot be represented by doubles, so loss of accuracy might happen for large double values in this case, and in any case - large double values are less accurate.

Conclusion: Which is better is domain specific. In some cases the first method should be better and in some the first. It really depends on the values of int1,int2, and double.
However- AFAIK, the general rule of thumb with double precision ops is keep the calculations as small as possible (Don't create huge numbers and then decrease them back, keep them small as longest as you can). This issue is known as loss of significant digits.

+1, for the right answer. Had to remove mine after checking in VS — Habib, Sep 12 '12 at 04:16

musefan · Answer 3 · 2012-09-05T14:24:52.170

0

Maybe I misunderstand your requirement but why do any division/multiplication inside the loop at all? Maybe this would get the same results:

decimal r1 = 100.0m, r2 = 1000.0m, r = r2 - r1;
int n = 30;
decimal[] position = new double[n];

decimal diff = r / n;
decimal current = r1;

for (int i = 0; i < n; i++)
{
    position[i] = current;
    current += diff;
}

edited Sep 05 '12 at 14:24

answered Sep 05 '12 at 13:06

musefan

47,875
21
135
185

1

This may cause errors. Since `diff` is not accurate, the small deviations may add up to a big mistake. – EFanZh Sep 05 '12 at 13:09
hmm, im not so sure (again maybe I don't see your needs exactly) could you post some example values? or examples of when you would end up with one substantially larger than another? – musefan Sep 05 '12 at 13:13
@EFanZh: I still don't understand how my code will leave you will "big mistakes". What input values can you specify for my code that will cause problems with accuracy? – musefan Sep 05 '12 at 13:46
Considering `r / n` is not precisely "r / n". you can try this: ` double a = 1000.0; int n = 10000; double t = a / n, sum = 0; for (int i = 0; i < n; i++) { sum += t; } Console.WriteLine(a - sum);` – EFanZh Sep 05 '12 at 13:54
@EFanZh: Sorry, don't see how that code is working on a range. Anyway, I used the input values `r1 = 100.0; r2 = 1000.0; n = 10000` with my code and got a `diff = 0.09` and a final total of `1000.00000000011` which shows a small error. However, if I use `decimal` (which is known to avoid floating point rounding errors) instead of 'double' then my final total is 1000.0 - Exactly spot on! ... does this help? (updated code) – musefan Sep 05 '12 at 14:24

Which way is more accurate?

3 Answers3