程序变慢但正在计算的数字变小

Question

我正在使用后续方法创建 Java 的 BigInteger class 的自定义实现：

相乘
划分，
添加
减法。

除法有问题

private BigInt createQuotient (BigInt aNumber, BigInt other){
    BigInt dividend = new BigInt(aNumber.toString());
    BigInt divisor = new BigInt(other.toString());
    dividend.isNegative = false;
    divisor.isNegative = false;
    BigInt finalQoutient = new BigInt("0");
    BigInt one = new BigInt("1");

    while(compareBigInts(dividend, divisor) == 1) {
            BigInt two = one;
            BigInt lastTwo = new BigInt("0");
            BigInt temp = divisor;
            BigInt lastTemp = new BigInt("0");
        while(compareBigInts(dividend, temp) == 1) {
                lastTwo = two;
                lastTemp = temp;

                if (two == one) {
                        two = two.add(one);
                }
                else{
                        two = two.add(two);
                }
                temp = divisor.multiply(two);

        }

        finalQoutient = finalQoutient.add(lastTwo);
        dividend = dividend.subtract(lastTemp);


}
finalQoutient = finalQoutient.add(one);
return finalQoutient;
}

代码代表这个算法：

假设 100 是我们的红利，5 是我们的除数，20 是我们最后的商。

while dividend > divisor, do:

2^0 * 5 = 5 which is less than our dividend, so we increment two ;  
2^1 * 5 = 10 which is less than our dividend, so we increment two ;  
2^2 * 5 = 20 which is less than our dividend, so we increment two ;  
2^3 * 5 = 40 which is less than our dividend, so we increment two ;  
2^4 * 5 = 80 which is less than our dividend, so we increment two ; (lastTemp)  
2^4 * 5 = 160 which is greater than our dividend, so we save the value before this one ; (temp)

然后我们将保存的值从股息中移除，使其变小。每次循环完成时，我们同时获取该值并将其添加到变量中。

我们这样做直到被除数小于除数，此时我们只需 return 存储的变量为每个循环添加 lastTemp。

考虑到这一点，我的程序适用于较小的数字，但随着 aNumber 变大而变得非常慢。由于我所有的变量都在缩小，我希望每次传递都更快，但是我的程序变慢了。

这是为什么？

完整 BigInt class.

https://github.com/collinarnett/big-int/blob/master/BigInt.java

Answer 1

显然，dividend.bigNum.size() 和 temp.bigNum.size() 的大小在每次迭代中呈指数增长。我已经添加

System.out.println(dividend + " " + temp + "; sizes are " + dividend.bigNum.size() + " " + temp.bigNum.size());

就在最里面的 while 循环之前，得到以下内容：

366000000000 36; sizes are 12 12
56762354688 36; sizes are 24 24
18107649024 36; sizes are 48 48
8443972608 36; sizes are 96 96
3612134400 36; sizes are 192 192
1196215296 36; sizes are 384 384
592235520 36; sizes are 768 768
290245632 36; sizes are 1536 1536
139250688 36; sizes are 3072 3072

发生这种情况的部分原因是您的 BigInt(String) 没有截断标题零（可能应该在 createArrayList 中完成），部分原因是它们在两个参数中都被 createProduct 加倍.

我对未来的建议是像调试正确性问题一样调试此问题：打印可变大小，查看预期大小，查看实际值。另外，您可以使用探查器。

程序变慢但正在计算的数字变小

Program slows down but the numbers being calculated get smaller

java

algorithm

biginteger

division