我将如何在不使用 java.math.BigInteger 的情况下使用任意大的整数进行算术运算，+ -/* % !
例如，90 的阶乘在 Java 中返回 0。
我希望能够解决这个问题。
最佳答案
我认为程序员应该已经实现了他自己的 bignum-library，所以欢迎来到这里。
(当然，稍后你会发现 BigInteger 更好，并使用它，但这是一次宝贵的学习经验。)
(你可以按照这个类(class)生活的源代码 on github 。另外，我把它(有点抛光)改成了 14-part blog series 。)
用 Java 创建一个简单的大数类
那么，我们需要什么？
首先，数字的表示，
基于 Java 提供给我们的数据类型。
由于您认为十进制转换是最复杂的部分，让我们保持基于十进制的模式。为了效率，我们不会存储真正的十进制数字，而是在基数 1 000 000 000 = 10^9 < 2^30 中工作。这适合 Java int(最多 2^31 或 2^32 )，并且两个这样的数字的乘积很好地适合 Java 0x25181242313431
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();
}
long(如果小于 int)，甚至对于没有 BASE(我们将其解释为 0)。所以，我们现在可以这样做:DecimalBigInt d = new DecimalBigInt(7, 5, 2, 12345);
System.out.println(d);
int ，不太有用。所以，我们添加一个 de.fencing_game.paul.examples.DecimalBigInt@6af62373 方法:/**
* A simple string view for debugging purposes.
* (Will be replaced later with a real decimal conversion.)
*/
public String toString() {
return "Big" + Arrays.toString(digits);
}
toString() ，这对测试更有用，不是吗？其次，从十进制格式转换。
我们很幸运:我们的基数 (10^9) 是我们想要从 (10) 转换的基数的幂。因此，我们总是有相同数量 (9) 的十进制数字代表一个“我们的格式”数字。 (当然，一开始可能会少一些数字。)在下面的代码中，
Big[7, 5, 2, 12345]是一个十进制数字的字符串。 int decLen = decimal.length();
int bigLen = (decLen-1) / BASE_DECIMAL_DIGITS + 1;
decimal 的方式。 (我希望它是正确的，我们稍后会测试它。) int firstSome = decLen - (bigLen-1) * BASE_DECIMAL_DIGITS;
我们创建我们的数组:
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);
bigLen = ceil(decLen/BASE_DECIMAL_DIGITS) 用于第一个较短的块。)我们现在使用通常的整数解析函数，并将结果放入数组中:
digits[i] = Integer.parseInt(block);
}
return new DecimalBigInt(digits);
DecimalBigInt d2 = DecimalBigInt.valueOf("12345678901234567890");
System.out.println(d2);
Big[12, 345678901, 234567890]
下一部分将是十进制格式，这应该更容易。
三、转换为十进制格式。
我们需要将每个数字输出为 9 个十进制数字。为此，我们可以使用
Math.max 类，它支持类似 printf 的格式字符串。一个简单的变体是这样的:
public String toDecimalString() {
Formatter f = new Formatter();
for(int digit : digits) {
f.format("%09d", digit);
}
return f.toString();
}
Formatter 和 000000007000000005000000002000012345。这适用于往返(即将它提供给 000000012345678901234567890 方法给出了一个等效的对象)，但前导零不太好看(并且可能与八进制数混淆)。所以我们需要分解我们漂亮的 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) {
...
}
valueOf , plus , minus 而不是 0x251812231343145 , 131343145 , 1313145 , 135那么，加法是如何工作的呢？它的工作原理与我们在学校学到的大于 9 的十进制数相同:添加相应的数字，如果其中一些结果大于 10(或在我们的例子中为
times)，则将一个进位到下一位。这可能导致结果数字比原始数字多一位。首先我们看两个数字具有相同位数的简单情况。然后它看起来就像这样:
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);
如果两个数字的位数不同，则情况会变得更复杂一些。
为了让它尽可能简单，我们将其拆分为几种方法:
此方法将一位数字添加到数组中的元素(可能已经包含一些非零值)，并将结果存储回数组中。如果有溢出，我们通过递归调用将它传送到下一个数字(索引少一个，而不是一个多)。这样我们可以确保我们的数字始终保持在有效范围内。
/**
* 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--;
}
}
add 方法:/**
* 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);
}
啊，一项测试:
subtract 给出 multiply ，看起来不错。乘法。
让我们回想起学校，我们是如何在纸上乘以更大的数字的？
123 * 123
----------
369 <== 123 * 3
246 <== 123 * 2
123 <== 123 * 1
--------
15129
由于我们的两个数字的乘积可能超出
BASE 的范围，因此我们使用 plus 进行乘法运算。/**
* 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);
}
d2.plus(d2) 方法来接受一个 Big[24, 691357802, 469135780] 参数。 (我只是将最后一个参数更改为 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]);
}
}
}
int - 非常清楚，不是吗？我们的
long 方法现在只需要分配结果数组，调用 addDigits 并包装结果。/**
* 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);
}
resultIndex 给出 multiplyDigit(result, resultIndex + i + j, leftFactor[i], rightFactor[j]) ，这与我的 Emacs 计算在这里计算的结果相同。比较
我们希望能够比较我们的两个对象。因此，我们实现了
times 及其 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;
}
}
multiplyDigits 。 return 0;
}
d2.times(d2) + Big[152, 415787532, 388367501, 905199875, 19052100]每个好的不可变类都应该以合适(和兼容)的方式实现 Comparable<DecimalBigInt> 和 0 。对于我们的
equals ，我们简单地将数字相加，将它们乘以一个小素数以确保数字切换不会产生相同的哈希码:/**
* calculates a hashCode for this object.
*/
public int hashCode() {
int hash = 0;
for(int digit : digits) {
hash = hash * 13 + digit;
}
return hash;
}
hashCode() 方法中，我们可以简单地委托(delegate)给 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 问题的提示下，我写了 my answer about how to convert from arbitrary (positional) number systems in the one in which we can (or want to) calculate 。 (在那里的示例中，我从三进制转换为十进制，而问题是关于十进制到二进制的。)
在这里，我们想从任意数字系统(好吧，基数在 2 到 36 之间，所以我们可以使用
equals() 将个位数转换为整数)转换为基数为 hashCode()(= 1.000.000.000)的系统(= 1.000.000.000)这里)。基本上我们使用 Horner scheme 来计算多项式的值，其中数字作为基数给定点处的系数。
sum[i=0..n] digit[i] * radix^i
value = 0;
for i = n .. 0
value = value * radix + digit[i]
return value
(它在 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;
}
将 转换为 一个任意位置系统更复杂，因为它涉及余数和除法(通过任意基数)，我们还没有实现 - 所以现在不是。当我对如何进行除法有一个好的想法时，它就会完成。 (这里我们只需要除以小(一位)数字，这可能比一般除法更容易。)
小数除法
在学校，我学到了 long division 。这是一个小(一位)除数的例子，在我们在德国使用的符号中(带有关于背景计算的注释，我们通常不会写)，在十进制系统中:
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.
如果我们有 native 余数运算，则减去它们。然后看起来
像这样(当然，我们这里不需要编写操作):
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，那么
hashCode() 是一位数，而 equals() 也是一位数，小于 d。这与归纳一起表明我们只需要将(带余数)两位数除以我们的除数。回到基数 BASE 的大数字:所有两位数都可以表示为 Java
Character.digit() ，我们有原生的 BASE 和 x / d 。/**
* 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;
}
x % d 返回。/**
* 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;
}
现在我们想要一个返回 DecimalBigInt 的公共(public)方法，所以我们创建了一个。它的任务是检查参数，为工作方法创建一个数组，丢弃余数，并根据结果创建一个 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));
现在我们有了转换为任意基数的基础知识。当然，不是很随意，只允许小于
long 的基数，但这应该不是太大的问题。正如在另一个关于转换数字的答案中已经回答的那样，我们必须进行“除法、余数、乘法、加法”。“乘加”部分实际上只是将各个数字放在一起，因此我们可以用一个简单的数组替换它-使用权。
因为我们总是需要商和余数，所以我们不会使用公共(public)方法
/ 和 % ，而是重复调用 lastRemainder 方法。/**
* 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!");
}
// 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;
BASE 是最后商的位数(不包括前导零)。如果这是0，我们就完成了。 while(quotLen > 0) {
int[] quot = new int[quotLen];
modulo 中，divideBy 中的余数。 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--;
}
}
// 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)));
divideDigits 和 quotLen ，与我们之前解析的数字相同(尽管来自字符串)。基于此，我们还可以格式化为字符串:
/**
* 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();
}
关于java - 如何在不使用 java.math.BigInteger 的情况下在 Java 中处理非常大的数字，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5318068/