java - 程序变慢但计算的数字变小

Question

我正在创建 Java 的 BigInteger 类的自定义实现，以及后续方法:

• 乘
• 除以，
• 添加
• 减去。

我对除法有疑问。

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) 

然后，我们将节省下来的值(value)从股息中删除，使其变小。每次循环完成时，我们都会同时获取该值并将其添加到变量中。

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

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

这是为什么？

完整的BigInt类。

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 加倍。

我对 future 的建议是以与正确性问题相同的方式调试此问题:打印变量大小，查看预期大小，查看实际值。此外，您还可以使用探查器。