13

我正在写一个类似于 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;
    }

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

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

因为这些正整数（表示为数字）可以是任意长的，所以我想确保我不会尝试在逐个数字的基础上进行任何操作。

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

4

4 回答 4

5

你可以只做长除法，但这肯定不是最好的方法（编辑：虽然这样的事情似乎是一种很好的方法）。您可以查看大整数库的其他实现，并在谷歌上搜索一些有用的信息。

于 2010-02-25T23:49:26.990 回答
2

这可能有点矫枉过正，但如果这是你为了好玩而做的那种事情，你会喜欢阅读这个： http ://www.fizyka.umk.pl/nrbook/c20-6.pdf （这是“算术任意精度”来自“C 中的数值配方”）。和本书的大部分内容一样，非常迷人，有很好的解释和大量的代码。

于 2010-02-26T00:59:48.007 回答
0

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

于 2010-02-25T23:46:12.050 回答
0

这篇文章A Larger Integer没有展示如何为“更大的整数”实现逐位运算，但它确实展示了如何根据两种 Int64 类型实现一个（显然功能齐全的）128 位整数。我想扩展使用 Int64 类型数组来产生任意长度整数的方法不会太难。我只是花了几分钟回顾一下这篇文章，乘法的实现看起来可能会涉及到任意长度。

本文展示了如何使用二进制除法来实现除法（商和余数）。

于 2010-05-26T17:12:51.730 回答