BigInteger: compter le nombre de chiffres après la virgule dans une méthode évolutive
J'ai besoin de compter le nombre de chiffres après la virgule d'un BigInteger
. Par exemple:
99
retourne2
1234
retourne4
9999
retourne4
12345678901234567890
retourne20
J'ai besoin pour ce faire pour un BigInteger
avec 184948
chiffres décimaux et plus. Comment puis-je faire rapide et évolutive?
La convertir en Chaîne de approche est lente:
public String getWritableNumber(BigInteger number) {
//Takes over 30 seconds for 184948 decimal digits
return "10^" + (number.toString().length() - 1);
}
Ce boucle-diviser par dix approche est d'autant plus lente:
public String getWritableNumber(BigInteger number) {
int digitSize = 0;
while (!number.equals(BigInteger.ZERO)) {
number = number.divide(BigInteger.TEN);
digitSize++;
}
return "10^" + (digitSize - 1);
}
Existe-il des méthodes plus rapides?
La lenteur est-il et à quelle vitesse avez-vous besoin?
Le plus rapide des 2 prend plus de 30 secondes pour un certain nombre de 184948 chiffres après la virgule. J'ai besoin d'elle à moins de 2 secondes.
2 secondes? Cela sonne un peu comme la limite de temps d'une programmation de la concurrence.
Il y a quelques belles twiddles pour ce faire, essayez de ici pour commencer. Peuvent ne pas s'appliquer à BigInteger.
Avec Goyave, c'est le one-liner
Le plus rapide des 2 prend plus de 30 secondes pour un certain nombre de 184948 chiffres après la virgule. J'ai besoin d'elle à moins de 2 secondes.
2 secondes? Cela sonne un peu comme la limite de temps d'une programmation de la concurrence.
Il y a quelques belles twiddles pour ce faire, essayez de ici pour commencer. Peuvent ne pas s'appliquer à BigInteger.
Avec Goyave, c'est le one-liner
BigIntegerMath.log10(x, RoundingMode.FLOOR) + 1
. Goyave utilise plusieurs astuces présentées ici.OriginalL'auteur Geoffrey De Smet | 2013-09-16
Vous devez vous connecter pour publier un commentaire.
Il semble que ça fonctionne. Je n'ai pas exécuter des tests exhaustifs encore, n or j'ai exécuté à tout moment des tests, mais il semble raisonnable de l'exécution.
A pris environ 3 secondes sur mon Celeron M ordinateur portable de sorte qu'il devrait frapper sous 2 secondes sur un bon kit.
J'ai trouvé une erreur dans le code lors du test - j'ai été en utilisant bitCount au lieu de bitLength - veuillez actualiser votre copie si vous avez pris une. Maintenant prend environ 0,22 secondes pour votre grand nombre.
Si vous souhaitez un algorithme plus rapide, prendre un coup d'oeil à ce que BigDecimal utilise pour calculer la longueur de sa mantisse 🙂
OriginalL'auteur OldCurmudgeon
Voici une méthode rapide basée sur Dariusz réponse:
Le code suivant vérifie les numéros de 1, 9, 10, 99, 100, 999, 1000, etc. tout le chemin à dix-mille chiffres:
Cela peut cocher une
BigInteger
avec184,948
chiffres décimaux et de plus en moins d'une seconde.OriginalL'auteur dln385
Je pense que vous pourriez utiliser bitLength() pour obtenir un log2 valeur, puis le changement de la base de 10.
Le résultat peut-être tort, cependant, par un chiffre, alors c'est seulement une approximation.
Cependant, si c'est acceptable, vous pouvez toujours ajouter 1 au résultat et lié à être au plus. Ou, soustraire 1, et obtenir au moins.
Il peut être possible de combiner cela avec
testBit
dans une boucle pour obtenir une réponse exacte, même si il est lent pour certains cas.Je ne peux pas penser comment le faire sans calculer le nombre d'origine. Vous pouvez tester quelques derniers morceaux, mais vous auriez du faire face à des probabilités de toute façon.
Eh bien, si vous avez 16 bits, la gamme est de 65536 (5 chiffres) - 131071 (6 chiffres). Si vous cochez les 3 premiers bits et vous obtenez
111
, ce serait une garantie de 6 chiffres, de même10
garanties 5 chiffres. De sorte que vous pouvez vraiment juste garder le contrôle de la gauche jusqu'à ce que vous obtenir dans une certaine gamme contenant un nombre fixe de chiffres.Faire BigInteger.pow() est relativement rapide (moins de 1 seconde pour 184948 chiffres décimaux IIRC). Alors peut-être
10.pow(result)
peut être utilisé pour résoudre le par 1 chiffre problèmeOriginalL'auteur Dariusz
C'est une autre façon de le faire plus vite que de Convertir en Chaîne de la méthode. Pas le meilleur moment de l'exécution, mais encore raisonnable de 0,65 secondes, contre 2.46 secondes avec Convertir en Chaîne de la méthode (à 180000 chiffres).
Cette méthode calcule la partie entière du logarithme en base 10 de la valeur donnée. Cependant, au lieu d'utiliser la boucle de diviser, il utilise une technique similaire à celle de l'Exponentiation par la Quadrature.
Ici n'est qu'une grossière mise en œuvre qui permet de réaliser l'exécution mentionné plus tôt:
Espérons que cela vous aide.
OriginalL'auteur Truthseeker Rangwan