4. Integer values are implemented and manipulated at the hardware-level, al- lowing for fast operations. But the hardware does not supported unlimited integer values. For example, when using a 32-bit architecture, the integers are limited to the range -2,147,483,648 through 2,147,483,647. If you use a 64-bit architecture, this range is increased to the range -9,223,372,036,854,775,808 through 9,223,372,036,854,775,807. But what if we need more than 19 digits to represent an integer value?

   In order to provide platform-independent integers and to support integers larger than 19 digits, Python implements its integer type in software. That means the storage and all of the operations that can be performed on the values are handled by executable instructions in the program and not by the hardware. Learning to implement integer values in software offers a good example of the need to provide efficient implementations. We define the Big Integer ADT below that can be used to store and manipulate integer values of any size, just like Pythons built-in int type.

5. BigInteger( initValue = "0" ): Creates a new big integer that is ini- tialized to the integer value specified by the given string.

6. toString (): Returns a string representation of the big integer.

7. comparable ( other ): Compares this big integer to the other big integer to determine their logical ordering. This comparison can be done using any of the logical operators: , >=, ==, !=.

8. arithmetic ( rhsInt ): Returns a new BigInteger object that is the re- sult of performing one of the arithmetic operations on the self and rhsInt big integers. Any of the following operations can be performed:

   + - * // % **

9. (a) Implement the Big Integer ADT using a singly linked list in which each digit of the integer value is stored in a separate node. The nodes should be ordered from the least-significant digit to the largest. For example, the linked list below represents the integer value 45,839:

   head 9 38 83 5 4

   (b) Implement the Big Integer ADT using a Python list for storing the indi- vidual digits of an integer.

11. 6.8 Modify your implementation of the Big Integer ADT from the previous ques- tion by adding the assignment combo operators that can be performed on the self and rhsInt big integers. Allow for any of the following operations to be performed:

    += -= *= //= %= **= >= |= &= ^= bitwise-ops ( rhsInt ): Returns a new BigInteger object that is the result of performing one of the bitwise operators on the self and rhsInt big integers. Any of the following operations can be performed:| & ^ >

illustrates new values being added to the top of the stack and one value being

removed from the top.

A stack is a data structure that stores a linear collection of items with access limited to a last-in first-out order. Adding and removing items is restricted to one end known as the top of the stack. An empty stack is one containing no items.

4. Stack(): Creates a new empty stack.

5. isEmpty(): Returns a boolean value indicating if the stack is empty.

6. length (): Returns the number of items in the stack.

7. pop(): Removes and returns the top item of the stack, if the stack is not empty. Items cannot be popped from an empty stack. The next item on the stack becomes the new top item.

8. peek(): Returns a reference to the item on top of a non-empty stack without removing it. Peeking, which cannot be done on an empty stack, does not modify the stack contents.

9. push( item ): Adds the given item to the top of the stack.

   To illustrate a simple use of the Stack ADT, we apply it to the problem of reversing a list of integer values. The values will be extracted from the user until a negative value is entered, which flags the end of the collection. The values will then be printed in reverse order from how they were entered. We could use a simple list for this problem, but a stack is ideal since the values can be pushed onto the stack as they are entered and then popped one at a time to print them in reverse order. A solution for this problem follows.

   PROMPT = "Enter an int value (= 0 :

    myStack.push( value ) value = int(input( PROMPT )) 

   while not myStack.isEmpty() : value = myStack.pop() print( value )

   Suppose the user enters the following values, one at a time:

   7 13 45 19 28 -1

When the outer while loop terminates after the negative value is extracted, the contents of the stack will be as illustrated in Figure 7.2. Notice the last value entered is at the top and the first is at the base. If we pop the values from the stack, they will be removed in the reverse order from which they were pushed onto the stack, producing a reverse ordering.

PUSH

Solve PROGRAMMING PROJECT 6.7 and PROGRAMMING PROJECT 6.8 using a single implementation. Provide enough number of meaningful test examples to demonstrate that your implementation works as specified by the BigInteger ADT. Test all APIs! PUSH 28 7 13 45 19 28 -1 19 45 13 7 MMING