<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">/** An instance wraps an integer (of any size) */
public class BigInt {

    /** The base in which big integers (BigInts) are maintained. 
        1 less BASE less= Short.MAX_VALUE.
    */
    public static final int BASE= 50;
    
    private static final Integer int0= new Integer(0);
    
    /* An integer is maintained in base BASE in field bigint; its sign
       is in variable sign. The elements in bigint are always of
       class Integer. An unsigned integer
       
            i = bk*BASE^k + ... + b2*BASE^2 + b1*BASE^1 + b0*BASE^0
       
       is maintained as the list (b0, b1, b2, ..., bk), so that the
       low-order digit is first and the high-order digit is last.
       This makes manipulating integers (e.g. adding) easier.
       
       The integer 0 is represented by bigint = (0) and
       sign being true.
       
       If the integer is not 0, the high order digit is nonzero.
       Note: in one or two places, integers are kept in another base.
       This will be explained at the right time.
    */ 
    private List bigint;    // The unsigned integer --see above
    private boolean sign;   // The sign of the integer: true means +; false means -
    
    /** Constructor: the integer 0 */
    public BigInt() {
        bigint= new List(int0,null);
        sign= true;
    }
    
    /** Constructor: an instance that represents i */
     public BigInt(long i) {
        sign= i&gt;=0;
        bigint= encode(Math.abs(i), BASE);
    }
    
     /** Constructor: an instance that represents i, but in base base */
     public BigInt(long i, int base) {
        sign= i&gt;=0;
        bigint= encode(Math.abs(i), base);
    }

    
    /** = the List that represents i in base base.
          Precondition: i &gt;= 0
     */
    private static List encode(long i, int base) {
        if (i == 0) 
            {  return new List(int0,null);  }
        // {i &gt; 0}
        List res= null;  // Will contain the final List
        long n= i;
        List p= null;
        // inv: p is the name of the last node in list res (null if res is null)
        //      The representation of i in base base is given by
        //      res followed by the representation of n
        while (n &gt; 0) {
            Integer nextDigit= new Integer((int)(n % base));
            if (p == null) {
                res= new List(nextDigit, null);
                p= res;
            }
            else {p.next= new List(nextDigit,null);
                  p= p.next;
            }
            n= n/base;
        }
        return res;
    
    }
    
    /** = the number of digits this integer requires in base BASE */
    public int numberDigits() {
        return List.length(this.bigint);
    }

    
    /** = "this BigInt equals b". Precondition: b != null 
           Task 1: WRITE THIS METHOD AND THEN DELETE THIS LINE!!!
     */
    public boolean equals(BigInt b) {
        return false;

    }

    
    /** = "this BigInt is less than b". Precondition: b != null */
    public boolean less(BigInt b) {
        if (this.sign != b.sign)
            {  return b.sign;  }
        return this.sign ? less(this.bigint, b.bigint) : less(b.bigint, this.bigint);
    }
    
    // = "unsigned integer b1 is less than unsigned integer b2"
    //   Precondition: b1 and b2 are nonnull.
    //   Task 2: WRITE THIS METHOD AND THEN DELETE THIS LINE!!!
    private static boolean less(List b1, List b2) { 
        return false; // replace this by our own statements
    }
    
    /** = - this */
    //   Task 3: WRITE THIS METHOD AND THEN DELETE THIS LINE!!!
    public BigInt negate() {
        return null;
    }
    
    /** = this - b. Precondition: b is not null 
        Task 7. WRITE THIS METHOD AND DELETE THIS LINE.
     */
    public BigInt subtract(BigInt b) {
        BigInt res= new BigInt();  // Will contain the result
        
        return res;   
    }
    
    /** = the unsigned integer that is b1 - b2. 
          Precondition: b1 and b2 are not null and b1 &gt; b2 
          Task 6. WRITE THIS METHOD AND DELETE THIS LINE.*/
    private static List subtract(List b1, List b2) {
        List p1= b1;
        List p2= b2;
        int carry;
        List res= new List(new Integer(0),null);
        List p3;
        /* inv: p1 is a node of b1.
                p2 is the corresponding node of b2.
                res is the sum of lists b1 and b2 up to 
                    and including nodes p1 and p2. 
                p3 is the last node of res.
                carry is the carry.
         */
        
        return removeleadzeros(res);
    }


    
    /** = this + b. Precondition: b is not null 
          Task 5. WRITE THIS METHOD AND THEN DELETE THIS LINE.
      */
    public BigInt add(BigInt b) {
        BigInt res= new BigInt(); // will contain the result

        return res;
    }
    
    /** = the unsigned integer that is b1 + b2. 
          Precondition: b1 and b2 are not null 
          Task 4: WRITE THIS METHOD AND THEN DELETE THIS LINE
      */
    private static List add(List b1, List b2) {
        List p1= b1;
        List p2= b2;
        List res= new List(new Integer(0), null);
        List p3;
        int carry;
        /*inv: p1 is a node of b1 (or null when done).
               p2 is the corresponding node of b2 (or null when done).
               p3 is the last node of res.
                  res is the sum of lists b1 and b2 up to and including nodes p1 and p2. 
                  and carry is the carry.
         */
        return res;
    }
    
    /** = b * x. Precondition: 0 at most x less BASE. */
    private static BigInt mult(BigInt b, int x) {
        if (x == 0 || isZero(b))
           {  return new BigInt();  }
        BigInt res= new BigInt();  // res will contain the result
        res.sign= b.sign;
        // Perform a conventional multiplication of b and x; stor result in res
            List p= b.bigint;
            int i= ((Integer)p.element).intValue()*x;
            res.bigint= new List(new Integer(i%BASE), null);
            List q= res.bigint;
            int carry= i/BASE;
            //inv: p is a node of b.bigint and
            //     q is the last node of res.bigint and
            //     res is the product of lists b.bigint and x up to and
            //        counting node p and 
            //     carry is the carry
            while (p.next != null) {
                p= p.next;
                i= ((Integer)p.element).intValue()*x + carry;
                q.next= new List(new Integer(i%BASE),null);
                q= q.next;
                carry= i/BASE;
            }
            if (carry &gt; 0)
                {  q.next= new List(new Integer(carry),null);  }
            
        return res;
    }
    
    // = b*BASE^c. Precondition: c &gt;= 0, b is a list like a bigint field
    private static List multBASE(List b, int c) {
        Integer k= int0;
        if (b.next==null &amp;&amp; ((Integer)b.element).intValue()==0)
            {  return b;  }
        List p= null;
        while (c != 0) {
            p= List.prepend(k,p);
            c= c-1;
        }
        return List.append(p,b);
    }
    
    /** = this * b. Precondition: b is not null */
    public BigInt mult(BigInt b) {
        if (isZero(this))
            {  return this;  }
        if (isZero(b))
            {  return b;  }
        // {neither this nor b is 0}
        List p= b.bigint;
        int c= 0;
        BigInt ans= new BigInt();  // ans will contain the result
        // Copy folder this into a new folder thisCopy and make
        // sign of the copy true
            BigInt thisCopy= new BigInt();
            thisCopy.sign= true;
            thisCopy.bigint= this.bigint;
        // inv: p is a node of b.bigint (null if at all done)
        //      c is the number of this node in b (the first is number 0)
        //      ans is the product of thisCopy and the first c nodes of b
        while (p != null) {
            BigInt temp= mult(thisCopy, ((Integer)p.element).intValue());
            temp.bigint= multBASE(temp.bigint,c);
            ans= ans.add(temp);
            p= p.next;
            c= c+1;
        }
        // Fix the sign of the result
            ans.sign= this.sign == b.sign;
        return ans;
    }
    
    // = "b is 0"
    private static boolean isZero(BigInt b) {
        return b.bigint.next==null &amp;&amp; 
               ((Integer)b.bigint.element).intValue()==0;
    }
    
    // = b with leading zeros removed. Since b represents an unsigned integer with
    // the low order digit first, by leading zeros we mean the ones at the end, not at
    // the beginning.
    // This method may change list b and return it!!
    //   (it's the only method that does so)
    public static List removeleadzeros(List b) {
            List p= b;
            List q= null;
            // Store in q the name of the highest-order nonzero (null if none)
                // inv: p is a node of list b (null if whole list has been processed)
                //      and q is name of highest-order nonzero node that occurs before p
                while (p != null) {
                    if (((Integer)p.element).intValue() != 0)
                        {  q= p; }
                    p= p.next;
                }
        if (q == null)
            return new List(int0,null);
        q.next= null;
        return b;
    }
  
    
    
    // digits[i] is the conventional String character that is used to represent
    // integer i in any base that is at most 16.
    private static final String[] digits= {"0", "1", "2", "3", "4", "5",
                                           "6", "7", "8", "9", "A", "B",
                                           "C", "D", "E", "F"};
    
    /** = this BigInt, written in base BASE, with the high-order digit first.&lt;br&gt;
          If BASE at most 16, it is given in conventional form. &lt;br&gt;
          If BASE greater 16, it is given with commas between the digits
             and is delimited by ( and )
     */
    public String toStringBASE() {
        // In creating the decimal representation of this integer, the high-order
        // digit has to be first. So store the reverse of this's
        // unsigned integer in b
            List b= List.reverse(bigint); // unsigned int with high-order digit first
        String s= sign ? "" : "-";  // sign of this integer
         
        if (BASE &gt; 16) {
            return s + List.toString(b);
        }
        // Construct the representation of the integer in s
            while (b != null) {
                int d= ((Integer)b.element).intValue();
                s= s + digits[d];
                b= b.next;
            }
        return s;
    }
    
   
    /** Store in q the quotient when b is divided by y
         and return the remainder. Quotient q will be in base base&lt;br&gt;&lt;br&gt;
        Precondition (0): b is in base base (not necessarily BASE).&lt;br&gt;
        Precondition (1): 0 less y less base.&lt;br&gt;
        Precondition (2): this &gt; 0.&lt;br&gt;
        Precondition (3): q is nonull and different this and y.
      */
    private static int division(BigInt b, int y, BigInt q, int base) {
        q.sign= true;
        int r= divisionSimple(b,y,q,base);
        if (0&lt;=r) {
            return r;  
        }
        // {1 &lt; b &lt; this}
        // Put the digits of this in array dig, with high-order bit first
            int n= List.length(b.bigint);
            int dig[]= new int[n];
            List p= b.bigint;
            for (int i= 0; i != n; i= i+1) {
                dig[n-1-i]= ((Integer)p.element).intValue();
                p= p.next;
            }
        
        // Divide integer in dig by y, putting quotient in qa in r
        // Remember that 1 &lt; b &lt; this.
            int[] qa= new int[dig.length];
            qa[0]= dig[0]/y;
            r= dig[0]%y;
            // inv: 0 &lt;= i &lt;= dig.length and
            //      qn[0..i-1] and r contain the quotient and remainder
            //      of dividing dig[0..i-1] by y
            for (int i= 1; i != dig.length; i++) {
                int temp= r*base + dig[i];
                qa[i]= temp/y;
                r= temp%y;
            }
 
        // Put the digits of qa into q.bigint. The first digit may be 0
            q.bigint= null;
            if (qa[0] != 0) 
                {  q.bigint= List.prepend(new Integer(qa[0]), q.bigint);  }
            for (int j= 1; j != qa.length; j++)
                { q.bigint= List.prepend(new Integer(qa[j]), q.bigint);  }
       return r;
    }
    
    /** Store in q the quotient when this is divided by y
         and return the remainder.&lt;br&gt;&lt;br&gt;
        Precondition (1): 0 less y less BASE.&lt;br&gt;
        Precondition (2): this &gt; 0&lt;br&gt;
        Precondition (3): q is nonnull and different this and y.
      */
    public int division(int y, BigInt q) {
        return division(this, y, q, BASE);
    }

    
     /** if 0 at most b at most y or y=1, store in q the quotient of b divided by y
         and return the remainder. q will be in base b.
         in all other cases, return -1.&lt;br&gt;&lt;br&gt;
        Precondition (0): b is in base base (not necessarily base BASE)&lt;br&gt;
        Precondition (1): 0 less y less base --this is a big restriction.&lt;br&gt;
        Precondition (2): this &gt;= 0 --this is also a big restriction&lt;br&gt;
        Precondition (2): q is nonull and different this and b.
      */
    private static int divisionSimple(BigInt b, int y, BigInt q, int base) {
        q.sign= true;
        BigInt by= new BigInt(y, base);
        if (b.less(by)) {
            q.bigint= new List(int0, null);
            return ((Integer)b.bigint.element).intValue();
        }
        if (b.equals(by)) {
            q.bigint= new List(new Integer(1), null);
           return 0;
        }
        if (by.equals(new BigInt(1, base))) {
            q.bigint= b.bigint;
            return 0;
        }
        return -1;
    }
    
   /**  = a List with same value as b (which is in base BASE) but its base is BASE^4.
          Precondition: 0 less BASE less 10 */
    private static List base4(List b) {
        List l= new List(b.element,null);
        List pb= b;
        List pl= l;
        int i= 0;   // 0 &lt;= i &lt; 4
        int basei= 1;
        // inv: pb is a node of b, and
        //      pl is the last node of l, and
        //      l, in base BASE^4, has the same value as b through pb, in base BASE, and
        //      i = (number of nodes of b before node pb) % 4
        //      basei= BASE^((i-1)%4)
        while (pb.next != null) {
            pb= pb.next;
            int ib= ((Integer)pb.element).intValue();
            i= (i+1)%4;
            if (i == 0) {
                pl.next= new List(new Integer(0),null);
                pl= pl.next;
                basei= 1;
            }
            else 
                { basei= basei*BASE; };
            int il= ((Integer)pl.element).intValue();
            il= il + ib*basei;
            pl.element= new Integer(il);          
        }       
        return l;
    }
          
    
    /** = this integer as a String (in decimal).
          This method works only if equals and less are working.
      */
    public String toString() {
        BigInt x= new BigInt();
        x.sign= true;
        x.bigint= this.bigint;
        int base= BASE;
        // The algorithm will perform successive divisions by 10 on
        // x. This will work only if the base in which x is stored is
        // at least 10. Therefore if BASE is in 2..9, change x to
        // contain the same number in base BASE^4 (and change base
        // accordingly)
            if (BASE &lt; 10) {
                x.bigint= base4(x.bigint);
                base= base*base*base*base;  
            }
                                   
        String s= "";
        // inv: the representation of abs(this) is s followed by (representation of x)
        while (!isZero(x)) {
            BigInt q= new BigInt();
            int r= x.division(x, 10, q, base);
            s= r + s;
            x= q;
        }
        if (s.equals(""))
            s="0";

        // remove leading 0's
            while (s.length() &gt; 1 &amp;&amp; s.charAt(0) =='0')
                s= s.substring(1);
                
        if (!this.sign)
            {  s= "-" + s;  }
            
        return s;
    }

}</pre></body></html>