java - 用非常大的数字提高加法的性能

Question

我编写了这个程序来计算非常大的数字，而不使用任何 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();
}

Answer 1

与其逐个字符地做，不如取 k一次一个字符，这样它就可以放入 Java int或 long .使用一些预定的阈值，既可以容纳“块”，也可以根据实现方式容纳任何溢出(即 (threshold * 2) < positive_type_limit )。为了使事情更容易，使用一个 10 的幂的阈值，这样你就可以直接将它映射到一个以 10 为基数的字符串表示中的字符(例如，如果你的溢出阈值是一百万，那么你可以在一段时间) - 这也有额外的好处，您可以有效地将其转换回字符串。

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

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

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

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

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