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
divrem.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 | /* Copyright (C) 2011 William Hart 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" /* TODO: tighten this code */ void _acb_poly_div(acb_ptr Q, acb_srcptr A, slong lenA, acb_srcptr B, slong lenB, slong prec) { slong lenQ, lenB2; acb_ptr Arev, Brev; lenQ = lenA - lenB + 1; Arev = _acb_vec_init(2 * lenQ); Brev = Arev + lenQ; _acb_poly_reverse(Arev, A + (lenA - lenQ), lenQ, lenQ); if (lenB >= lenQ) { _acb_poly_reverse(Brev, B + (lenB - lenQ), lenQ, lenQ); lenB2 = lenQ; } else { _acb_poly_reverse(Brev, B, lenB, lenB); lenB2 = lenB; } _acb_poly_div_series(Q, Arev, lenQ, Brev, lenB2, lenQ, prec); _acb_poly_reverse(Q, Q, lenQ, lenQ); _acb_vec_clear(Arev, 2 * lenQ); } void _acb_poly_divrem(acb_ptr Q, acb_ptr R, acb_srcptr A, slong lenA, acb_srcptr B, slong lenB, slong prec) { const slong lenQ = lenA - lenB + 1; _acb_poly_div(Q, A, lenA, B, lenB, prec); if (lenB > 1) { if (lenQ >= lenB - 1) _acb_poly_mullow(R, Q, lenQ, B, lenB - 1, lenB - 1, prec); else _acb_poly_mullow(R, B, lenB - 1, Q, lenQ, lenB - 1, prec); _acb_vec_sub(R, A, R, lenB - 1, prec); } } void _acb_poly_rem(acb_ptr R, acb_srcptr A, slong lenA, acb_srcptr B, slong lenB, slong prec) { const slong lenQ = lenA - lenB + 1; acb_ptr Q = _acb_vec_init(lenQ); _acb_poly_divrem(Q, R, A, lenA, B, lenB, prec); _acb_vec_clear(Q, lenQ); } int acb_poly_divrem(acb_poly_t Q, acb_poly_t R, const acb_poly_t A, const acb_poly_t B, slong prec) { const slong lenA = A->length, lenB = B->length; if (lenB == 0 || acb_contains_zero(B->coeffs + lenB - 1)) { return 0; } if (lenA < lenB) { acb_poly_set(R, A); acb_poly_zero(Q); return 1; } if (Q == A || Q == B) { acb_poly_t T; acb_poly_init(T); acb_poly_divrem(T, R, A, B, prec); acb_poly_swap(Q, T); acb_poly_clear(T); return 1; } if (R == A || R == B) { acb_poly_t U; acb_poly_init(U); acb_poly_divrem(Q, U, A, B, prec); acb_poly_swap(R, U); acb_poly_clear(U); return 1; } acb_poly_fit_length(Q, lenA - lenB + 1); acb_poly_fit_length(R, lenB - 1); _acb_poly_divrem(Q->coeffs, R->coeffs, A->coeffs, lenA, B->coeffs, lenB, prec); _acb_poly_set_length(Q, lenA - lenB + 1); _acb_poly_set_length(R, lenB - 1); _acb_poly_normalise(R); return 1; } |