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
713
1301
15
Returns: 0.5480398217951847
1
10000
1
Returns: 6.103515625E-5
1
10000
2
Returns: 8.481740951538086E-5
1
10000
3
Returns: 9.408412734046578E-5
1
10000
11
Returns: 9.99968565805973E-5
10
9999
20
Returns: 0.0010001000034717592
777
778
7
Returns: 0.9986685331499519
4
9
6
Returns: 0.4413278102874756
7
22
2
Returns: 0.287109375
333
512
1
Returns: 0.650390625
333
512
20
Returns: 0.650390625
14
28
5
Returns: 0.4999847412109375
3
12
9
Returns: 0.2499990463256836
1
24
19
Returns: 0.041666666666515084
17
17
3
Returns: 0.897003173828125
19
19
11
Returns: 0.999950257556668
50
50
1
Returns: 0.78125
513
513
2
Returns: 0.7509756088256836
513
513
15
Returns: 0.9999703643707892
513
513
20
Returns: 0.999999082895404
11
9998
4
Returns: 0.0010748269598298554
9
10
8
Returns: 0.8996480405330658
5983
7439
13
Returns: 0.8042747681139668
1823
9837
18
Returns: 0.1853207153579327
0
8473
20
Returns: 0.0
1
30
2
Returns: 0.033203125
2
31
1
Returns: 0.0625
28
29
3
Returns: 0.9647216796875
23
29
4
Returns: 0.7930421829223633
5001
10000
1
Returns: 0.30523681640625
5001
10000
2
Returns: 0.4241718649864197
5001
10000
15
Returns: 0.5000996376310812
5001
10000
20
Returns: 0.5000999967452651
63
65
1
Returns: 0.4921875
63
65
2
Returns: 0.73443603515625
63
65
9
Returns: 0.9675879022119923
10000
10000
20
Returns: 0.9999999934918318
1
10000
20
Returns: 9.999999934918317E-5
1000
1000
20
Returns: 1.0
798
799
20
Returns: 0.998748435544362
1
1
3
Returns: 1.0
1
8193
20
Returns: 1.220552970403139E-4
8000
8193
20
Returns: 0.9764423763225112
1
1
20
Returns: 1.0
4535
6161
20
Returns: 0.736081804901235
9999
10000
20
Returns: 0.9998999934924826
20
997
20
Returns: 0.020060180541624874
8193
8193
20
Returns: 0.9999990486512919
5
99
20
Returns: 0.050505050505044086
1
1
10
Returns: 1.0
2
999
20
Returns: 0.0020020020020020016
783
999
20
Returns: 0.7837837837837837
50
10000
20
Returns: 0.0049999999674591586
1
1
1
Returns: 1.0
4200
8400
20
Returns: 0.4999997149101312
1
8194
20
Returns: 1.2204040163186624E-4
1000
10000
20
Returns: 0.09999999934918317
3
4
2
Returns: 0.75
5
10000
20
Returns: 4.999999967459158E-4
80
4100
20
Returns: 0.019512176873762718
100
8190
20
Returns: 0.01221001221001221
4579
6789
20
Returns: 0.674473412873766
100
128
20
Returns: 0.78125
1
9999
4
Returns: 9.770321513903613E-5
1
1
5
Returns: 1.0
123
10000
20
Returns: 0.01229999991994953
54
8193
20
Returns: 0.006590986040176951
1
9000
20
Returns: 1.1111109783128265E-4
25
25
1
Returns: 0.78125
3500
7689
20
Returns: 0.4551957341656913
1
8
1
Returns: 0.125
1
1
7
Returns: 1.0
5000
10000
20
Returns: 0.4999999967459159
7
2048
20
Returns: 0.00341796875
2
9
20
Returns: 0.22222220755497427
15
16
20
Returns: 0.9375
9998
9999
20
Returns: 0.9998999834710648
1
1
2
Returns: 1.0
1
2
15
Returns: 0.5
2
3
5
Returns: 0.666015625
5
7
20
Returns: 0.7142857142857142
10
16
20
Returns: 0.625
4000
8100
19
Returns: 0.4938271604938271