我编写这个程序是为了计算非常大的数字,而不使用任何 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 int
或long
。使用一些预定的阈值,该阈值可以容纳“ 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/