Big Number Representations

[ReignInChaos]

Note: Although Java comes with Big Number Representations, this is an insight on how it implemented behind the scenes.

Every computer comes with limitations and the one limitation is memory. How much "stuff" and data a computer can store and remember. Primitive data types have limitations in themselves also. For example, an int has a max value of 2(32) -1 and this goes for every data type. But what if there was an abstract data type that could rely on the limitations of the language and not the OS. In this case, an integer representation that is actually a list of integers. The largest 'int' would be 9 or 1001. We have just increased the max value without overflow. Heres some code:

public class BigNum {
    private List <Integer> digits;  // each digit 0..9
    private static final BigNum ZERO = new BigNum(0);
    private static final BigNum ONE = new BigNum(1);
    /**
     *
     */
    public BigNum()
    {
         digits = new LinkedList <Integer> ();
    }
    /**
     *
     * @param n The integer to be converted into a BigNum
     */
    public BigNum (int n)
   {
        this();
    if (n==0)
        digits.add (0);

    while (n>0)
      {
        digits.add (n % 10);    // low order digit
        n = n/10;
      }
     //size = digits.size();        //obsolete
     //this.normalize();
  }
    /**
     *
     * @param s The string to be converted into a BigNum
     */
  public BigNum(String s)
  {
      this();
      if(s.length() != 0) {
        for(int i = s.length()-1;i>=0;i--)
        {
             digits.add(s.charAt(i) - '0');
        }
      }
  }

These contructors take a value and store it as its respective BigNum. One interesting point to make is that negative numbers must be accounted for. This accomplished by making each BigNum a ten's complement. The reason for this is because when an int or other number type is stored, it is converted into memory as a two's compelement version. Most computers cannot directly associate a '-' as a negative number like humans do. I say most because it can be shown that a computer could understand '-' as negative but I haven't seen or heard of one before.

    /**
    * Negate this BigNum, and return the result.  Written by (sdb)
    * @return the negated BigNum value
    */
    private BigNum negate() {
        BigNum result = new BigNum();
        boolean nonZero = false;

        // copy zeroes
        Iterator<Integer> it = digits.iterator();
        int d = it.next();

        if (!it.hasNext() && d == 0) {
            result.digits.add(0);
        }
        while (it.hasNext() && d == 0) {
            result.digits.add(d);
            d = it.next();
        }

        // subtract first nonzero digit from 10
        if (d != 0) {
            result.digits.add(10 - d);

        // subtract all other digits from 9
        }
        while (it.hasNext()) {
            d = it.next();
            result.digits.add(9 - d);
            nonZero = true;
        }

        // check for overflow
        if (!nonZero && d == 5) {
            result.digits.add(0);
        }
        return result;
    }

Using a boolean method to find out if a BigNum is negative will aid in arithmetic.

    /**
     * Checks if a BigNum is negative
     * @return true if negative. false if not
     */
    private boolean isNeg() {
        if (this.digits.get(this.digits.size() - 1) > 4) {
            return true;
        } else {
            return false;
        }
    }

Finally, we have a full implementation of an arbitrary precision integer. This is especially important in fields that deal with very large or small numbers. For instance, NASA or mircobiologists would find this extremely useful.

Adding is simple because all that is needed is to iterate over the list and account for carry's. However, say you add 0001 and 982374982734, the size is different therefore, the smaller BigNum needs to propigated to be the same size as the bigger one. Also, overflow does need to be accounted for and is checked after the addition has occured.

    /**
     * Adds two BigNum numbers.
     * @param rSide
     * @return The answer after the addition
     */
    public BigNum add(BigNum num) {
        BigNum ans = new BigNum();
        int carry = 0;                   //carry value
        int sum = 0;                     //sum value
        //propigates if this is bigger
        if (this.digits.size() > num.digits.size()) {
            //n is the smaller number
            if (num.isNeg()) {
                num.digits.add(9);
            } else {
                num.digits.add(0);
            }
        }
        //propigates if num is bigger
        if (this.digits.size() < num.digits.size()) {
            //this is the smaller number
            if (this.isNeg()) {
                this.digits.add(9);
            } else {
                this.digits.add(0);
            }
        }
        //Left side iterator
        Iterator<Integer> itL = this.digits.listIterator();
        //Right side iterator
        Iterator<Integer> itR = num.digits.listIterator();
        //standard addition algorithm
        while (itL.hasNext() && itR.hasNext()) {
            sum = itL.next() + itR.next() + carry;
            carry = sum / 10;
            sum = sum % 10;
            ans.digits.add(sum);
        }
        while (itL.hasNext()) {
            sum = itL.next() + carry;
            carry = sum / 10;
            sum = sum % 10;
            ans.digits.add(sum);
        }
        while (itR.hasNext()) {
            sum = itR.next() + carry;
            carry = sum / 10;
            sum = sum % 10;
            ans.digits.add(sum);
        }
        //adding two positive numbers
        if (!this.isNeg() && !num.isNeg()) {
            ans.digits.add(0);
        }
        //adding two negative numbers
        if (this.isNeg() && num.isNeg()) {
            ans.digits.add(9);
        }
        //overflow check
        if (ans.isNeg()) {
            ans.digits.add(9);
        }
        return ans;
    }

Other functionality can be created once the basic concept is complete and I will leave that up to you to decide to expand. I can't give away all my secrets.

[Jordan]

Very nice tutorial, +rep.

[WingedPanther]

+rep. I've been using GMP with the ProjectEuler problems because many of the calculations exceed unsigned long int. I'm glad Java has something similar.

[drdebcol]

Yeah, the best way of declaring big number is by using an array of digits where first number is the heaviest and the last number is the easiest.
It is interesting how you made that. I was making the same algorithm in Delphi some time ago and i had the same problem with length. I am a perfectionist and i wanted to make it like for real numbers (14312,1243124) with "," and i made it for addition, but it was heavy for division.

[Turk4n]

Cool !

[WingedPanther]

Every time I've thought about creating a custom big-int class, I've thought in terms of an array of ints. You can use modulus and integer division to shift half the int to the next (higher) term in the array. The advantage would be that you don't have to worry about reimplementing a lot of the logic of arithmetic.