java.math.BigInteger pow (exposant) question

Question

J'ai fait quelques tests sur la méthode pow (exponent). Malheureusement, mes compétences en mathématiques ne sont pas assez fortes pour gérer le problème suivant.

J'utilise ce code:

BigInteger.valueOf(2).pow(var); 

Résultats:

• var | temps en ms
• 2000000 |
• 2500000 |
• 3000000 | 22379
• 3500000 | 32147
• 4000000 |
• 4500000 |
• 5000000 | 49922

Voir? 2,500,000 exposant est calculé presque aussi vite que 2,000,000. 4 500 000 est calculé beaucoup plus vite que 4 000 000.

Pourquoi est-ce?

Pour vous donner un peu d'aide, voici l'implémentation originale de BigInteger.pow (exposant):

public BigInteger pow(int exponent) { 
    if (exponent < 0) 
     throw new ArithmeticException("Negative exponent"); 
    if (signum==0) 
     return (exponent==0 ? ONE : this); 

    // Perform exponentiation using repeated squaring trick 
     int newSign = (signum<0 && (exponent&1)==1 ? -1 : 1); 
    int[] baseToPow2 = this.mag; 
     int[] result = {1}; 

    while (exponent != 0) { 
     if ((exponent & 1)==1) { 
     result = multiplyToLen(result, result.length, 
             baseToPow2, baseToPow2.length, null); 
     result = trustedStripLeadingZeroInts(result); 
     } 
     if ((exponent >>>= 1) != 0) { 
       baseToPow2 = squareToLen(baseToPow2, baseToPow2.length, null); 
     baseToPow2 = trustedStripLeadingZeroInts(baseToPow2); 
     } 
    } 
    return new BigInteger(result, newSign); 
    } 

Answer 1

L'algorithme utilise l'équarrissage répété (squareToLen) et la multiplication (multiplyToLen).Le délai d'exécution de ces opérations dépend de la taille des numéros concernés. Les multiplications des grands nombres vers la fin du calcul sont beaucoup plus chères que celles du début. La multiplication n'est effectuée que lorsque cette condition est vraie: ((exponent & 1)==1). Le nombre d'opérations carrées dépend du nombre de bits dans le nombre (sauf les zéros en tête), mais une multiplication n'est requise que pour les bits qui sont mis à 1. Il est plus facile de voir les opérations requises en regardant le binaire représentation du nombre:

 
2000000: 0000111101000010010000000 
2500000: 0001001100010010110100000 
3000000: 0001011011100011011000000 
3500000: 0001101010110011111100000 
4000000: 0001111010000100100000000 
4500000: 0010001001010101000100000 
5000000: 0010011000100101101000000 

Notez que 2,5M et 4,5M sont chanceux car ils ont moins de bits élevés fixés que les chiffres qui les entourent. La prochaine fois que cela se produit est à 8.5M:

 
8000000: 0011110100001001000000000 
8500000: 0100000011011001100100000 
9000000: 0100010010101010001000000 

Les taches douces sont des puissances exactes de 2.

 
1048575: 0001111111111111111111111 // 16408 ms 
1048576: 0010000000000000000000000 // 6209 ms 

Answer 2

Juste une supposition:

l'exposant est géré peu à peu, et si le moins significatif bit est 1 travail supplémentaire est fait.

Si L est le nombre de bits de l'exposant et A le nombre de bits qui sont une et t1 le temps de traiter la partie commune et t2 le traitement en temps supplémentaire lorsque le LSBit est une

puis le temps d'exécution serait

l t1 + t2 A

ou le temps est dépendante du nombre de 1 dans la représentation binaire.

en train d'écrire un petit programme pour vérifier ma théorie ...

Answer 3

Je ne sais pas combien de fois vous avez exécuté vos horaires. Comme l'ont souligné certains commentateurs, vous devez effectuer des opérations de temps plusieurs fois pour obtenir de bons résultats (et ils peuvent encore se tromper).

En supposant que vous avez bien synchronisé les choses, rappelez-vous qu'il y a beaucoup de raccourcis qui peuvent être pris en mathématiques. Vous n'avez pas à faire les opérations 5 * 5 * 5 * 5 * 5 * 5 pour calculer 5^6.

Voici une façon de le faire beaucoup plus rapidement.