Division is an expensive operation for a computer to perform, compared to addition, subtraction, and even multiplication.
The exception is when dividing by powers of 2, because this can be done either with a bit shift (for a fixed-point value) or by subtracting 1 from the exponent (for a floating-point value).
In this problem, we will approximate the quotient of two numbers using only addition, multiplication, and division by powers of 2.
Consider the following identity:
1 1 c^0 c^1 c^2
--- = ----- = ----- + ----- + ----- + ...
b t-c t^1 t^2 t^3
If t is a power of 2, then the denominator of each term will be a power of 2.
Given integers a, b, and terms, approximate a/b by computing the first terms terms of the identity above, and multiplying the result by a.
Select t to be the smallest power of 2 greater than or equal to b.
|