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_newton.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 | /* 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" static void _interpolate_newton(acb_ptr ys, acb_srcptr xs, slong n, slong prec) { acb_t p, q, t; slong i, j; acb_init(p); acb_init(q); acb_init(t); for (i = 1; i < n; i++) { acb_set(t, ys + i - 1); for (j = i; j < n; j++) { acb_sub(p, ys + j, t, prec); acb_sub(q, xs + j, xs + j - i, prec); acb_set(t, ys + j); acb_div(ys + j, p, q, prec); } } acb_clear(p); acb_clear(q); acb_clear(t); } static void _newton_to_monomial(acb_ptr ys, acb_srcptr xs, slong n, slong prec) { acb_t t, u; slong i, j; acb_init(t); acb_init(u); for (i = n - 2; i >= 0; i--) { acb_set(t, ys + i); acb_set(ys + i, ys + i + 1); for (j = i + 1; j < n - 1; j++) { acb_mul(u, ys + j, xs + i, prec); acb_sub(ys + j, ys + j + 1, u, prec); } acb_mul(u, ys + n - 1, xs + i, prec); acb_sub(ys + n - 1, t, u, prec); } _acb_poly_reverse(ys, ys, n, n); acb_clear(t); acb_clear(u); } void _acb_poly_interpolate_newton(acb_ptr poly, acb_srcptr xs, acb_srcptr ys, slong n, slong prec) { if (n == 1) { acb_set(poly, ys); } else { _acb_vec_set(poly, ys, n); _interpolate_newton(poly, xs, n, prec); while (n > 0 && acb_is_zero(poly + n - 1)) n--; _newton_to_monomial(poly, xs, n, prec); } } void acb_poly_interpolate_newton(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_newton(poly->coeffs, xs, ys, n, prec); _acb_poly_normalise(poly); } } |