Hello,
I’ve been tasked in my Computer Science class with creating a custom implementation of Java’s BigInteger class, with subsequent methods: multiply, divide,add and subtract. I’m currently on the last portion, division wherein lies my problem.
private BigInt createQuotient (BigInt dividend, BigInt divisor){
divisor.isNegative = false;
dividend.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;
}
This current block of code is designed to represent 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.
TLDR
The code works very well but slows down significantly once bigger numbers are introduced. I have been testing this code for the past couple of days with no progress being made. I would prefer not to rewrite all of the underlying methods if possible so I would very much appreciate it if someone could help me optimize this method.
Here’s a link to the full code: