Published: Jun 9, 2017
Do division or power calculation without language provided operators – we see this sort of questions among algorithm problems. I wrote Addtion without +/- operators in the post about XOR related questions. “Divide without division” and “power without its operator or function” are examples as well.
Not like the addition, a division and power need to repeat. Intuitive implementations would be simply repeat subtraction or multiplication. Those calculates correctly, however, time complexity tends to be O(n). Better ways are out there.
I’m going to write a memo how to calculate effectively such Math-y stuff without exact operators to divide/power.
Problem Description - Divide without division and mod
“Given two integers, dividend and divisor, calculate division without divide and modulo operators.”
The division itself is nothing special. An answer will be an integer when the dividend is divided by divisor.
For example, given 10 (dividend) and -3 (divisor), the answer will be -3.
The idea to divide without division/modulo operators
Simple solution is count up one by one starting from zero, while subtracting the divisor from dividend. A counter is the quotient, which is the answer.
int sign = ...
int a = Math.abs(dividend);
int b = Math.abs(divisor);
int count = 0;
while (a >= b) {
a -= b;
count++;
}
return sign * count;
This solution’s performance is considered O(n), where n is the quotient. This is simple and correct, but surely can be improved.
To improve above, I should see the number a bit different way. All numbers can be expressed as:
X = x_0 * (2 ^ 0) + x_1 * (2 ^ 1) + x_2 * (2 ^ 2) + ..... + x_n * (2 ^ n)
For example, 10 is 10 * (2 ^ 0) + 1 * (2 ^ 1) + 0 * (2 ^ 2) + 1 * (2 ^ 3), and
3 is 1 * (2 ^ 0) + 1 * (2 ^ 1).
If I write how to manually calculate the division:
1 1 <- quotient
---------
1 1) 1 0 1 0
1 1
---------
1 0 0
1 1
---------
1 <-- modulo
The first step is to find where is the highest bit. While shifting divisor to the left and counting how many time to repeat, I will get the answer.
devidend: 10 = 1010 divisor: 3 = 11 count: 1 the first iteration: divisor: 11 << 1 => 110 count: 1 << 1 => 10 the second iteration divisor: 110 << 1 => 1100 (exceeds 1010) count: 10 << 1 => 100
The second step is to find what is the quotient. I’ve already learned how many times to repeat. So, I want to know each bit is zero or one.
This step goes like in the manual calculation.
1010 - 110 = 100 --> the second bit is one 100 - 11 = 1 --> the first bit is one 1 - ... (no more)
This division’s time complexity turns to O(log(n)) .
Java code for dividing number without division
The result is:
-3 228
Problem Description - Implement Power
Given two integers, x and y, implement a function (method) to
calculate x ^ y.
I believe every computer language provides a way to calculate a power out of the box. However, the problem asks the implementation without using such existing feature.
The idea to construct from/to a string with markers
Also, there’s a simple solution. Repeating multiplication y times gives me the answer. The performance of this simple solution will be O(n) (n = y).
There’s a way to improve this.
The improved version calculates x ^ (y / 2) recursively.
While returning, calculate (x ^ (y / 2)) * (x ^ (y / 2)).
If y is odd, multiply x.
y is even: y = 2n x ^ y = x ^ (2n) = (x ^ n) * (x ^ n) y is odd: y = 2n + 1 x ^ y = x ^ (2n + 1) = x * x ^ (2n) = x * (x ^ n) * (x ^ n)
This way, the time complexity goes down to O(log(n)).
Java code for constructing a binary tree from a string with markers
The result is:
1024 -512