小开

Java 中使用运算符 +、 -、 *、 /和 %的算术运算受到 Java 基本数据类型的约束。

这意味着如果你不能把你想要的数字放进一个范围内，比如说 double或者 long，那么你就必须使用一个“大数字”库，比如 Java 内置的(BigDecimal，BigInteger) ，或者一个第三方库，或者编写你自己的。这也意味着你不能使用算术运算符，因为 Java 不支持运算符重载。

小开

如果您试图避免使用 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;
}

小开

最佳答案

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

(当然，稍后您会发现 BigInteger 更好，并使用它，但它是一种宝贵的学习经验。)

(您可以按照本课程生活在 Github 上的源代码。此外，我重新制作了这个(有点抛光)到 14部分的博客系列。)

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

我们需要什么？

首先，数字的表示形式,

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

由于您认为十进制转换是最复杂的部分，因此让我们保持在基于十进制的模式中。为了提高效率，我们将不存储真正的十进制数字，而是以 1 000 000 000 = 10^9 < 2^30为基数。这适合于 Javaint(到 2^31或 2^32) ，两个这样的数字的产品适合于 Javalong。

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

然后是数字数组:

private int[] digits;

我们是用小端还是大端来存储数字，也就是说，大的部分是第一个还是最后一个？这并不重要，所以我们决定使用 big-endian，因为这是人类想要的解读方式。(现在我们关注的是非负数值——稍后我们将为负数添加一个符号位。)

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

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

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

这是第一个十进制数字块的长度，应在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来完成第一个较短的块。) 现在我们使用通常的 Integer 解析函数，并将结果放入数组:

    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，subtract，multiply。

那么，加法是如何工作的呢？它的工作原理和我们在学校学到的大于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 ]中加上乘积(并注意进位)。当然，这里的索引是从右边计数的，而不是从左边。(现在我真希望我用了 little-endian 数)

由于我们两个数字的乘积可以超出 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 计算结果相同。

比较

我们希望能够比较两个对象，因此，我们实现了 Comparable<DecimalBigInt>和它的 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

从任意基表示转换

在下一个关于弗罗多萨摩亚的问题的提示下，我写了我的答案是关于如何从我们可以(或想要)计算的任意(位置)数字系统转换。(在这个示例中，我将三进制转换为十进制，而问题是关于十进制转换为二进制。)

在这里，我们希望从任意数字系统(基数在2和36之间，因此我们可以使用 Character.digit()将单位数字转换为整数)转换为基数为 BASE的系统(= 1.000.000.000，但这并不重要)。

基本上，我们使用霍纳计划来计算多项式的值与数字作为系数在给定的点的基数。

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

可以用这个循环来计算:

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

因为我们的输入字符串是 big-endian，所以我们不需要倒计时，但是可以使用一个简单的增强 for 循环。 (在 Java 中看起来更丑，因为我们没有运算符重载，也没有 int 到 our 的自动装箱 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，那么 x / d是一位数，而 x % d也是一位数，小于 d。这个结合归纳，表明我们只需要用我们的除数除(余数)两位数。

回到基数为 BASE 的大数: 所有的两位数都可以表示为 Javalong，这里我们有原生的 /和 %。

/**
* 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方法。

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

如果商中有前导零(最多有一个，因为基数小于基数) ，我们将商的大小缩小一会更小。

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

这些输出 [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]，与我们之前解析的数字相同(但是来自 String)。

在此基础上，我们还可以将其格式化为字符串:

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

小开

使用下面的代码将任意长度的数字相乘:-

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


}


}

小开

强文本公共类 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)); }

}

小开

当我想做到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; }

小开

如果我们想要对真正大的数字执行算术运算，那么它们必须是某种对象形式，比如 String。

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

在这种情况下，我将像在笔记本上那样执行算术运算。例如-让我们假设我们必须做加法。首先比较两个字符串的长度。做三个新字符串。第一个字符串比较小。第二个字符串是较长字符串中最右边的子字符串，其长度等于较小的字符串。第三根弦是左边剩下的长线。现在添加第一个和第二个字符串从结束转换字符到整数，一次一个字符，并保持进位在一个整型变量。在每次添加之后，立即在 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; }

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