ApproximateDivision
SRM 389 · 2008-01-24 · by legakis
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.
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.
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
Submissions are judged against all 89 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ApproximateDivision with a public method double quotient(int a, int b, int terms) · 89 test cases · 2 s / 256 MB per case