如何在不使用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^31或2^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(); }
这两个数字返回000000007000000005000000002000012345和000000012345678901234567890 。 这适用于往返行程（即将其馈送给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 ，而不是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格式，这会更漂亮一点。）
如果两个号码都没有相同的位数，则会变得更复杂。
为了让它尽可能简单，我们把它分成几种方法：
此方法向数组中的元素（可能已包含某个非零值）添加一位数字，并将结果存储回数组中。 如果发生溢出，我们通过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小的基数，但这不应该是一个太大的问题。
正如已经在另一个关于数字转换的答案中所回答的，我们必须做“除法，余数，乘法，加法”，“乘加”部分实际上只是把个别数字放在一起，所以我们可以用一个简单的数组来代替它，访问。
因为我们总是需要商和余数，所以我们不会使用公有方法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];
然后，我们为结果数字创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; }
