Logarithmus eines BigDecimal

Question

Wie kann ich den Logarithmus eines BigDecimal berechnen? Kennt jemand irgendwelche Algorithmen, die ich verwenden kann?

Mein bisheriges Google hat sich die (nutzlose) Idee ausgedacht, einfach zu einem Double zu konvertieren und Math.log zu verwenden.

Ich werde die Genauigkeit der Antwort zur Verfügung stellen.

bearbeiten: jede Basis wird tun. Wenn es in Base x einfacher ist, mache ich das.

Answer 1

Java Number Cruncher: The Java Programmer's Guide to Numerical Computing bietet eine Lösung mit Newton's Method. Quellcode aus dem Buch ist verfügbar here. Folgendes wurde dem Kapitel 12 entnommen.5 Big Decmial Funktionen (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); 
} 

/** 
* Compute the integral root of x to a given scale, x >= 0. 
* Use Newton's algorithm. 
* @param x the value of x 
* @param index the integral root value 
* @param scale the desired scale of the result 
* @return the result value 
*/ 
public static BigDecimal intRoot(BigDecimal x, long index, 
           int scale) 
{ 
    // Check that x >= 0. 
    if (x.signum() < 0) { 
     throw new IllegalArgumentException("x < 0"); 
    } 

    int  sp1 = scale + 1; 
    BigDecimal n = x; 
    BigDecimal i = BigDecimal.valueOf(index); 
    BigDecimal im1 = BigDecimal.valueOf(index-1); 
    BigDecimal tolerance = BigDecimal.valueOf(5) 
             .movePointLeft(sp1); 
    BigDecimal xPrev; 

    // The initial approximation is x/index. 
    x = x.divide(i, scale, BigDecimal.ROUND_HALF_EVEN); 

    // Loop until the approximations converge 
    // (two successive approximations are equal after rounding). 
    do { 
     // x^(index-1) 
     BigDecimal xToIm1 = intPower(x, index-1, sp1); 

     // x^index 
     BigDecimal xToI = 
       x.multiply(xToIm1) 
        .setScale(sp1, BigDecimal.ROUND_HALF_EVEN); 

     // n + (index-1)*(x^index) 
     BigDecimal numerator = 
       n.add(im1.multiply(xToI)) 
        .setScale(sp1, BigDecimal.ROUND_HALF_EVEN); 

     // (index*(x^(index-1)) 
     BigDecimal denominator = 
       i.multiply(xToIm1) 
        .setScale(sp1, BigDecimal.ROUND_HALF_EVEN); 

     // x = (n + (index-1)*(x^index))/(index*(x^(index-1))) 
     xPrev = x; 
     x = numerator 
       .divide(denominator, sp1, BigDecimal.ROUND_DOWN); 

     Thread.yield(); 
    } while (x.subtract(xPrev).abs().compareTo(tolerance) > 0); 

    return x; 
} 

/** 
* Compute e^x to a given scale. 
* Break x into its whole and fraction parts and 
* compute (e^(1 + fraction/whole))^whole using Taylor's formula. 
* @param x the value of x 
* @param scale the desired scale of the result 
* @return the result value 
*/ 
public static BigDecimal exp(BigDecimal x, int scale) 
{ 
    // e^0 = 1 
    if (x.signum() == 0) { 
     return BigDecimal.valueOf(1); 
    } 

    // If x is negative, return 1/(e^-x). 
    else if (x.signum() == -1) { 
     return BigDecimal.valueOf(1) 
        .divide(exp(x.negate(), scale), scale, 
          BigDecimal.ROUND_HALF_EVEN); 
    } 

    // Compute the whole part of x. 
    BigDecimal xWhole = x.setScale(0, BigDecimal.ROUND_DOWN); 

    // If there isn't a whole part, compute and return e^x. 
    if (xWhole.signum() == 0) return expTaylor(x, scale); 

    // Compute the fraction part of x. 
    BigDecimal xFraction = x.subtract(xWhole); 

    // z = 1 + fraction/whole 
    BigDecimal z = BigDecimal.valueOf(1) 
         .add(xFraction.divide(
           xWhole, scale, 
           BigDecimal.ROUND_HALF_EVEN)); 

    // t = e^z 
    BigDecimal t = expTaylor(z, scale); 

    BigDecimal maxLong = BigDecimal.valueOf(Long.MAX_VALUE); 
    BigDecimal result = BigDecimal.valueOf(1); 

    // Compute and return t^whole using intPower(). 
    // If whole > Long.MAX_VALUE, then first compute products 
    // of e^Long.MAX_VALUE. 
    while (xWhole.compareTo(maxLong) >= 0) { 
     result = result.multiply(
          intPower(t, Long.MAX_VALUE, scale)) 
        .setScale(scale, BigDecimal.ROUND_HALF_EVEN); 
     xWhole = xWhole.subtract(maxLong); 

     Thread.yield(); 
    } 
    return result.multiply(intPower(t, xWhole.longValue(), scale)) 
        .setScale(scale, BigDecimal.ROUND_HALF_EVEN); 
} 

Answer 2

Ein hacky kleiner Algorithmus, der für große Zahlen funktioniert, verwendet die Beziehung log(AB) = log(A) + log(B). Hier ist, wie es zu tun in der Basis 10 (die man trivialerweise auf andere Logarithmusbasis umwandeln kann):

1. Zählen Sie die Anzahl der Dezimalstellen in der Antwort. Das ist der integrale Teil Ihres Logarithmus, plus eins. Beispiel: floor(log10(123456)) + 1 ist 6, da 123456 6 Ziffern hat.

2. Sie können hier aufhören, wenn alles, was Sie den ganzzahligen Teil des Logarithmus müssen: nur 1 subtrahieren aus dem Ergebnis von Schritt 1

3. Um den Bruchteil des Logarithmus zu erhalten, teilen Sie die Zahl von 10^(number of digits) Berechnen Sie dann das Protokoll mit math.log10() (oder was auch immer; verwenden Sie eine einfache Serienapproximation, wenn nichts anderes verfügbar ist), und fügen Sie es dem ganzzahligen Teil hinzu. Beispiel: Um den Bruchteil von log10(123456) zu erhalten, berechnen Sie math.log10(0.123456) = -0.908..., und fügen Sie es zu dem Ergebnis von Schritt 1 hinzu: 6 + -0.908 = 5.092, das log10(123456) ist. Beachten Sie, dass Sie im Grunde nur einen Dezimalpunkt an die Vorderseite der großen Zahl anheften; es gibt wahrscheinlich eine gute Möglichkeit, dies in Ihrem Anwendungsfall zu optimieren, und für wirklich große Zahlen müssen Sie nicht einmal alle Ziffern anfassen - log10(0.123) ist eine große Annäherung an log10(0.123456789).

Answer 3

Man könnte es

mit zersetzen

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

Grundsätzlich b+1 wird die Anzahl der Stellen in der Zahl sein, und a wird ein Wert zwischen 0 und 1 liegen, die man den Logarithmus berechnen könnte durch regelmäßige Verwendung double Arithmetik.

Oder es gibt mathematische Tricks, die Sie verwenden können - zum Beispiel, Logarithmen von Zahlen nahe 1 kann

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

Je nach durch eine Reihenentwicklung berechnet werden, welche Art von Nummer Sie versuchen, den Logarithmus zu nehmen Vielleicht gibt es so etwas, das du benutzen kannst.

EDIT: Um den Logarithmus in der Basis 10 zu erhalten, können Sie den natürlichen Logarithmus dividieren durch ln(10) oder in ähnlicher Weise für jede andere Basis.

Answer 4

Dies ist, was ich habe kommen mit:

//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 5

Pseudocode-Algorithmus für einen Logarithmus zu tun.

Angenommen, wir wollen log_n von 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; 

Der große while-Schleife ein wenig verwirrend erscheinen mag.

Bei jedem Durchgang können Sie entweder Ihre Eingabe quadrieren oder Sie können die Quadratwurzel Ihrer Basis nehmen; So oder so, Sie müssen Ihren Bruch durch 2 teilen. Ich finde die Eingabe quadrieren und die Basis in Ruhe lassen, um genauer zu sein.

Wenn der Eingang auf 1 geht, sind wir durch. Der Logarithmus von 1 für jede Base ist 0, was bedeutet, dass wir keine weiteren hinzufügen müssen.

Wenn (Ergebnis + Bruch) nicht größer als Ergebnis ist, dann haben wir die Grenzen der Genauigkeit für unser Nummerierungssystem erreicht. Wir können aufhören.

Offensichtlich, wenn Sie mit einem System arbeiten, das beliebig viele Stellen der Genauigkeit hat, wollen Sie etwas anderes dort setzen, um die Schleife zu begrenzen.

Answer 6

Eine Java-Implementierung von Meower68 pseudcode, die ich mit ein paar Zahlen getestet:

public static BigDecimal log(int base_int, BigDecimal x) { 
     BigDecimal result = BigDecimal.ZERO; 

     BigDecimal input = new BigDecimal(x.toString()); 
     int decimalPlaces = 100; 
     int scale = input.precision() + decimalPlaces; 

     int maxite = 10000; 
     int ite = 0; 
     BigDecimal maxError_BigDecimal = new BigDecimal(BigInteger.ONE,decimalPlaces + 1); 
     System.out.println("maxError_BigDecimal " + maxError_BigDecimal); 
     System.out.println("scale " + scale); 

     RoundingMode a_RoundingMode = RoundingMode.UP; 

     BigDecimal two_BigDecimal = new BigDecimal("2"); 
     BigDecimal base_BigDecimal = new BigDecimal(base_int); 

     while (input.compareTo(base_BigDecimal) == 1) { 
      result = result.add(BigDecimal.ONE); 
      input = input.divide(base_BigDecimal, scale, a_RoundingMode); 
     } 

     BigDecimal fraction = new BigDecimal("0.5"); 
     input = input.multiply(input); 
     BigDecimal resultplusfraction = result.add(fraction); 
     while (((resultplusfraction).compareTo(result) == 1) 
       && (input.compareTo(BigDecimal.ONE) == 1)) { 
      if (input.compareTo(base_BigDecimal) == 1) { 
       input = input.divide(base_BigDecimal, scale, a_RoundingMode); 
       result = result.add(fraction); 
      } 
      input = input.multiply(input); 
      fraction = fraction.divide(two_BigDecimal, scale, a_RoundingMode); 
      resultplusfraction = result.add(fraction); 
      if (fraction.abs().compareTo(maxError_BigDecimal) == -1){ 
       break; 
      } 
      if (maxite == ite){ 
       break; 
      } 
      ite ++; 
     } 

     MathContext a_MathContext = new MathContext(((decimalPlaces - 1) + (result.precision() - result.scale())),RoundingMode.HALF_UP); 
     BigDecimal roundedResult = result.round(a_MathContext); 
     BigDecimal strippedRoundedResult = roundedResult.stripTrailingZeros(); 
     //return result; 
     //return result.round(a_MathContext); 
     return strippedRoundedResult; 
    } 

Answer 7

Wenn alles, was Sie brauchen, um die Kräfte von 10 in der Zahl zu finden ist, können Sie:

public int calculatePowersOf10(BigDecimal value) 
{ 
    return value.round(new MathContext(1)).scale() * -1; 
} 

Answer 8

Ich war auf der Suche nach genau diesem Ding und ging schließlich mit einem fortgesetzten Fraktionsansatz.Die fortgesetzte Fraktion kann bei here oder here

-Code zu finden:

import java.math.BigDecimal; 
import java.math.MathContext; 

public static long ITER = 1000; 
public static MathContext context = new MathContext(100); 
public static BigDecimal ln(BigDecimal x) { 
    if (x.equals(BigDecimal.ONE)) { 
     return BigDecimal.ZERO; 
    } 

    x = x.subtract(BigDecimal.ONE); 
    BigDecimal ret = new BigDecimal(ITER + 1); 
    for (long i = ITER; i >= 0; i--) { 
    BigDecimal N = new BigDecimal(i/2 + 1).pow(2); 
     N = N.multiply(x, context); 
     ret = N.divide(ret, context); 

     N = new BigDecimal(i + 1); 
     ret = ret.add(N, context); 

    } 

    ret = x.divide(ret, context); 
    return ret; 
} 

Answer 9

Dieser ist super schnell, denn:

• Nein toString()
• Nein BigInteger Mathe (Newtons/Kettenbruch)
• Nicht einmal instanziieren eine neue BigInteger
• verwendet nur eine feste Anzahl von sehr schnellen Operationen

Ein Anruf etwa 20 Mikrosekunden (ca. 50k Anrufe pro Sekunde)

Aber nimmt:

• Dies funktioniert nur für BigInteger

Problemumgehung für BigDecimal (nicht auf Geschwindigkeit getestet):

• Verschieben des Dezimalpunktes, bis der Wert> 2^53
• Verwendung toBigInteger() (ein div verwendet intern)

---

Dieser Algorithmus nutzt die Tatsache, dass das Protokoll berechnet werden kann als die Summe des Exponenten und des Logarithmus der Mantisse. Beispiel:

12345 hat 5 Stellen, so dass die Basis 10 log liegt zwischen 4 und 5. log (12345) = 4 + log (1,2345) = 4,09149 ... (Basis 10 log)

---

Diese Funktion berechnet das Log der Basis 2, da das Auffinden der Anzahl der belegten Bits trivial ist.

public double log(BigInteger val) 
{ 
    // Get the minimum number of bits necessary to hold this value. 
    int n = val.bitLength(); 

    // Calculate the double-precision fraction of this number; as if the 
    // binary point was left of the most significant '1' bit. 
    // (Get the most significant 53 bits and divide by 2^53) 
    long mask = 1L << 52; // mantissa is 53 bits (including hidden bit) 
    long mantissa = 0; 
    int j = 0; 
    for (int i = 1; i < 54; i++) 
    { 
     j = n - i; 
     if (j < 0) break; 

     if (val.testBit(j)) mantissa |= mask; 
     mask >>>= 1; 
    } 
    // Round up if next bit is 1. 
    if (j > 0 && val.testBit(j - 1)) mantissa++; 

    double f = mantissa/(double)(1L << 52); 

    // Add the logarithm to the number of bits, and subtract 1 because the 
    // number of bits is always higher than necessary for a number 
    // (ie. log2(val)<n for every val). 
    return (n - 1 + Math.log(f) * 1.44269504088896340735992468100189213742664595415298D); 
    // Magic number converts from base e to base 2 before adding. For other 
    // bases, correct the result, NOT this number! 
} 

Answer 10

Alte Frage, aber ich denke eigentlich, diese Antwort ist vorzuziehen. Es hat eine gute Präzision und unterstützt Argumente praktisch jeder Größe.

private static final double LOG10 = Math.log(10.0); 

/** 
* Computes the natural logarithm of a BigDecimal 
* 
* @param val Argument: a positive BigDecimal 
* @return Natural logarithm, as in Math.log() 
*/ 
public static double logBigDecimal(BigDecimal val) { 
    return logBigInteger(val.unscaledValue()) + val.scale() * Math.log(10.0); 
} 

private static final double LOG2 = Math.log(2.0); 

/** 
* Computes the natural logarithm of a BigInteger. Works for really big 
* integers (practically unlimited) 
* 
* @param val Argument, positive integer 
* @return Natural logarithm, as in <tt>Math.log()</tt> 
*/ 
public static double logBigInteger(BigInteger val) { 
    int blex = val.bitLength() - 1022; // any value in 60..1023 is ok 
    if (blex > 0) 
     val = val.shiftRight(blex); 
    double res = Math.log(val.doubleValue()); 
    return blex > 0 ? res + blex * LOG2 : res; 
} 

Kernlogik (logBigInteger Methode) von this other answer von mir kopiert.