How to handle multiplication of numbers close to 1

Question

I have a bunch of floating point numbers (Java doubles), most of which are very close to 1, and I need to multiply them together as part of a larger calculation. I need to do this a lot.

The problem is that while Java doubles have no problem with a number like:

0.0000000000000000000000000000000001 (1.0E-34)

they can't represent something like:

1.0000000000000000000000000000000001

Consequently of this I lose precision rapidly (the limit seems to be around 1.000000000000001 for Java's doubles).

I've considered just storing the numbers with 1 subtracted, so for example 1.0001 would be stored as 0.0001 - but the problem is that to multiply them together again I have to add 1 and at this point I lose precision.

To address this I could use BigDecimals to perform the calculation (convert to BigDecimal, add 1.0, then multiply), and then convert back to doubles afterwards, but I have serious concerns about the performance implications of this.

Can anyone see a way to do this that avoids using BigDecimal?

Edit for clarity: This is for a large-scale collaborative filter, which employs a gradient descent optimization algorithm. Accuracy is an issue because often the collaborative filter is dealing with very small numbers (such as the probability of a person clicking on an ad for a product, which may be 1 in 1000, or 1 in 10000).

Speed is an issue because the collaborative filter must be trained on tens of millions of data points, if not more.

Answer 1

Yep: because

(1 + x) * (1 + y) = 1 + x + y + x*y

In your case, x and y are very small, so x*y is going to be far smaller - way too small to influence the results of your computation. So as far as you're concerned,

(1 + x) * (1 + y) = 1 + x + y

This means you can store the numbers with 1 subtracted, and instead of multiplying, just add them up. As long as the results are always much less than 1, they'll be close enough to the mathematically precise results that you won't care about the difference.

EDIT: Just noticed: you say most of them are very close to 1. Obviously this technique won't work for numbers that are not close to 1 - that is, if x and y are large. But if one is large and one is small, it might still work; you only care about the magnitude of the product x*y. (And if both numbers are not close to 1, you can just use regular Java double multiplication...)

Answer 2

Isn't this sort of situation exactly what BigDecimal is for?

Edited to add:

"Per the second-last paragraph, I would prefer to avoid BigDecimals if possible for performance reasons." – sanity

"Premature optimization is the root of all evil" - Knuth

There is a simple solution practically made to order for your problem. You are concerned it might not be fast enough, so you want to do something complicated that you think will be faster. The Knuth quote gets overused sometimes, but this is exactly the situation he was warning against. Write it the simple way. Test it. Profile it. See if it's too slow. If it is then start thinking about ways to make it faster. Don't add all this additional complex, bug-prone code until you know it's necessary.

Answer 3

Perhaps you could use logarithms?

Logarithms conveniently reduce multiplication to addition.

Also, to take care of the initial precision loss, there is the function log1p (at least, it exists in C/C++), which returns log(1+x) without any precision loss. (e.g. log1p(1e-30) returns 1e-30 for me)

Then you can use expm1 to get the decimal part of the actual result.

Answer 4

If you really need the precision, you will have to use something like BigDecimal, even if it's slower than Double.

If you don't really need the precision, you could perhaps go with David's answer. But even if you use multiplications a lot, it might be some Premature Optimization, so BIgDecimal might be the way to go anyway

Answer 5

Depending on where the numbers are coming from and how you are using them, you may want to use rationals instead of floats. Not the right answer for all cases, but when it is the right answer there's really no other.

If rationals don't fit, I'd endorse the logarithms answer.

Edit in response to your edit:

If you are dealing with numbers representing low response rates, do what scientists do:

• Represent them as the excess / deficit (normalize out the 1.0 part)
• Scale them. Think in terms of "parts per million" or whatever is appropriate.

This will leave you dealing with reasonable numbers for calculations.

Answer 6

When you say "most of which are very close to 1", how many, exactly?

Maybe you could have an implicit offset of 1 in all your numbers and just work with the fractions.

Answer 7

Its worth noting that you are testing the limits of your hardware rather than Java. Java uses the 64-bit floating point in your CPU.

I suggest you test the performance of BigDecimal before you assume it won't be fast enough for you. You can still do tens of thousands of calculations per second with BigDecimal.

Answer 8

As David points out, you can just add the offsets up.

(1+x) * (1+y) = 1 + x + y + x*y

However, it seems risky to choose to drop out the last term. Don't. For example, try this:

x = 1e-8 y = 2e-6 z = 3e-7 w = 4e-5

What is (1+x)(1+y)(1+z)*(1+w)? In double precision, I get:

(1+x)(1+y)(1+z)*(1+w)

ans =

      1.00004231009302

However, see what happens if we just do the simple additive approximation.

1 + (x+y+z+w)

ans =

            1.00004231

We lost the low order bits that may have been important. This is only an issue if some of the differences from 1 in the product are at least sqrt(eps), where eps is the precision you are working in.

Try this instead:

f = @(u,v) u + v + u*v;

result = f(x,y);

result = f(result,z);

result = f(result,w);

1+result

ans =

      1.00004231009302

As you can see, this gets us back to the double precision result. In fact, it is a bit more accurate, since the internal value of result is 4.23100930230249e-05.