2

我编写了这个程序来计算非常大的数字，而不使用任何 BigInteger 方法。我完成了它，它工作正常。我使用 StringBuilder 和大量的 parseInt 调用来完成它。有没有更有效的方法来做到这一点？

顺便说一句，这只是工作表，忽略糟糕的编程风格，完成我的工作后，我会重新组织它。

private String add (String x, String y)
{
    String g = "";
    StringBuilder str = new StringBuilder();
    int sum;
    double atHand = 0;
    int dif = (int)(Math.abs(x.length()-y.length())); 

    if(x.length() >= y.length())   //adding zero for equalise number of digits.
    {
        for(int i = 0; i<dif; i++)
            g += "0";
        y = g+y;    
    }
    else 
    {
        for(int i = 0; i<dif; i++)
            g += "0";
        x = g + x;
    }

    for (int i = y.length()-1; i >=0 ; i--)
    {
        sum = Integer.parseInt(x.substring(i, i+1)) +Integer.parseInt(y.substring(i,i+1)) + (int)atHand; 

        if(sum<10) 
        {
            str.insert(0, Integer.toString(sum)); 
            atHand = 0;  
        }else
        {
            if(i==0)
                str.insert(0, Integer.toString(sum)); 
            else
            {
                atHand = sum *0.1;
                sum = sum %10;  
                str.insert(0, Integer.toString(sum));
            }
        }
    }
    return str.toString();
}
4

1 回答 1

3

而不是一个字符一个字符地做，你应该k一次取一个字符，这样它就可以适应 Javaint或long. 使用一些预定的阈值，既可以容纳“块”，又可以容纳任何溢出（即这样的），具体取决于实现(threshold * 2) < positive_type_limit。为方便起见，请使用 10 的幂的阈值，因此您可以直接将其映射到以 10 为基数的字符串表示形式的字符（例如，如果您的溢出阈值为 100 万，那么您可以在一次） - 这还有一个额外的好处，您可以有效地将其转换回字符串。

那么你的“块”要大得多。然后，您将使用这些块和您的限制/阈值（基于您使用的整数原始类型）添加并进行溢出。所以基本上你是在一个数组上操作ints。

你仍然会有 的时间复杂度O(n)，但它会更小n（更具体地说，它将O(n/k)是k一个块代表的十进制数字的数量。）

我相信所有解决方案都涉及将大数字拆分为较小的块并对其进行操作。您已经这样做了，只是您当前的解决方案是blocksize=k=1.

为了充分利用块，您可以使用 2 的幂作为限制，例如对于 32 位无符号整数类型，您可以将阈值设置为2^31（或者您可以将其设置为 2^32，但这取决于位置和您如何存储溢出以传递给下一个元素）。

如果 BigInteger 使用类似的技术，我不会感到惊讶。

于 2012-06-07T14:27:30.127 回答