fro*_*moa 62 java math integer biginteger
我怎么去做算术,+ - /*%!,任意大整数而不使用java.math.BigInteger？
例如,factorial为90在Java中返回0.我希望能够解决这个问题.
Paŭ*_*ann 250
我认为程序员应该已经实现了他自己的bignum-library,所以欢迎来到这里.
(当然,稍后你会得到BigInteger更好,并使用它,但这是一个宝贵的学习经验.)
(你可以在github上关注这门课程的源代码.另外,我将这个(有点抛光)重新制作成一个由14部分组成的博客系列.)
那么,我们需要什么？
基于Java给我们的数据类型.
如你所想,十进制转换是最复杂的部分,让我们保持基于十进制的模式.为了提高效率,我们将存储不是真正的十进制数字,而是在base中工作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,因为这是人类想要阅读它的方式.(现在我们专注于非负值 - 稍后我们将为负数添加一个符号位.)
出于测试目的,我们添加了一个允许从这样的int []初始化的构造函数.
/**
* creates a DecimalBigInt based on an array of digits.
* @param digits a list of digits, each between 0 (inclusive)
* and {@link BASE} (exclusive).
* @throws IllegalArgumentException if any digit is out of range.
*/
public DecimalBigInt(int... digits) {
for(int digit : digits) {
if(digit < 0 || BASE <= digit) {
throw new IllegalArgumentException("digit " + digit +
" out of range!");
}
}
this.digits = digits.clone();
}
作为一个额外的好处,这个构造函数也可用于单个int(如果小于BASE),甚至是否int(我们将其解释为0).所以,我们现在可以这样做:
DecimalBigInt d = new DecimalBigInt(7, 5, 2, 12345);
System.out.println(d);
这给了我们de.fencing_game.paul.examples.DecimalBigInt@6af62373,不是那么有用.所以,我们添加一个toString()方法:
/**
* A simple string view for debugging purposes.
* (Will be replaced later with a real decimal conversion.)
*/
public String toString() {
return "Big" + Arrays.toString(digits);
}
输出现在Big[7, 5, 2, 12345],这对测试更有用,不是吗？
我们很幸运:我们的基地(10 ^ 9)是我们想要转换的基础的力量(10).因此,我们总是有相同数字(9)的十进制数字代表一个"我们的格式"数字.(当然,在开头可能会有一些数字更少.)在下面的代码中,decimal是一个十进制数字的字符串.
int decLen = decimal.length();
int bigLen = (decLen-1) / BASE_DECIMAL_DIGITS + 1;
这个奇怪的公式是Java int的写作方式 bigLen = ceil(decLen/BASE_DECIMAL_DIGITS).(我希望它是正确的,我们稍后会测试它.)
int firstSome = decLen - (bigLen-1) * BASE_DECIMAL_DIGITS;
这是第一个十进制数字块的长度,应该在1到9之间(包括1和9).
我们创建我们的数组:
int[] digits = new int[bigLen];
循环遍历要创建的数字:
for(int i = 0; i < bigLen ; i++) {
我们的每个数字都由原始数字中的一个数字块表示:
String block =
decimal.substring(Math.max(firstSome + (i-1)*BASE_DECIMAL_DIGITS, 0),
firstSome + i *BASE_DECIMAL_DIGITS);
(Math.max这里需要第一个较短的块.)我们现在使用通常的Integer解析函数,并将结果放入数组中:
digits[i] = Integer.parseInt(block);
}
从现在创建的数组中,我们创建了DecimalBigInt对象:
return new DecimalBigInt(digits);
让我们看看这是否有效:
DecimalBigInt d2 = DecimalBigInt.valueOf("12345678901234567890");
System.out.println(d2);
输出:
Big[12, 345678901, 234567890]
看起来正确:-)我们应该测试一些其他数字(不同长度).
下一部分将是十进制格式,这应该更容易.
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();
}
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();
}
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.
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);
(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.
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
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.)
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);
}
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]);
}
}
}
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?
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);
}
For testing, d2.times(d2) gives Big[152, 415787532, 388367501, 905199875, 19052100], which is the same what my Emacs calc calculates here.
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;
}
}
If everything was same, obviously our numbers are identical, and we can return 0.
return 0;
}
equals + hashCode()Every good immutable class should implement equals() and hashCode() in a suitable (and compatible) way.
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;
}
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;
}
So, enough for today. Subtraction (and maybe negative numbers) and division are more complicated, so I'm omitting them for now. For calculating the factorial of 90 this should be enough.
Here the factorial function:
/**
* 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;
}
This gives us
fac(90) = 1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000
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.)
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).
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
can be calculated with this loop:
value = 0;
for i = n .. 0
value = value * radix + digit[i]
return value
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.
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:
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.
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;
}
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;
}
This method still returns an int, the remainder.
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));
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.
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!");
}
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.
while(quotLen > 0) {
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.
int rem = divideDigits(quot, 0,
current, current.length - quotLen,
radix);
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.
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(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.
// 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:
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).
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();
}