Je pense qu'un programmeur aurait dû implémenter sa propre bibliothèque bignum une fois, alors bienvenue ici.

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

(Vous pouvez suivre le code source de cette vie de cours sur github. En outre, j'ai refait cela (un peu poli) dans une série de blog en 14 parties.)

Création d'une classe de Grand nombre simple en Java

Alors, que faisons-nous le 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 la décimale. Pour plus d'efficacité, nous ne stockerons pas de vrais chiffres décimaux, mais fonctionnerons en base 1 000 000 000 = 10^9 < 2^30. Cela s'inscrit dans une Java int (jusqu'à 2^31 ou 2^32), et le produit de deux de ces chiffres s'intègre parfaitement dans un Java long.

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

Alors le chiffres-tableau:

private int[] digits;

Stockons - nous les chiffres en little-ou big endian, c'est-à-dire les plus grandes parties en premier ou en dernier? Cela n'a pas vraiment d'importance, nous décidons donc du 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.)

À des fins de test, nous ajoutons un constructeur qui permet l'initialisation à 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 single int (si plus petit que BASE), et même pour no 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. Nous ajoutons donc une méthode toString():

/**
 * 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 à partir de laquelle nous voulons convertir (10). Ainsi, nous avons toujours le même nombre (9) de chiffres décimaux représentant un chiffre "notre format". (Bien sûr, au début il peut y avoir certains chiffres 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 étrange formule est une manière 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;

C'est la longueur du premier bloc de chiffres décimaux, devrait être comprise entre 1 et 9 (inclus).

Nous créons notre tableau:

 int[] digits = new int[bigLen];

En boucle à travers le chiffres à créer:

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

Chacun de notre chiffres est représentée par un bloc de chiffres dans le numéro d'origine:

    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 d'analyse des entiers habituelle et mettons le résultat dans le tableau:

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

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

return new DecimalBigInt(digits);

Voyons si cela fonctionne:

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

Sortie:

Big[12, 345678901, 234567890]

A l'air juste :- ) Nous devrions le tester avec d'autres nombres (de longueur différente) aussi.

La prochaine partie sera le formatage décimal, cela devrait être encore plus facile.

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

Nous devons sortir nos chiffres individuels sous la forme de 9 chiffres décimaux chacun. Pour cela, nous pouvons utiliser la classe 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();
}

Retourne 000000007000000005000000002000012345 et 000000012345678901234567890 pour nos deux nombres. Ce fonctionne pour un aller-retour (c'est-à-dire que l'alimenter à la méthode 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 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 c'est simple (et nous pouvons en utiliser des parties pour la multiplication tard).

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

Je veux les noms de méthodes que vous pouvez lire comme vous le feriez lire la formule, ainsi plus, minus, times au lieu de add, subtract, multiply.

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

D'abord, nous regardons le cas simple que les deux nombres ont le même nombre de chiffres. Ensuite, 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, de sorte que nous pouvons porter les débordements au 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 le rendre aussi simple que possible, nous le divisons 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 stocke le résultat dans le tableau. S'il y avait un débordement, nous le portons au chiffre suivant (qui a un index de moins, pas un de plus) 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);
    }
}

Le suivant fait la même chose pour tout un tableau de chiffres à ajouter:

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

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

/**
 * 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 cherchions avant si le débordement est possible et seulement ensuite créer le tableau un plus grand que nécessaire.

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

Multiplication.

Souvenons-nous de la rentrée scolaire, comment avons-nous multiplié les plus grands nombres sur papier?

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

Donc, nous devons multiplier chaque chiffre[i] du premier nombre par chaque chiffre[j] du deuxième nombre, et ajouter le produit en chiffre [i + j] du résultat (et faites attention à porter). Bien sûr, ici, les index sont comptés de droite, pas de gauche. (Maintenant, j'aurais vraiment aimé avoir utilisé des nombres little-endian.)

Puisque le produit de deux de nos chiffres peut sortir de la plage 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 méthode pour prendre un resultIndex paramètre. (Et je viens de changer le dernier argument en un paramètre varargs, pour être capable d'écrire ce mieux ici.)

Donc, voici la méthode de multiplication croisée:

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 avoir les bons calculs d'index. Avec une représentation little-endian, cela aurait été multiplyDigit(result, resultIndex + i + j, leftFactor[i], rightFactor[j]) - bien plus clair, n'est-ce pas?

Notre méthode times n'a plus qu'à allouer le tableau de résultats, invoquer 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 le même que ce que calcule mon calc Emacs ici.

Comparaison

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

public int compareTo(DecimalBigInt that) {

Comment savoir si l'un de nos nombres est plus grand qu'un autre? Tout d'abord, nous comparons la longueur des tableaux. Comme nous avons pris soin de ne pas induire des zéros (avons-nous?), le tableau plus long devrait avoir le plus grand nombre.

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

Si la longueur est la même, nous pouvons comparer par élément. Puisque nous utilisons big endian (c'est-à-dire le grand la fin vient 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 pareil, évidemment nos nombres sont identiques, et nous pouvons retourner 0.

    return 0;
}

equals + hashCode()

Toute bonne classe immuable devrait implémenter equals() et hashCode() de manière appropriée (et compatible).

Pour notre hashCode(), nous résumons simplement les chiffres, en les multipliant par un petit nombre premier pour nous assurer que la commutation de chiffres n'entraîne pas le même hachage code:

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

Dans la méthode 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 l'instant. 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;
}

Ceci nous donne

fac(90) = 1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000

Conversion à partir de représentations arbitraires-radix

Invité par la question suivante de frodosamoa, j'ai écrit ma réponse sur la façon de convertir des systèmes de nombres arbitraires (positionnels) dans celui dans lequel nous pouvons (ou voulons) calculer . (Dans l'exemple là-bas, j'ai converti de trinaire en décimal, alors que la question portait sur décimal en binaire.)

Ici, nous voulons convertir à partir d'un système de nombres arbitraires (d'accord, avec radix entre 2 et 36, ainsi nous pouvons employer Character.digit() pour convertir des chiffres simples en ints) à notre système avec radix BASE (= 1.000.000.000, mais ce n'est pas vraiment important ici).

Fondamentalement, nous utilisons Schéma de 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

Puisque nos chaînes d'entrée sont big-endian, nous n'avons pas à compter, mais pouvons utiliser un simple amélioré pour la boucle. (Cela semble plus laid en Java, car nous n'avons pas de surcharge d'opérateur et pas d'autoboxing de int à 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;
}

Dans mon implémentation réelle j'ai ajouté une vérification des erreurs (et des exceptions) pour nous assurer que nous avons vraiment un numéro valide, et bien sûr un commentaire de documentation.

Convertir en un système de position arbitraire est plus compliqué, car il implique le reste et la division (par arbitraire radix), que nous n'avons pas les mettre en œuvre - donc pas pour l'instant. Ce sera fait quand j'aurai une bonne idée sur la façon de faire la division. (Nous n'avons besoin ici que d'une division par de petits nombres (à un chiffre), ce qui peut être plus facile qu'une division générale.)

Division par petits nombres

À l'école, j'ai appris la division longue. 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 normalement ne serait pas écrire), 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.

De couse, nous n'avons pas besoin de calculer ces produits (0, 12, 0, 30, 42) et soustrayez - les si nous avons une opération restante native. Puis il ressemble comme ceci (bien sûr, nous n'aurions pas besoin d'écrire les opérations ici):

 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à assez à division courte, si nous l'écrivons dans un autre format.

Nous pouvons observer (et prouver) ce qui suit:

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

Pour revenir à nos grands nombres avec la BASE radix: tous les nombres à deux chiffres sont représentables en Java long, et là nous avons des / et % natifs.

/**
 * 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, toujours nourrir le résultat du rappel précédent comme 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 renvoyant un DecimalBigInt, donc nous en créons un. Il 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 principal qui peut être 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 avons également 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 ceci:

    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

Maintenant, nous avons les bases pour convertir en une base arbitraire. Bien sûr, pas vraiment arbitraire, seuls les rayons inférieurs à BASE sont autorisés, mais cela ne devrait pas être un trop gros problème.

Comme déjà répondu dans une autre réponse sur la conversion des nombres, nous devons faire "division, reste, multiplier, ajouter. Le " multiplier-ajouter" une partie est en fait seulement mettre ensemble les chiffres individuels, de sorte que nous pouvons le remplacer par un simple array-access.

Comme nous avons toujours besoin à la fois du quotient et du reste, nous n'utiliserons pas les méthodes publiques modulo et divideBy, mais appelons à plusieurs reprises la méthode divideDigits.

/**
 * 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, une gestion de cas spéciaux 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 principaux) dans le dernier quotient. Si c'est 0, nous avons terminé.

    while(quotLen > 0)  {

Un nouveau tableau pour le quotient suivant.

        int[] quot = new int[quotLen];

L'opération quotient-et-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 tour suivant.

        current = quot;

S'il y a des zéros principaux dans le quotient (là la plupart du temps, puisque radix est plus petit que la BASE), nous réduisons la taille du quotient d'un. La matrice suivante sera plus petite.

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

Après la boucle, il peut y avoir des zéros principaux 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);
}

C'est tout. Il ressemble un peu compliqué, cependant. Voici un exemple de comment 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)));

Ceux-ci impriment [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0] et [1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0], juste les mêmes nombres que nous avons analysés auparavant (à partir d'une chaîne, cependant).

Sur cette base, nous pouvons formatez également sous forme de chaîne:

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