如何逐个数字地执行程序中的除法？

Question

我正在编写类似于mpz(C)或BigInteger(Java)的类.这只是为了好玩,所以请不要继续谈论我不应该如何写自己的.

我有一个类似于的类:

public class HugeInt
{
    public List<Integer> digits;

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

现在,执行此类的add()和subtract()方法非常简单.这是一个例子:

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;
    }

同样,做多次也不是那么难.

我在维基百科上看到有一个关于分区算法的页面,但我不确定哪一个适合我正在尝试做的事情.

因为这些正整数(表示为数字)可以任意长,所以我想确保我不会尝试对除了逐位数字之外的任何操作进行任何操作.

但是,任何人都能指出我正确的方向来划分两个被表示为's的数字吗？此外,我可以忽略余数,因为这是整数除法.List<Integer>

Answer 1

你可以做多分,但这肯定不是最好的方法(编辑:虽然看起来像这样的东西是一个很好的方法).您可以查看大整数库的其他实现,并且一些谷歌搜索会发现一些有用的信息.

Answer 2

因为我假设你只是处理整数除法，所以这并不难。乘法是重复的加法，除法则是相反的——重复的减法。所以你要做的就是检查你可以从股息中减去除数多少次。例如，10 3 次减 3 不会小于 0，因此整数除商为 3。