Tree @HEAD (Download .tar.gz)
- ..
- test
- add.c
- add_series.c
- add_si.c
- agm1_series.c
- atan_series.c
- binomial_transform.c
- binomial_transform_basecase.c
- binomial_transform_convolution.c
- borel_transform.c
- clear.c
- compose.c
- compose_divconquer.c
- compose_horner.c
- compose_series.c
- compose_series_brent_kung.c
- compose_series_horner.c
- contains.c
- contains_fmpq_poly.c
- contains_fmpz_poly.c
- cos_pi_series.c
- cos_series.c
- cosh_series.c
- cot_pi_series.c
- derivative.c
- digamma_series.c
- div_root.c
- div_series.c
- divrem.c
- elliptic_k_series.c
- elliptic_p_series.c
- equal.c
- erf_series.c
- evaluate.c
- evaluate2.c
- evaluate2_horner.c
- evaluate2_rectangular.c
- evaluate_horner.c
- evaluate_rectangular.c
- evaluate_vec_fast.c
- evaluate_vec_iter.c
- exp_pi_i_series.c
- exp_series.c
- exp_series_basecase.c
- find_roots.c
- fit_length.c
- fprintd.c
- gamma_series.c
- get_coeff_acb.c
- get_unique_fmpz_poly.c
- graeffe_transform.c
- init.c
- inlines.c
- integral.c
- interpolate_barycentric.c
- interpolate_fast.c
- interpolate_newton.c
- inv_borel_transform.c
- inv_series.c
- lambertw_series.c
- lgamma_series.c
- log1p_series.c
- log_series.c
- majorant.c
- mul.c
- mullow.c
- mullow_classical.c
- mullow_transpose.c
- mullow_transpose_gauss.c
- normalise.c
- overlaps.c
- polylog_series.c
- pow_acb_series.c
- pow_series.c
- pow_ui.c
- pow_ui_trunc_binexp.c
- powsum_one_series_sieved.c
- powsum_series_naive.c
- powsum_series_naive_threaded.c
- product_roots.c
- randtest.c
- refine_roots_durand_kerner.c
- reverse.c
- revert_series.c
- revert_series_lagrange.c
- revert_series_lagrange_fast.c
- revert_series_newton.c
- rgamma_series.c
- rising_ui_series.c
- root_bound_fujiwara.c
- root_inclusion.c
- rsqrt_series.c
- set.c
- set2_arb_poly.c
- set2_fmpq_poly.c
- set2_fmpz_poly.c
- set_coeff_acb.c
- set_coeff_si.c
- set_fmpz_poly.c
- set_length.c
- set_round.c
- set_si.c
- set_trunc.c
- set_trunc_round.c
- shift_left.c
- shift_right.c
- sin_cos_pi_series.c
- sin_cos_series.c
- sin_cos_series_basecase.c
- sin_cos_series_tangent.c
- sin_pi_series.c
- sin_series.c
- sinc_series.c
- sinh_cosh_series.c
- sinh_cosh_series_basecase.c
- sinh_cosh_series_exponential.c
- sinh_series.c
- sqrt_series.c
- sub.c
- sub_series.c
- tan_series.c
- taylor_shift.c
- taylor_shift_convolution.c
- taylor_shift_divconquer.c
- taylor_shift_horner.c
- tree.c
- validate_real_roots.c
- validate_roots.c
- valuation.c
- zeta_em_bound.c
- zeta_em_choose_param.c
- zeta_em_sum.c
- zeta_em_tail_bsplit.c
- zeta_em_tail_naive.c
- zeta_series.c
interpolate_fast.c @HEAD — raw · history · blame
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 | /* Copyright (C) 2012 Fredrik Johansson This file is part of Arb. Arb is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License (LGPL) as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. See <http://www.gnu.org/licenses/>. */ #include "acb_poly.h" void _acb_poly_interpolation_weights(acb_ptr w, acb_ptr * tree, slong len, slong prec) { acb_ptr tmp; slong i, n, height; if (len == 0) return; if (len == 1) { acb_one(w); return; } tmp = _acb_vec_init(len + 1); height = FLINT_CLOG2(len); n = WORD(1) << (height - 1); _acb_poly_mul_monic(tmp, tree[height-1], n + 1, tree[height-1] + (n + 1), (len - n + 1), prec); _acb_poly_derivative(tmp, tmp, len + 1, prec); _acb_poly_evaluate_vec_fast_precomp(w, tmp, len, tree, len, prec); for (i = 0; i < len; i++) acb_inv(w + i, w + i, prec); _acb_vec_clear(tmp, len + 1); } void _acb_poly_interpolate_fast_precomp(acb_ptr poly, acb_srcptr ys, acb_ptr * tree, acb_srcptr weights, slong len, slong prec) { acb_ptr t, u, pa, pb; slong i, pow, left; if (len == 0) return; t = _acb_vec_init(len); u = _acb_vec_init(len); for (i = 0; i < len; i++) acb_mul(poly + i, weights + i, ys + i, prec); for (i = 0; i < FLINT_CLOG2(len); i++) { pow = (WORD(1) << i); pa = tree[i]; pb = poly; left = len; while (left >= 2 * pow) { _acb_poly_mul(t, pa, pow + 1, pb + pow, pow, prec); _acb_poly_mul(u, pa + pow + 1, pow + 1, pb, pow, prec); _acb_vec_add(pb, t, u, 2 * pow, prec); left -= 2 * pow; pa += 2 * pow + 2; pb += 2 * pow; } if (left > pow) { _acb_poly_mul(t, pa, pow + 1, pb + pow, left - pow, prec); _acb_poly_mul(u, pb, pow, pa + pow + 1, left - pow + 1, prec); _acb_vec_add(pb, t, u, left, prec); } } _acb_vec_clear(t, len); _acb_vec_clear(u, len); } void _acb_poly_interpolate_fast(acb_ptr poly, acb_srcptr xs, acb_srcptr ys, slong len, slong prec) { acb_ptr * tree; acb_ptr w; tree = _acb_poly_tree_alloc(len); _acb_poly_tree_build(tree, xs, len, prec); w = _acb_vec_init(len); _acb_poly_interpolation_weights(w, tree, len, prec); _acb_poly_interpolate_fast_precomp(poly, ys, tree, w, len, prec); _acb_vec_clear(w, len); _acb_poly_tree_free(tree, len); } void acb_poly_interpolate_fast(acb_poly_t poly, acb_srcptr xs, acb_srcptr ys, slong n, slong prec) { if (n == 0) { acb_poly_zero(poly); } else { acb_poly_fit_length(poly, n); _acb_poly_set_length(poly, n); _acb_poly_interpolate_fast(poly->coeffs, xs, ys, n, prec); _acb_poly_normalise(poly); } } |