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

标签 java performance biginteger

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

最佳答案

您应该采用k,而不是逐个字符地进行操作。一次一个字符,这样它就可以适合 Java intlong 。使用一些预定的阈值,该阈值可以容纳“ block ”,并且根据实现,任何溢出(即 (threshold * 2) < positive_type_limit )。为了使事情变得更简单,请使用 10 的幂的阈值,这样您就可以将其直接映射到以 10 为基数的字符串表示形式中的字符(例如,如果您的溢出阈值是一百万,那么您可以在a time) - 这还有一个额外的好处,您可以有效地将其转换回字符串。

那么你的“障碍”就会大得多。然后,您可以使用这些 block 和限制/阈值(基于您使用的整数基元类型)添加并执行溢出。所以基本上你是在 ints 的数组上进行操作.

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

我相信所有解决方案都涉及将大数拆分成更小的 block 并对它们进行操作。您已经完成了此操作,只是您当前的解决方案是 blocksize=k=1 的特殊情况。

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

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

关于java - 提高非常大的数字的加法性能,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10933470/

相关文章:

java - Android Studio(Java)中无法使用时间戳,当点击按钮时,模拟器会喊下来

python - 有一个numpy biginteger吗?

java - 如何将2048位的BigInteger分解成固定数量的64位的字?

java - 如何使用 Spring security 保护包含的页面

java - Java 中的 AMF 客户端

java - 从Java中的字符串中提取数字

java - 如何将/META-INF/BenchmarkList 附加到 jmh 任务以修复 "ERROR: Unable to find the resource:/META-INF/BenchmarkList"

ios - UITableView 滚动在 iOS 模拟器中不稳定

javascript - google lighthouse 如何计算 javascript 评估时间,以及为什么对于不同环境中的相同脚本,它会有很大差异

iOS 大整数 NSNumberFormatter 不工作