我认为程序员应该实现他自己的bignum库一次，所以欢迎在这里。

（当然，稍后你会得到BigInteger更好，并使用它，但这是一个宝贵的学习经验。

（您可以在github上遵循本课程生活的源代码。另外，我把这个（有点打磨）改造成了一个由14部分组成的博客系列。

在 Java 中创建一个简单的大数类

那么，我们需要什么呢？

首先，数字的表示，

基于Java给我们的数据类型。

由于您认为十进制转换是最复杂的部分，因此让我们保持基于十进制的模式。为了提高效率，我们将不存储真正的十进制数字，而是以 基数工作 。这适合 Java（最多 or ），并且两个此类数字的乘积非常适合 Java 。1 000 000 000 = 10^9 < 2^30int2^312^32long

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

然后是数字数组：

private int[] digits;

我们是将数字存储在小端序还是大端序中，即较大的部分首先还是最后？这并不重要，所以我们决定使用大端序，因为这是人类想要阅读它的方式。（现在我们专注于非负值 - 稍后我们将为负数添加一个符号位。

出于测试目的，我们添加了一个构造函数，它允许从这样的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();
}

作为额外的好处，这个构造函数也可用于单个（如果小于），甚至不可用于（我们将解释为0）。因此，我们现在可以这样做：intBASEint

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

这给了我们，不是那么有用。因此，我们添加一个方法：de.fencing_game.paul.examples.DecimalBigInt@6af62373toString()

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

输出现在是 ，这对测试更有用，不是吗？Big[7, 5, 2, 12345]

其次，从十进制格式转换。

我们在这里很幸运：我们的基数（10^9）是我们想要转换的基数的幂（10）。因此，我们总是有相同数量的（9）十进制数字代表一个“我们的格式”数字。（当然，在开始时可能会有一些数字较少。在下面的代码中，是一个十进制数字字符串。decimal

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

这个奇怪的公式是Java的一种写作方式。（我希望它是正确的，我们稍后会测试它。bigLen = ceil(decLen/BASE_DECIMAL_DIGITS)

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

这是第一个十进制数字块的长度，应介于 1 和 9 之间（包括 1 和 9）。

我们创建数组：

 int[] digits = new int[bigLen];

遍历要创建的数字：

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

我们的每个数字都由原始数字中的一组数字表示：

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

（对于第一个较短的块，这里需要 。我们现在使用通常的整数解析函数，并将结果放入数组中：Math.max

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

从现在创建的数组中，我们创建我们的DecimalBigInt对象：

return new DecimalBigInt(digits);

让我们看看这是否有效：

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

输出：

Big[12, 345678901, 234567890]

看起来对：-）我们也应该用其他一些数字（长度不同）来测试它。

下一部分将是十进制格式，这应该更容易。

第三，转换为十进制格式。

我们需要将单个数字输出为每个十进制数字。为此，我们可以使用该类，它支持类似printf的格式字符串。Formatter

一个简单的变体是这样的：

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

这返回和我们的两个数字。这适用于往返（即将其馈送到方法中给出一个等效的对象），但是前导零并不好看（并且可能会与八进制数混淆）。因此，我们需要分解我们美丽的 for-each 循环，并对第一个和后面的数字使用不同的格式字符串。000000007000000005000000002000012345000000012345678901234567890valueOf

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

加法。

让我们从加法开始，因为这很简单（我们可以在以后使用它的一部分进行乘法）。

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

我想要可以像阅读公式一样阅读的方法名称，因此，，而不是，，。plusminustimesaddsubtractmultiply

那么，添加是如何工作的呢？它的工作原理与我们在学校中学到的高于9的十进制数相同：将相应的数字相加，如果对于某些数字，则结果大于10（或者在我们的例子中），则将一个数字带到下一个数字。这可能会导致生成的数字比原始数字多一位数字。BASE

首先，我们看一个简单的情况，即两个数字具有相同的位数。然后它看起来就像这样：

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);

（我们从右到左，因此我们可以将任何溢出到下一个数字。如果我们决定使用Little Endian格式，这将更加漂亮。

如果两个数字的位数不同，则会变得更加复杂。

为了让它尽可能简单，我们将其拆分为几个方法：

此方法将一个数字添加到数组中的元素（该元素可能已包含一些非零值），并将结果存储回数组中。如果存在溢出，我们通过递归调用将其传递到下一个数字（索引少一个，而不是一个索引更多）。通过这种方式，我们可以确保我们的数字始终保持在有效范围内。

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

接下来对要添加的整个数字数组执行相同的操作：

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

现在我们可以实现我们的方法：plus

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

如果我们先看看溢出是否可能，然后创建一个比必要的更大的数组，我们可以在这里做得更好一点。

啊，一个测试：给，这看起来是正确的。d2.plus(d2)Big[24, 691357802, 469135780]

乘法。

让我们回到学校，我们是如何在纸上乘以更大的数字的？

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

因此，我们必须将第一个数字的每个数字[i]与第二个数字的每个数字[j]相乘，并将乘积加在结果的数字[i + j]中（并注意携带）。当然，这里的索引是从右边计数的，而不是从左边计算的。（现在我真的希望我用了小端数。

由于我们两个数字的乘积可以超出 的范围，我们用于乘法。intlong

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

现在我们可以看到为什么我声明我的方法来获取参数。（我刚刚将最后一个参数更改为 varargs 参数，以便能够更好地在这里编写此参数。addDigitsresultIndex

所以，这里是交叉乘法：

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]);
        }
    }
}

我希望我的指数计算是正确的。使用小端表示，它本来会更清晰，不是吗？multiplyDigit(result, resultIndex + i + j, leftFactor[i], rightFactor[j])

我们的方法现在只需要分配结果数组，调用并包装结果。timesmultiplyDigits

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

对于测试，给出 ，这与我的Emacs计算在这里计算的相同。d2.times(d2)Big[152, 415787532, 388367501, 905199875, 19052100]

比较

我们希望能够比较我们的两个对象。因此，我们实现及其比较到方法。Comparable<DecimalBigInt>

public int compareTo(DecimalBigInt that) {

如何知道我们的一个数字是否大于另一个数字？首先，我们比较数组的长度。由于我们注意不要诱导任何前导零（是吗？），较长的数组应该具有更大的数字。

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

如果长度相同，我们可以按元素进行比较。由于我们使用大端序（即大端先出现），因此我们从开头开始。

    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;
        }
    }

如果一切都是相同的，显然我们的数字是相同的，我们可以返回 。0

    return 0;
}

equals + hashCode()

每个好的不可变类都应该以合适（和兼容）的方式实现。equals()hashCode()

对于我们的，我们简单地对数字求和，用一个小素数将它们相乘，以确保数字切换不会导致相同的哈希代码：hashCode()

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

在该方法中，我们可以简单地委托给 compareTo 方法，而不是再次实现相同的算法：equals()

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

所以，今天足够了。减法（也许还有负数）和除法更复杂，所以我现在省略它们。对于计算 90 的阶乘，这应该足够了。

计算大阶乘：

这里的阶乘函数：

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

这给了我们

fac(90) = 1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000

从任意基数表示形式转换

在下一个问题的提示下，我写下了关于如何从任意（位置）数字系统转换的答案，我们可以（或想要）计算。（在示例中，我从三进制转换为十进制，而问题大约是十进制到二进制。

在这里，我们想从任意数字系统（好吧，基数在2到36之间，所以我们可以使用Charact.digit（）将个位数转换为整数）到基数（= 1.000.000.000，但这里并不重要）的系统。BASE

基本上，我们使用Horner方案来计算多项式的值，其中数字作为基数给出的点的系数。

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

可以用这个循环计算：

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

由于我们的输入字符串是大端的，因此我们不必倒计时，但可以使用简单的增强 for 循环。（在Java中它看起来更丑陋，因为我们没有运算符重载，也没有从int到我们的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;
}

在我的实际实现中，我添加了一些错误检查（和异常抛出），以确保我们真的有一个有效的数字，当然还有一个文档注释。

转换为任意位置系统更复杂，因为它涉及余数和除法（由任意基数），我们尚未实现 - 所以现在不是。当我对如何进行划分有一个好主意时，就会完成。（我们只需要在这里除以小的（一位数）数字，这可能比一般的除法更容易。

除以小数

在学校里，我学会了长除法。下面是一个小的（一位数）除数的例子，用十进制系统表示我们在德国使用的符号（带有关于背景计算的注释，我们通常不会写）：

 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.

当然，如果我们有原生余数运算，我们不需要计算这些乘积（0，12，0，30，42）并减去它们。然后它看起来像这样（当然，我们在这里不需要编写操作）：

 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.

这已经看起来很像短的划分，如果我们用另一种格式编写它。

我们可以观察（并证明）以下内容：

如果我们有一个两位数 x，第一位数字小于我们的除数 d，则 than 是一位数字，也是一位数字，小于 d。这与归纳法一起表明，我们只需要将（用余数）两位数除以除数。x / dx % d

回到我们用基数BASE的大数字：所有两位数的数字都可以表示为Java，在那里我们有本机和。long/%

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

现在，我们将在循环中调用此方法，始终将上一个回调的结果作为 .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;
}

此方法仍返回一个 int，即余数。

现在我们想要一个返回DecimalBigInt的公共方法，所以我们创建一个。它的任务是检查参数，为工作方法创建数组，丢弃余数，并从结果中创建DecimalBigInt。（构造函数删除可能存在的前导零。

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

我们也有一个类似的方法，它返回余数：

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

可以按如下方式调用这些方法：

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

转换为任意基数

现在，我们掌握了转换为任意基数的基础知识。当然，不是真正的任意，只是基数小于允许的，但这不应该是一个太大的问题。BASE

正如在另一个关于转换数字的答案中已经回答的那样，我们必须做“除法，余数，乘法，加法。“乘加”部分实际上只是将各个数字放在一起，因此我们可以用简单的数组访问来代替它。

由于我们总是需要商和余数，因此我们不会使用 public 方法和 ，而是反复调用该方法。modulodivideBydivideDigits

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

首先，0的特殊情况处理。

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

然后，我们为结果数字（足够长）和其他一些变量创建一个数组。

    // 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是最后商中的位数（不包括前导零）。如果这是 0，我们就完成了。

    while(quotLen > 0)  {

下一个商的新数组。

        int[] quot = new int[quotLen];

商和余数运算。商现在在 中，余数在 中。quotrem

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

我们将余数放在输出数组中（从最后一个数字填充它）。

        rDigits[rIndex] = rem;
        rIndex --;

然后，我们将数组交换到下一轮。

        current = quot;

如果商中有前导零（最多有一个，因为基数小于 BASE），我们将商的大小缩小一。下一个数组将更小。

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

在循环之后，rDigits数组中可能有前导零，我们切断它们。

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

就是这样。不过，它看起来有点复杂。以下是如何使用它的示例：

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

这些 print 和 与 之前解析的数字完全相同（尽管是从 String 中）。[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0][1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0]

基于此，我们还可以格式化为字符串：

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

如果您试图避免使用 ，则可能需要实现或研究二进制编码十进制的库。如果你想使用它，你可以完成90的阶乘：BigIntegerBigInteger

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;
}