If what you want is a division method faster than division by repeated subtraction (which you posted), and that will run indefinitely when you try to divide by zero, you can implement your own version of the Goldschmidt division, and not throw an error when the divisor is zero.
The algorithm works like this:
1. Create an estimate for the factor f
2. Multiply both the dividend and the divisor by f
3. If the divisor is close enough to 1
Return the dividend
4. Else
Go back to step 1
Normally, we would need to scale down the dividend and the divisor before starting, so that 0 < divisor < 1 is satisfied. In this case, since we are going to divide by zero, there’s no need for this step. We also need to choose an arbitrary precision beyond which we consider the result good enough.
The code, with no check for divisor == 0, would be like this:
static double goldschmidt(double dividend, double divisor) {
double epsilon = 0.0000001;
while (Math.abs(1.0 - divisor) > epsilon) {
double f = 2.0 - divisor;
dividend *= f;
divisor *= f;
}
return dividend;
}
This is much faster than the division by repeated subtraction method, since it converges to the result quadratically instead of linearly. When dividing by zero, it would not really matter, since both methods won’t converge. But if you try to divide by a small number, such as 10^(-9), you can clearly see the difference.
If you don’t want the code to run indefinitely, but to return Infinity when dividing by zero, you can modify it to stop when dividend reaches Infinity:
static double goldschmidt(double dividend, double divisor) {
double epsilon = 0.0000001;
while (Math.abs(1.0 - divisor) > 0.0000001 && !Double.isInfinite(dividend)) {
double f = 2.0 - divisor;
dividend *= f;
divisor *= f;
}
return dividend;
}
If the starting values for dividend and divisor are such that dividend >= 1.0 and divisor == 0.0, you will get Infinity as a result after, at most, 2^10 iterations. That’s because the worst case is when dividend == 1 and you need to multiply it by two (f = 2.0 - 0.0) 1024 times to get to 2^1024, which is greater than Double.MAX_VALUE.
The Goldschmidt division was implemented in AMD Athlon CPUs. If you want to read about some lower level details, you can check this article:
Floating Point Division and Square Root Algorithms and Implementation
in the AMD-K7
TM
Microprocessor.
Edit:
Addressing your comments:
Note that the code for the Restoring Division method you posted iterates 2048 (2^11) times. I lowered the value of n in your code to 1024, so we could compare both methods doing the same number of iterations.
I ran both implementations 100000 times with dividend == 1, which is the worst case for Goldschmidt, and measured the running time like this:
long begin = System.nanoTime();
for (int i = 0; i < 100000; i++) {
goldschmidt(1.0, 0.0); // changed this for restoringDivision(1) to test your code
}
long end = System.nanoTime();
System.out.println(TimeUnit.NANOSECONDS.toMillis(end - begin) + "ms");
The running time was ~290ms for Goldschmidt division and ~23000ms (23 seconds) for your code. So this implementation was about 80x faster in this test. This is expected, since in one case we are doing double multiplications and in the other we are working with BigInteger.
The advantage of your implementation is that, since you are using BigInteger, you can make your result as large as BigInteger supports, while the result here is limited by Double.MAX_VALUE.
In practice, when dividing by zero, the Goldschmidt division is doubling the dividend, which is equivalent to a shift left, at each iteration, until it reaches the maximum possible value. So the equivalent using BigInteger would be:
static BigInteger divideByZero(int dividend) {
return BigInteger.valueOf(dividend)
.shiftLeft(Integer.MAX_VALUE - 1 - ceilLog2(dividend));
}
static int ceilLog2(int n) {
return (int) Math.ceil(Math.log(n) / Math.log(2));
}
The function ceilLog2() is necessary, so that the shiftLeft() will not cause an overflow. Depending on how much memory you have allocated, this will probably result in a java.lang.OutOfMemoryError: Java heap space exception. So there is a compromise to be made here:
- You can get the division simulation to run really fast, but with a result upper bound of
Double.MAX_VALUE,
or
- You can get the result to be as big as
2^(Integer.MAX_VALUE - 1), but it would probably take too much memory and time to get to that limit.
Edit 2:
Addressing your new comments:
Please note that no division is happening in your updated code. It’s just trying to find the biggest possible BigInteger
First, let us show that the Goldschmidt division degenerates into a shift left when divisor == 0:
static double goldschmidt(double dividend, double divisor) {
double epsilon = 0.0000001;
while (Math.abs(1.0 - 0.0) > 0.0000001 && !Double.isInfinite(dividend)) {
double f = 2.0 - 0.0;
dividend *= f;
divisor = 0.0 * f;
}
return dividend;
}
The factor f will always be equal to 2.0 and the first while condition will always be true. So if we eliminate the redundancies:
static double goldschmidt(double dividend, 0) {
while (!Double.isInfinite(dividend)) {
dividend *= 2.0;
}
return dividend;
}
Assuming dividend is an Integer, we can do the same multiplication using a shift left:
static int goldschmidt(int dividend) {
while (...) {
dividend = dividend << 1;
}
return dividend;
}
If the maximum value we can reach is 2^n, we need to loop n times. When dividend == 1, this is equivalent to:
static int goldschmidt(int dividend) {
return 1 << n;
}
When the dividend > 1, we need to subtract ceil(log2(dividend)) to prevent an overflow:
static int goldschmidt(int dividend) {
return dividend << (n - ceil(log2(dividend));
}
Thus showing that the Goldschmidt division is equivalent to a shift left if divisor == 0.
However, shifting the bits to the left would pad bits on the right with 0. Try running this with a small dividend and left shift it (once or twice to check the results). This thing will never get to
2^(Integer.MAX_VALUE - 1).
Now that we’ve seen that a shift left by n is equivalent to a multiplication by 2^n, let’s see how the BigInteger version works. Consider the following examples that show we will get to 2^(Integer.MAX_VALUE - 1) if there is enough memory available and the dividend is a power of 2:
For dividend = 1
BigInteger.valueOf(dividend).shiftLeft(Integer.MAX_VALUE - 1 - ceilLog2(dividend))
= BigInteger.valueOf(1).shiftLeft(Integer.MAX_VALUE - 1 - 0)
= 1 * 2^(Integer.MAX_VALUE - 1)
= 2^(Integer.MAX_VALUE - 1)
For dividend = 1024
BigInteger.valueOf(dividend).shiftLeft(Integer.MAX_VALUE - 1 - ceilLog2(dividend))
= BigInteger.valueOf(1024).shiftLeft(Integer.MAX_VALUE - 1 - 10)
= 1024 * 2^(Integer.MAX_VALUE - 1)
= 2^10 * 2^(Integer.MAX_VALUE - 1 - 10)
= 2^(Integer.MAX_VALUE - 1)
If dividend is not a power of 2, we will get as close as we can to 2^(Integer.MAX_VALUE - 1) by repeatedly doubling the dividend.