큰 수의 로그

https://stackoverflow.com/questions/739532

09-09-2019
|

문제

BigDecimal의 로그를 어떻게 계산할 수 있습니까? 내가 사용할 수있는 알고리즘을 아는 사람이 있습니까?

지금까지의 인터넷 검색은 단지 더블로 변환하고 Math.Log를 사용한다는 (쓸모없는) 아이디어를 제시했습니다.

필요한 답변의 정밀도를 제공하겠습니다.

편집 : 모든 기지가 수행됩니다. 기본 X에서 더 쉽다면 그렇게하겠습니다.

해결책

Java Number Cruncher : 수치 컴퓨팅에 대한 Java 프로그래머 안내서 사용 솔루션을 제공합니다 뉴턴의 방법. 책의 소스 코드를 사용할 수 있습니다 여기. 다음은 장에서 가져 왔습니다 12.5 큰 경사 기능 (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);
}

다른 팁

많은 숫자에 적합한 해킹 된 작은 알고리즘은 관계를 사용합니다. log(AB) = log(A) + log(B). 다음은 기본 10에서 수행하는 방법입니다 (다른 로그 기반으로 사소하게 변환 할 수 있음).

답에 소수점 숫자의 수를 계산하십시오. 그것은 로그의 필수 부분입니다. 하나 추가. 예시: floor(log10(123456)) + 1 123456은 6 자리를 가지고 있기 때문에 6입니다.
필요한 모든 것이 로그의 정수 부분 만 있으면 여기서 멈출 수 있습니다. 1 단계 결과에서 1 만 빼십시오.
로그의 분수 부분을 얻으려면 숫자를 10^(number of digits), 그런 다음 사용하는 로그를 계산하십시오 math.log10() (또는 무엇이든; 다른 것이 없으면 간단한 시리즈 근사치를 사용하고 정수 부분에 추가하십시오. 예 : 분수 부분을 얻으려면 log10(123456), 계산 math.log10(0.123456) = -0.908..., 1 단계의 결과에 추가하십시오. 6 + -0.908 = 5.092, 그것은 log10(123456). 당신은 기본적으로 많은 수의 소수점을 다수의 앞쪽으로 다루고 있습니다. 유스 케이스에서 이것을 최적화하는 좋은 방법이있을 것입니다. 실제로 큰 숫자의 경우 모든 숫자를 잡는 데 귀찮게 할 필요조차 없습니다. log10(0.123) 큰 근사치입니다 log10(0.123456789).

이것은 매우 빠릅니다. 왜냐하면 :이기 때문입니다.

아니 toString()
아니 BigInteger 수학 (Newton 's/Contined Fraction)
새로운 것을 인스턴스화조차하지 않습니다 BigInteger
고정 된 수의 매우 빠른 작업 만 사용합니다

한 번의 통화는 약 20 마이크로 초가 필요합니다 (초당 약 50k 호출)

하지만:

만 작동합니다 BigInteger

해결 방법 BigDecimal (속도 테스트되지 않음) :

값이> 2^53이 될 때까지 소수점을 이동
사용 toBigInteger() (하나를 사용합니다 div 내부)

이 알고리즘은 로그가 지수의 합 및 Mantissa의 로그로 계산 될 수 있다는 사실을 사용합니다. 예 :

12345는 5 자리 숫자가 있으므로베이스 10 로그는 4와 5 사이입니다. 로그 (12345) = 4 + log (1.2345) = 4.09149 ... (베이스 10 로그)

이 함수는 점유 비트의 수를 찾는 것이 사소한 것이므로 기본 2 로그를 계산합니다.

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

당신은 그것을 사용하여 분해 할 수 있습니다

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

원래 b+1 숫자의 숫자 수가 될 것입니다. a 정기적으로 사용하여 로그를 계산할 수있는 0과 1 사이의 값이됩니다. double 산수.

또는 사용할 수있는 수학적 트릭이 있습니다. 예를 들어, 1에 가까운 숫자 로그는 시리즈 확장으로 계산할 수 있습니다.

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

로그를 가져 가려고하는 숫자에 따라 사용할 수있는 것과 같은 것이있을 수 있습니다.

편집하다:베이스 10에서 로그를 얻으려면 자연 로그를 ln(10), 또는 다른 기지에 대해서도 유사하게.

이것이 제가 생각해 낸 것입니다.

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

몇 가지 숫자로 테스트 한 Meower68 Pseudcode의 Java 구현 :

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

필요한 것은 사용할 수있는 숫자에서 10의 힘을 찾는 것입니다.

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

로그를 수행하기위한 의사 코드 알고리즘.

x의 log_n을 원한다고 가정합니다

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

큰 루프는 약간 혼란스러워 보일 수 있습니다.

각 패스에서 입력을 제곱하거나베이스의 제곱근을 취할 수 있습니다. 어느 쪽이든, 당신은 당신의 분수를 2로 나누어야합니다. 나는 입력을 제곱하고베이스를 내버려두고 더 정확합니다.

입력이 1로 이동하면 우리는 모든베이스의 1의 로그는 0이므로 더 이상 추가 할 필요가 없습니다.

(결과 + fraction)이 결과보다 크지 않은 경우 번호 시스템의 정밀도에 도달했습니다. 우리는 멈출 수있다.

분명히, 정밀도가 많은 시스템으로 작업하고 있다면 루프를 제한하기 위해 다른 것을 넣고 싶을 것입니다.

나는이 정확한 것을 찾고 있었고 결국 지속적인 분수 접근법으로 갔다. 지속적인 분수는에서 찾을 수 있습니다 여기 또는 여기

암호:

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

오래된 질문이지만 실제로이 대답이 바람직하다고 생각합니다. 정밀도가 좋고 실질적으로 모든 크기의 주장을 지원합니다.

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

핵심 논리 (logBigInteger 메소드)가 복사됩니다 이 다른 대답 내.

BigInteger에 대한 기능을 만들었지 만 BigDecimal을 위해 쉽게 수정할 수 있습니다. 로그를 분해하고 로그의 일부 속성을 사용하는 것은 내가하는 일이지만 이중 정밀도 만 얻습니다. 그러나 그것은 어떤 기지에서도 작동합니다. :)

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

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow