Challenge
Given a number x
and a precision e
, find the lowest positive integer q
such that x
can be approximated as a fraction p / q
within precision e
.
In other words, find the lowest positive integer q
such that there exists an integer p
such that abs(x - p/q) < e
.
Input
- The pair
(x, e)
wherex
is a floating-point number, ande
is a positive floating-point number. - Alternatively, a pair
(x, n)
wheren
is a nonnegative integer; thene
is implicitly defined as10**(-n)
or2**(-n)
, meaningn
is the precision in number of digits/bits.
Restricting x
to positive floating-point is acceptable.
Output
The denominator q
, which is a positive integer.
Test cases
- Whenever
e > 0.5
------------------------>1
becausex
≈ an integer - Whenever
x
is an integer ---------------->1
becausex
≈ itself (3.141592653589793, 0.2)
------------>1
becausex
≈ 3(3.141592653589793, 0.0015)
-------->7
becausex
≈ 22/7(3.141592653589793, 0.0000003)
--->113
becausex
≈ 355/113(0.41, 0.01)
------------------------------->12
for 5/12 or5
for 2/5, see Rules below
Rules
- This is code-golf, the shortest code wins!
- Although the input is "a pair", how to encode a pair is unspecified
- The type used for
x
must allow a reasonable precision - Floating-point precision errors can be ignored as long as the algorithm is correct. For instance, the output for
(0.41, 0.01)
should be12
for 5/12, but the output5
is acceptable because 0.41-2/5 gives 0.009999999999999953
5
of2/5
instead of the12
of5/12
for(0.41, 0.01)
-- because0.41-2/5
gives0.009999999999999953
. \$\endgroup\$