Comment gérer de très grands nombres en Java sans utiliser java.math.BigInteger ?

Question

Comment faire de l'arithmétique, + - / * % !, avec des nombres entiers arbitrairement grands sans utiliser java.math.BigInteger ?

Par exemple, la factorielle de 90 renvoie 0 en Java. J'aimerais être en mesure de résoudre ce problème.

Answer 1

Je pense qu'un programmeur devrait avoir implémenté sa propre bignum-library une fois, donc bienvenue ici.

(Bien sûr, plus tard, vous comprendrez que BigInteger est meilleur, et vous l'utiliserez, mais c'est une expérience d'apprentissage précieuse).

(Vous pouvez suivre le code source de ce cours vie sur github . Aussi, j'ai refait ceci (un peu poli) dans une Série de blogs en 14 parties .)

Création d'une classe simple de grands nombres en Java

Alors, de quoi avons-nous besoin ?

Tout d'abord, une représentation du nombre,

basé sur les types de données que Java nous donne.

Comme vous pensez que la conversion décimale est la partie la plus compliquée, restons dans un mode basé sur les décimales. Pour des raisons d'efficacité, nous n'enregistrerons pas de véritables chiffres décimaux, mais travaillerons en base 1 000 000 000 = 10^9 < 2^30 . Cela s'inscrit dans un programme Java int (jusqu'à 2^31 ou 2^32 ), et le produit de deux de ces chiffres s'intègre parfaitement dans une Java long .

final static int BASE = 1000000000;
final static int BASE_DECIMAL_DIGITS = 9;

Puis le tableau des chiffres :

private int[] digits;

Stockons-nous les chiffres en little- ou big-endian, c'est-à-dire les plus grands en premier ou en dernier ? Cela n'a pas vraiment d'importance, nous optons donc pour big-endian puisque c'est ainsi que les humains veulent le lire. (Pour l'instant, nous nous concentrons sur les valeurs non négatives - plus tard, nous ajouterons un bit de signe pour les nombres négatifs).

Pour des raisons de test, nous ajoutons un constructeur qui permet d'initialiser à partir d'un tel int[].

/**
 * creates a DecimalBigInt based on an array of digits.
 * @param digits a list of digits, each between 0 (inclusive)
 *    and {@link BASE} (exclusive).
 * @throws IllegalArgumentException if any digit is out of range.
 */
public DecimalBigInt(int... digits) {
    for(int digit : digits) {
        if(digit < 0 ||  BASE <= digit) {
            throw new IllegalArgumentException("digit " + digit +
                                               " out of range!");
        }
    }
    this.digits = digits.clone();
}

En prime, ce constructeur est également utilisable pour une seule et unique int (si elle est inférieure à BASE ), et même pour aucun int (que nous interpréterons comme 0). Donc, nous pouvons maintenant faire ceci :

DecimalBigInt d = new DecimalBigInt(7, 5, 2, 12345);
System.out.println(d);

Cela nous donne de.fencing_game.paul.examples.DecimalBigInt@6af62373 pas si utile. Donc, nous ajoutons un toString() método:

/**
 * A simple string view for debugging purposes.
 * (Will be replaced later with a real decimal conversion.)
 */
public String toString() {
    return "Big" + Arrays.toString(digits);
}

La sortie est maintenant Big[7, 5, 2, 12345] ce qui est plus utile pour les tests, n'est-ce pas ?

Deuxièmement, la conversion du format décimal.

Nous avons de la chance ici : notre base (10^9) est une puissance de la base que nous voulons convertir (10). Ainsi, nous avons toujours le même nombre (9) de chiffres décimaux représentant un chiffre de "notre format". (Bien sûr, au début, il peut y avoir quelques chiffres de moins.) Dans le code suivant, decimal est une chaîne de chiffres décimaux.

 int decLen = decimal.length();
 int bigLen = (decLen-1) / BASE_DECIMAL_DIGITS + 1;

Cette formule étrange est une façon Java int d'écrire bigLen = ceil(decLen/BASE_DECIMAL_DIGITS) . (J'espère que c'est correct, nous le testerons plus tard).

 int firstSome = decLen - (bigLen-1) * BASE_DECIMAL_DIGITS;

Il s'agit de la longueur du premier bloc de chiffres décimaux, qui doit être comprise entre 1 et 9 (inclus).

Nous créons notre tableau :

 int[] digits = new int[bigLen];

Passage en boucle des chiffres à créer :

 for(int i = 0; i < bigLen; i++) {

Chacun des notre est représenté par un bloc de chiffres dans le numéro original :

    String block =
        decimal.substring(Math.max(firstSome + (i-1)*BASE_DECIMAL_DIGITS, 0),
                          firstSome +   i  *BASE_DECIMAL_DIGITS);

(Le Math.max est nécessaire ici pour le premier bloc plus court). Nous utilisons maintenant la fonction habituelle d'analyse des entiers, et plaçons le résultat dans le tableau :

    digits[i] = Integer.parseInt(block);
}

A partir du tableau maintenant créé, nous créons notre objet DecimalBigInt :

return new DecimalBigInt(digits);

Voyons si ça marche :

DecimalBigInt d2 = DecimalBigInt.valueOf("12345678901234567890");
System.out.println(d2);

Sortie :

Big[12, 345678901, 234567890]

Cela semble correct :-) Nous devrions le tester avec d'autres nombres (de longueur différente) également.

La prochaine étape sera le formatage décimal, ce qui devrait être encore plus facile.

Troisièmement, la conversion au format décimal.

Nous devons produire nos chiffres individuels sous la forme de 9 chiffres décimaux chacun. Pour cela, nous pouvons utiliser la fonction Formatter qui prend en charge les chaînes de format de type printf.

Une variante simple serait la suivante :

public String toDecimalString() {
    Formatter f = new Formatter();
    for(int digit : digits) {
        f.format("%09d", digit);
    }
    return f.toString();
}

Ce retour 000000007000000005000000002000012345 y 000000012345678901234567890 pour nos deux numéros. Cela fonctionne pour un aller-retour (c'est-à-dire en l'alimentant au valueOf donne un objet équivalent), mais les zéros de tête ne sont pas vraiment agréables à regarder (et pourraient créer une confusion avec les nombres octaux). Nous devons donc séparer notre belle boucle for-each et utiliser une chaîne de formatage différente pour le premier chiffre et les chiffres suivants.

public String toDecimalString() {
    Formatter f = new Formatter();
    f.format("%d", digits[0]);
    for(int i = 1; i < digits.length; i++) {
        f.format("%09d", digits[i]);
    }
    return f.toString();
}

Ajout.

Commençons par l'addition, car elle est simple (et nous pourrons en utiliser certaines parties pour la multiplication plus tard).

/**
 * calculates the sum of this and that.
 */
public DecimalBigInt plus(DecimalBigInt that) {
    ...
}

Je veux des noms de méthodes que l'on peut lire comme on lirait la formule, donc plus , minus , times au lieu de add , subtract , multiply .

Alors, comment fonctionne l'addition ? Elle fonctionne de la même manière que nous l'avons apprise à l'école pour les nombres décimaux supérieurs à 9 : additionnez les chiffres correspondants, et si pour certains d'entre eux le résultat est supérieur à 10 (ou BASE dans notre cas), on passe au chiffre suivant. Cela peut faire en sorte que le nombre résultant ait un chiffre de plus que les chiffres originaux.

Tout d'abord, nous examinons le cas simple où les deux nombres ont le même nombre de chiffres. Dans ce cas, cela ressemble simplement à ceci :

int[] result = new int[this.digits.length];
int carry = 0;
for(int i = this.digits.length-1; i > 0; i--) {
    int digSum = carry + this.digits[i] + that.digits[i];
    result[i] = digSum % BASE;
    carry = digSum / BASE;
}
if(carry > 0) {
    int[] temp = new int[result.length + 1];
    System.arraycopy(result, 0, temp, 1, result.length);
    temp[0] = carry;
    result = temp;
}
return new DecimalBigInt(result);

(Nous allons de droite à gauche, afin de pouvoir reporter tout débordement sur le chiffre suivant. Ce serait un peu plus joli si nous avions décidé d'utiliser le format Little Endian).

Si les deux nombres n'ont pas le même nombre de chiffres, cela devient un peu plus compliqué.

Pour que ce soit aussi simple que possible, nous l'avons divisé en plusieurs méthodes :

Cette méthode ajoute un chiffre à un élément du tableau (qui peut déjà contenir une valeur non nulle), et enregistre le résultat dans le tableau. S'il y a un dépassement de capacité, nous le reportons au chiffre suivant (dont l'indice est inférieur d'une unité, et non supérieur d'une unité) au moyen d'un appel récursif. De cette façon, nous nous assurons que nos chiffres restent toujours dans la plage valide.

/**
 * adds one digit from the addend to the corresponding digit
 * of the result.
 * If there is carry, it is recursively added to the next digit
 * of the result.
 */
private void addDigit(int[] result, int resultIndex,
                      int addendDigit)
{
    int sum = result[resultIndex] + addendDigit;
    result[resultIndex] = sum % BASE;
    int carry = sum / BASE;
    if(carry > 0) {
        addDigit(result, resultIndex - 1, carry);
    }
}

La suivante fait de même pour un tableau entier de chiffres à additionner :

/**
 * adds all the digits from the addend array to the result array.
 */
private void addDigits(int[] result, int resultIndex,
                       int... addend)
{
    int addendIndex = addend.length - 1;
    while(addendIndex >= 0) {
        addDigit(result, resultIndex,
                 addend[addendIndex]);
        addendIndex--;
        resultIndex--;
    }
}

Maintenant, nous pouvons mettre en œuvre notre plus método:

/**
 * calculates the sum of this and that.
 */
public DecimalBigInt plus(DecimalBigInt that) {
    int[] result = new int[Math.max(this.digits.length,
                                    that.digits.length)+ 1];

    addDigits(result, result.length-1, this.digits);
    addDigits(result, result.length-1, that.digits);

    // cut of leading zero, if any
    if(result[0] == 0) {
        result = Arrays.copyOfRange(result, 1, result.length);
    }
    return new DecimalBigInt(result);
}

Nous pourrions faire un peu mieux ici si nous regardions avant si un débordement est possible et si nous créions le tableau un peu plus grand que nécessaire.

Ah, un test : d2.plus(d2) donne Big[24, 691357802, 469135780] ce qui semble correct.

Multiplication.

Souvenons-nous de l'école, comment on multipliait les grands nombres sur le papier ?

123 * 123
----------
      369   <== 123 * 3
     246    <== 123 * 2
    123     <== 123 * 1
  --------
    15129

Il faut donc multiplier chaque chiffre [i] du premier nombre avec chaque chiffre [j] du deuxième nombre, et ajouter le produit en chiffre [i+j] du résultat (et faire attention à la retenue). Bien sûr, ici les indices sont comptés à partir de la droite, et non de la gauche. (Maintenant, je regrette vraiment de ne pas avoir utilisé des chiffres little-endian).

Puisque le produit de deux de nos chiffres peut sortir de l'éventail de int nous utilisons long pour la multiplication.

/**
 * multiplies two digits and adds the product to the result array
 * at the right digit-position.
 */
private void multiplyDigit(int[] result, int resultIndex,
                           int firstFactor, int secondFactor) {
    long prod = (long)firstFactor * (long)secondFactor;
    int prodDigit = (int)(prod % BASE);
    int carry = (int)(prod / BASE);
    addDigits(result, resultIndex, carry, prodDigit);
}

Maintenant nous pouvons voir pourquoi j'ai déclaré mon addDigits pour prendre un resultIndex paramètre. (Et je viens de changer le dernier argument en un paramètre varargs, pour pouvoir mieux écrire ceci ici).

Voici donc la méthode des multiplications croisées :

private void multiplyDigits(int[] result, int resultIndex,
                            int[] leftFactor, int[] rightFactor) {
    for(int i = 0; i < leftFactor.length; i++) {
        for(int j = 0; j < rightFactor.length; j++) {

            multiplyDigit(result, resultIndex - (i + j),
                          leftFactor[leftFactor.length-i-1],
                          rightFactor[rightFactor.length-j-1]);
        }
    }
}

J'espère que j'ai bien calculé l'indice. Avec une représentation little-endian, cela aurait été multiplyDigit(result, resultIndex + i + j, leftFactor[i], rightFactor[j]) - C'est plus clair, n'est-ce pas ?

Notre site times n'a plus qu'à allouer le tableau de résultats, invoquer la méthode multiplyDigits et envelopper le résultat.

/**
 * returns the product {@code this × that}.
 */
public DecimalBigInt times(DecimalBigInt that) {
    int[] result = new int[this.digits.length + that.digits.length];
    multiplyDigits(result, result.length-1, 
                   this.digits, that.digits);

    // cut off leading zero, if any
    if(result[0] == 0) {
        result = Arrays.copyOfRange(result, 1, result.length);
    }
    return new DecimalBigInt(result);
}

Pour les tests, d2.times(d2) donne Big[152, 415787532, 388367501, 905199875, 19052100] ce qui est la même chose que ce que calcule mon Emacs ici.

Comparaison

Nous voulons être en mesure de comparer deux de nos objets. Donc, nous implémentons Comparable<DecimalBigInt> et sa méthode compareTo.

public int compareTo(DecimalBigInt that) {

Comment savoir si un de nos chiffres est plus grand qu'un autre ? Tout d'abord, nous comparons la longueur des tableaux. Comme nous avons pris soin de ne pas introduire de zéros non significatifs (n'est-ce pas ?), le tableau le plus long devrait contenir le plus grand nombre.

    if(this.digits.length < that.digits.length) {
        return -1;
    }
    if (that.digits.length < this.digits.length) {
        return 1;
    }

Si les longueurs sont identiques, nous pouvons comparer par éléments. Puisque nous utilisons big endian (c'est-à-dire la grande fin arrive en premier ), nous commençons par le début.

    for(int i = 0; i < this.digits.length; i++) {
        if(this.digits[i] < that.digits[i]) {
            return -1;
        }
        if(that.digits[i] < this.digits[i]) {
            return 1;
        }
    }

Si tout était identique, évidemment nos nombres sont identiques, et nous pouvons retourner 0 .

    return 0;
}

equals + hashCode()

Toute bonne classe immuable doit implémenter equals() y hashCode() d'une manière appropriée (et compatible).

Pour notre hashCode() Dans ce cas, il suffit d'additionner les chiffres et de les multiplier par un petit nombre premier pour s'assurer que l'échange de chiffres ne donne pas le même code de hachage :

/**
 * calculates a hashCode for this object.
 */
public int hashCode() {
    int hash = 0;
    for(int digit : digits) {
        hash = hash * 13 + digit;
    }
    return hash;
}

Dans le equals() nous pouvons simplement déléguer à la méthode compareTo, au lieu d'implémenter à nouveau le même algorithme :

/**
 * compares this object with another object for equality.
 * A DecimalBigInt is equal to another object only if this other
 * object is also a DecimalBigInt and both represent the same
 * natural number.
 */
public boolean equals(Object o) {
    return o instanceof DecimalBigInt &&
        this.compareTo((DecimalBigInt)o) == 0;
}

---

Donc, assez pour aujourd'hui. La soustraction (et peut-être les nombres négatifs) et la division sont plus compliquées, donc je les omets pour le moment. Pour calculer la factorielle de 90, cela devrait suffire.

Calcul des grandes factorielles :

Ici la fonction factorielle :

/**
 * calculates the factorial of an int number.
 * This uses a simple iterative loop.
 */
public static DecimalBigInt factorial(int n) {
    DecimalBigInt fac = new DecimalBigInt(1);
    for(int i = 2; i <= n; i++) {
        fac = fac.times(new DecimalBigInt(i));
    }
    return fac;
}

Cela nous donne

fac(90) = 1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000

Conversion de représentations à rayons arbitraires

Poussé par la question suivante de frodosamoa, j'ai écrit ma réponse sur la façon de convertir un système numérique arbitraire (positionnel) en un système dans lequel nous pouvons (ou voulons) calculer. . (Dans cet exemple, j'ai converti du trinaire au décimal, alors que la question portait sur le passage du décimal au binaire).

Ici, nous voulons convertir d'un système numérique arbitraire (ok, avec un radix entre 2 et 36, donc nous pouvons utiliser Character.digit() pour convertir les chiffres simples en ints) à notre système avec radix BASE (= 1.000.000.000, mais ce n'est pas vraiment important ici).

En gros, nous utilisons Schéma Horner pour calculer la valeur du polynôme avec les chiffres comme coefficients au point donné par le radix.

sum[i=0..n] digit[i] * radix^i

peut être calculé avec cette boucle :

value = 0;
for  i = n .. 0
  value = value * radix + digit[i]
return value

Comme nos chaînes d'entrée sont big-endian, nous n'avons pas besoin de compter à rebours, mais nous pouvons utiliser une simple boucle for améliorée. (C'est plus moche en Java, puisque nous n'avons pas de surcharge d'opérateur, et pas d'autoboxing de int vers notre type DecimalBigInt).

public static DecimalBigInt valueOf(String text, int radix) {
    DecimalBigInt bigRadix = new DecimalBigInt(radix);
    DecimalBigInt value = new DecimalBigInt(); // 0
    for(char digit : text.toCharArray()) {
       DecimalBigInt bigDigit =
           new DecimalBigInt(Character.digit(digit, radix));
       value = value.times(bigRadix).plus(bigDigit);
    }
    return value;
}

Sur mon implémentation actuelle J'ai ajouté une vérification des erreurs (et la levée d'exceptions) pour m'assurer que nous avons vraiment un numéro valide, et bien sûr un commentaire de documentation.

---

Convertir à un système positionnel arbitraire est plus compliqué, car il implique le reste et la division (par le radix arbitraire), que nous n'avons pas encore implémenté - donc pas pour le moment. Cela sera fait quand j'aurai une bonne idée de la façon de faire la division. (Nous n'avons besoin ici que de la division par de petits nombres (à un chiffre), ce qui peut être plus facile qu'une division générale).

La division par les petits nombres

A l'école, j'ai appris longue division . Voici un exemple pour un petit diviseur (à un chiffre), dans la notation que nous utilisons ici en Allemagne (avec des annotations sur les calculs de fond, que nous n'écririons normalement pas), dans le système décimal :

 12345 : 6 = 02057     1 / 6 =  0
-0┊┊┊┊                 0 * 6 =  0
──┊┊┊┊
 12┊┊┊                12 / 6 =  2
-12┊┊┊                 2 * 6 = 12
 ──┊┊┊
  03┊┊                 3 / 6 =  0
 - 0┊┊                 0 * 6 =  0
  ──┊┊
   34┊                34 / 6 =  5
  -30┊                 5 * 6 = 30
   ──┊
    45                45 / 6 =  7
   -42                 7 * 6 = 42
    ──
     3     ==> quotient 2057, remainder 3.

Bien sûr, nous n'avons pas besoin de calculer ces produits (0, 12, 0, 30, 42). et de les soustraire si nous avons une opération de reste native. Alors, cela donne comme ceci (bien sûr, nous n'aurions pas besoin d'écrire les opérations) :

 12345 : 6 = 02057     1 / 6 =  0,   1 % 6 = 1
 12┊┊┊                12 / 6 =  2,  12 % 6 = 0
  03┊┊                 3 / 6 =  0,   3 % 6 = 3
   34┊                34 / 6 =  5,  34 % 6 = 4
    45                45 / 6 =  7,  45 % 6 = 3
     3
           ==> quotient 2057, remainder 3.

Cela ressemble déjà à courte division si nous l'écrivons dans un autre format.

Nous pouvons observer (et prouver) ce qui suit :

Si nous avons un nombre à deux chiffres x dont le premier chiffre est plus petit que notre diviseur d, alors x / d est un nombre à un chiffre, et x % d est également un nombre à un chiffre, plus petit que d. Ceci, ainsi que l'induction, montre que nous n'avons jamais besoin de diviser (avec le reste) des nombres à deux chiffres par notre diviseur.

Revenons à nos grands nombres avec le radix BASE : tous les nombres à deux chiffres sont représentables sous la forme d'un code Java. long et nous avons un natif / y % .

/**
 * does one step in the short division algorithm, i.e. divides
 *  a two-digit number by a one-digit one.
 *
 * @param result the array to put the quotient digit in.
 * @param resultIndex the index in the result array where
 *             the quotient digit should be put.
 * @param divident the last digit of the divident.
 * @param lastRemainder the first digit of the divident (being the
 *           remainder of the operation one digit to the left).
 *           This must be < divisor.
 * @param divisor the divisor.
 * @returns the remainder of the division operation.
 */
private int divideDigit(int[] result, int resultIndex,
                        int divident, int lastRemainder,
                        int divisor) {
    assert divisor < BASE;
    assert lastRemainder < divisor;

    long ent = divident + (long)BASE * lastRemainder;

    long quot = ent / divisor;
    long rem = ent % divisor;

    assert quot < BASE;
    assert rem < divisor;

    result[resultIndex] = (int)quot;
    return (int)rem;
}

Nous allons maintenant appeler cette méthode en boucle, en renvoyant toujours le résultat de l'appel précédent en tant que lastRemainder .

/**
 * The short division algorithm, like described in
 * <a href="http://en.wikipedia.org/wiki/Short_division">Wikipedia's
 *   article <em>Short division</em></a>.
 * @param result an array where we should put the quotient digits in.
 * @param resultIndex the index in the array where the highest order digit
 *     should be put, the next digits will follow.
 * @param divident the array with the divident's digits. (These will only
 *          be read, not written to.)
 * @param dividentIndex the index in the divident array where we should
 *         start dividing. We will continue until the end of the array.
 * @param divisor the divisor. This must be a number smaller than
 *        {@link #BASE}.
 * @return the remainder, which will be a number smaller than
 *     {@code divisor}.
 */
private int divideDigits(int[] result, int resultIndex,
                         int[] divident, int dividentIndex,
                         int divisor) {
    int remainder = 0;
    for(; dividentIndex < divident.length; dividentIndex++, resultIndex++) {
        remainder = divideDigit(result, resultIndex,
                                divident[dividentIndex],
                                remainder, divisor);
    }
    return remainder;
}

Cette méthode renvoie toujours un int, le reste.

Maintenant, nous voulons avoir une méthode publique retournant un DecimalBigInt, donc nous en créons une. Elle a pour tâche de vérifier les arguments, de créer un tableau pour la méthode de travail, de rejeter le reste et de créer un DecimalBigInt à partir du résultat. (Le constructeur supprime un zéro de tête qui pourrait se trouver là).

/**
 * Divides this number by a small number.
 * @param divisor an integer with {@code 0 < divisor < BASE}.
 * @return the integer part of the quotient, ignoring the remainder.
 * @throws IllegalArgumentException if the divisor is <= 0 or >= BASE.
 */
public DecimalBigInt divideBy(int divisor)
{
    if(divisor <= 0 || BASE <= divisor) {
        throw new IllegalArgumentException("divisor " + divisor +
                                           " out of range!");
    }

    int[] result = new int[digits.length];
    divideDigits(result, 0,
                 digits, 0,
                 divisor);
    return new DecimalBigInt(result);
}

Nous disposons également d'une méthode similaire, qui renvoie le reste à la place :

/**
 * Divides this number by a small number, returning the remainder.
 * @param divisor an integer with {@code 0 < divisor < BASE}.
 * @return the remainder from the division {@code this / divisor}.
 * @throws IllegalArgumentException if the divisor is <= 0 or >= BASE.
 */
public int modulo(int divisor) {
    if(divisor <= 0 || BASE <= divisor) {
        throw new IllegalArgumentException("divisor " + divisor +
                                           " out of range!");
    }
    int[] result = new int[digits.length];
    return divideDigits(result, 0,
                        digits, 0,
                        divisor);
}

Ces méthodes peuvent être invoquées comme suit :

    DecimalBigInt d3_by_100 = d3.divideBy(100);
    System.out.println("d3/100 = " + d3_by_100);
    System.out.println("d3%100 = " + d3.modulo(100));

Conversion en radix arbitraire

Nous avons maintenant les bases pour convertir vers un radix arbitraire. Bien sûr, pas vraiment arbitraire, seulement les radix plus petits que BASE sont autorisés, mais cela ne devrait pas poser trop de problèmes.

Comme déjà répondu dans une autre réponse sur la conversion des nombres, nous devons faire "division, reste, multiplier, ajouter". La partie "multiplier-addition" ne fait en fait que rassembler les chiffres individuels, nous pouvons donc la remplacer par un simple accès au tableau.

Comme nous avons toujours besoin du quotient et du reste, nous n'utiliserons pas les méthodes publiques modulo y divideBy mais au lieu de cela, elle appelle de façon répétée la divideDigits méthode.

/**
 * converts this number to an arbitrary radix.
 * @param radix the target radix, {@code 1 < radix < BASE}.
 * @return the digits of this number in the base-radix system,
 *     in big-endian order.
 */
public int[] convertTo(int radix)
{
    if(radix <= 1 || BASE <= radix) {
        throw new IllegalArgumentException("radix " + radix +
                                           " out of range!");
    }

Tout d'abord, un traitement de cas spécial pour 0.

    // zero has no digits.
    if(digits.length == 0)
        return new int[0];

Ensuite, nous créons un tableau pour les chiffres du résultat (assez long), et quelques autres variables.

    // raw estimation how many output digits we will need.
    // This is just enough in cases like BASE-1, and up to
    // 30 digits (for base 2) too much for something like (1,0,0).
    int len = (int) (Math.log(BASE) / Math.log(radix) * digits.length)+1;
    int[] rDigits = new int[len];
    int rIndex = len-1;
    int[] current = digits;
    int quotLen = digits.length;

quotLen est le nombre de chiffres (à l'exclusion des zéros initiaux) dans le dernier quotient. Si cette valeur est égale à 0, nous avons terminé.

    while(quotLen > 0)  {

Un nouveau tableau pour le prochain quotient.

        int[] quot = new int[quotLen];

L'opération du quotient et du reste. Le quotient est maintenant dans quot , le reste dans rem .

        int rem = divideDigits(quot, 0,
                               current, current.length - quotLen,
                               radix);

Nous mettons le reste dans le tableau de sortie (en le remplissant à partir du dernier chiffre).

        rDigits[rIndex] = rem;
        rIndex --;

Ensuite, nous échangeons les tableaux pour le prochain tour.

        current = quot;

S'il y a des zéros de tête dans le quotient (il y en aura au plus un, car radix est plus petit que BASE), nous réduisons la taille du quotient de un. Le tableau suivant suivant sera plus petit.

        if(current[0] == 0) {
            // omit leading zeros in next round.
            quotLen--;
        }
    }

Après la boucle, il peut y avoir des zéros de tête dans le tableau rDigits, et nous les coupons.

    // cut of leading zeros in rDigits:
    while(rIndex < 0 || rDigits[rIndex] == 0) {
        rIndex++;
    }
    return Arrays.copyOfRange(rDigits, rIndex, rDigits.length);
}

Voilà, c'est tout. Ça a l'air un peu compliqué, cependant. Voici un exemple de la façon de l'utiliser :

    System.out.println("d4 in base 11: " +
                       Arrays.toString(d4.convertTo(11)));
    System.out.println("d5 in base 7: " +
                       Arrays.toString(d5.convertTo(7)));

Ces imprimés [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0] y [1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0] Les chiffres sont les mêmes que ceux que nous avons analysés auparavant (à partir d'une chaîne, cependant).

Sur cette base, nous pouvons également formater comme une chaîne de caractères :

/**
 * Converts the number to a String in a given radix.
 * This uses {@link Character.digit} to convert each digit
 * to one character.
 * @param radix the radix to use, between {@link Character.MIN_RADIX}
 *   and {@link Character.MAX_RADIX}.
 * @return a String containing the digits of this number in the
 *   specified radix, using '0' .. '9' and 'a' .. 'z' (as much as needed).
 */
public String toString(int radix) {
    if(radix < Character.MIN_RADIX || Character.MAX_RADIX < radix) {
        throw new IllegalArgumentException("radix out of range: " + radix);
    }
    if(digits.length == 0)
        return "0";
    int[] rdigits = convertTo(radix);
    StringBuilder b = new StringBuilder(rdigits.length);
    for(int dig : rdigits) {
        b.append(Character.forDigit(dig, radix));
    }
    return b.toString();
}

Answer 2

Vous pourriez vouloir mettre en place ou rechercher une bibliothèque de décimal codé en binaire si vous essayez d'éviter BigInteger . Vous pouvez réaliser la factorielle de 90 avec BigInteger si vous voulez l'utiliser :

public static BigInteger factorial(BigInteger value) {
    BigInteger total = BigInteger.ONE;
    for (int i = 0; value.compareTo(BigInteger.ONE) == 1; i++) {
        total = total.multiply(value);
        value = value.subtract(BigInteger.ONE);
    }
    return total;
}

Answer 3

Utilisez le code ci-dessous pour multiplier des nombres de n'importe quelle longueur:-.

public class BigNumberMultiplication {

private static int[] firstBigNumber = null;
private static int[] secondBigNumber = null;

public static int[] baseMul(int[] baseMultiple, int base) {

    System.out.println("baseMultiple" + Arrays.toString(baseMultiple) + base);
    for (int i = 0; i < baseMultiple.length; i++) {
        baseMultiple[i] *= base;
    }
    System.out.println("basemultipleresultwithoutcarryforward" + baseMultiple);
    return carryForward(baseMultiple);
}

public static int[] basePowerMul(int[] basePowerMultiple, int base, int power) {

    int basePowerMultipleTemp[] = baseMul(basePowerMultiple, base);
    System.out.println("basePowerMultipleTemp" + Arrays.toString(basePowerMultipleTemp) + "power" + power);
    int basePowerMultipleResult[] = new int[basePowerMultipleTemp.length + (power - 1)];
    for(int i = 0; i < basePowerMultipleTemp.length; i++)
        basePowerMultipleResult[i] = basePowerMultipleTemp[i];
    if(power > 1){
    for(int i = 0; i < (power - 1); i++)
        basePowerMultipleResult[basePowerMultipleTemp.length + i] = 0;
    }
    System.out.println("basepowermulresult" + Arrays.toString(basePowerMultipleResult));
    return basePowerMultipleResult;
}
public static int[] addBigNumber(int[] finalNumberInArray, int[] finalNumberInArrayTemp){
    System.out.println("final number in array" + Arrays.toString(finalNumberInArray) + "finalNumberInTemp" + Arrays.toString(finalNumberInArrayTemp));
    int n = finalNumberInArray.length;
    for(int i = (finalNumberInArrayTemp.length - 1); i >= 0; i--){
        finalNumberInArray[n - 1] += finalNumberInArrayTemp[i];
        n--;
    }

    return carryForward(finalNumberInArray);

}

public static int[] carryForward(int[] arrayWithoutCarryForward){

    int[] arrayWithCarryForward = null;
    System.out.println("array without carry forward" + Arrays.toString(arrayWithoutCarryForward));
    for (int i = arrayWithoutCarryForward.length - 1; i > 0; i--) {
        if (arrayWithoutCarryForward[i] >= 10) {
            int firstDigit = arrayWithoutCarryForward[i] % 10;
            int secondDigit = arrayWithoutCarryForward[i] / 10;
            arrayWithoutCarryForward[i] = firstDigit;
            arrayWithoutCarryForward[i - 1] += secondDigit;
        } 
    }

    if(arrayWithoutCarryForward[0] >= 10){
        arrayWithCarryForward = new int[arrayWithoutCarryForward.length + 1];
        arrayWithCarryForward[0] = arrayWithoutCarryForward[0] / 10;
        arrayWithCarryForward[1] = arrayWithoutCarryForward[0] % 10;
    for(int i = 1; i < arrayWithoutCarryForward.length; i++)
        arrayWithCarryForward[i + 1] = arrayWithoutCarryForward[i];
    }
    else{
        arrayWithCarryForward = arrayWithoutCarryForward;
    }
    System.out.println("array with carry forward" + Arrays.toString(arrayWithCarryForward));
    return arrayWithCarryForward;
}
public static int[] twoMuscularNumberMul(){
    int finalNumberInArray[] = null;
    for(int i = 0; i < secondBigNumber.length; i++){
        if(secondBigNumber[i] == 0){}
        else {

             int[] finalNumberInArrayTemp = basePowerMul(Arrays.copyOf(firstBigNumber, firstBigNumber.length), secondBigNumber[i], secondBigNumber.length - i);
             if(finalNumberInArray == null){
                 finalNumberInArray = finalNumberInArrayTemp;
                 System.out.println("finalNumberInArray" + Arrays.toString(finalNumberInArray));
             }
             else{
                 finalNumberInArray = addBigNumber(finalNumberInArray, finalNumberInArrayTemp);
             System.out.println("finalNumberInArray" + Arrays.toString(finalNumberInArray));
             }
        }
    }
    return finalNumberInArray;
}

public static int [] readNumsFromCommandLine() {

    Scanner s = new Scanner(System.in);
    System.out.println("Please enter the number of digit");
    int count = s.nextInt();
    System.out.println("please enter the nuumber separated by space");
    s.nextLine();

    int [] numbers = new int[count];
    Scanner numScanner = new Scanner(s.nextLine());
    for (int i = 0; i < count; i++) {
        if (numScanner.hasNextInt()) {
            numbers[i] = numScanner.nextInt();
        } else {
            System.out.println("You didn't provide enough numbers");
            break;
        }
    }

    return numbers;
}
public static void main(String[] args) {

    firstBigNumber = readNumsFromCommandLine();
    secondBigNumber = readNumsFromCommandLine();
    System.out.println("1st number" + Arrays.toString(firstBigNumber) + "2nd number" + Arrays.toString(secondBigNumber));
    int[] finalArray = twoMuscularNumberMul();
    System.out.println(Arrays.toString(finalArray));

    }

}

Answer 4

Lorsque je veux faire 90 ! ou un autre calcul massif, j'essaie d'utiliser un tableau int[], chaque élément contenant un des chiffres. Ensuite, j'applique la multiplication traditionnelle en utilisant un stylo et du papier pour obtenir la réponse dans un autre tableau int[].

Voici le code que j'ai écrit en Java qui calcule 100 ! assez rapidement. N'hésitez pas à l'utiliser comme bon vous semble.

public int factoial(int num) {
    int sum = 0;
    int[][] dig = new int[3][160];
    dig[0][0] = 0;
    dig[0][1] = 0;
    dig[0][2] = 1;

    for (int i = 99; i > 1; i--) {
        int len = length(i);
        for (int k = 1; k <= len; k++) { // Sets up multiplication
            int pos = len - k;
            dig[1][pos] = ((i / (int) (Math.pow(10, pos))) % 10);
        }
        int temp;
        for (int k = 0; k < len; k++) { // multiplication
            for (int j = 0; j < 159; j++) {
                dig[2][k + j] += (dig[1][k] * dig[0][j]);
                if (dig[2][k + j] >= 10) {
                    dig[2][k + j + 1] += dig[2][k + j] / 10;
                    dig[2][k + j] = dig[2][k + j] % 10;
                }
            }
        }
        sum = 0;
        for (int k = 159; k >= 0; k--) {
            System.out.print(dig[2][k]);
            dig[0][k] = dig[2][k];
            dig[1][k] = 0;
            sum += dig[2][k];
            dig[2][k] = 0;
        }
        System.out.println();
    }
    return sum;
}

Answer 5

Opérations arithmétiques en Java à l'aide des opérateurs + , - , * , / y % sont liées par les contraintes de la Types de données primitives Java .

Cela signifie que si vous ne pouvez pas faire entrer les chiffres que vous souhaitez dans la fourchette de, disons, a double ou long vous devrez alors utiliser une bibliothèque de "grands nombres", telle que celle intégrée à Java ( BigDecimal , BigInteger ), ou une bibliothèque tierce, ou encore écrivez la vôtre. Cela signifie également que vous ne pouvez pas utiliser les opérateurs arithmétiques, car Java ne prend pas en charge la surcharge des opérateurs.