My Math Forum An approximation for log(a+b)

 Number Theory Number Theory Math Forum

 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.
 February 8th, 2011, 04:48 AM #2 Global Moderator     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.
 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.
 February 8th, 2011, 06:36 AM #4 Global Moderator     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.
 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?
February 9th, 2011, 05:51 AM   #6
Global Moderator

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).

 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!
February 9th, 2011, 07:42 AM   #8
Global Moderator

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.

 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.

 Tags approximation, loga

,

,

,

,

,

,

,

,

,

,

,

# log (1-a/b)

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top