-2

ques:

I have a large number of floating point numbers (~10,000 numbers) , each having 6 digits after decimal. Now, the multiplication of all these numbers would yield about 60,000 digits. But the double range is for 15 digits only. The output product has to have 6 digits of precision after decimal.

my approach:

I thought of multiplying these numbers by 10^6 and then multiplying them and later dividing them by 10^12.

I also thought of multiplying these numbers using arrays to store their digits and later converting them to decimal. But this also appears cumbersome and may not yield correct result.

Is there an alternate easier way to do this?

Community
  • 1
  • 1
bnks452
  • 1
  • 1

1 Answers1

2

I thought of multiplying these numbers by 10^6 and then multiplying them and later dividing them by 10^12.

This would only achieve further loss of accuracy. In floating-point, large numbers are represented approximately just like small numbers are. Making your numbers bigger only means you are doing 19999 multiplications (and one division) instead of 9999 multiplications; it does not magically give you more significant digits.

This manipulation would only be useful if it prevented the partial product to reach into subnormal territory (and in this case, multiplying by a power of two would be recommended to avoid loss of accuracy due to the multiplication). There is no indication in your question that this happens, no example data set, no code, so it is only possible to provide the generic explanation below:

Floating-point multiplication is very well behaved when it does not underflow or overflow. At the first order, you can assume that relative inaccuracies add up, so that multiplying 10000 values produces a result that's 9999 machine epsilons away from the mathematical result in relative terms(*).

The solution to your problem as stated (no code, no data set) is to use a wider floating-point type for the intermediate multiplications. This solves both the problems of underflow or overflow and leaves you with a relative accuracy on the end result such that once rounded to the original floating-point type, the product is wrong by at most one ULP.

Depending on your programming language, such a wider floating-point type may be available as long double. For 10000 multiplications, the 80-bit “extended double” format, widely available in x86 processors, would improve things dramatically and you would barely see any performance difference, as long as your compiler does map this 80-bit format to a floating-point type. Otherwise, you would have to use a software implementation such as MPFR's arbitrary-precision floating-point format or the double-double format.

(*) In reality, relative inaccuracies compound, so that the real bound on the relative error is more like (1 + ε)9999 - 1 where ε is the machine epsilon. Also, in reality, relative errors often cancel each other, so that you can expect the actual relative error to grow like the square root of the theoretical maximum error.

Pascal Cuoq
  • 79,187
  • 7
  • 161
  • 281
  • "This manipulation would only be useful if it prevented the partial product to reach into subnormal territory (and in this case, multiplying by a power of two would be recommended to avoid loss of accuracy due to the multiplication)." Can you please explain what this means? – bnks452 Jul 12 '15 at 13:30
  • @bnks452 I would prefer it if you provided an example data set and I could tell you that you do not need to worry about subnormals. Otherwise, there is a definition [here](https://en.wikipedia.org/wiki/Denormal_number) and the sentence relevant to the discussion is “it allows a calculation to lose precision slowly when the result is small.”, meaning that although you do not get zero, when a partial product was a subnormal number, the end result may be less accurate than expected. – Pascal Cuoq Jul 12 '15 at 13:36
  • By multiplying numbers by 10^6 i meant storing them as integers and multiplying, because my data set consists of floating point numbers < 1 and >0 and having 6 digits after the decimal. for eg: 0.123456, 0.986173 etc. There are about 10000 numbers like this and i have to get an output having 6 digits after decimal. – bnks452 Jul 12 '15 at 13:53
  • @bnks452 but that wouldn't work because although the double-precision format can represent numbers up to 10^300, it cannot represent integers exactly above 2^53. You would reach the limit in 6 multiplication. – Pascal Cuoq Jul 12 '15 at 13:57
  • perhaps I can convert the product after 6 multiplication back to decimal number <0, taking only the starting 6 digits? Because my final product is to be computed with epsilon 10^-6. – bnks452 Jul 12 '15 at 14:07
  • 2
    Double-precision is more than enough to compute a product of 10000 factors to 10^-6. You are doing something wrong. I cannot tell you what. – Pascal Cuoq Jul 12 '15 at 14:12