Big integer multiplication in java

Question

This is my own method and I am also using my own BigInt class I did everything but I cannot seem to find out where I am doing wrong if someone can help me, I will be really thankful.

public BigInt mul(BigInt o) {
    int max = n.length > o.n.length ? n.length : o.n.length;
    int[] newdigits = new int[n.length + o.n.length];

    for (int i = 0; i < max; i++)
    {
        int carry = 0;
        for (int i2 = 0; i2 < o.n.length || carry > 0; i2++)
        {
        int otherDigit = i2 >= o.n.length ? 0: o.n[i2];
            int val = (n[i] * otherDigit) + carry;
            newdigits[i + i2] += val % 10;
            carry = val / 10;
         }
     }
     return new BigInt(newdigits);
}

This is my code so far it works but in the result i get one extra zero, as an example: when i multiply 100*10 I get 01000 instead of 1000 and other issue is that when i multiply 9999*1999 I get this: 1817262619101 but the correct answer is 19988001. Can some one help me on this?

Here is my BigInt class:

 public class BigInt {

    public static void main(String[] args) {

        BigInt a = new BigInt(args.length == 2 ? args[0] : "9999");
        BigInt b = new BigInt(args.length == 2 ? args[1] : "1999");

        System.out.println(a + (a.equals(b) ? " equals " : " does not equal ") + b);

        System.out.println(a + (a.compareTo(b) < 0 ? " < " : (a.compareTo(b) > 0 ? " > " : " = ")) + b);

        System.out.println(a + " + " + b + " = " + a.add(b));
        if (a.compareTo(b) >= 0) {
            System.out.println(a + " - " + b + " = " + a.sub(b));
        }
        System.out.println(a + " * " + b + " = " + a.mul(b));
        if (a.compareTo(b) >= 0) {
            System.out.println(a + " / " + b + " = " + a.div(b));
        }
    }
}

final class BigInt implements Comparable<BigInt> {

   int[] digits;
   int size;


    public BigInt() {

        n = new int[1];
    }

    public BigInt(String s) {

        n = new int[s.length()];

        for (int i = 0; i < n.length; ++i) {
            n[n.length - i - 1] = s.charAt(i) - '0';
        }

        n = trim(n);
    }

    private BigInt(int[] n) {

        this.n = new int[n.length];

        for (int i = 0; i < n.length; ++i) {
            this.n[i] = n[i];
        }
    }

    public BigInt add(BigInt o) {
        return null;
    }

    public int compareTo(BigInt o) {

        if (n.length < o.n.length) {
            return -1;
        }
        else if (n.length > o.n.length) {
            return +1;
        }

        for (int i = n.length-1; i >= 0; --i) {
            if (n[i] < o.n[i]) {
                return -1;
            }
            else if (n[i] > o.n[i]) {
                return +1;
            }
        }

        return 0;
    }

    public BigInt div(BigInt o) {

        return null;
    }

    public boolean equals(Object o) {

        if (o instanceof BigInt) {
            if (n.length == ((BigInt)o).n.length) {
                for (int i = 0; i < n.length; ++i) {
                    if (n[i] != ((BigInt)o).n[i]) {
                        return false;
                    }
                }
                return true;
            }
        }

        return false;
    }

     public BigInt mul(BigInt o) {
        int max = n.length > o.n.length ? n.length : o.n.length;
        int[] newdigits = new int[n.length + o.n.length];

        for (int i = 0; i < max; i++)
        {
            int carry = 0;
            for (int i2 = 0; i2 < o.n.length || carry > 0; i2++)
            {
            int otherDigit = i2 >= o.n.length ? 0: o.n[i2];
                int val = (n[i] * otherDigit) + carry;
                newdigits[i + i2] += val % 10;
                carry = val / 10;
             }
         }
         return new BigInt(newdigits);
    }

    public BigInt sub(BigInt o) {

      return null;
    }
    public String toString() {

        String s = "";

        for (int i : n) {
            s = i + s;
        }

        return s;
    }

    private int[] trim(int[] nums) {

        int size = nums.length;

        for (int i = nums.length - 1; i > 0; --i) {
            if (nums[i] != 0) {
                break;
            }
            --size;
        }

        int[] res = new int[size];

        for (int i = 0; i < size; ++i) {
            res[i] = nums[i];
        }

        return res;
    }

    private int[] n;
}

Answer 1

Didn't feel like debugging your code, but here is how I'd implement that multiplication. It's a little less efficient, but easier to keep track of the carry.

public BigInt mul(BigInt o) {
    int max = n.length > o.n.length ? n.length : o.n.length;
    int[] newdigits = new int[n.length + o.n.length];

    for (int i = 0; i < max; i++) {
        for (int i2 = 0; i2 < max; i2++) {
            int digit1 = i >= n.length ? 0 : n[i];
            int digit2 = i2 >= o.n.length ? 0 : o.n[i2];
            if (digit1 > 0 && digit2 > 0) {
                int value = digit1 * digit2;
                int pos = i + i2;
                while (value > 0) {
                    int newDigit = (newdigits[pos] + value) % 10;
                    value = (newdigits[pos] + value) / 10;
                    newdigits[pos] = newDigit;
                    pos++;
                }
            }
        }
    }

    return new BigInt(newdigits);
}

Answer 2

First, look the possible lengths:

[1] * [1] = [1] OR length(1) + length(1) -> length(1)

[9] * [9] = [8,1] OR length(1) + length(1) -> length(2)

One solution

Psudocode:

if (newdigits[ (length-1) ] == 0)
    int[] newarray = new int[ (length-1) ]
    copy newdigits to newarray
    return newarray

You have to look at the carry of the largest digit before the earlier digits.

Secondly, you need to add the previous value you found to the val variable.

End of i=0:

[1, 9, 9, 7, 1, 0, 0, 0]

Adding during i=1:

[0, 1, 9, 9, 7, 1, 0, 0]

End of i=1:

[1, 10, 18, 16, 8, 1, 0, 0]

I suggest you try using Arrays.toString(newdigits) or use a debugger to catch these problems in the future.