I think that a programmer had to implement his own bigmoon library once, so I welcome you here.
(Of course, you will later find that BigInteger is better, and use this, but it is a valuable learning experience.)
(You can follow the source code for this course on github . Also, I redid this (slightly polished) into a 14-section blog series .)
Creating a simple class of large numbers in Java
So what do we need?
First, the representation of a number,
based on the data types that Java gives us.
Do you think decimal conversion is the hardest part, let's stay in decimal mode. For efficiency, we will not store real decimal digits, but work in the database 1 000 000 000 = 10^9 < 2^30 . This corresponds to a Java int (up to 2^31 or 2^32 ), and the product of two such digits fits perfectly into Java long .
final static int BASE = 1000000000; final static int BASE_DECIMAL_DIGITS = 9;
Then a set of numbers:
private int[] digits;
Do we save the numbers at the small or large end, i.e. larger parts first or last time? It doesn't really matter, so we make a decision about how people want to read it. (At the moment, we focus on non-negative values ββ- later we will add a signed bit for negative numbers.)
For testing purposes, we add a constructor that allows us to initialize such an int [].
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(); }
As an added bonus, this constructor can also be used for a single int (if less than BASE ) and even for no int (which we will interpret as 0). So now we can do this:
DecimalBigInt d = new DecimalBigInt(7, 5, 2, 12345); System.out.println(d);
This gives us de.fencing_game.paul.examples.DecimalBigInt@6af62373 , which is not so useful. So, we add the toString() method:
public String toString() { return "Big" + Arrays.toString(digits); }
Now the result is Big[7, 5, 2, 12345] , which is more useful for testing, isn't it?
Secondly, conversion from decimal format.
We were lucky: our base (10 ^ 9) is the strength of the base that we want to convert from (10). Thus, we always have the same number (9) of decimal digits representing the βour formatβ digit. (Of course, there may be fewer digits at the beginning.) In the following code, decimal is a string of decimal digits.
int decLen = decimal.length(); int bigLen = (decLen-1) / BASE_DECIMAL_DIGITS + 1;
This weird formula is the Java way of writing bigLen = ceil(decLen/BASE_DECIMAL_DIGITS) . (I hope this is correct, we will check it later.)
int firstSome = decLen - (bigLen-1) * BASE_DECIMAL_DIGITS;
This is the length of the first block of decimal digits, must be between 1 and 9 (inclusive).
We create our array:
int[] digits = new int[bigLen];
Quoting through the numbers you need to create:
for(int i = 0; i < bigLen ; i++) {
Each of our numbers is represented by a block of numbers in the original number:
String block = decimal.substring(Math.max(firstSome + (i-1)*BASE_DECIMAL_DIGITS, 0), firstSome + i *BASE_DECIMAL_DIGITS);
( Math.max needed here for the first shorter block.) Now we use the usual function for parsing integers and put the result in an array:
digits[i] = Integer.parseInt(block); }
From the created array, we create our DecimalBigInt object:
return new DecimalBigInt(digits);
Let's see if this works:
DecimalBigInt d2 = DecimalBigInt.valueOf("12345678901234567890"); System.out.println(d2);
Output:
Big[12, 345678901, 234567890]
It looks right :-) We need to check it with some other numbers (of different lengths) too.
The next part will be decimal formatting, this should be even simpler.
Thirdly, conversion to decimal format.
We need to output our individual digits as 9 decimal digits each. For this, we can use the Formatter class, which supports printf format strings.
A simple option would be the following:
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 round-trip (i.e., passing it to the valueOf method gives an equivalent object), but leading zeros are not very nice to look at (and can create confusion with octal numbers). Therefore, we need to break our beautiful for each cycle and use a different format string for the first and next 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.
We'll start by adding, because it's simple (and we can use parts of it for later multiplication).
public DecimalBigInt plus(DecimalBigInt that) { ... }
I need method names that you can read as if you were reading a formula, so plus , minus , times instead of add , subtract , multiply .
So how does the add-on work? It works in the same way as we learned it at school, for decimal numbers exceeding 9: add the corresponding numbers, and if for some time the result is more than 10 (or BASE in our case), transfer it to the next digit, This can lead to the fact that the resulting number will have one digit more than the original.
First we look at the simple case where both numbers have the same number of digits. Then it just looks 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 transfer any overflows to the next digit. It would be a bit prettier if we decided to use the Little Endian format.)
If both numbers do not have the same number of digits, this is a little complicated.
To make this as simple as possible, we will divide it into several methods:
This method adds one digit to the array element (which may already contain some non-zero value) and stores the result in the array. If there was an overflow, we transfer it to the next digit (which has an index one less than one) using a recursive call. Thus, we guarantee that our numbers will always be in the acceptable range.
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 following does the same for a whole array of numbers:
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:
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);
We could do a little better if we looked earlier, if overflow is even possible, and only then create an array that is larger than necessary.
Ah, one test: d2.plus(d2) gives Big[24, 691357802, 469135780] that looks right.
Multiplication.
Think back to school, how did we multiply large numbers on paper?
123 * 123 ---------- 369 <== 123 * 3 246 <== 123 * 2 123 <== 123 * 1 -------- 15129
So, we must multiply each digit [i] of the first number by each digit [j] of the second number and add the product to the figure [i + j] of the result (and pay attention to the carry). Of course, here the indices are calculated on the right, and not on the left. (Now I'm really sorry that I did not use low-valued numbers.)
Since the product of our two digits may go beyond the int range, we use long to multiply.
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 understand why I announced that my addDigits method accepts the resultIndex parameter. (And I just changed the last argument to the varargs parameter so that it would be better to write this here.)
So here is the cross-multiplication 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]); } } }
Hope I have index calculations. With a little endian view, that would be multiplyDigit(result, resultIndex + i + j, leftFactor[i], rightFactor[j]) - pretty clear, right?
Our times method now only needs to allocate an array of results, call multiplyDigits and wrap the result.
public DecimalBigInt times(DecimalBigInt that) { int[] result = new int[this.digits.length + that.digits.length]; multiplyDigits(result, result.length-1, this.digits, that.digits);
For testing, d2.times(d2) gives Big[152, 415787532, 388367501, 905199875, 19052100] , which is the same as my Emacs calc calculates.
Comparison
We want to be able to compare our two objects. So, we implement Comparable<DecimalBigInt> and the compareTo method.
public int compareTo(DecimalBigInt that) {
How to find out if one of our numbers is larger? First, we compare the length of the arrays. Since we took care not to lead to any leading zeros (we?), A longer array should have a larger number.
if(this.digits.length < that.digits.length) { return -1; } if (that.digits.length < this.digits.length) { return 1; }
If the length is the same, we can compare the item. Since we use a large endian (that is, a large end in the first place), we start from the very 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 the same, it is obvious that our numbers are identical, and we can return 0 .
return 0; }
equals + hashCode()
Every good immutable class should implement equals() and hashCode() appropriate (and compatible) way.
For our hashCode() we simply sum the digits, multiplying them by a small downtime, to make sure that switching the digits does not result in the same hash code:
public int hashCode() { int hash = 0; for(int digit : digits) { hash = hash * 13 + digit; } return hash; }
In the equals() method, we can simply delegate the compareTo method, rather than repeating the same algorithm:
public boolean equals(Object o) { return o instanceof DecimalBigInt && this.compareTo((DecimalBigInt)o) == 0; }
So that's enough for today. Subtraction (and maybe negative numbers) and division are more complicated, so now I omit them. To calculate factorial 90, this should be enough.
Calculation of large factorials:
Here's the factorial function:
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; }
It gives us
fac(90) = 1485715964481761497309522733620825737885569961284688766942216863704985393094065876545992131370884059645617234469978112000000000000000000000
Convert from arbitrary radial representations
In response to the following question frodosamoa, I wrote my answer on how to convert from arbitrary (positional) systems with numbers to one in which we can (or want) to calculate . (In the example there, I converted from three-dimensional to decimal, while the question was about the decimal value for binary.)
Here we want to convert from an arbitrary system of numbers (well, with a radius between 2 and 36, so we can use Character.digit() to convert individual digits to ints) into our system using radix BASE (= 1.000.000.000, but here it is not very important).
We mainly use the Horner scheme to calculate the value of a polynomial with numbers as coefficients at the point given by the base.
sum[i=0..n] digit[i] * radix^i
can be calculated using this loop:
value = 0; for i = n .. 0 value = value * radix + digit[i] return value
Since our input lines are large, we do not need to pay attention, but they can use a simple extended loop. (This 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();
In my actual implementation, I added some error checking (and throwing exception) to make sure that we really have a real number, and, of course, a comment on the documentation.
Transformation in an arbitrary positional system is more complicated, because it includes the remainder and division (into arbitrary radix), which we have not yet implemented - so for now. This will be done when I have a good idea on how to make the separation. (We only need division by small (single-digit) numbers, which can be simpler than general division.)
Small numbers
At school, I learned a long division . Here is an example of a small (one-bit) divisor in the notation that we use here in Germany (with annotations about background calculations that we usually won't write) in the 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.
We should not calculate these products (0, 12, 0, 30, 42) and subtract them if we have a native remainder operation. Then it looks (of course, we will not need to write operations here):
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.
It already looks like a short split if we write it in a different format.
We can observe (and prove) the following:
If we have a two-digit number x with the first digit less than our divisor d, than x / d is a one-digit number, and x % d also a one-digit number less than d. This, together with induction, shows that we need to ever divide (with the remainder) two-digit numbers by our divisor.
Returning to our large numbers with a BASE base: all two-digit numbers are represented as Java long , and there we have native / and % .
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; }
Now we will call this method in a loop, always feeding the result from the previous callback as lastRemainder .
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 int, the remainder.
Now we want the public method to return DecimalBigInt, so we create it. He has the task of checking the arguments, creating an array for the working method, discarding the remainder, and creating DecimalBigInt from the result. (The constructor removes the leading zero, which may be there.)
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 that returns the remainder instead:
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 called as follows:
DecimalBigInt d3_by_100 = d3.divideBy(100); System.out.println("d3/100 = " + d3_by_100); System.out.println("d3%100 = " + d3.modulo(100));
Convert to arbitrary radius
Now we have the basics for converting to an arbitrary radius. Of course, not very arbitrary, only radions smaller than BASE permissible, but this should not be too big a problem.
As already mentioned in another answer on the conversion of numbers, we must do "division, remainder, multiply, add." The multiply-add part is actually only single digits, so we can replace it with simple access to the array.
Since we always need both the private and the rest, we will not use the public modulo and divideBy , but instead call the divideDigits method divideDigits .
public int[] convertTo(int radix) { if(radix <= 1 || BASE <= radix) { throw new IllegalArgumentException("radix " + radix + " out of range!"); }
First, handling a special case for 0.
// zero has no digits. if(digits.length == 0) return new int[0];
Then we create an array for the digits of the result (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 zeros) in the last quotient. If it is 0, we are done.
while(quotLen > 0) {
A new array for the next private.
int[] quot = new int[quotLen];
Operation quotient-and-else. The factor 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 with the last digit).
rDigits[rIndex] = rem; rIndex
Then we replace the arrays for the next round.
current = quot;
If the factor has leading zeros (there will be no more than one, since radix is ββless than BASE), we reduce the size of the factor by one. The next array will be smaller.
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); }
What is 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)));
[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] , , ( String).
:
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(); }