Logarithme d'un BigDecimal

StackOverflow https://stackoverflow.com/questions/739532

  •  09-09-2019
  •  | 
  •  

Question

Comment puis-je calculer le logarithme d'un BigDecimal? Est-ce que quelqu'un sait de tout algorithmes que je peux utiliser?

Mon googler a jusqu'ici trouver la (inutile) idée de la conversion en double et en utilisant Math.log.

Je fournirai la précision de la réponse requise.

edit: toute base fera. S'il est plus facile dans la base x, je vais le faire.

Était-ce utile?

La solution

Java Number Cruncher: Le Guide de Java Programmer à l'informatique numérique fournit une solution en utilisant Méthode de Newton . Le code source du livre est disponible . Ce qui suit a été pris du chapitre 12.5 Fonctions Big Decmial (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);
}

Autres conseils

Un peu algorithme hacky qui fonctionne très bien pour un grand nombre utilise la relation log(AB) = log(A) + log(B). Voici comment le faire dans la base 10 (que vous pouvez convertir en trivialement toute autre base de logarithme):

  1. Comptez le nombre de chiffres décimaux dans la réponse. C'est la partie intégrante de votre logarithme, plus un . Exemple: floor(log10(123456)) + 1 est 6, depuis 123.456 a 6 chiffres

    2. .

  2. Vous pouvez arrêter ici si vous avez besoin est la partie entière du logarithme:. Juste soustrayez 1 du résultat de l'étape 1

  3. Pour la partie décimale du logarithme, diviser le nombre par 10^(number of digits), puis calculer le journal de ce en utilisant math.log10() (ou autre, utiliser une approximation simple de la série si rien est disponible ailleurs), et l'ajouter à la partie entière. Exemple: pour obtenir la fraction de log10(123456), compute math.log10(0.123456) = -0.908..., et l'ajouter au résultat de l'étape 1: 6 + -0.908 = 5.092, qui est log10(123456). Notez que vous êtes fondamentalement juste clouant sur un point décimal à l'avant du grand nombre; il y a probablement une bonne façon d'optimiser dans votre cas d'utilisation, et pour un nombre très gros vous ne même pas besoin de se soucier de saisir tous les chiffres -. log10(0.123) est une approximation log10(0.123456789)

Celui-ci est super rapide, parce que:

  • Non toString()
  • Pas de mathématiques BigInteger (fraction de Newton / suite)
  • Pas même instancier une nouvelle BigInteger
  • utilise seulement un nombre fixe d'opérations très rapides

Un appel dure environ 20 microsecondes (environ 50k appels par seconde)

  • Ne fonctionne que pour BigInteger

Solution pour BigDecimal (non testé pour la vitesse):

  • décaler le point décimal jusqu'à ce que la valeur est> 2 ^ 53
  • Utilisation toBigInteger() (utilise une div interne)

Cet algorithme utilise le fait que le journal peut être calculé comme la somme de l'exposant et le journal de la mantisse. par exemple:

12345 a 5 chiffres, de sorte que le log base 10 est compris entre 4 et 5. log (12345) = 4 + log (1,2345) = 4,09149 ... (log base 10)

Cette fonction calcule log base 2 parce que trouver le nombre de bits occupés est trivial. 

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!
}

Vous pouvez le décomposer en utilisant 

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

En gros b+1 va être le nombre de chiffres du nombre et a sera une valeur comprise entre 0 et 1, vous pouvez calculer le logarithme en utilisant l'arithmétique régulière double.

Ou il y a des trucs mathématiques que vous pouvez utiliser - par exemple, logarithmes des nombres proches de 1 peut être calculé par une extension de la série 

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

Selon le type de numéro que vous essayez de prendre le logarithme, il peut y avoir quelque chose comme cela, vous pouvez utiliser.

EDIT :. Pour obtenir le logarithme en base 10, vous pouvez diviser le logarithme naturel par ln(10), ou même pour toute autre base

est ce que je suis venu avec: 

//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;
}

Une implémentation Java de Meower68 pseudcode que je testé avec quelques chiffres: 

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;
    }

Si tout ce que vous avez besoin est de trouver les puissances de 10 dans le numéro, vous pouvez utiliser: 

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

algorithme pseudo-code pour faire un logarithme.

En supposant que nous voulons log_n x 

double fraction, input;
int base;
double result;

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;
 }

La grande boucle while peut sembler un peu confus.

Sur chaque passe, vous pouvez soit carré votre entrée ou vous pouvez prendre la racine carrée de votre base; De toute façon, vous devez diviser votre fraction 2. Je trouve l'entrée d'élévation au carré, et en laissant la base seule, pour être plus précis.

Si l'entrée passe à 1, nous sommes à travers. Le journal de 1, pour toute base, est 0, ce qui signifie que nous ne avons pas besoin d'ajouter plus.

if (résultat + fraction) n'est pas supérieure résultat, nous avons atteint les limites de précision pour notre système de numérotation. Nous pouvons arrêter.

De toute évidence, si vous travaillez avec un système qui a arbitrairement de chiffres de précision, vous voulez mettre quelque chose d'autre là-bas pour limiter la boucle.

Je cherchais cette chose exacte et finalement allé avec une approche de fraction continue. La fraction continue se trouve à ou ici

Code: 

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;
}

vieille question, mais je pense que cette réponse est préférable. Il a une bonne précision et prend en charge les arguments de pratiquement toute taille. 

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;
}

La logique de noyau (méthode de logBigInteger) est copiée à partir de cette autre réponse de la mine .

J'ai créé une fonction pour BigInteger mais il peut être facilement modifié pour BigDecimal. Le journal et décomposant en utilisant certaines propriétés du journal est ce que je fais, mais je reçois seulement double précision. Mais cela fonctionne pour toute base. :) 

public double BigIntLog(BigInteger bi, double base) {
    // Convert the BigInteger to BigDecimal
    BigDecimal bd = new BigDecimal(bi);
    // Calculate the exponent 10^exp
    BigDecimal diviser = new BigDecimal(10);
    diviser = diviser.pow(bi.toString().length()-1);
    // Convert the BigDecimal from Integer to a decimal value
    bd = bd.divide(diviser);
    // Convert the BigDecimal to double
    double bd_dbl = bd.doubleValue();
    // return the log value
    return (Math.log10(bd_dbl)+bi.toString().length()-1)/Math.log10(base);
}
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top