# Making Division in my BigInt method more efficient

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) {
}
else{
}
temp = divisor.multiply(two);
}

dividend= dividend.subtract(lastTemp);

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

I’m not a java guy and no idea how pros would do division like this, but used to write small amounts of assembly a long time ago…

Rather than iterating through in order it may pay to cheat with lookup tables and bit operations.

If you can test for the highest “set” bit in both the original integer and the divisor, you can maybe guess at a starting point. Bit operations and/or table lookups are computationally “cheap”.

e.g., if the highest bit set on your integer is 30 (e.g., 1,073,741,824), and the highest bit set on the divisor is 20 (e.g., 1,048,576), you know that you’re talking at least 512 for the dividend - you have 9 or more, but maybe less than 10 bits worth of magnitude difference.

In that example the answer is exactly 1024, but that’s because i only set those particular high order bits… any lower bits set on the divisor may make it lower than 1024…

So counting up from numbers below 512 is pointless at that point… you already know the number is at least 512…

Just an idea from someone who hasn’t been instructed on that stuff specifically.

edit:
in other words, use the modulus on high order bit amounts first to get a ballpark for where to “start”.

You could do a binary search, though it relies on your multiplication and comparison being relatively fast:
Let’s call the difference between the highest bit of your dividend and the highest bit of your divisior k.
set you lower bound to 2, and your upper bound to 2^k.
This runs in O(k * (multiplication time + comparison time)).
If you don’t know how to do a binary search, reply to this post and i’ll tell you.

1 Like