diff options
author | Andreas Enge <andreas.enge@inria.fr> | 2017-11-15 14:24:41 +0100 |
---|---|---|
committer | Andreas Enge <andreas.enge@inria.fr> | 2017-11-15 14:24:41 +0100 |
commit | dd32b241d83c3b58cd28815f3ee9adfd2ede7dd1 (patch) | |
tree | e0babf316b5e08eb81441eb6d92546b33a2f18e4 /src | |
parent | f5615ced969fe902a78e27dbed791724377e51e2 (diff) | |
download | mpc-git-dd32b241d83c3b58cd28815f3ee9adfd2ede7dd1.tar.gz |
rootofunity: Move the error analysis from the source code to the
documentation,
* src/rootofunity.c: Drop error analysis.
* doc/algorithms.tex" Add error analysis.
Diffstat (limited to 'src')
-rw-r--r-- | src/rootofunity.c | 41 |
1 files changed, 3 insertions, 38 deletions
diff --git a/src/rootofunity.c b/src/rootofunity.c index 9b4b7be..4b6974f 100644 --- a/src/rootofunity.c +++ b/src/rootofunity.c @@ -156,7 +156,9 @@ mpc_rootofunity (mpc_ptr rop, unsigned long n, unsigned long k, mpc_rnd_t rnd) prec = MPC_MAX_PREC(rop); - mpfr_init2 (t, 67); /* see the argument at the end of the following loop */ + /* For the error analysis justifying the following algorithm, + see algorithms.tex. */ + mpfr_init2 (t, 67); mpfr_init2 (s, 67); mpfr_init2 (c, 67); mpq_init (kn); @@ -171,45 +173,8 @@ mpc_rootofunity (mpc_ptr rop, unsigned long n, unsigned long k, mpc_rnd_t rnd) mpfr_set_prec (c, prec); mpfr_const_pi (t, MPFR_RNDN); - /* The absolute error is bounded by 0.5 ulp(t) = 2^(1-prec), - and with prec >= 2 we have 50/2^4 <= t, - so the relative error is bounded above by - 2^(1-prec)/t <= 0.64*2^(-prec); otherwise said, - |(t-pi)/t| <= 0.64*2^(-prec). */ mpfr_mul_q (t, t, kn, MPFR_RNDN); - /* We analyse mpfr_mul_q (u, t, kn, MPFR_RNDN). - |u-kn*pi| <= |kn*t-kn*pi| + 0.5 ulp(u) - = |kn*t/u| * |u| * |(t-pi)/t| + 0.5 ulp(u) - <= |kn*t/u| * 2^Exp(u) * 0.64*2^(-prec) + 0.5 ulp(u) - <= max(|kn*t/u|,1) * 1.14 ulp(u) - since 2^Exp(u)*2^(-prec) < ulp(u). - The factor |kn*t/u| is larger than 1 only if rounding down has - occurred for |u| by at most 0.5 ulp(u); with prec >= 6, the - worst case bound is then 32.5/32, - and the total error bounded by 1.16 ulp(u). */ - mpfr_sin_cos (s, c, t, MPFR_RNDN); - /* error (1.16*2^{Exp (t) - Exp (s resp. c)} + 0.5) ulp - according to Section 1.2.3 on error propagation of the sine - and cosine functions in algorithms.tex. - We have 0<t<2*pi, so Exp (t) <= 3. - Unfortunately s or c can be close to 0, but with n<2^64, - we lose at most about 64 bits: - Where the minimum of s and c over all primitive n-th roots of - unity is reached depends on n mod 4. - To simplify the argument, we will consider the 4*n-th roots of - unity, which contain the n-th roots of unity and which are - symmetrically distributed with respect to the real and imaginary - axes, so that it becomes enough to consider only s for k=1. - With n<2^64, the absolute values of all s or c are at least - sin (2 * pi * 2^(-64) / 4) > 2^(-64) of exponent at least -63. - So the error is bounded above by - (1.16*2^66+0.5) ulp < 2^67 ulp. - To obtain a more precise bound for smaller n, which is useful - especially at small precision, we may use the error bound of - (1.16*2^(3 - Exp (s or c)) + 0.5) ulp - < 2^(4 - Exp (s or c)) ulp, since Exp (s or c) is at most 0. */ - } while ( !mpfr_can_round (c, prec - (4 - mpfr_get_exp (c)), MPFR_RNDN, MPFR_RNDZ, |