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.