如何在不使用java.math.BigInteger的情况下处理Java中的大数字

我将如何去做算术,+ – / *%!,使用任意大的整数而不使用java.math.BigInteger

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

我认为一个程序员应该曾经实现过他自己的图书馆,所以在这里欢迎。

(当然,以后你会得到BigInteger更好,并使用它,但这是一个很有价值的学习经验。)

(你可以在github上看到这个课程的源代码,而且我把它重新编译成了一个有14个部分的博客系列 。)

在Java中创build一个简单的Big数字类

那么,我们需要什么?

首先,表示数字,

基于Java给我们的数据types。

正如你认为的十进制转换是最复杂的部分,让我们留在十进制模式。 为了提高效率,我们将存储不是真正的小数位数,但以1 000 000 000 = 10^9 < 2^30基数工作。 这适合于一个Java int (高达2^312^32 ),两个这样的数字的产品恰好适合于Java long

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

那么数组数组:

 private int[] digits; 

我们是否将数字存储在小端或大端,即较大的部分首先还是最后? 这并不重要,所以我们决定使用big-endian,因为这是人类想要读的。 (现在我们专注于非负值 – 稍后我们将为负值添加一个符号位。)

出于testing目的,我们添加一个构造函数,允许从这样一个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] ,这对testing更有用,不是吗?

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

我们在这里很幸运:我们的基地(10 ^ 9)是我们想从(10)转换的基地的力量。 因此,我们总是有相同的数字(9)十进制数字代表一个“我们的格式”数字。 (当然,一开始可能会less一些数字。)在下面的代码中, decimal是一个十进制数字的string。

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

这个奇怪的公式是写bigLen = ceil(decLen/BASE_DECIMAL_DIGITS)的Java int方法。 (我希望它是正确的,我们稍后会testing它。)

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

这是第一个十进制数字块的长度,应该在1和9之间(包括)。

我们创build我们的数组:

  int[] digits = new int[bigLen]; 

循环显示要创build的数字:

  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 。)现在我们使用通常的Integerparsing函数,并将结果放入数组中:

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

从现在创build的数组中,我们创build了DecimalBigInt对象:

 return new DecimalBigInt(digits); 

让我们看看这是否工作:

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

输出:

 Big[12, 345678901, 234567890] 

看起来是正确的:-)我们应该用一些其他的数字(不同的长度)来testing它。

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

三,转换为十进制格式。

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

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

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

这两个数字返回000000007000000005000000002000012345000000012345678901234567890 。 这适用于往返行程(即将其馈送给valueOf方法提供等效的对象),但前导零并不是真的很好看(可能会造成与八进制数字混淆)。 所以我们需要分开我们美丽的for-each循环,并为第一个和后面的数字使用不同的格式化string。

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

我想要的方法名称,你可以阅读就像你会阅读的公式,因此, minus ,而不是addsubtractmultiply

那么,如何增加工作? 它与我们在学校学到的十进制数字大于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格式,这会更漂亮一点。)

如果两个号码都没有相同的位数,则会变得更复杂。

为了让它尽可能简单,我们把它分成几种方法:

此方法向数组中的元素(可能已包含某个非零值)添加一位数字,并将结果存储回数组中。 如果发生溢出,我们通过recursion调用将它传递给下一个数字(索引less一个,而不是一个)。 这样我们确保我们的数字始终保持在有效范围内。

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

我们可以在这里做一些更好的事情,如果我们会看看,如果溢出是所有可能的,只有然后创build一个大于必要的数组。

啊,一个testing: 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]); } } } 

我希望我有指数计算的权利。 用little-endian表示法,它应该是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); } 

对于testing, d2.times(d2)给出Big[152, 415787532, 388367501, 905199875, 19052100] ,这与我的Emacs calc在这里计算的结果是一样的。

对照

我们希望能够比较我们的两个对象。 所以,我们实现了Comparable<DecimalBigInt>及其compareTo方法。

 public int compareTo(DecimalBigInt that) { 

如何知道我们的数字是否大于另一个? 首先,我们比较arrays的长度。 当我们注意不要引起任何前导零(我们?),更长的数组应该有更大的数字。

  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方法,而不是再次实现相同的algorithm:

 /** * 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,但是这个在这里并不重要)。

基本上我们使用Hornerscheme来计算在基数给定的点上以数字为系数的多项式的值。

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

可以用这个循环来计算:

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

由于我们的inputstring是big-endian,我们不必倒数,但可以使用一个简单的增强for循环。 (在Java中它看起来更丑陋,因为我们没有运算符重载,也没有从int到我们的DecimalBigInttypes的自动装箱。

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

在我的实际实现中,我添加了一些错误检查(和exception抛出),以确保我们确实有一个有效的数字,当然还有一个文档注释。


转换一个任意的位置系统是比较复杂的,因为它涉及余数和除数(通过任意的基数),我们还没有实现 – 现在不是这样。 当我对如何做分工有一个好主意的时候,我会做。 (在这里我们只需要用小数字(一位数字)来划分,这比一般的划分要容易一些。)

由小数字划分

在学校,我学会了长远的分工 。 下面是一个小数位(1位数除数)的例子,我们在德国使用的符号(有关背景计算的注释,我们通常不会写),用十进制表示:

  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. 

如果我们用另外一种格式来写的话,这已经看起来很像了。

我们可以观察(并certificate)以下内容:

如果我们有一个两位数的数字x,第一位小于我们的除数d,那么x / d是一个一位数的数字, x % d也是一个小于d的一位数字。 这与归纳法一起表明,我们只需要用除数除(余数)两位数字。

用BASE回到我们的大数字:所有的两位数字都可以用Java来表示,而我们有native /%

 /** * does one step in the short division algorithm, ie 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; } 

我们现在将在一个循环中调用这个方法,总是将前一个callback的结果作为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的公共方法,所以我们创build一个。 它的任务是检查参数,为工作方法创build一个数组,放弃余数,并从结果中创build一个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小的基数,但这不应该是一个太大的问题。

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

因为我们总是需要商和余数,所以我们不会使用公有方法modulodivideBy ,而是反复调用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]; 

然后,我们为结果数字创build一个数组(足够长),以及其他一些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是最后一个商的位数(不包括前导零)。 如果这是0,我们就完成了。

  while(quotLen > 0) { 

下一个商的新arrays。

  int[] quot = new int[quotLen]; 

商和余数操作。 现在商是rem ,余额是rem

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

我们把余数放在输出数组中(从最后一位数字填入)。

  rDigits[rIndex] = rem; rIndex --; 

然后我们交换arrays进行下一轮。

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

这些打印[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] ,与我们之前parsing的数字相同(从string,虽然)。

基于此,我们也可以格式化为一个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(); } 

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

Java中使用运算符+-*/%算术运算受Java基本数据types的约束约束。

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

使用下面的代码来乘以任何长度的数字:

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

}

When I want to do 90! or some other massive calculation, I try and use an int[] array, each element holding one of the digits. Then I apply the traditional multiplication we using pen and paper to get the answer in another int[] array.

This is the code I wrote in Java which calculates 100! rather quickly. Feel free to use this however you like.

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