Logarithmic time integer division using bit shift addition and subtraction only

user_1435959 0
Viewed 1335

I was asked to implement integer division with logarithmic time complexity using only bit shifts, additions and subtractions.

I can see how I can deal with a divisor which is a power of 2, but how can I deal with an odd divisor, such that the time remains logarithmic?

Is it even possible?

EDIT: a way to do it in a time complexity that isn't logarithmic but still better than linear will also be welcomed.

Thanks

integer-division bit-shift
2 Answers

It's just like doing long division on paper but in binary. You shift bits from the divided into an accumulator until it's at least as large as the divisor, then subtract the divisor from the accumulator and continue until you've processed all the bits all the while recording a 0 for every shift w/o a subtract and a 1 for every time you do subtract.

15/5 (1111/101)
dividend accumulator result
1111      0000       0  - can't subtract, shift
1110      0001       0  - can't subtract, shift
1100      0011       0  - can't subtract, shift
1000      0111       0  - can subtract, set 1
1000      0010       1  - can't subtract, shift
0000      0101       10 - can subtract, set 1
0000      0000       11 - we're done since we shifted 4 times

The answer is 3 (11).

The top bit of the dividend shifts into the bottom of the accumulator. The result is shifted every time the dividend/accumulator are shifted.

It's logarithmic in time for the value of the dividend, not the number of bits in the dividend.

Tony_Lee_58190

I don't know why answers are "not possible". Maybe I don't understand the question. In theory it's possible to make, but on hardware that enables parallel calculations. In "normal" computer there will be big cost of creating and managing threads. Let's say that we have division:

a/b = x

We want to calculate x in logarithmic time using only bit shifts, additions and subtractions. So we are looking x that fulfills this:

a = bx

It's possible to find this by binary searching. In each step of binary searching we have to make one multiplication and one comparison. Multiplication can be done in logarithmic time, because we can do polynomial number of sums. It's possible to use polynomial number of threads. Even sum can be done in logarithmic time by implementing adder circuit (https://en.wikipedia.org/wiki/Adder_(electronics)). Of course comparison also can be done in logarithmic time. So you can do division in logarithmic time by using polynomial number of threads.

user_151628560
Related