My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
February 8th, 2011, 04:39 AM   #1
Newbie
 
Joined: Feb 2011

Posts: 13
Thanks: 0

An approximation for log(a+b)

Hello,
I have very big numbers that overflow as an integer value. Therefore, I keep the logarithms of those values. The problem is that: I need log(a+b) but I only know loga and logb. How can I approximate to find log(a+b)?

---------------------------------------------------------------------------------------------------------------------
More specifically problem is exactly like this: I need to calculate this: dk=alpha*gamma(nk)+dleftk*drightk
alpha is a small double value here.
gamma(nk)=(n-1)! (overflows for big integers)
dleftk and drightk are calculated recursively according to the same equation. Therefore, I have log(gamma(nk)) and log(dleftk*drightk) and I need to calculate dk.

I thought taking the logarithms is the best way, but any other solution will be appreciated as well.
Thanks.
malaguena is offline  
 
February 8th, 2011, 04:48 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: An approximation for log(a+b)

Do you know anything in particular about a and b, other than that they're large? For example, is one usually much bigger than the other, or are they usually about the same size?

One thing that has been useful to me in the past is representing log(a + b) as log(a * (1 + b/a)) = log a + log (1 + b/a). If b is small compared to a you can replace the latter with a power series approximation. To second order, log a + b/a - b^2/2a^2, for example.
CRGreathouse is offline  
February 8th, 2011, 05:04 AM   #3
Newbie
 
Joined: Feb 2011

Posts: 13
Thanks: 0

Re: An approximation for log(a+b)

More specifically problem is exactly like this: I need to calculate this: dk=alpha*gamma(nk)+dleftk*drightk
alpha is a small double value here.
gamma(nk)=(n-1)! (overflows for big integers)
dleftk and drightk are calculated recursively according to the same equation. Therefore, I have log(gamma(nk)) and log(dleftk*drightk) and I need to calculate dk.

dk is calculated for a tree, and here dleftk and drightk represent the children of the node dk.

I thought of taking the logarithms is the best way, but any other solution will be appreciated as well.
malaguena is offline  
February 8th, 2011, 06:36 AM   #4
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: An approximation for log(a+b)

My solution seems appropriate, then. Take the larger of log(alpha*gamma(nk)) and log(dleftk*drightk) and call this A; call the other B. The number you want is A + log(1 + exp(B - A)) which will be close to A. If A is much larger than B, but you still need high precision, you'll need to either use a special "log 1 + x" function (this is more common than you might imagine) or to roll your own calculation with series as I mentioned above.
CRGreathouse is offline  
February 9th, 2011, 12:45 AM   #5
Newbie
 
Joined: Feb 2011

Posts: 13
Thanks: 0

Re: An approximation for log(a+b)

Thank you very much for the solution.
The only thing I could not get is the power series. Why do we need the power series approximation here?
malaguena is offline  
February 9th, 2011, 05:51 AM   #6
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: An approximation for log(a+b)

Quote:
Originally Posted by malaguena
Thank you very much for the solution.
The only thing I could not get is the power series. Why do we need the power series approximation here?
If B is much smaller than A then exp(B - A) will be close to 0 which will cause you to lose most of your precision when you add it to 1.

For example, suppose your computer used 6 decimal places in calculation and you had A = 20, B = 9. You'd get B - A = -1.10000e1 (-11) and exp(B - A) = 1.67017e-5 (0.00001...). All of this is fine, the rounding errors are small. Now add 1 and you get 1.00002e0. Suddenly you've lost almost all precision. If you take the logarithm, you'll get 2.00000e-5, but just keeping the original 1.67017e-5 would give you a more accurate result. The true result (as closely as you can store) is 1.67016e-5.

Now if instead of adding 1 and taking the logarithm you had instead subtracted half the square of the number you would have had square = 2.78947e-10, half of square = 1.39474e-10, difference = 1.67016e-5, which is the exact answer (or as close as you can get, anyway).
CRGreathouse is offline  
February 9th, 2011, 07:03 AM   #7
Newbie
 
Joined: Feb 2011

Posts: 13
Thanks: 0

Re: An approximation for log(a+b)

Now it is clear. I think it is also possible to increase the order to increase the accuracy.
Thanks a lot!
malaguena is offline  
February 9th, 2011, 07:42 AM   #8
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: An approximation for log(a+b)

Quote:
Originally Posted by malaguena
I think it is also possible to increase the order to increase the accuracy.
Yes. Depending on how small the numbers are (that is how far apart A and B are) you might not need too many terms, but unless speed is a concern it doesn't really matter too much. In any case you can do a single test: if larger than some amount calculate log(1 + __), otherwise use the series.
CRGreathouse is offline  
February 10th, 2011, 04:59 AM   #9
Newbie
 
Joined: Feb 2011

Posts: 13
Thanks: 0

Re: An approximation for log(a+b)

Ok. I tried, and 2 factors is enough in the series. Speed is an issue as well in my program.
Many thanks again.
malaguena is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
approximation, loga



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Approximation kyry Calculus 2 January 31st, 2014 09:47 PM
Approximation Shamieh Calculus 1 October 9th, 2013 10:09 AM
I approximation aaron-math Calculus 1 October 3rd, 2011 12:34 PM
Pi Approximation Wissam Number Theory 16 March 13th, 2011 04:41 PM
Pi Approximation Marcel777 Number Theory 5 September 27th, 2010 11:49 PM





Copyright © 2019 My Math Forum. All rights reserved.