如何在 Java 中处理非常大的数字而不使用 java.math.BigInteger

Question

在不使用 java.math.BigInteger 的情况下，如何使用任意大的整数进行算术 + - / * % !？

例如，在 Java 中，90 的阶乘返回 0。 我希望能够解决这个问题。

Answer 1

我认为程序员应该实现过一次自己的bignum-library，所以欢迎来到这里。

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

（你可以关注本课程life的源代码 在 github 上。此外，我将其重新制作（有点抛光）为14 部分博客系列.)

在 Java 中创建一个简单的 Big number 类

那么，我们需要什么？

的数字表示

首先，基于 Java 提供的数据类型

。当您认为十进制转换是最复杂的部分时，让我们保持基于十进制的模式。为了提高效率，我们不会存储真正的十进制数字，而是以基数 1 000 000 000 = 10^9 1 000 000 000 = 10^9 2^30。这适合 Java int（最多 2^31 或 2^32），以及两个这样的数字的乘积< /em> 非常适合 Java long。

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

作为一个额外的好处，这个构造函数还可以用于单个 int （如果小于 BASE），甚至可以用于没有 int （我们将解释为 0)。所以，我们现在可以这样做：

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

这给了我们 de.fencing_game.paul.examples.DecimalBigInt@6af62373，但不太有用。所以，我们添加一个 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);
}

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

二、十进制格式的转换。

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

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

这个奇怪的公式是 Java int 的写法：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]

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

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

三、转换为十进制格式。

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

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

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

这对于我们的两个数字返回 000000007000000005000000002000012345 和 000000012345678901234567890 。这适用于往返（即，将其提供给 valueOf 方法，给出一个等效的对象），但前导零看起来不太好（并且可能会与八进制数产生混淆）。因此，我们需要分解漂亮的 for-each 循环，并对第一个和后面的数字使用不同的格式字符串。

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) {
    ...
}

我希望您可以像阅读公式一样阅读方法名称，因此使用 plus、minus、times 而不是 add、<代码>减法、<代码>乘法。

那么，加法是如何工作的呢？它的工作原理与我们在学校学到的大于 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]中（注意进位）。当然，这里的索引是从右开始计算的，而不是从左开始。 （现在我真的希望我使用的是小端数字。）

由于两个数字的乘积可能超出 int 的范围，因此我们使用 long 用于乘法。

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

现在我们可以明白为什么我声明我的 addDigits 方法来接受 resultIndex 参数。 （我刚刚将最后一个参数更改为 varargs 参数，以便能够在这里更好地编写它。）

因此，这里是交叉相乘方法：

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]) - 更清楚，不是吗？

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

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

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

比较

我们希望能够比较两个对象。因此，我们实现了Comparable及其compareTo方法。

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

在 equals() 方法我们只需委托给compareTo 方法，而不是再次实现相同的算法：

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

从任意基数表示形式的转换

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

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

基本上，我们使用 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.

这看起来已经很像 短除法< /a>，如果我们用另一种格式来写。

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

如果我们有一个两位数 x，其第一位数字小于除数 d，则 x / d 是一位数，并且 x % d 也是一位数，小于 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 的基数，但这不应该是一个太大的问题。

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

由于我们总是需要商和余数，因此我们不会使用公共方法 modulo 和 divideBy，而是重复调用 divideDigits code> 方法。

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

商和余数运算。商现在位于 quot 中，
余数在 rem 中。

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

Answer 2

如果您尝试的话，您可能想实现或研究二进制编码的十进制的库以避免 BigInteger。如果您想使用 BigInteger，您可以使用它来完成 90 的阶乘：

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

使用下面的代码来乘以任意长度的数字：-

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

Java 中使用运算符 +、-、*、/ 和 % 受 Java 原始数据类型 的约束。

这意味着，如果您无法将所需的数字放入 double 或 long 的范围内，那么您将不得不使用“大数字”库，例如 Java 内置的 (BigDecimal ，BigInteger) ，或第三方库，或自己编写。这也意味着您不能使用算术运算符，因为 Java 不支持运算符重载。

Answer 5

当我想做90的时候！或其他一些大规模计算，我尝试使用 int[] 数组，每个元素保存一个数字。然后我应用传统的乘法，使用笔和纸在另一个 int[] 数组中得到答案。

这是我用 Java 编写的计算 100 的代码！相当快。您可以随意使用它。

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 6

强文本公共类 BigInteger {

     public static String checkSignWithRelational(int bigInt1, int bigInt2){
            if( bigInt1 < 0){
                return "negative";
            }else {
                return "positive";
            }
     }
     BigInteger( long init)
     {
         Long.parseLong(bigInt1);
     }
     BigInteger String (String init){
        return null; 
     }

    private static int intLenght(int bigInt) {

        return Integer.toString(bigInt).length();
    }

    private static int[] intToArray(int bigInt, int bigIntLength, int arrayLength) {

        int array[] = new int[arrayLength ]; 
        for (int i = 0; i < arrayLength ; i++) {
            array[i] = ( i<bigIntLength ?
                             getDigitAtIndex(bigInt, bigIntLength - i -1) :0 ); 
        }
        return array;
}
    static String add(int bigInt1, int bigInt2) {
        //Find array length
        int length1 = intLenght(bigInt1);
        int length2 = intLenght(bigInt2);
        int arrayLength = Math.max(length1, length2);


        int array1[] = intToArray(bigInt1, length1, arrayLength);
        int array2[] = intToArray(bigInt2, length2, arrayLength);


        return add(array1, array2);
    }


    private static String add(int[] array1, int[] array2) {
        int carry=0;
        int addArray[] = new int[array1.length + 1];


        for (int i = 0; i < array1.length; i++) {
            addArray[i] = (array1[i] + array2[i] + carry) % 10 ; 
            carry = (array1[i] + array2[i] + carry) / 10; 
        }
        addArray[array1.length] = carry;
        return arrayToString(addArray);
    }

    private static int getDigitAtIndex(int longint,int index){        
        return Integer.parseInt(Integer.toString(longint).substring(index, index+1)); 
    }
    private static String arrayToString(int[] addArray) {
        String add = "";
        boolean firstNonZero = false; 
        for (int i = addArray.length-1; i >= 0 ; i--) {  

            if(!firstNonZero && (addArray[i]==0)){ 
                continue;
            } else{
                firstNonZero=true;
            }
            add += addArray[i];
            if((i%3 ==0)&&i!=0){ add +=",";}  //formatting
        }
        String sumStr = add.length()==0?"0":add; 
        return sumStr;
    }
    public static String sub(int bigInt1, int bigInt2) {


        int length1 = intLenght(bigInt1);
        int length2 = intLenght(bigInt2);
        int arrayLength = Math.max(length1, length2);


        int array1[] = intToArray(bigInt1, length1, arrayLength);
        int array2[] = intToArray(bigInt2, length2, arrayLength);


        return sub(array1, array2);
    }
    private static String sub(int[] array1, int[] array2) {
        int carry=0;
        int sub[] = new int[array1.length + 1];


        for (int i = 0; i < array1.length; i++) {
            sub[i] = (array1[i] - array2[i] + carry) % 10 ; //sum digits + carry; then extract last digit
            carry = (array1[i] - array2[i] + carry) / 10; //Compute carry
        }
        sub[array1.length] = carry;
        return arrayToString(sub);
    }
    public static String mul(int bigInt1, int bigInt2) {
        int length1 = intLenght(bigInt1), length2 = intLenght(bigInt2), length = Math.max(length1, length2);        
        int array1[] = intToArray(bigInt1, length1, length); int array2[] = intToArray(bigInt2, length2, length);
        return mul(array1, array2);
    }
    private static String mul(int[] array1, int[] array2) {
        int product[] = new int[array1.length + array2.length];
        for(int i=0; i<array1.length; i++){        
            for(int j=0; j<array2.length; j++){ 

                int prod = array1[i] * array2[j];       
                int prodLength = intLenght(prod);
                int prodAsArray[] =  intToArray(prod, prodLength, prodLength); 


                for (int k =0; k < prodAsArray.length; k++) {
                    product[i+j+k] += prodAsArray[k];


                    int currentValue = product[i+j+k];
                    if(currentValue>9){
                        product[i+j+k] = 0;                
                        int curValueLength = intLenght(currentValue);
                        int curValueAsArray[] = intToArray(currentValue, curValueLength, curValueLength);
                        for (int l = 0; l < curValueAsArray.length; l++) {
                            product[i+j+k+l] += curValueAsArray[l];
                        }
                    }
                }      
            }
        }
        return arrayToString(product);
    }

   public static int div(int bigInt1, int bigInt2) {
       if ( bigInt2 == 0){
           throw new ArithmeticException("Division by 0 is undefined:" + bigInt1+ "/" + bigInt2);
       }
       int sign = 1;
       if(bigInt1 < 0) {
           bigInt1 = -bigInt1;
           sign = -sign;
       }
       if (bigInt2 < 0){
           bigInt2 = -bigInt2;
           sign = -sign;

       }
       int result  =0;
       while (bigInt1 >= 0){
           bigInt1 -= bigInt2;
           result++;
       }
       return (result - 1) * sign;
   }

    public static String check(String bigInt1, String bigInt2){
        int difference;
        StringBuilder first = new StringBuilder(bigInt1);
        StringBuilder second = new StringBuilder(bigInt2);

        if(bigInt1.length()> bigInt2.length()){
            difference = bigInt1.length() - bigInt2.length();
            for(int x = difference; x > 0; x--){
                second.insert(0,"0");

            }
        bigInt2 = second.toString();
        return bigInt2;

        }else {
            difference = bigInt2.length() - bigInt1.length();
            for (int x = difference; x> 0; x--)
            {
                first.insert(0, "0");
            }
            bigInt1 = first.toString();
            return bigInt1;
        }
    }
    public static int mod(int bigInt1, int bigInt2){
        int res = bigInt1 % bigInt2;
        return (res);

    }

    public static void main(String[] args) {

        int bigInt1 = Integer.parseInt("987888787");
        int bigInt2 = Integer.parseInt("444234343");
        System.out.println(bigInt1+" + "+bigInt2+" = "+add(bigInt1, bigInt2));
        System.out.println(bigInt1+" - "+bigInt2+" = "+sub(bigInt1, bigInt2));
        System.out.println(bigInt1+" * "+bigInt2+" = "+mul(bigInt1, bigInt2));
        System.out.println(bigInt1+" / "+bigInt2+" = "+div(bigInt1, bigInt2));
        System.out.println(bigInt1+" % "+bigInt2+" = "+mod(bigInt1, bigInt2));
    }

}

Answer 7

如果我们想要对非常大的数字执行算术运算，那么它们必须采用某种对象形式，例如字符串。

令它们为字符长度大于BigInteger范围的字符串。

在本例中，我将像在笔记本上执行算术运算一样执行算术运算。
例如 - 假设我们必须进行加法。
首先比较两个字符串的长度。
制作三个新弦。
第一个字符串是较小的字符串。
第二个字符串是较长字符串的最右边子字符串，其长度等于较小字符串。
第三根弦是左边剩下的长弦。
现在添加末尾的第一个和第二个字符串，将字符转换为整数，一次一个字符，并将进位保留在 int 变量中。每次相加后，立即将总和追加到 StringBuffer 中。两个字符串相加后，对第三个字符串进行同样的操作，继续添加进位。最后反转StringBuffer并返回String。

这是我用于加法的代码

public String addNumber(String input1,String input2){
int n=0;String tempStr;
String one="";
String two="";
if(input1.length()>input2.length()){
    n=input1.length()-input2.length();
    tempStr=new String(input1);
    one=new String(input1.substring(n,input1.length()));
    two=new String(input2);
}else{
    n=input2.length()-input1.length();
    tempStr=new String(input2);
    one=new String(input2.substring(n,input2.length()));
    two=new String(input1);
}
StringBuffer temp=new StringBuffer();
for(int i=0;i<n;i++){
    temp.append(tempStr.charAt(i));
}
StringBuffer newBuf=new StringBuffer();
int carry=0;
int c;
for(int i=one.length()-1;i>=0;i--){
    int a=Character.getNumericValue(one.charAt(i));
    int b=Character.getNumericValue(two.charAt(i));
    c=a+b+carry;

    newBuf.append(""+(c%10));
    c=c/10;
    carry=c%10;
}
String news=new String(temp);
for(int i=news.length()-1;i>=0;i--){
c=(Character.getNumericValue(news.charAt(i)))+carry;
newBuf.append(""+(c%10));
c=c/10;
carry=c%10;
}
if(carry==1){
    newBuf.append(""+carry);
}
String newisis=new String(newBuf.reverse());
return newisis;
}