CODEWITHSUNDEEP
logarithmnumerical-methods
mat kelcey
mat kelcey

Reputation: 3145

problem with arithmetic using logarthms to avoid numerical underflow

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 the values of 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])+... )

but i need the actual ratio....

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!

Mat

Upvotes: 4

Views: 574

Answers (3)

High Performance Mark
High Performance Mark

Reputation: 78324

Strip out the numerators and denominators since they are the same for the whole sequence. Compute the ratio of numerators element-by-element (rather as @Mark suggests), finally multiply the result by the right power of the denominator-of-B/denominator-of-A.

Or, if that threatens integer overflow in computing the product of the numerators or powers of the denominators, something like:

A'/B' = (numerator(A[0])/numerator(b[0]))*(denominator(B)/denominator(A) * ...

I've probably got some of the fractions upside-down, but I guess you can figure that out ?

Upvotes: 0

Vatine
Vatine

Reputation: 21268

If you want to keep it in logarithms, remember that A/B corresponds to log A - log B, so after you've summed the logarithms of A and B, you can find the ratio of the larger to the smaller by exponentiating your log base with max(logsumA, logsumB)-min(logsumA,logsumB).

Upvotes: 1

Mark Byers
Mark Byers

Reputation: 838376

You could calculate it in a slightly different order:

A' / B' = a[0] / b[0] * a[1] / b[1] * a[2] / b[2] * ...

Upvotes: 4

Related Questions