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

Since I assume you're just dealing with integer division it's not very hard. Multiplication is repeated addition, division is the opposite - repeated subtraction. So what you'll do is check how many times you can subtract the divisor from the dividend. For example, 3 can be subtracted from 10 3 times without going <0, so the integer division quotient is 3.

Answer 2

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.

Answer 3

This may be a slight overkill, but if this is the kind of things you do for fun, you'll enjoy reading this: http://www.fizyka.umk.pl/nrbook/c20-6.pdf (that's "Arithmetic at Arbitrary Precision" from "Numerical recipes in C"). Pretty fascinating, as is most of this book, with good explanations and lots of code.

Answer 4

This article A Larger Integer does not show how to implement digit by digit operations for "larger integers", but it does show how to implement a (apparently fully functional) 128 bit integer in terms of two Int64 types. I would imagine that it would not be too hard to extend the approach to use an array of Int64 types to yield an arbitary length integer. I just spent a few minutes looking back over the article and the implementation of multiply looks like it could get pretty involved for arbitrary length.

The article shows how to implement division (quotient and remainder) using binary division.