如何在程序中逐位进行除法?

2022-09-04 22:48:47

我正在编写一个类似于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()和addtract()方法非常简单。下面是一个示例:

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

同样,做乘法也不是那么难。

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

因为这些正整数(表示为数字)可以任意长,所以我想确保我不会尝试在逐位以外的任何事情上执行任何操作。

但是,任何人都可以为我指出正确的方向,以便对表示为的两个数字进行除法?另外,我可以忽略余数,因为这是整数除法。List<Integer>


答案 1

你可以只做长除法,但这肯定不是最好的方法(编辑:尽管看起来这样的事情是一个很好的方法)。你可以看看大整数库的其他实现,一些谷歌搜索会发现相当多的有用信息。


答案 2

这可能有点过分,但如果这是你为了好玩而做的事情,你会喜欢读这个:http://www.fizyka.umk.pl/nrbook/c20-6.pdf(这是“C中的数字配方”中的“任意精度算术”)。非常令人着迷,就像本书的大部分内容一样,有很好的解释和大量的代码。