CODEWITHSUNDEEP
javaalgorithmdivisionbiginteger
Collin Arnett
Collin Arnett

Reputation: 37

Program slows down but the numbers being calculated get smaller

I'm creating a custom implementation of Java's BigInteger class, with subsequent methods:

I have a problem with division.

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;
}

Code represents this algorithm:

Let's say 100 is our dividend and 5 is our divisor with 20 being our final quotient.

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)

We then take that saved value and remove it from the dividend, making it smaller. We simultaneously take that value and add it to a variable each time a loop is completed.

We do this until the dividend gets to be smaller than the divisor, at which point we simply return the variable that stored added lastTemp for each loop.

With that in mind, my program works for smaller numbers but becomes extremely slow as aNumber becomes larger. Since all my variables are shrinking I would expect each pass to be faster, however my program gets slower.

Why is this?

Full BigInt class.

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

Upvotes: 2

Views: 128

Answers (1)

yeputons
yeputons

Reputation: 9238

Apparently, sizes of dividend.bigNum.size() and temp.bigNum.size() grow exponentially on each iteration. I've added

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

right before your innermost while loop and got the following:

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

That happens in part because your BigInt(String) does not truncate heading zeros (probably should be done in createArrayList) and in part because they're doubled by createProduct in both arguments.

My recommendation for the future is to debug this issue the same way as if it were a correctness issue: print variable sizes, look at expected sizes, look at real values. Also, you can use profiler.

Upvotes: 2

Related Questions