Math Without Operator To Do It

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

Resources

Latest Posts

Setting Up GCP Instance for Deep Learning

This post is going to be very different from what I write here. The content is a memo how I create a GCP (Google Cloud Platform) instance for Deep Learning. While I study algorithm stuff, I also have been studying Deep Learning. In my early days, I tried to train my Deep Learning model only on a laptop. My laptop is 2012 model MacBook Pro, so I would say it is reasonably fast. However, when it comes to Deep Learning, the training was quite painful on the such machine. Often, I ran the training over night to get a disappointed result. Still, I didn’t use any of pricey cloud environment since it was my personal study unrelated to my day job. I wanted to save money.

Complete Binary Tree

Problems which ask a binary tree traverse, add/delete nodes, etc. are popular in algorithm questions. The binary trees are often just a binary tree or binary search tree. Sometimes, the problem pinpoints a particular type of a binary tree, for example, a balanced binary tree or complete binary tree.

Catalan number

What is Catalan number ? The Catalan number belongs to the domain of combinatorial mathematics. It is a sequence of natural numbers such that: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, ... The sequence appears in counting problems. Wikipedia has the details about the sequence: Catalan Number.