This is java. You are creating a BigInt class. It can hold one number that is ve
ID: 643723 • Letter: T
Question
This is java.
You are creating a BigInt class. It can hold one number that is very large. The first part of the assignment is to create a constructor that can take a String and convert it to your internal representation of a BigInt. Use an array or ArrayList to hold the integer. Below is a Demo program that your BigInt class should be able to handle. Keep in mind that the number could be negative. Also keep in mind you will need to add and subtract Multiply Devide and modulus BigInt values. Below the Demo are several lines of code dealing with methods of the String class. You must be able to work with String methods to both take the string from the constructor and turn it into the integers in the ArrayList and then turn the ArrayList of integers to a string in the toString() method. The toString() method is called automatically when a BigInt instance is put in a System.out.println() as demonstrated by the next line of code. System.out.println("new BigInt value is " B1); Here the string "new BigInt value is " is concatenated with the BigInt B1. The System class knows to invoke the BigInt toString()method. The following code will do the same thing: System.out.println("new BigInt value is " B1.toString()); Below the string methods is the Bottle class. Study it carefully. The Bottle class encapsulates a Bottle. The private instance variable pennies holds the contents of the bottle. It is a bottle of pennies. There are methods of the Bottle class that do operations on Bottle values. Study each method. The add method: public Bottle add(Bottle J). it should run the following demo.
import java.util.Scanner; public class BigInt_Add_Sub_Mul_Div_Mod_Demo {
public static void main(String[] args)
{
BigInt b1;
BigInt b2; BigInt b3;
b1 = new BigInt("-0");
b2 = new BigInt("+0");
b3 = b1.add(b2);
System.out.println("1) sum b3 is " + b1 +" + " + b2 + " = " + b3);
b3 = b1.subtract(b2);
System.out.println("difference b3 is " + b1 +" - " + b2 + " = " + b3);
b3 = b1.multiply(b2);
System.out.println("product b3 is " + b1 +" * " + b2 + " = " + b3);
b1 = new BigInt("1");
b2 = new BigInt("1");
b3 = b1.add(b2);
System.out.println(" 2) sum b3 is " + b1 +" + " + b2 + " = " + b3);
b3 = b1.subtract(b2);
System.out.println("difference b3 is " + b1 +" - " + b2 + " = " + b3);
b3 = b1.multiply(b2);
System.out.println("product b3 is " + b1 +" * " + b2 + " = " + b3);
b3 = b1.divideBy(b2);
System.out.println("quotient b3 is " + b1 +" / " + b2 + " = " + b3);
b3 = b1.modulus(b2);
System.out.println("modulus b3 is " + b1 +" mod " + b2 + " = " + b3);
b1 = new BigInt("-1");
b2 = new BigInt("1");
b3 = b1.add(b2);
System.out.println(" 3) sum b3 is " + b1 +" + " + b2 + " = " + b3);
b3 = b1.subtract(b2);
System.out.println("difference b3 is " + b1 +" - " + b2 + " = " + b3);
b3 = b1.multiply(b2);
System.out.println("product b3 is " + b1 +" * " + b2 + " = " + b3);
b3 = b1.divideBy(b2);
System.out.println("quotient b3 is " + b1 +" / " + b2 + " = " + b3);
b3 = b1.modulus(b2);
System.out.println("modulus b3 is " + b1 +" mod " + b2 + " = " + b3);
b1 = new BigInt("1"); b2 = new BigInt("-1"); b3 = b1.add(b2);
System.out.println(" 4) sum b3 is " + b1 +" + " + b2 + " = " + b3);
b3 = b1.subtract(b2); System.out.println("difference b3 is " + b1 +" - " + b2 + " = " + b3);
b3 = b1.multiply(b2); System.out.println("product b3 is " + b1 +" * " + b2 + " = " + b3);
b3 = b1.divideBy(b2); System.out.println("quotient b3 is " + b1 +" / " + b2 + " = " + b3);
b3 = b1.modulus(b2); System.out.println("modulus b3 is " + b1 +" mod " + b2 + " = " + b3);
b1 = new BigInt("-1");
b2 = new BigInt("-1");
b3 = b1.add(b2);
System.out.println(" 5) sum b3 is " + b1 +" + " + b2 + " = " + b3);
b3 = b1.subtract(b2);
System.out.println("difference b3 is " + b1 +" - " + b2 + " = " + b3);
b3 = b1.multiply(b2);
System.out.println("product b3 is " + b1 +" * " + b2 + " = " + b3);
b3 = b1.divideBy(b2);
System.out.println("quotient b3 is " + b1 +" / " + b2 + " = " + b3);
b3 = b1.modulus(b2);
System.out.println("modulus b3 is " + b1 +" mod " + b2 + " = " + b3);
b1 = new BigInt("+1");
b2 = new BigInt("+1");
b3 = b1.add(b2);
System.out.println(" 6) sum b3 is " + b1 +" + " + b2 + " = " + b3);
b3 = b1.subtract(b2);
System.out.println("difference b3 is " + b1 +" - " + b2 + " = " + b3);
b3 = b1.multiply(b2);
System.out.println("product b3 is " + b1 +" * " + b2 + " = " + b3);
b3 = b1.divideBy(b2);
System.out.println("quotient b3 is " + b1 +" / " + b2 + " = " + b3);
b3 = b1.modulus(b2);
System.out.println("modulus b3 is " + b1 +" mod " + b2 + " = " + b3);
b1 = new BigInt("-100"); b2 = new BigInt("100");
b3 = b1.add(b2); System.out.println(" 7) sum b3 is " + b1 +" + " + b2 + " = " + b3);
b3 = b1.subtract(b2);
System.out.println("difference b3 is " + b1 +" - " + b2 + " = " + b3);
b3 = b1.multiply(b2);
System.out.println("product b3 is " + b1 +" * " + b2 + " = " + b3);
b3 = b1.divideBy(b2);
System.out.println("quotient b3 is " + b1 +" / " + b2 + " = " + b3);
b3 = b1.modulus(b2);
System.out.println("modulus b3 is " + b1 +" mod " + b2 + " = " + b3);
b1 = new BigInt("100");
b2 = new BigInt("-100");
b3 = b1.add(b2);
System.out.println(" 8) sum b3 is " + b1 +" + " + b2 + " = " + b3);
b3 = b1.subtract(b2);
System.out.println("difference b3 is " + b1 +" - " + b2 + " = " + b3);
b3 = b1.multiply(b2);
System.out.println("product b3 is " + b1 +" * " + b2 + " = " + b3);
b3 = b1.divideBy(b2);
System.out.println("quotient b3 is " + b1 +" / " + b2 + " = " + b3);
b3 = b1.modulus(b2);
System.out.println("modulus b3 is " + b1 +" mod " + b2 + " = " + b3);
b1 = new BigInt("-100");
b2 = new BigInt("-100");
b3 = b1.add(b2);
System.out.println(" 9) sum b3 is " + b1 +" + " + b2 + " = " + b3);
b3 = b1.subtract(b2);
System.out.println("difference b3 is " + b1 +" - " + b2 + " = " + b3);
b3 = b1.multiply(b2);
System.out.println("product b3 is " + b1 +" * " + b2 + " = " + b3);
b3 = b1.divideBy(b2);
System.out.println("quotient b3 is " + b1 +" / " + b2 + " = " + b3);
b3 = b1.modulus(b2);
System.out.println("modulus b3 is " + b1 +" mod " + b2 + " = " + b3);
b1 = new BigInt("100");
b2 = new BigInt("100");
b3 = b1.add(b2);
System.out.println(" 10) sum b3 is " + b1 +" + " + b2 + " = " + b3);
b3 = b1.subtract(b2);
System.out.println("difference b3 is " + b1 +" - " + b2 + " = " + b3);
b3 = b1.multiply(b2);
System.out.println("product b3 is " + b1 +" * " + b2 + " = " + b3);
b3 = b1.divideBy(b2);
System.out.println("quotient b3 is " + b1 +" / " + b2 + " = " + b3);
b3 = b1.modulus(b2);
System.out.println("modulus b3 is " + b1 +" mod " + b2 + " = " + b3);
b1 = new BigInt("200"); b2 = new BigInt("-0"); b3 = b1.add(b2);
System.out.println(" 11) sum b3 is " + b1 +" + " + b2 + " = " + b3);
b3 = b1.subtract(b2);
System.out.println("difference b3 is " + b1 +" - " + b2 + " = " + b3);
b3 = b1.multiply(b2);
System.out.println("product b3 is " + b1 +" * " + b2 + " = " + b3);
//b3 = b1.divideBy(b2);
//System.out.println("quotient b3 is " + b1 +" / " + b2 + " = " + b3);
//b3 = b1.modulus(b2); //System.out.println("modulus b3 is " + b1 +" mod " + b2 + " = " + b3);
b1 = new BigInt("-200");
b2 = new BigInt("-0");
b3 = b1.add(b2);
System.out.println(" 12) sum b3 is " + b1 +" + " + b2 + " = " + b3);
b3 = b1.subtract(b2);
System.out.println("difference b3 is " + b1 +" - " + b2 + " = " + b3);
b3 = b1.multiply(b2);
System.out.println("product b3 is " + b1 +" * " + b2 + " = " + b3);
//b3 = b1.divideBy(b2);
//System.out.println("quotient b3 is " + b1 +" / " + b2 + " = " + b3);
//b3 = b1.modulus(b2);
//System.out.println("modulus b3 is " + b1 +" mod " + b2 + " = " + b3);
b1 = new BigInt("-0");
b2 = new BigInt("200");
b3 = b1.add(b2);
System.out.println(" 13) sum b3 is " + b1 +" + " + b2 + " = " + b3);
b3 = b1.subtract(b2);
System.out.println("difference b3 is " + b1 +" - " + b2 + " = " + b3);
b3 = b1.multiply(b2); System.out.println("product b3 is " + b1 +" * " + b2 + " = " + b3);
b3 = b1.divideBy(b2);
System.out.println("quotient b3 is " + b1 +" / " + b2 + " = " + b3);
b3 = b1.modulus(b2);
System.out.println("modulus b3 is " + b1 +" mod " + b2 + " = " + b3);
b1 = new BigInt("-0");
b2 = new BigInt("-200");
b3 = b1.add(b2);
System.out.println(" 14) sum b3 is " + b1 +" + " + b2 + " = " + b3);
b3 = b1.subtract(b2);
System.out.println("difference b3 is " + b1 +" - " + b2 + " = " + b3);
b3 = b1.multiply(b2);
System.out.println("product b3 is " + b1 +" * " + b2 + " = " + b3);
b3 = b1.divideBy(b2);
System.out.println("quotient b3 is " + b1 +" / " + b2 + " = " + b3);
b3 = b1.modulus(b2);
System.out.println("modulus b3 is " + b1 +" mod " + b2 + " = " + b3);
b1 = new BigInt("37");
b2 = new BigInt("26");
b3 = b1.add(b2);
System.out.println(" 15) sum b3 is " + b1 +" + " + b2 + " = " + b3);
b3 = b1.subtract(b2);
System.out.println("difference b3 is " + b1 +" - " + b2 + " = " + b3);
b3 = b1.multiply(b2);
System.out.println("product b3 is " + b1 +" * " + b2 + " = " + b3);
b3 = b1.divideBy(b2);
System.out.println("quotient b3 is " + b1 +" / " + b2 + " = " + b3);
b3 = b1.modulus(b2);
System.out.println("modulus b3 is " + b1 +" mod " + b2 + " = " + b3);
b1 = new BigInt("-200111111111111111199999999");
b2 = new BigInt("3333333333333388888888888888888888555555555555555555555555");
b3 = b1.add(b2);
System.out.println(" 19) sum b3 is " + b1 +" + " + b2 + " = " + b3);
b3 = b1.subtract(b2);
System.out.println("difference b3 is " + b1 +" - " + b2 + " = " + b3);
b3 = b1.multiply(b2);
System.out.println("product b3 is " + b1 +" * " + b2 + " = " + b3);
b3 = b1.divideBy(b2);
System.out.println("quotient b3 is " + b1 +" / " + b2 + " = " + b3);
b3 = b1.modulus(b2);
System.out.println("modulus b3 is " + b1 +" mod " + b2 + " = " + b3);
b1 = new BigInt("66666666666666666666677777777777777777777711111111111111111200");
b2 = new BigInt("-3333333333333333333344444444444");
b3 = b1.add(b2);
System.out.println(" 20) sum b3 is " + b1 +" + " + b2 + " = " + b3);
b3 = b1.subtract(b2);
System.out.println("difference b3 is " + b1 +" - " + b2 + " = " + b3);
b3 = b1.multiply(b2);
System.out.println("product b3 is " + b1 +" * " + b2 + " = " + b3);
b3 = b1.divideBy(b2);
System.out.println("quotient b3 is " + b1 +" / " + b2 + " = " + b3);
b3 = b1.modulus(b2); System.out.println("modulus b3 is " + b1 +" mod " + b2 + " = " + b3);
b1 = new BigInt("-66666666666666666666677777777777777777777711111111111111111200");
b2 = new BigInt("-333333");
b3 = b1.add(b2);
System.out.println(" 21) sum b3 is " + b1 +" + " + b2 + " = " + b3);
b3 = b1.subtract(b2);
System.out.println("difference b3 is " + b1 +" - " + b2 + " = " + b3);
b3 = b1.multiply(b2);
System.out.println("product b3 is " + b1 +" * " + b2 + " = " + b3);
b3 = b1.divideBy(b2);
System.out.println("quotient b3 is " + b1 +" / " + b2 + " = " + b3);
b3 = b1.modulus(b2);
System.out.println("modulus b3 is " + b1 +" mod " + b2 + " = " + b3);
b1 = new BigInt("6666666");
b2 = new BigInt("3333333333333333333344444444444444444444455555555555555550");
b3 = b1.add(b2);
System.out.println(" 22) sum b3 is " + b1 +" + " + b2 + " = " + b3);
b3 = b1.subtract(b2);
System.out.println("difference b3 is " + b1 +" - " + b2 + " = " + b3);
b3 = b1.multiply(b2);
System.out.println("product b3 is " + b1 +" * " + b2 + " = " + b3);
b3 = b1.divideBy(b2);
System.out.println("quotient b3 is " + b1 +" / " + b2 + " = " + b3);
b3 = b1.modulus(b2);
System.out.println("modulus b3 is " + b1 +" mod " + b2 + " = " + b3);
}
}
Explanation / Answer
Creating a simple Big number class in Java
So, what do we need?
First, a representation of the number,
based on the datatypes which Java gives us.
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.
Then the digits-array:
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.)
For testing purposes, we add a constructor which allows initializing from such a int[].
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:
This gives us de.fencing_game.paul.examples.DecimalBigInt@6af62373, not so useful. So, we add a toString() method:
The output is now Big[7, 5, 2, 12345], which is more useful for testing, isn't it?
Second, conversion from decimal format.
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.
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.)
This is the length of the first block of decimal digits, should be between 1 and 9 (inclusive).
We create our array:
Looping through the digits to be created:
Each of our digits is represented by a block of digits in the original number:
(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:
From the array now created we create our DecimalBigInt object:
Let's see if this works:
Output:
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.
Third, conversion to decimal format.
We need to output our individual digits as 9 decimal digits each. For this we can use the Formatterclass, which supports printf-like format strings.
A simple variant would be this:
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.
Addition.
Let's start with addition, as this is simple (and we can use parts of it for the multiplication later).
I want method names that you can read like you would read the formula, thus plus, minus, timesinstead 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:
(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.
The next does the same for a whole array of digits to add:
Now we can implement our plus method:
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.
Multiplication.
Let's remember back to school, how did we multiply bigger numbers on paper?
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.
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:
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.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.