I'm creating a custom implementation of Java's BigInteger class, with subsequent methods:
- multiply
- divide,
- add
- subtract.
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
