Tachyon - 1 year ago 48

Java Question

We know that we can use bitwise operators to divide any two numbers. For example:

`int result = 10 >> 1; //reult would be 5 as it's like dividing 10 by 2^1`

Is there any chance we can divide a number by 0 using bits manipulation?

`i = 1;`

while(0 * i != 10){

i++;

}

Let's assume that there is no cap on the maximum value of

`i`

So, as there is a way to do this. How can I achieve this by directly manipulating bits?

Answer

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`

.