Logarithm of a BigDecimal

Question

How can I calculate the logarithm of a BigDecimal? Does anyone know of any algorithms I can use?

My googling so far has come up with the (useless) idea of just converting to a double and using Math.log.

I will provide the precision of the answer required.

edit: any base will do. If it's easier in base x, I'll do that.

Answer 1

A hacky little algorithm that works great for large numbers uses the relation log(AB) = log(A) + log(B). Here's how to do it in base 10 (which you can trivially convert to any other logarithm base):

1. Count the number of decimal digits in the answer. That's the integral part of your logarithm, plus one. Example: floor(log10(123456)) + 1 is 6, since 123456 has 6 digits.

2. You can stop here if all you need is the integer part of the logarithm: just subtract 1 from the result of step 1.

3. To get the fractional part of the logarithm, divide the number by 10^(number of digits), then compute the log of that using math.log10() (or whatever; use a simple series approximation if nothing else is available), and add it to the integer part. Example: to get the fractional part of log10(123456), compute math.log10(0.123456) = -0.908..., and add it to the result of step 1: 6 + -0.908 = 5.092, which is log10(123456). Note that you're basically just tacking on a decimal point to the front of the large number; there is probably a nice way to optimize this in your use case, and for really big numbers you don't even need to bother with grabbing all of the digits -- log10(0.123) is a great approximation to log10(0.123456789).

Answer 2

You could decompose it using

log(a * 10^b) = log(a) + b * log(10)

Basically b+1 is going to be the number of digits in the number, and a will be a value between 0 and 1 which you could compute the logarithm of by using regular double arithmetic.

Or there are mathematical tricks you can use - for instance, logarithms of numbers close to 1 can be computed by a series expansion

ln(x + 1) = x - x^2/2 + x^3/3 - x^4/4 + ...

Depending on what kind of number you're trying to take the logarithm of, there may be something like this you can use.

EDIT: To get the logarithm in base 10, you can divide the natural logarithm by ln(10), or similarly for any other base.

Answer 3

This is what I've come up with:

//http://everything2.com/index.pl?node_id=946812        
public BigDecimal log10(BigDecimal b, int dp)
{
 final int NUM_OF_DIGITS = dp+2; // need to add one to get the right number of dp
                                 //  and then add one again to get the next number
                                 //  so I can round it correctly.

 MathContext mc = new MathContext(NUM_OF_DIGITS, RoundingMode.HALF_EVEN);

 //special conditions:
 // log(-x) -> exception
 // log(1) == 0 exactly;
 // log of a number lessthan one = -log(1/x)
 if(b.signum() <= 0)
  throw new ArithmeticException("log of a negative number! (or zero)");
 else if(b.compareTo(BigDecimal.ONE) == 0)
  return BigDecimal.ZERO;
 else if(b.compareTo(BigDecimal.ONE) < 0)
  return (log10((BigDecimal.ONE).divide(b,mc),dp)).negate();

 StringBuffer sb = new StringBuffer();
 //number of digits on the left of the decimal point
 int leftDigits = b.precision() - b.scale();

 //so, the first digits of the log10 are:
 sb.append(leftDigits - 1).append(".");

 //this is the algorithm outlined in the webpage
 int n = 0;
 while(n < NUM_OF_DIGITS)
 {
  b = (b.movePointLeft(leftDigits - 1)).pow(10, mc);
  leftDigits = b.precision() - b.scale();
  sb.append(leftDigits - 1);
  n++;
 }

 BigDecimal ans = new BigDecimal(sb.toString());

 //Round the number to the correct number of decimal places.
 ans = ans.round(new MathContext(ans.precision() - ans.scale() + dp, RoundingMode.HALF_EVEN));
 return ans;
}

Answer 4

Java Number Cruncher: The Java Programmer's Guide to Numerical Computing provides a solution using Newton's Method. Source code from the book is available here. The following has been taken from chapter 12.5 Big Decmial Functions (p330 & p331):

/**
 * Compute the natural logarithm of x to a given scale, x > 0.
 */
public static BigDecimal ln(BigDecimal x, int scale)
{
    // Check that x > 0.
    if (x.signum() <= 0) {
        throw new IllegalArgumentException("x <= 0");
    }

    // The number of digits to the left of the decimal point.
    int magnitude = x.toString().length() - x.scale() - 1;

    if (magnitude < 3) {
        return lnNewton(x, scale);
    }

    // Compute magnitude*ln(x^(1/magnitude)).
    else {

        // x^(1/magnitude)
        BigDecimal root = intRoot(x, magnitude, scale);

        // ln(x^(1/magnitude))
        BigDecimal lnRoot = lnNewton(root, scale);

        // magnitude*ln(x^(1/magnitude))
        return BigDecimal.valueOf(magnitude).multiply(lnRoot)
                    .setScale(scale, BigDecimal.ROUND_HALF_EVEN);
    }
}

/**
 * Compute the natural logarithm of x to a given scale, x > 0.
 * Use Newton's algorithm.
 */
private static BigDecimal lnNewton(BigDecimal x, int scale)
{
    int        sp1 = scale + 1;
    BigDecimal n   = x;
    BigDecimal term;

    // Convergence tolerance = 5*(10^-(scale+1))
    BigDecimal tolerance = BigDecimal.valueOf(5)
                                        .movePointLeft(sp1);

    // Loop until the approximations converge
    // (two successive approximations are within the tolerance).
    do {

        // e^x
        BigDecimal eToX = exp(x, sp1);

        // (e^x - n)/e^x
        term = eToX.subtract(n)
                    .divide(eToX, sp1, BigDecimal.ROUND_DOWN);

        // x - (e^x - n)/e^x
        x = x.subtract(term);

        Thread.yield();
    } while (term.compareTo(tolerance) > 0);

    return x.setScale(scale, BigDecimal.ROUND_HALF_EVEN);
}

Answer 5

Pseudocode algorithm for doing a logarithm.

Assuming we want log_n of x

result = 0;
base = n;
input = x;

while (input > base)
  result++;
  input /= base;

fraction = 1/2;
input *= input;   

while (((result + fraction) > result) && (input > 1))
  if (input > base)
    input /= base;
    result += fraction;
  input *= input;
  fraction /= 2.0;

The big while loop may seem a bit confusing.

On each pass, you can either square your input or you can take the square root of your base; either way, you must divide your fraction by 2. I find squaring the input, and leaving the base alone, to be more accurate.

If the input goes to 1, we're through. The log of 1, for any base, is 0, which means we don't need to add any more.

if (result + fraction) is not greater than result, then we've hit the limits of precision for our numbering system. We can stop.

Obviously, if you're working with a system which has arbitrarily many digits of precision, you will want to put something else in there to limit the loop.