AngouriMath

Navigation

← Back to list of members

IsProvablyNoSmallRational​(System.​Double)

 Method (no overloads)

Summary

Whether Create(PeterO.Numbers.EDecimal,System.Boolean,PeterO.Numbers.EDecimal), from a machine number, provably answers the
Real it was given for x: neither its rounding onto an integer nor its
continued-fraction search can return anything else. false is no claim at all.

Remarks

What the downcasting can return. Write t for
PrecisionErrorZeroRange, B for
MaxAbsNumeratorOrDenominatorValue, P for the working precision's
digits and u = 10^(1 - P). Other than the Real itself it returns either an integer
within DowncastingTolerance of x -- excluded below by measuring
x's distance to the nearest integer, with a factor of two to spare -- or a ratio p/q,
|p|, q <= B, from FindRationalExactly(PeterO.Numbers.EDecimal,System.Int32,PeterO.Numbers.EDecimal). That runs the continued fraction
of |x|: y_0 = |x|, a_i = floor(y_i), r_i = y_i - a_i exactly,
y_(i+1) = 1/r_i rounded to the working precision, so that y_(i+1) = (1/r_i)(1 + theta) with |theta| <= u (to places, an error under 10^(-P) on a quotient over 1; to digits, an ulp);
refuses a level with a_i > B; and stops at the level n where
r_n < a_n t (1 + u), at most FloatToRationalIterCount - 1 levels
down, returning R = [a_0; a_1, ..., a_n].
How far such an answer is from x. Let rho_i = [a_i; ..., a_n], v_i = 1/r_(i-1) and
e_i = |y_i - rho_i|. Then e_n = r_n < a_n t (1 + u), and
e_(i-1) = |1/v_i - 1/rho_i| <= (e_i + u v_i) / (v_i rho_i). Every rho_i and every
y_i past the first is at least 1, so e_(i-1) <= e_i (1 + u) + u and every
e_i <= E = (B t (1 + u) + N u)(1 + u)^N for N >= n; hence
v_i >= c rho_i with c = (1 - E)/(1 + u). Since the product of the rho_i is
q, unrolling gives |x - R| <= K (a_n t (1 + u) + N u q^2) / q^2, K = c^(-N).
Within the gate below -- P >= 30, B <= 10^9, B t <= 10^(-3),
N = 100 -- E < 1.001e-3 and K < 1.12; 1.2 is used.
Which ratios those can be. The same bound with a_n <= B and q <= B is under
1/(2 q^2), so by Legendre's theorem R is a convergent p_k/q_k of |x| itself. The levels the search took are one of R's two expansions, so n <= k + 1 and
a_n is a_k, 1, or a_(k-1) + 1. And |x| - p_k/q_k is
1/(q_k^2 (x_(k+1) + q_(k-1)/q_k)) exactly, x_(k+1) the complete quotient. So the
search can return the convergent only if
x_(k+1) + q_(k-1)/q_k >= 1/(K (A t (1 + u) + N u q_k^2)),
A = min(B, max(a_k, a_(k-1) + 1)) -- a partial quotient after it near 1/(A t), a hundred
million at the defaults, where a double that is no small rational has its next quotient near its own
size. A double is m / 2^k, so its continued fraction is Euclid's algorithm on two machine
integers, run here exactly; every convergent within B is tested, with another factor of two
for the rounding of the doubles the test is made in, and one the search can return -- or a
fraction the double equals -- sends the value to the search.
The gate. The bound needs the context to round as it is assumed to: digits in decimal, no
traps, a rounding mode, and exponents where every quotient (at most 10^max(324, P)) and every
tolerance (at least t) is normal. Any other setting is left to the search.

























Angouri © 2019-2026 · Project's repo · Site's repo · Octicons · Transparency · 6003 pages online