How can I perform division in a program, digit by digit?

Question

I'm messing around with writing a class similar to mpz (C) or BigInteger (Java). This is just for fun, so please don't go on about how I shouldn't be writing my own.

I have a class similar to:

public class HugeInt
{
    public List<Integer> digits;

    public HugeInt(String value)
    {
        // convert string value into its seperate digits. 
        // store them in instance variable above
    }
}

Now, doing the add() and subtract() method of this class are pretty simple. Here is an example:

private List<Integer> add(List<Integer> a, List<Integer> b)
    {
        List<Integer> smallerDigits = (compareDigits(a,b) < 0) ? a : b;
        List<Integer> largerDigits = (compareDigits(a,b) >= 0) ? a : b;
        List<Integer> result = new ArrayList<Integer>();

        int carry = 0;

        for(int i = 0; i < largerDigits.size(); i++)
        {
            int num1 = largerDigits.get(i);
            int num2 = (i < smallerDigits.size()) ? smallerDigits.get(i) : 0;

            result.add((num1 + num2 + carry) % 10);
            carry = ((num1 + num2 + carry) / 10);
        }

        if (carry != 0) result.add(carry);

        return result;
    }

Similarly, doing the multiply wasn't that hard either.

I see on wikipedia there is a page on Division Algorithms, but I'm not sure which one is appropriate for what I'm trying to do.

Because these positive integers (represented as digits) can be arbitrarily long, I want to make sure I don't attempt to do any operations on anything other than digit-by-digit basis.

However, can anyone point me in the right direction for doing a division of two numbers that are represented as List<Integer>'s? Also, I can ignore the remainder as this is integer division.

Answer 1

You could just do long division, but this certainly isn't the optimal way to do it (edit: although it seems that something like this is a good way to do it). You could look at other implementations of big integer libraries, and a bit of Googling turns up a fair bit of useful information.