Problem with arithmetic using logarithms to avoid numerical underflow (take 2)

Question

I have two lists of fractions;

say A = [ 1/212, 5/212, 3/212, ... ]

and B = [ 4/143, 7/143, 2/143, ... ].

If we define A' = a[0] * a[1] * a[2] * ... and B' = b[0] * b[1] * b[2] * ...

I want to calculate a normalised value of A' and B'

ie specifically the values of A' / (A'+B') and B' / (A'+B')

My trouble is A are B are both quite long and each value is small so calculating the product causes numerical underflow very quickly...

I understand turning the product into a sum through logarithms can help me determine which of A' or B' is greater

ie max( log(a[0])+log(a[1])+..., log(b[0])+log(b[1])+... )

and that using logs I can calculate the value of A' / B' but how do I do A' / A'+B'

My best bet to date is to keep the number representations as fractions, ie A = [ [1,212], [5,212], [3,212], ... ] and implement my own arithmetic but it's getting clumsy and I have a feeling there is a (simple) way of logarithms I'm just missing....

The numerators for A and B don't come from a sequence. They might as well be random for the purpose of this question. If it helps the denominators for all values in A are the same, as are all the denominators for B.

Any ideas most welcome!

( ps. I asked a similar question 24 hours ago regarding the ratio A'/B' but it was actually the wrong question to ask. I'm actually after A'/(A'+B'). Sorry, my mistake. )

Answer 1

I see few ways here

First of all you can notice that

A' / (A'+B') = 1 / (1 + B'/A')

and you know how to calculate B'/A' with logarithms.

Another way is to implement your own rational arithmetic but you don't need to go far about it. Since you know that denominators are the same for the whole array, it immediately gives you

numerator(A') = numerator(a[0]) * numerator(a[1]) ...
denumerator(A') = denumerator(a[0]) ^ A.length

All you now need to do is to sum A' and B' which is easy and then multiply A' and 1/(A'+B') which is also easy. The hardest part here is to normalize resulting value which is done with modulo operation and is trivial.

Alternatively, since you most likely using some popular scripting language, most of them have classes for rational arithmetic built in, Python and Ruby have them for sure.

Answer 2

My best bet to date is to keep the number representations as fractions and implement my own arithmetic but it's getting clumsy

What language are you using? If you can overload operators, it should be really easy to make up a Fraction class that you can treat as a number pretty much everywhere.

As an example, determining whether a fraction A / B is larger than C / D is basically comparing whether A * D is larger than B * C.

Answer 3

Both A and B have the same denominator in each fraction you mention. Is that true for every term in the list? If that's so, why don't you factor that out when you calculate the product? The denominator will simply be X^n, when X is the value and n is the number of terms in the list.

If you do that, you'll have the opposite problem: overflow in the numerator. You know that it can't be smaller than max(X)^n, where max(X) is the maximum value in the numerator and n is the number of terms in the list. If you can calculate that, you can see if your computer will have a problem. You can't put 10 pounds of anything in a 5 pound bag.

Unfortunately, the properties of logarithms limit you to the following simplifications:

and

So you're stuck with:

If you're using a language that supports infinite precision numbers (e.g., Java BigDecimal) it might make your life a little easier. But there's still a good argument for doing some thinking before you compute. Why use brute force when you can be elegant?

Answer 4

Well ... if you know A'(A'+B'), then B'(A'+B') should be one minus that. I personally would not use logarithms. I would use the actual fractions. I would also use some sort of BigInt class to represent the numerator and denominator. Which language are you using? Python can be a good fit.