如何在不使用java.math.BigInteger的情况下在Java中处理非常大的数字 [英] How to handle very large numbers in Java without using java.math.BigInteger
问题描述
如何在不使用 java.math.BigInteger ？
例如，因子90在Java中返回0。
我希望能够解决这个问题。
For instance, the factorial of 90 returns 0 in Java. I would like to be able to solve that.
推荐答案
我认为程序员应该实施自己的bignum-库一次，所以欢迎来到这里。
I think a programmer should have implemented his own bignum-library once, so welcome here.
（当然，稍后你会得到BigInteger更好，并使用它，但这是一个宝贵的学习经验。）
(Of course, later you'll get that BigInteger is better, and use this, but it is a valuable learning experience.)
（您可以按照本课程的源代码。另外，我将这个（有点抛光）重新制作成 14部分博客系列。）
(You can follow the source code of this course life on github. Also, I remade this (a bit polished) into a 14-part blog series.)
那么，我们需要什么？
。
正如你所想的那样cimal转换是最复杂的部分，让我们保持基于十进制的模式。为了提高效率，我们将存储不是真正的十进制数字，而是在基数 1 000 000 000 = 10 ^ 9< 2 ^ 30 。这适用于Java int （最多 2 ^ 31 或 2 ^ 32 ），两个这样的数字的产品非常适合Java long 。
As you think the decimal conversion is the most complicated part, let's stay in a decimal based mode. For efficiency, we'll store not real decimal digits, but work in base 1 000 000 000 = 10^9 < 2^30. This fits in a Java int (up to 2^31 or 2^32), and the product of two such digits fits nicely in a Java long.
final static int BASE = 1000000000;
final static int BASE_DECIMAL_DIGITS = 9;
然后是digits-array：
Then the digits-array:
private int[] digits;
我们是以小端还是大端存储数字，即较大的部分是先还是最后？这并不重要，所以我们决定使用big-endian，因为这是人类想要阅读它的方式。 （现在我们专注于非负值 - 稍后我们将为负数添加一个符号位。）
Do we store the digits in little- or big endian, i.e. the bigger parts first or last? It does not really matter, so we decide on big-endian since this is how humans want to read it. (For now we concentrate on non-negative values - later we'll add a sign bit for negative numbers.)
出于测试目的，我们添加一个允许初始化的构造函数来自这样的int []。
For testing purposes, we add a constructor which allows initializing from such a 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）。所以，我们现在可以这样做：
As a added bonus, this constructor is also usable for a single int (if smaller than BASE), and even for no int (which we'll interpret as 0). So, we now can do this:
DecimalBigInt d = new DecimalBigInt(7, 5, 2, 12345);
System.out.println(d);
这给我们 de.fencing_game.paul.examples.DecimalBigInt@6af62373 ，没那么有用。所以，我们添加一个 toString（）方法：
This gives us de.fencing_game.paul.examples.DecimalBigInt@6af62373, not so useful. So, we add a toString() method:
/**
* 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] ，这对测试更有用，不是吗？
The output is now Big[7, 5, 2, 12345], which is more useful for testing, isn't it?
我们很幸运：我们的基数（10 ^ 9）是我们想要从（10）转换的基数的幂。因此，我们总是有相同数字（9）的十进制数字代表一个我们的格式数字。 （当然，在开头可能会有一些数字更少。）在下面的代码中， decimal 是一个十进制数字的字符串。
We are lucky here: our base (10^9) is a power of the base we want to convert from (10). Thus, we always have the same number (9) of decimal digits representing one "our format" digit. (Of course, in the beginning there may be some digits less.) In the following code, decimal is a String of decimal digits.
int decLen = decimal.length();
int bigLen = (decLen-1) / BASE_DECIMAL_DIGITS + 1;
这个奇怪的公式是Java int写作方式 bigLen = ceil（decLen） / BASE_DECIMAL_DIGITS）。 （我希望它是正确的，我们稍后会测试它。）
This strange formula is a Java int way of writing bigLen = ceil(decLen/BASE_DECIMAL_DIGITS). (I hope it is correct, we'll later test it.)
int firstSome = decLen - (bigLen-1) * BASE_DECIMAL_DIGITS;
这是第一个十进制数字块的长度，应该在1到9之间（含） 。
This is the length of the first block of decimal digits, should be between 1 and 9 (inclusive).
我们创建数组：
int[] digits = new int[bigLen];
循环创建数字：
for(int i = 0; i < bigLen ; i++) {
每个我们的数字由原始数字中的一个数字块表示：
Each of our digits is represented by a block of digits in the original number:
String block =
decimal.substring(Math.max(firstSome + (i-1)*BASE_DECIMAL_DIGITS, 0),
firstSome + i *BASE_DECIMAL_DIGITS);
（此处需要 Math.max 对于第一个较短的块。）
我们现在使用通常的Integer解析函数，并将结果放入数组中：
(The Math.max is needed here for the first shorter block.)
We now use the usual Integer parsing function, and put the result into the array:
digits[i] = Integer.parseInt(block);
}
从现在创建的数组中我们创建了DecimalBigInt对象：
From the array now created we create our DecimalBigInt object:
return new DecimalBigInt(digits);
让我们看看是否有效：
DecimalBigInt d2 = DecimalBigInt.valueOf("12345678901234567890");
System.out.println(d2);
输出：
Big[12, 345678901, 234567890]
看起来正确:-)我们应该测试它还带有一些其他数字（不同长度）。
Looks right :-) We should test it with some other numbers (of different length) too.
下一部分将是十进制格式，这应该更容易。
Next part will be decimal formatting, this should be even easier.
我们需要输出各自的9位十进制数字。为此，我们可以使用 Formatter 类，它支持类似printf的格式字符串。
We need to output our individual digits as 9 decimal digits each. For this we can use the Formatter class, which supports printf-like format strings.
一个简单的变体将是这个：
A simple variant would be this:
public String toDecimalString() {
Formatter f = new Formatter();
for(int digit : digits) {
f.format("%09d", digit);
}
return f.toString();
}
返回 000000007000000005000000002000012345 和 000000012345678901234567890 我们的两个号码。这适用于往返（即将其提供给 valueOf 方法给出一个等效对象），但是前导零并不是很好看（并且可能会造成混淆）用八进制数）。所以我们需要拆开我们漂亮的for-each循环，并为第一个和后面的数字使用不同的格式化字符串。
This returns 000000007000000005000000002000012345 and 000000012345678901234567890 for our two numbers. This works for a round-trip (i.e. feeding it to the valueOf method gives an equivalent object), but the leading zeros are not really nice to look at (and could create confusion with octal numbers). So we need to break apart our beautiful for-each loop and use a different formatting string for the first and the following digits.
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();
}
加法。
让我们从加法开始，因为这很简单（我们可以稍后使用它的一部分进行乘法）。
Addition.
Let's start with addition, as this is simple (and we can use parts of it for the multiplication later).
/**
* calculates the sum of this and that.
*/
public DecimalBigInt plus(DecimalBigInt that) {
...
}
我想要你可以阅读的方法名称，就像你会阅读公式一样，因此加上，减去，次而不是添加，减去 ，乘以。
I want method names that you can read like you would read the formula, thus plus, minus, times instead of add, subtract, multiply.
那么，加法如何运作？它与我们在学校学到的高于9的十进制数一样工作：添加相应的数字，如果有一些结果大于10（或 BASE 在我们的例子中），携带一个到下一个数字。这可能导致结果数字比原始数字多一位。
So, how does addition work? It works the same as we learned it in school for decimal numbers higher than 9: add the corresponding digits, and if for some of then the result is bigger than 10 (or BASE in our case), carry one to the next digit. This can cause the resulting number to have one digit more than the original ones.
首先我们看一下这两个数字具有相同位数的简单情况。然后它看起来像这样：
First we look at the simple case that both numbers have same number of digits. Then it looks simply like this:
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格式，可能会更漂亮。）
(We go from right to left, so we can carry any overflows to the next digit. This would be a bit prettier if we had decided using Little Endian format.)
如果两个数字的数字位数不同，则会有点复杂。
If both numbers do not have the same number of digits, it gets a bit more complicated.
为了让它尽可能简单，我们将它分成几种方法：
To let it as simple as possible, we split it to several methods:
此方法将一个数字添加到数组中的元素（可能已经包含一些非零值），并将结果存储回数组中。如果有溢出，我们通过递归调用将它带到下一个数字（其索引少一个，而不是一个）。这样我们就可以确保我们的数字始终保持在有效范围内。
This method adds one digit to an element in the array (which may already contain some non-zero value), and stores the result back in the array. If there was overflow, we carry it to the next digit (which has index one less, not one more) by means of a recursive call. This way we make sure our digits stay always in the valid range.
/**
* 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);
}
}
下一步对整个数字数组都是一样的添加：
The next does the same for a whole array of digits to add:
/**
* 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--;
}
}
现在我们可以实现加上方法：
Now we can implement our plus method:
/**
* 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);
}
如果溢出处于以前的状态，我们可以在这里做得更好一点所有可能的，然后才创建一个大于必要的数组。
We could do a bit better here if we would look before if overflow is at all possible and only then create the array one bigger than necessary.
啊，一个测试： d2.plus（d2）给出 Big [24,691357802,469135780] ，看起来是正确的。
Ah, one test: d2.plus(d2) gives Big[24, 691357802, 469135780], which looks right.
让我们记得回到学校，我们如何在纸上增加更大的数字？
Let's remember back to school, how did we multiply bigger numbers on paper?
123 * 123
----------
369 <== 123 * 3
246 <== 123 * 2
123 <== 123 * 1
--------
15129
所以，我们必须将第一个数字的每个数字[i]乘以第二个数字的每个数字[j]，并将结果的数字[i + j]中的乘积相加（并注意携带）。当然，这里的索引是从右边开始计算的，而不是从左边开始计算的。 （现在我真的希望我使用了小端数字。）
So, we have to multiply each digit[i] of the first number with each digit[j] of the second number, and add the product in digit[i+j] of the result (and pay attention to carry). Of course, here the indexes are counted from right, not from left. (Now i really wish I had used little-endian numbers.)
由于我们两个数字的乘积可以超出范围 int ，我们使用 long 进行乘法。
Since the product of two of our digits can get outside of the range of int, we use long for multiplication.
/**
* 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参数，以便能够更好地在此处编写。）
Now we can see why I declared my addDigits method to take a resultIndex parameter. (And I just changed the last argument to a varargs parameter, to be able to write this here better.)
所以，这里的交叉乘法方法：
So, here the cross-multiplying method:
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（结果，resultIndex + i + j，leftFactor [i]，rightFactor [j]） - 相当清楚，isn'是吗？
I hope I have the index-calculations right. With a little-endian representation, it would have been multiplyDigit(result, resultIndex + i + j, leftFactor[i], rightFactor[j]) - quite clearer, isn't it?
我们的次方法现在只需要分配结果数组，调用 multiplyDigits 并包装结果。
Our times method now has only to allocate the result array, invoke multiplyDigits and wrap the result.
/**
* returns the product {@code this × that}.
*/
public DecimalBigInt times(DecimalBigInt that) {
int[] result = new int[this.digits.length + that.digits.length];
multiplyDigits(result, result.length-1,
this.digits, that.digits);
// cut off leading zero, if any
if(result[0] == 0) {
result = Arrays.copyOfRange(result, 1, result.length);
}
return new DecimalBigInt(result);
}
进行测试时， d2.times（d2）给出 Big [152,415787532,388367501,905199875,19052100] ，这与我的Emacs calc在此计算的相同。
For testing, d2.times(d2) gives Big[152, 415787532, 388367501, 905199875, 19052100], which is the same what my Emacs calc calculates here.
我们希望能够比较两个对象。因此，我们实现 Comparable< DecimalBigInt> 及其compareTo方法。
We want to be able to compare two of our objects. So, we implement Comparable<DecimalBigInt> and its compareTo method.
public int compareTo(DecimalBigInt that) {
如何知道我们的某个数字是否大于另一个？首先，我们比较数组的长度。由于我们注意不要引出任何前导零（我们是吗？），较长的数组应该有更大的数字。
How to know if one of our numbers is bigger than another? First, we compare the length of the arrays. As we took care not to induce any leading zeros (did we?), the longer array should have the bigger number.
if(this.digits.length < that.digits.length) {
return -1;
}
if (that.digits.length < this.digits.length) {
return 1;
}
如果长度相同，我们可以按元素比较。由于我们使用大端（即大端首先），我们从头开始。
If the length are same, we can compare elementwise. Since we use big endian (i.e. the big end comes first), we start at the beginning.
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 。
If everything was same, obviously our numbers are identical, and we can return 0.
return 0;
}
等于 + hashCode（）
每个好的不可变类都应该实现 equals（）和 hashCode（）以合适的（兼容的）方式。
equals + hashCode()
Every good immutable class should implement equals() and hashCode() in a suitable (and compatible) way.
对于我们的 hashCode（），我们简单地将数字相加，将它们乘以小素数以确保数字切换不会产生相同的哈希码：
For our hashCode(), we simply sum up the digits, multiplying them with a small prime to make sure digit-switching does not result in same hash code:
/**
* calculates a hashCode for this object.
*/
public int hashCode() {
int hash = 0;
for(int digit : digits) {
hash = hash * 13 + digit;
}
return hash;
}
在中等于（）方法我们只需委托compareTo方法，而不是再次实现相同的算法：
In the equals() method we simply can delegate to the compareTo method, instead of implementing the same algorithm again:
/**
* 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问题提示时，我写了我的回答是关于如何从我们可以（或想要）计算的任意（位置）数字系统转换。 （在那里的示例中，我从三进制转换为十进制，而问题是关于十进制到二进制。）
Converting from arbitrary-radix representations
Prompted by the next question of frodosamoa, I wrote my answer about how to convert from arbitrary (positional) number systems in the one in which we can (or want to) calculate. (In the example there, I converted from trinary to decimal, while the question was about decimal to binary.)
这里我们要从任意数字系统转换（好吧） ，基数在2到36之间，所以我们可以使用 Character.digit（） 将单个数字转换为整数）到我们的系统，基数 BASE （= 1.000.000.000，但这在这里并不重要）。
Here we want to convert from an arbitrary number system (okay, with radix between 2 and 36, so we can use Character.digit() to convert single digits to ints) to our system with radix BASE (= 1.000.000.000, but this is not really important here).
基本上我们使用 Horner scheme 计算多项式的值，其中数字为基数给定点处的系数。
Basically we use Horner scheme to calculate the value of polynomial with the digits as coefficients at the point given by the radix.
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到
DecimalBigInt类型的自动装箱。）
Since our input strings are big-endian, we don't have to count down, but can use a simple enhanced for loop. (It looks more ugly in Java, since we have no operator overloading, and no autoboxing from int to our DecimalBigInt type.)
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;
}
在我的实际实现我添加了一些错误检查（和异常抛出）以确保我们确实有一个有效的数字，当然还有文档注释。
In my actual implementation I added some error checking (and exception throwing) to ensure that we really have a valid number, and of course a documentation comment.
将转换为任意位置系统更复杂，因为它涉及余数和除法（由我们还没有实现的任意基数 - 所以现在不行。当我对如何进行分工有一个好主意时，它就会完成。 （我们这里只需要用小（一位数）数字来划分，这可能比一般划分更容易。）
Converting to an arbitrary positional system is more complicated, as it involves remainder and division (by the arbitrary radix), which we did not implement yet - so not for now. It will be done when I have a good idea on how to do division. (We need only division by small (one-digit) numbers here, which may be easier than a general division.)
在学校，我学习了长期分工。下面是一个小（一位数）除数的例子，我们在德国使用的符号（带有关于背景计算的注释，我们通常不会写），十进制：
In school, I learned long division. Here is an example for a small (one-digit) divisor, in the notation we use here in Germany (with annotations about the background calculations, which we normally would not write), in decimal system:
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）
如果我们有本机余数运算，则减去它们。然后它看起来像这样的
（当然，我们这里不需要编写操作）：
Of couse, we don't need to calculate these products (0, 12, 0, 30, 42) and subtract them if we have a native remainder operation. Then it looks like this (of course, we here would not need to write the operations):
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.
这看起来很像短片，如果我们用其他格式写的话。
This already looks quite like short division, if we write it in another format.
我们可以观察（和证明）以下内容：
We can observe (and prove) the following:
如果我们有一个两位数的x，第一个数字小于我们的除数d，那么 x / d 是一位数字， x％d 也是一位数字，小于d。这与归纳一起表明我们只需要用除数除以（两位数）两位数的数字。
If we have a two-digit number x with first digit smaller than our divisor d, than x / d is a one-digit number, and x % d is also a one-digit number, smaller than d. This, together with induction, shows that we only ever need to divide (with remainder) two-digit numbers by our divisor.
用基数BASE回到我们的大数字：所有两位数字都可以表示为Java long ，并且我们有原生 / 和％。
Coming back to our big numbers with radix BASE: all two-digit numbers are representable as a Java long, and there we have native / and %.
/**
* 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 。
We will now call this method in a loop, always feeding the result from the previous call back as 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，余数。
This method still returns an int, the remainder.
现在我们想要一个返回DecimalBigInt的公共方法，所以我们创建一个。它的任务是检查参数，为工作方法创建数组，丢弃余数，并从结果中创建DecimalBigInt。 （构造函数删除可能存在的前导零。）
Now we want to have a public method returning a DecimalBigInt, so we create one. It has the task to check the arguments, create an array for the working method, discard the remainder, and create a DecimalBigInt from the result. (The constructor removes a leading zero which may be there.)
/**
* 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);
}
我们也有一个类似的方法，它返回剩余的：
We also have a similar method, which returns the remainder instead:
/**
* 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);
}
这些方法可以这样调用：
These methods can be invoked like this:
DecimalBigInt d3_by_100 = d3.divideBy(100);
System.out.println("d3/100 = " + d3_by_100);
System.out.println("d3%100 = " + d3.modulo(100));
转换为任意基数
现在我们有基本的转换为任意基数。当然，不是真的任意，只允许小于 BASE 的基数，但这不应该是一个太大的问题。
Conversion to arbitrary radix
Now we have the basics to convert to an arbitrary radix. Of course, not really arbitrary, only radixes smaller than BASE are allowed, but this should not be a too big problem.
正如在关于转换数字的另一个答案中已经回答的那样，我们必须做除法，余数，乘法，加法。乘法 - 加法部分实际上只是将各个数字组合在一起，所以我们可以将它替换为简单的数组访问。
As already answered in another answer about converting numbers, we have to do "division, remainder, multiply, add. The "multiply-add" part is in fact only putting together the individual digits, so we can replace it by a simple array-access.
因为我们总是需要商和余数，所以我们不会使用公共方法 modulo 和 divideBy ，而是反复调用 divideDigits 方法。
As we always need both the quotient and the remainder, we won't use the public methods modulo and divideBy, but instead repeatedly call the divideDigits method.
/**
* 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的特殊情况。
First, a special-case handling for 0.
// zero has no digits.
if(digits.length == 0)
return new int[0];
然后，我们为结果数字创建一个数组（足够长），
和一些其他变量。
Then, we create an array for the result digits (long enough), and some other 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 is the number of digits (excluding leading zeroes) in the last quotient. If this is 0, we are done.
quotLen is the number of digits (excluding leading zeroes) in the last quotient. If this is 0, we are done.
while(quotLen > 0) {
A new array for the next quotient.
A new array for the next quotient.
int[] quot = new int[quotLen];
The quotient-and-remainder operation. The quotient is now in quot,
the remainder in rem.
The quotient-and-remainder operation. The quotient is now in quot,
the remainder in rem.
int rem = divideDigits(quot, 0,
current, current.length - quotLen,
radix);
We put the remainder in the output array (filling it from the last digit).
We put the remainder in the output array (filling it from the last digit).
rDigits[rIndex] = rem;
rIndex --;
Then we swap the arrays for the next round.
Then we swap the arrays for the next round.
current = quot;
If there are leading zeros in the quotient (there will be at most one, since
radix is smaller than BASE), we shrink the quotient size by one. The next array
will be smaller.
If there are leading zeros in the quotient (there will be at most one, since radix is smaller than BASE), we shrink the quotient size by one. The next array will be smaller.
if(current[0] == 0) {
// omit leading zeros in next round.
quotLen--;
}
}
After the loop there may be leading zeros in the rDigits array, and we cut them off.
After the loop there may be leading zeros in the rDigits array, and we cut them off.
// cut of leading zeros in rDigits:
while(rIndex < 0 || rDigits[rIndex] == 0) {
rIndex++;
}
return Arrays.copyOfRange(rDigits, rIndex, rDigits.length);
}
That’s it. It looks a bit complicated, though. Here is an example of how to use it:
That's it. It looks a bit complicated, though. Here is an example of how to use it:
System.out.println("d4 in base 11: " +
Arrays.toString(d4.convertTo(11)));
System.out.println("d5 in base 7: " +
Arrays.toString(d5.convertTo(7)));
These print [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0] and [1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0], just the same numbers as we parsed before (from a String, though).
These print [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0] and [1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0], just the same numbers as we parsed before (from a String, though).
Based on this we can also format as a string:
Based on this we can also format as a 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();
}
这篇关于如何在不使用java.math.BigInteger的情况下在Java中处理非常大的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
