Integer.MAX_VALUE is the maximum value of a Java int: 2147483647. If you want to work with...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Integer.MAX_VALUE is the maximum value of a Java int: 2147483647. If you want to work with even bigger integers, you have the option of using the type long, which has the maximum value of Long.MAX_VALUE=9223372036854775807. But what if this is not enough? What if you are working on something like an astronomy application, and need to keep track of things such as number of stars in the universe? This is of the order of 1023, larger than the maximum long value. For situations like this, you need to be able to work with an integer type that can hold arbitrarily large or small positive and negative values, with any number of digits. There is no built-in type in the language for this, so you need to craft your own. In this assignment, you will do exactly this, by implementing a class called BigInteger, with a representative small set of operations. The trick is to store an integer as a linked list of digits. For example, the integer 754 will be stored as: 4-5->7 Why are the digits stored backward? It's because computations such as adding or multiplying big integers are easier to do if the linked list stores digits in ascending order of positional value. So the least significant digit is in the first node of the linked list, and the most significant digit is in the last node. This is a simple linked list, NOT circular, with a front pointer. The sign (positive or negative), is stored separately in a boolean field in the program. Also, there can never be zeros at the end of the list. Such zeros will be insignificant. So, for instance, 00754 will be stored as: 4 -> 5 -> 7 (NOT 4 -> 5 ->7->0 -> 0) Consequently, the value 0 will be stored as an EMPTY LINKED LIST. The number of digits is 0, and it is not negative. Implementation and Point Assignment: You will see a project called BigInteger with classes BigInteger, DigitNode, and BigTest in package bigint. The DigitNode class implements the linked list node that will hold a digit of a big integer linked list. You need to fill in the implementation of the following methods in the BigInteger class: Method parse add Points 15 35 multiply 30 Note: When parsing an input string as an integer, you can use the Character.isDigit(char) method to tell if a character is a digit. Make sure to read the comments that precede classes, fields, and methods for code-specific details that do not appear here. Observe the following rules while working on BigInteger.java: You may NOT add any import statements to the file. You may NOT add any new classes (you will only be submitting BigInteger.java). You may NOT add any fields to BigInteger class. You may NOT modify the headers of any of the given methods. You may NOT delete any methods. You MAY add helper methods if needed, as long as you make them private. Also, you may NOT make any changes to the DigitNode class (you will ONLY be submitting BigInteger.java). When we test your submission, we will use the exact same version of DigitNode that we shipped to you. WARNING: If your linked list stores digits with most significant digit first, you will get ZERO for the corresponding test case, even if the result is mathematically correct. NO EXCEPTIONS. If your linked list stores insignificant zeros, you will get ZERO for the corresponding test case, even if the result is mathematically correct. NO EXCEPTIONS. If you use an array anywhere in your program, you will get ZERO. NO EXCEPTIONS. If you convert the input to a Java numeric type value (such as int or long) and then do arithmetic on it, instead of working with individual digits stored in a linked list, you will get ZERO. NO EXCEPTIONS. Running/Testing: Use the class BigTest to test your implementation. Carefully read the code in the file to get a good idea of how the BigInteger methods are used. Here's a sample run of BigTest: (p)arse, (a)dd, (m)ultiply, or (q)uit? => p Enter integer => 125 Value = 125 (p)arse, (a)dd, (m)ultiply, or (q)uit? => p Enter integer => -126 Value = -126 (p)arse, (a)dd, (m)ultiply, or (q)uit? => p Enter integer => +1 Value = 1 (p)arse, (a)dd, (m)ultiply, or (q)uit? => p Enter integer => 005 Value = 5 (p)arse, (a)dd, (m)ultiply, or (q)uit? => p Enter integer => 123xy56 Incorrect Format (p)arse, (a)dd, (m)ultiply, or (q)uit? => a Enter first integer => 12 Enter second integer => -13 Sum: -1 (p)arse, (a)dd, (m)ultiply, or (q)uit? => a Enter first integer => 16756726 Enter second integer => 0 Sum: 16756726 (p)arse, (a)dd, (m)ultiply, or (q)uit? => m Enter first integer => 12 Enter second integer => 200 Product: 2400 (p)arse, (a)dd, (m)ultiply, or (q)uit? => m Enter first integer => 178 Enter second integer => -156 Product: -27768 (p)arse, (a)dd, (m)ultiply, or (q)uit? => m Enter first integer => -16 Enter second integer => -05 Product: 80 (p)arse, (a)dd, (m)ultiply, or (q)uit? => q package bigint; /** * This class encapsulates a BigInteger, i.e. a positive or negative integer with any number of digits, which overcomes the computer storage length limitation of an integer. */ public class BigInteger { /** * True if this is a negative integer */ boolean negative; /** *Number of digits in this integer */ int numDigits; /** * Reference to the first node of this integer's linked list representation * NOTE: The linked list stores the Least Significant Digit in the FIRST node. * For instance, the integer 235 would be stored as: * 5 -> 3 --> 2 * Insignificant digits are not stored. So the integer 00235 will be stored as: 532 (No zeros after the last 2) DigitNode front; * * /** * Initializes this integer to a positive number with zero digits, in other * words this is the 0 (zero) valued integer. */ public BigInteger() { negative = false; numDigits = 0; front = null; } /** * * Parses an input integer string into a corresponding BigInteger instance. A correctly formatted integer would have an optional sign as the first * character (no sign means positive), and at least one digit character (including zero). * Examples of correct format, with corresponding values Format Value +0 0 -0 0 123 1023 * * * * * * * * * * * * * * * * E Spaces between digits are not ignored. So "12 345" will not parse as * an integer - the input is incorrectly formatted. * * * * An integer with value will correspond to a null (empty) list see the BigInteger * constructor * * +123 1023 0012 0 -123 -001 +000 12 0 -123 -1 0 * +123 "will still parse Leading and trailing spaces are ignored. So " correctly, as +123, after ignoring leading and trailing spaces in the input string. */ public static BigInteger parse(String integer) throws IllegalArgumentException { * * } /** * Adds the first and second big integers, and returns the result in a NEW BigInteger object. DOES NOT MODIFY the input big integers. @param integer Integer string that is to be parsed @return BigInteger instance that stores the input integer. @throws IllegalArgumentException If input is incorrectly formatted * * NOTE that either or both of the input big integers could be negative. * (which means this method can effectively subtract as well.) * } // following line is a placeholder - compiler needs a return // modify it according to need return null; @param first First big integer @param second Second big integer @return Result big integer public static BigInteger add (BigInteger first, BigInteger second) { // following line is a placeholder compiler needs a return // modify it according to need return null; } ** * Returns the BigInteger obtained by multiplying the first big integer * with the second big integer * * This method DOES NOT MODIFY either of the input big integers * * @param first First big integer E @param second Second big integer @return A new BigInteger which is the product of the first and second big integers * */ public static BigInteger multiply (BigInteger first, BigInteger second) { // following line is a placeholder - compiler needs a return // modify it according to need return null; } /* (non-Javados.) * @see java.lang.Object#toString() */ public String toString() { if (front == null) { return "0"; } } String retval= front.digit + ""; for (DigitNode curr = front.next; curr != null; curr = curr.next) { retval = curr.digit + retval; } if (negative) { retval = } return retval; + retval; package bigint; import java.io.IOException; public class BigTest { static Scanner sc; public static void parse() throws IOException { } } System.out.print("\tEnter integer => "); String integer = sc.nextLine(); try { BigInteger bigInteger = BigInteger.parse(integer); System.out.println("\t\tValue + bigInteger); } catch (IllegalArgumentException e) { System.out.println("\t\tIncorrect Format"); } } public static void add () throws IOException { System.out.print("\tEnter first integer => "); sc.nextLine(); String integer BigInteger firstBigInteger = BigInteger.parse(integer); System.out.print("\tEnter second integer => "); integer = sc.nextLine(); BigInteger second BigInteger = BigInteger.parse(integer); public static void multiply() throws IOException { = 11 BigInteger result = BigInteger.add(firstBigInteger, secondBigInteger); System.out.println("\t\tSum: + result); 11 System.out.print("\tEnter first integer => "); String integer = sc.nextLine(); BigInteger firstBigInteger = BigInteger.parse(integer); System.out.print("\tEnter second integer => "); integer sc.nextLine(); BigInteger secondBigInteger = BigInteger.parse(integer); BigInteger result = BigInteger.multiply(firstBigInteger, secondBigInteger); System.out.println("\t\tProduct: + result); "1 } public static void main(String[] args) throws IOException { } // TODO Auto-generated method stub sc = new Scanner (System.in); } char choice; = while ((choice switch (choice) { } private static char getChoice () { System.out.print("\n(p)arse, (a)dd, (m)ultiply, or (q)uit? => "); String in = sc.nextLine(); char choice; getChoice ()) != 'q') { case 'p' parse(); break; case 'a': add(); break; case 'm' multiply(); break; default: System.out.println("Incorrect choice"); } else { if (in == null || in.length() choice = ''; } return choice; == 0) { choice = in.toLowerCase().charAt(0); package bigint; /** * This class encapsulates a linked list for a digit of a big integer. */ public class DigitNode { /** * The digit */ int digit; /** * Pointer to next digit in the linked list */ DigitNode next; /** * Initializes this digit node with a digit and next pointer * * * @param digit Digit @param next Next pointer DigitNode(int digit, DigitNode next) { this.digit = digit; this.next = next; } /* (non-Javados.) * @see java.lang.Object#toString() public String toString() { return digit + ""; } Integer.MAX_VALUE is the maximum value of a Java int: 2147483647. If you want to work with even bigger integers, you have the option of using the type long, which has the maximum value of Long.MAX_VALUE=9223372036854775807. But what if this is not enough? What if you are working on something like an astronomy application, and need to keep track of things such as number of stars in the universe? This is of the order of 1023, larger than the maximum long value. For situations like this, you need to be able to work with an integer type that can hold arbitrarily large or small positive and negative values, with any number of digits. There is no built-in type in the language for this, so you need to craft your own. In this assignment, you will do exactly this, by implementing a class called BigInteger, with a representative small set of operations. The trick is to store an integer as a linked list of digits. For example, the integer 754 will be stored as: 4-5->7 Why are the digits stored backward? It's because computations such as adding or multiplying big integers are easier to do if the linked list stores digits in ascending order of positional value. So the least significant digit is in the first node of the linked list, and the most significant digit is in the last node. This is a simple linked list, NOT circular, with a front pointer. The sign (positive or negative), is stored separately in a boolean field in the program. Also, there can never be zeros at the end of the list. Such zeros will be insignificant. So, for instance, 00754 will be stored as: 4 -> 5 -> 7 (NOT 4 -> 5 ->7->0 -> 0) Consequently, the value 0 will be stored as an EMPTY LINKED LIST. The number of digits is 0, and it is not negative. Implementation and Point Assignment: You will see a project called BigInteger with classes BigInteger, DigitNode, and BigTest in package bigint. The DigitNode class implements the linked list node that will hold a digit of a big integer linked list. You need to fill in the implementation of the following methods in the BigInteger class: Method parse add Points 15 35 multiply 30 Note: When parsing an input string as an integer, you can use the Character.isDigit(char) method to tell if a character is a digit. Make sure to read the comments that precede classes, fields, and methods for code-specific details that do not appear here. Observe the following rules while working on BigInteger.java: You may NOT add any import statements to the file. You may NOT add any new classes (you will only be submitting BigInteger.java). You may NOT add any fields to BigInteger class. You may NOT modify the headers of any of the given methods. You may NOT delete any methods. You MAY add helper methods if needed, as long as you make them private. Also, you may NOT make any changes to the DigitNode class (you will ONLY be submitting BigInteger.java). When we test your submission, we will use the exact same version of DigitNode that we shipped to you. WARNING: If your linked list stores digits with most significant digit first, you will get ZERO for the corresponding test case, even if the result is mathematically correct. NO EXCEPTIONS. If your linked list stores insignificant zeros, you will get ZERO for the corresponding test case, even if the result is mathematically correct. NO EXCEPTIONS. If you use an array anywhere in your program, you will get ZERO. NO EXCEPTIONS. If you convert the input to a Java numeric type value (such as int or long) and then do arithmetic on it, instead of working with individual digits stored in a linked list, you will get ZERO. NO EXCEPTIONS. Running/Testing: Use the class BigTest to test your implementation. Carefully read the code in the file to get a good idea of how the BigInteger methods are used. Here's a sample run of BigTest: (p)arse, (a)dd, (m)ultiply, or (q)uit? => p Enter integer => 125 Value = 125 (p)arse, (a)dd, (m)ultiply, or (q)uit? => p Enter integer => -126 Value = -126 (p)arse, (a)dd, (m)ultiply, or (q)uit? => p Enter integer => +1 Value = 1 (p)arse, (a)dd, (m)ultiply, or (q)uit? => p Enter integer => 005 Value = 5 (p)arse, (a)dd, (m)ultiply, or (q)uit? => p Enter integer => 123xy56 Incorrect Format (p)arse, (a)dd, (m)ultiply, or (q)uit? => a Enter first integer => 12 Enter second integer => -13 Sum: -1 (p)arse, (a)dd, (m)ultiply, or (q)uit? => a Enter first integer => 16756726 Enter second integer => 0 Sum: 16756726 (p)arse, (a)dd, (m)ultiply, or (q)uit? => m Enter first integer => 12 Enter second integer => 200 Product: 2400 (p)arse, (a)dd, (m)ultiply, or (q)uit? => m Enter first integer => 178 Enter second integer => -156 Product: -27768 (p)arse, (a)dd, (m)ultiply, or (q)uit? => m Enter first integer => -16 Enter second integer => -05 Product: 80 (p)arse, (a)dd, (m)ultiply, or (q)uit? => q package bigint; /** * This class encapsulates a BigInteger, i.e. a positive or negative integer with any number of digits, which overcomes the computer storage length limitation of an integer. */ public class BigInteger { /** * True if this is a negative integer */ boolean negative; /** *Number of digits in this integer */ int numDigits; /** * Reference to the first node of this integer's linked list representation * NOTE: The linked list stores the Least Significant Digit in the FIRST node. * For instance, the integer 235 would be stored as: * 5 -> 3 --> 2 * Insignificant digits are not stored. So the integer 00235 will be stored as: 532 (No zeros after the last 2) DigitNode front; * * /** * Initializes this integer to a positive number with zero digits, in other * words this is the 0 (zero) valued integer. */ public BigInteger() { negative = false; numDigits = 0; front = null; } /** * * Parses an input integer string into a corresponding BigInteger instance. A correctly formatted integer would have an optional sign as the first * character (no sign means positive), and at least one digit character (including zero). * Examples of correct format, with corresponding values Format Value +0 0 -0 0 123 1023 * * * * * * * * * * * * * * * * E Spaces between digits are not ignored. So "12 345" will not parse as * an integer - the input is incorrectly formatted. * * * * An integer with value will correspond to a null (empty) list see the BigInteger * constructor * * +123 1023 0012 0 -123 -001 +000 12 0 -123 -1 0 * +123 "will still parse Leading and trailing spaces are ignored. So " correctly, as +123, after ignoring leading and trailing spaces in the input string. */ public static BigInteger parse(String integer) throws IllegalArgumentException { * * } /** * Adds the first and second big integers, and returns the result in a NEW BigInteger object. DOES NOT MODIFY the input big integers. @param integer Integer string that is to be parsed @return BigInteger instance that stores the input integer. @throws IllegalArgumentException If input is incorrectly formatted * * NOTE that either or both of the input big integers could be negative. * (which means this method can effectively subtract as well.) * } // following line is a placeholder - compiler needs a return // modify it according to need return null; @param first First big integer @param second Second big integer @return Result big integer public static BigInteger add (BigInteger first, BigInteger second) { // following line is a placeholder compiler needs a return // modify it according to need return null; } ** * Returns the BigInteger obtained by multiplying the first big integer * with the second big integer * * This method DOES NOT MODIFY either of the input big integers * * @param first First big integer E @param second Second big integer @return A new BigInteger which is the product of the first and second big integers * */ public static BigInteger multiply (BigInteger first, BigInteger second) { // following line is a placeholder - compiler needs a return // modify it according to need return null; } /* (non-Javados.) * @see java.lang.Object#toString() */ public String toString() { if (front == null) { return "0"; } } String retval= front.digit + ""; for (DigitNode curr = front.next; curr != null; curr = curr.next) { retval = curr.digit + retval; } if (negative) { retval = } return retval; + retval; package bigint; import java.io.IOException; public class BigTest { static Scanner sc; public static void parse() throws IOException { } } System.out.print("\tEnter integer => "); String integer = sc.nextLine(); try { BigInteger bigInteger = BigInteger.parse(integer); System.out.println("\t\tValue + bigInteger); } catch (IllegalArgumentException e) { System.out.println("\t\tIncorrect Format"); } } public static void add () throws IOException { System.out.print("\tEnter first integer => "); sc.nextLine(); String integer BigInteger firstBigInteger = BigInteger.parse(integer); System.out.print("\tEnter second integer => "); integer = sc.nextLine(); BigInteger second BigInteger = BigInteger.parse(integer); public static void multiply() throws IOException { = 11 BigInteger result = BigInteger.add(firstBigInteger, secondBigInteger); System.out.println("\t\tSum: + result); 11 System.out.print("\tEnter first integer => "); String integer = sc.nextLine(); BigInteger firstBigInteger = BigInteger.parse(integer); System.out.print("\tEnter second integer => "); integer sc.nextLine(); BigInteger secondBigInteger = BigInteger.parse(integer); BigInteger result = BigInteger.multiply(firstBigInteger, secondBigInteger); System.out.println("\t\tProduct: + result); "1 } public static void main(String[] args) throws IOException { } // TODO Auto-generated method stub sc = new Scanner (System.in); } char choice; = while ((choice switch (choice) { } private static char getChoice () { System.out.print("\n(p)arse, (a)dd, (m)ultiply, or (q)uit? => "); String in = sc.nextLine(); char choice; getChoice ()) != 'q') { case 'p' parse(); break; case 'a': add(); break; case 'm' multiply(); break; default: System.out.println("Incorrect choice"); } else { if (in == null || in.length() choice = ''; } return choice; == 0) { choice = in.toLowerCase().charAt(0); package bigint; /** * This class encapsulates a linked list for a digit of a big integer. */ public class DigitNode { /** * The digit */ int digit; /** * Pointer to next digit in the linked list */ DigitNode next; /** * Initializes this digit node with a digit and next pointer * * * @param digit Digit @param next Next pointer DigitNode(int digit, DigitNode next) { this.digit = digit; this.next = next; } /* (non-Javados.) * @see java.lang.Object#toString() public String toString() { return digit + ""; }
Expert Answer:
Answer rating: 100% (QA)
package bigint public class BigInteger boolean negative int numDigits DigitNode front public BigInte... View the full answer
Related Book For
Customer Service Career Success Through Customer Loyalty
ISBN: 978-0133056259
6th edition
Authors: Paul R. Timm
Posted Date:
Students also viewed these programming questions
-
You need to work really .............. if you want to be a success.
-
A quantitative definition of solubility is the maximum number of grams of a solute that will dissolve in a given volume of water at a particular temperature. Describe an experiment that would enable...
-
If you want to limit the maximum shortterm borIn 1859, 24 wild rabbits were released at barwon park in southern victoiria,rowing to $500, how much excess cash must you carry
-
Question 3: Assume that Narine Inc. is considering leasing a car from Proctor Inc. for a period of four years. The fair value of the car today is $36,000. The current market interest rate for...
-
In 2011, KZF Inc. purchased stock as follows: (a) Acquired 2,000 shares of Gallery Arts Corp. common stock (par value $20) in exchange for 1,200 shares of KZF Inc. preferred stock (par value $30)....
-
Now suppose that Rowe has an argument with her husband and wants to withdraw from being a member of David-son Masonry is the term for such a withdrawal, and what effect would it have on the LLC?
-
The 2005 comparative balance sheet and income statement of Get Wired, Inc., follow on the next page. Get Wired, Inc., had no noncash investing and financing transactions during 2005. During the year,...
-
Explain why such forecasting devices as moving averages, weighted moving averages, and exponential smoothing are not well suited for data series that have trends.
-
At December 31, 2021, House Co. reported the following information on its balance sheet. Accounts receivable $960,000 Less: Allowance for doubtful accounts 80,000 During 2022, the company had the...
-
Sustainable Industries manufactures cardboard containers (boxes) made from recycled paper products. The company operates two divisions, paper recycling and box manufacturing, as decentralized...
-
Statement of financial position/Balance sheet structure Level of difficulty: Moderate Chugoku Electric Power Company, Inc., was established in 1951 as one of ten electric power companies in Japan. It...
-
The demand for Woobles is unit elastic. When Woobles are priced at $20.00, 10 units are sold. If the price is increased to $40, how many units of Woobles will be sold? Show your work. A 17% decrease...
-
Among the factors believed to drive success are budget (expressing both the cost of the novel and the writer's fee), genre (romantic vs. non-romantic), bookstore classification ratings (general (G)...
-
Find the total monthly payment, including taxes and insurance. Mortgage Interest Rate Term of Loan Annual Taxes Annual Insurance $79,500 4% 25 years $674 $228
-
A sun-like star is barely visible to naked-eye observers on earth when it is a distance of 7.0 light years, or 6.610 16 m, away. The sun emits a power of 3.810 26 W. Part A Using this information, at...
-
Social Media Marketing for Expansion A guest speaker at a small business development conference has a main audience of business owners who want to incorporate social media marketing into their...
-
10 A is a cash method taxpayer. A owns real estate and paid a real estate tax bill of $7,200 covering the period from January 1, 2022 to December 31, 2022. A later sells the property on April 1,...
-
The graph of an equation is given. (a) Find the intercepts. (b) Indicate whether the graph is symmetric with respect to the x-axis, the y-axis, or the origin. -3 6 -6 3 x
-
Let's go back to the ongoing case you selected. This will be either your current employer, a specific organization you want to work in, or one of the two hypothetical organizations described in...
-
Let's consider the flip side of good listening for a moment. How can we make it easier for other people to listen to us? Some things are easier to listen to than others. If we want to be listened to,...
-
Dave and Andy opened their gym, Elevate Triathlon Training, a year ago. Both are active triathletes and they found that many fitness trainers, although good at giving patrons a healthy workout, were...
-
The life \(T\) in hours of a vibration transducer is found to follow exponential distribution \[p_{T}(t)= \begin{cases}\lambda e^{-\lambda t}, & t \geq 0 \\ 0, & t <0\end{cases}\] where \(\lambda\)...
-
Fill in the Blank. If any parameter of a vibrating system is not known precisely, the resulting vibration is called ____________ vibration.
-
The probability distribution function, \(P(\widetilde{x})\), denotes a. \(P(x \leq \tilde{x})\) b. \(P(x>\widetilde{x})\) c. \(P(\tilde{x} \leq x \leq \tilde{x}+\Delta x)\)
Study smarter with the SolutionInn App