Logaritmo per BigInteger

Ho un numero BigInteger , per esempio oltre 2 64 . Ora voglio calcolare il logaritmo di quel numero di BigInteger , ma il metodo BigInteger.log() non esiste. Come faccio a calcolare il logaritmo (naturale) del mio grande valore BigInteger ?

Se vuoi supportare arbitrariamente interi grandi, non è sicuro farlo

 Math.log(bigInteger.doubleValue()); 

perché ciò fallirebbe se l’argomento supera il double intervallo (circa 2 ^ 1024 o 10 ^ 308, cioè più di 300 cifre decimali).

Ecco la mia ricetta:

 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 Math.log() */ 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; } 

L’ho provato con BigInteger molto grandi (più di 500000 cifre decimali) e l’errore relativo massimo è sempre stato inferiore a 5.0e-16, che è nell’ordine della double precisione.


Qualche esempio di codice, nel caso tu voglia testarlo tu stesso:

  public static double testLogBigInteger(int[] factors, int[] exponents) { double l1 = 0; BigInteger bi = BigInteger.ONE; for (int i = 0; i < factors.length; i++) { int exponent = exponents[i]; int factor = factors[i]; if (factor <= 1) continue; for (int n = 0; n < exponent; n++) { bi = bi.multiply(BigInteger.valueOf(factor)); } l1 += Math.log(factor) * exponent; } double l2 = logBigInteger(bi); double err = Math.abs((l2 - l1) / l1); int decdigits = (int) (l1 / Math.log(10) + 0.5); System.out.printf("e=%e digitss=%d \n", err, decdigits); return err; } public static void testManyTries(int tries) { int[] f = { 1, 1, 1, 1, 1 }; int[] e = { 1, 1, 1, 1, 1 }; Random r = new Random(); double maxerr = 0; for (int n = 0; n < tries; n++) { for (int i = 0; i < f.length; i++) { f[i] = r.nextInt(100000) + 2; e[i] = r.nextInt(1000) + 1; } double err = testLogBigInteger(f, e); if (err > maxerr) maxerr = err; } System.out.printf("Max err: %e \n", maxerr); } 

Aggiornamento: per completezza e perché ne ho avuto bisogno, ecco una sorta di funzione inversa:

 /** * Same as Math.exp() but returns a BigInteger. Oriented towards big numbers. * Works even for outputs that exceed the double range * * @param b Should be a large positive value * @return The value of e (base of the natural logarithms) raised to the power b */ public static BigInteger bigexp(double b) { if( Double.isNaN(b) || Double.isInfinite(b) ) throw new IllegalArgumentException("Infinite or negative values not accepted: " + b); // e^b = e^(b2+c) = e^b2 2^t with e^c = 2^t double bc = 680.0; if( b < bc ) return BigDecimal.valueOf(Math.exp(b)).setScale(0, BigDecimal.ROUND_HALF_EVEN).toBigInteger(); double b2 = bc; double c = b - bc; int t = (int) Math.ceil(c / LOG2); c = t * LOG2; b2 = b - c; BigInteger v = BigDecimal.valueOf(Math.exp(b2)).setScale(0, BigDecimal.ROUND_HALF_EVEN).toBigInteger(); return v.shiftLeft(t); } public static BigInteger bigpow(double a, double b) { return bigexp(b * Math.log(a)); } 

Ho avuto qualche aiuto da google ma a quanto pare non hai bisogno di applicare il log ai tuoi numeri BigInteger molto grandi direttamente, dal momento che può essere scomposto nel modo seguente:

 928 = 1000 * 0.928 lg 928 = lg 1000 * lg 0.928 = 3 + lg 0.928 

Il tuo problema è quindi ridotto al calcolo / approssimazione dei logaritmi che consentono una precisione crescente arbitraria, forse math.stackexchange.com?

Convertilo in un liek BigDecimal questo:

 new BigDecimal(val); // where val is a BigInteger 

e registro chiamate da BigDecimalUtils su di esso: D

Quanto sei preciso che sia necessario? Se hai solo bisogno di 15 cifre di precisione, puoi farlo

 BigInteger bi = double log = Math.log(bi.doubleValue()); 

Questo funzionerebbe per valori fino a 1023 bit. Dopo di ciò il valore non si adatterebbe più in un doppio.

Se è ansible utilizzare Google Guava e richiede solo il registro di base 2 o di base 10, è ansible utilizzare i metodi della class BigIntegerMath di Guava.