ApproximateDivision | Topcoder Archive

Problem Statement

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.

Definition

Class:: ApproximateDivision
Method:: quotient
Parameters:: int, int, int
Returns:: double
Method signature:: double quotient(int a, int b, int terms)
(be sure your method is public)

Notes

Your return value must have an absolute or relative error less than 1e-9.

Constraints

b will be between 1 and 10000, inclusive.
a will be between 0 and b, inclusive.
terms will be between 1 and 20, inclusive.

Examples

```
2
```
```
5
```
```
2
```
```
Returns: 0.34375
```
In this case t is chosen to be 8, and therefore c is 3. The first two terms are 1/8 and 3/64.
```
7
```
```
8
```
```
5
```
```
Returns: 0.875
```
If b is a power of two, the first term is equal to exactly 1/b, and all other terms are zero.
```
1
```
```
3
```
```
10
```
```
Returns: 0.33333301544189453
```
```
1
```
```
10000
```
```
2
```
```
Returns: 8.481740951538086E-5
```
```
1
```
```
7
```
```
20
```
```
Returns: 0.14285714285714285
```
```
0
```
```
4
```
```
3
```
```
Returns: 0.0
```
```
50
```
```
50
```
```
1
```
```
Returns: 0.78125
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.