include/flint/ca_poly.h

0001 /*
0002     Copyright (C) 2020 Fredrik Johansson
0003
0004     This file is part of FLINT.
0005
0006     FLINT is free software: you can redistribute it and/or modify it under
0007     the terms of the GNU Lesser General Public License (LGPL) as published
0008     by the Free Software Foundation; either version 3 of the License, or
0009     (at your option) any later version.  See <https://www.gnu.org/licenses/>.
0010 */
0011
0012 #ifndef CA_POLY_H
0013 #define CA_POLY_H
0014
0015 #ifdef CA_POLY_INLINES_C
0016 #define CA_POLY_INLINE
0017 #else
0018 #define CA_POLY_INLINE static inline
0019 #endif
0020
0021 #include "ca_vec.h"
0022
0023 #ifdef __cplusplus
0024 extern "C" {
0025 #endif
0026
0027 /* Polynomial object */
0028
0029 /* todo: return NULL when out of bounds? */
0030 CA_POLY_INLINE ca_ptr
0031 ca_poly_coeff_ptr(ca_poly_t poly, slong i)
0032 {
0033     return poly->coeffs + i;
0034 }
0035
0036 /* Vectors of polynomials */
0037
0038 typedef struct
0039 {
0040     ca_poly_struct * entries;
0041     slong length;
0042     slong alloc;
0043 }
0044 ca_poly_vec_struct;
0045
0046 typedef ca_poly_vec_struct ca_poly_vec_t[1];
0047
0048 /* Memory management */
0049
0050 void ca_poly_init(ca_poly_t poly, ca_ctx_t ctx);
0051 void ca_poly_init2(ca_poly_t poly, slong len, ca_ctx_t ctx);
0052 void ca_poly_clear(ca_poly_t poly, ca_ctx_t ctx);
0053 void ca_poly_fit_length(ca_poly_t poly, slong len, ca_ctx_t ctx);
0054 void _ca_poly_set_length(ca_poly_t poly, slong len, ca_ctx_t ctx);
0055 void _ca_poly_normalise(ca_poly_t poly, ca_ctx_t ctx);
0056
0057 CA_POLY_INLINE void
0058 ca_poly_swap(ca_poly_t poly1, ca_poly_t poly2, ca_ctx_t FLINT_UNUSED(ctx))
0059 {
0060     FLINT_SWAP(ca_poly_struct, *poly1, *poly2);
0061 }
0062
0063 /* Assignment and simple values */
0064
0065 void ca_poly_set_ca(ca_poly_t poly, const ca_t x, ca_ctx_t ctx);
0066 void ca_poly_set_si(ca_poly_t poly, slong x, ca_ctx_t ctx);
0067
0068 CA_POLY_INLINE void
0069 ca_poly_zero(ca_poly_t poly, ca_ctx_t ctx)
0070 {
0071     _ca_poly_set_length(poly, 0, ctx);
0072 }
0073
0074 CA_POLY_INLINE void
0075 ca_poly_x(ca_poly_t poly, ca_ctx_t ctx)
0076 {
0077     ca_poly_fit_length(poly, 2, ctx);
0078     ca_zero(poly->coeffs, ctx);
0079     ca_one(poly->coeffs + 1, ctx);
0080     _ca_poly_set_length(poly, 2, ctx);
0081 }
0082
0083 CA_POLY_INLINE void
0084 ca_poly_one(ca_poly_t poly, ca_ctx_t ctx)
0085 {
0086     ca_poly_set_si(poly, 1, ctx);
0087 }
0088
0089 void ca_poly_set(ca_poly_t res, const ca_poly_t src, ca_ctx_t ctx);
0090 void ca_poly_set_fmpz_poly(ca_poly_t res, const fmpz_poly_t src, ca_ctx_t ctx);
0091 void ca_poly_set_fmpq_poly(ca_poly_t res, const fmpq_poly_t src, ca_ctx_t ctx);
0092
0093 void ca_poly_transfer(ca_poly_t res, ca_ctx_t res_ctx, const ca_poly_t src, ca_ctx_t src_ctx);
0094
0095 void ca_poly_set_coeff_ca(ca_poly_t poly, slong n, const ca_t x, ca_ctx_t ctx);
0096
0097 /* Conversions */
0098
0099 void ca_poly_get_fexpr(fexpr_t res, const ca_poly_t A, ulong flags, ca_ctx_t ctx);
0100
0101 /* Random generation */
0102
0103 void ca_poly_randtest(ca_poly_t poly, flint_rand_t state, slong len, slong depth, slong bits, ca_ctx_t ctx);
0104 void ca_poly_randtest_rational(ca_poly_t poly, flint_rand_t state, slong len, slong bits, ca_ctx_t ctx);
0105
0106 /* Input and output */
0107
0108 void ca_poly_print(const ca_poly_t poly, ca_ctx_t ctx);
0109 void ca_poly_printn(const ca_poly_t poly, slong digits, ca_ctx_t ctx);
0110
0111 /* Degree and leading coefficient */
0112
0113 int ca_poly_is_proper(const ca_poly_t poly, ca_ctx_t ctx);
0114 int ca_poly_make_monic(ca_poly_t res, const ca_poly_t poly, ca_ctx_t ctx);
0115
0116 void _ca_poly_reverse(ca_ptr res, ca_srcptr poly, slong len, slong n, ca_ctx_t ctx);
0117 void ca_poly_reverse(ca_poly_t res, const ca_poly_t poly, slong n, ca_ctx_t ctx);
0118
0119 /* Comparisons */
0120
0121 truth_t _ca_poly_check_equal(ca_srcptr poly1, slong len1, ca_srcptr poly2, slong len2, ca_ctx_t ctx);
0122 truth_t ca_poly_check_equal(const ca_poly_t poly1, const ca_poly_t poly2, ca_ctx_t ctx);
0123
0124 truth_t ca_poly_check_is_zero(const ca_poly_t poly, ca_ctx_t ctx);
0125 truth_t ca_poly_check_is_one(const ca_poly_t poly, ca_ctx_t ctx);
0126
0127 /* Arithmetic */
0128
0129 void _ca_poly_shift_left(ca_ptr res, ca_srcptr poly, slong len, slong n, ca_ctx_t ctx);
0130 void ca_poly_shift_left(ca_poly_t res, const ca_poly_t poly, slong n, ca_ctx_t ctx);
0131
0132 void _ca_poly_shift_right(ca_ptr res, ca_srcptr poly, slong len, slong n, ca_ctx_t ctx);
0133 void ca_poly_shift_right(ca_poly_t res, const ca_poly_t poly, slong n, ca_ctx_t ctx);
0134
0135 void ca_poly_neg(ca_poly_t res, const ca_poly_t src, ca_ctx_t ctx);
0136
0137 void _ca_poly_add(ca_ptr res, ca_srcptr poly1, slong len1, ca_srcptr poly2, slong len2, ca_ctx_t ctx);
0138 void ca_poly_add(ca_poly_t res, const ca_poly_t poly1, const ca_poly_t poly2, ca_ctx_t ctx);
0139
0140 void _ca_poly_sub(ca_ptr res, ca_srcptr poly1, slong len1, ca_srcptr poly2, slong len2, ca_ctx_t ctx);
0141 void ca_poly_sub(ca_poly_t res, const ca_poly_t poly1, const ca_poly_t poly2, ca_ctx_t ctx);
0142
0143 void _ca_poly_mul(ca_ptr C, ca_srcptr A, slong lenA, ca_srcptr B, slong lenB, ca_ctx_t ctx);
0144 void ca_poly_mul(ca_poly_t res, const ca_poly_t poly1, const ca_poly_t poly2, ca_ctx_t ctx);
0145
0146 CA_POLY_INLINE void
0147 ca_poly_mul_ca(ca_poly_t res, const ca_poly_t poly, const ca_t c, ca_ctx_t ctx)
0148 {
0149     ca_poly_fit_length(res, poly->length, ctx);
0150     _ca_vec_scalar_mul_ca(res->coeffs, poly->coeffs, poly->length, c, ctx);
0151     _ca_poly_set_length(res, poly->length, ctx);
0152     _ca_poly_normalise(res, ctx);
0153 }
0154
0155 CA_POLY_INLINE void
0156 ca_poly_div_ca(ca_poly_t res, const ca_poly_t poly, const ca_t c, ca_ctx_t ctx)
0157 {
0158     ca_poly_fit_length(res, poly->length, ctx);
0159     _ca_vec_scalar_div_ca(res->coeffs, poly->coeffs, poly->length, c, ctx);
0160     _ca_poly_set_length(res, poly->length, ctx);
0161     _ca_poly_normalise(res, ctx);
0162 }
0163
0164 /* todo: improve, document */
0165 CA_POLY_INLINE void
0166 ca_poly_div_fmpz(ca_poly_t res, const ca_poly_t poly, const fmpz_t c, ca_ctx_t ctx)
0167 {
0168     ca_t t;
0169     ca_init(t, ctx);
0170     ca_set_fmpz(t, c, ctx);
0171     ca_poly_div_ca(res, poly, t, ctx);
0172     ca_clear(t, ctx);
0173 }
0174
0175 void _ca_poly_mullow_same_nf(ca_ptr C, ca_srcptr A, slong Alen, ca_srcptr B, slong Blen, slong len, ca_field_t K, ca_ctx_t ctx);
0176
0177 void _ca_poly_mullow(ca_ptr C, ca_srcptr A, slong lenA, ca_srcptr B, slong lenB, slong n, ca_ctx_t ctx);
0178 void ca_poly_mullow(ca_poly_t res, const ca_poly_t poly1, const ca_poly_t poly2, slong n, ca_ctx_t ctx);
0179
0180 void _ca_poly_divrem_basecase(ca_ptr Q, ca_ptr R, ca_srcptr A, slong lenA, ca_srcptr B, slong lenB, const ca_t invB, ca_ctx_t ctx);
0181 int ca_poly_divrem_basecase(ca_poly_t Q, ca_poly_t R, const ca_poly_t A, const ca_poly_t B, ca_ctx_t ctx);
0182
0183 void _ca_poly_divrem(ca_ptr Q, ca_ptr R, ca_srcptr A, slong lenA, ca_srcptr B, slong lenB, const ca_t invB, ca_ctx_t ctx);
0184 int ca_poly_divrem(ca_poly_t Q, ca_poly_t R, const ca_poly_t A, const ca_poly_t B, ca_ctx_t ctx);
0185
0186 int ca_poly_div(ca_poly_t Q, const ca_poly_t A, const ca_poly_t B, ca_ctx_t ctx);
0187 int ca_poly_rem(ca_poly_t R, const ca_poly_t A, const ca_poly_t B, ca_ctx_t ctx);
0188
0189 void _ca_poly_pow_ui_trunc(ca_ptr res, ca_srcptr f, slong flen, ulong exp, slong len, ca_ctx_t ctx);
0190 void ca_poly_pow_ui_trunc(ca_poly_t res, const ca_poly_t poly, ulong exp, slong len, ca_ctx_t ctx);
0191
0192 void _ca_poly_pow_ui(ca_ptr res, ca_srcptr f, slong flen, ulong exp, ca_ctx_t ctx);
0193 void ca_poly_pow_ui(ca_poly_t res, const ca_poly_t poly, ulong exp, ca_ctx_t ctx);
0194
0195 /* Evaluation and composition */
0196
0197 void _ca_poly_evaluate_horner(ca_t res, ca_srcptr f, slong len, const ca_t x, ca_ctx_t ctx);
0198 void ca_poly_evaluate_horner(ca_t res, const ca_poly_t f, const ca_t a, ca_ctx_t ctx);
0199
0200 void _ca_poly_evaluate(ca_t res, ca_srcptr f, slong len, const ca_t x, ca_ctx_t ctx);
0201 void ca_poly_evaluate(ca_t res, const ca_poly_t f, const ca_t a, ca_ctx_t ctx);
0202
0203 void _ca_poly_compose(ca_ptr res, ca_srcptr poly1, slong len1, ca_srcptr poly2, slong len2, ca_ctx_t ctx);
0204 void ca_poly_compose(ca_poly_t res, const ca_poly_t poly1, const ca_poly_t poly2, ca_ctx_t ctx);
0205
0206
0207 /* Integral and derivative */
0208
0209 void _ca_poly_derivative(ca_ptr res, ca_srcptr poly, slong len, ca_ctx_t ctx);
0210 void ca_poly_derivative(ca_poly_t res, const ca_poly_t poly, ca_ctx_t ctx);
0211
0212 void _ca_poly_integral(ca_ptr res, ca_srcptr poly, slong len, ca_ctx_t ctx);
0213 void ca_poly_integral(ca_poly_t res, const ca_poly_t poly, ca_ctx_t ctx);
0214
0215 /* Greatest common divisor */
0216
0217 slong _ca_poly_gcd_euclidean(ca_ptr G, ca_srcptr A, slong lenA, ca_srcptr B, slong lenB, ca_ctx_t ctx);
0218 int ca_poly_gcd_euclidean(ca_poly_t G, const ca_poly_t A, const ca_poly_t B, ca_ctx_t ctx);
0219
0220 slong _ca_poly_gcd(ca_ptr G, ca_srcptr A, slong lenA, ca_srcptr B, slong lenB, ca_ctx_t ctx);
0221 int ca_poly_gcd(ca_poly_t G, const ca_poly_t A, const ca_poly_t B, ca_ctx_t ctx);
0222
0223 /* Power series division */
0224
0225 void _ca_poly_inv_series(ca_ptr res, ca_srcptr f, slong flen, slong len, ca_ctx_t ctx);
0226 void ca_poly_inv_series(ca_poly_t res, const ca_poly_t f, slong len, ca_ctx_t ctx);
0227
0228 void _ca_poly_div_series(ca_ptr res, ca_srcptr f, slong flen, ca_srcptr g, slong glen, slong len, ca_ctx_t ctx);
0229 void ca_poly_div_series(ca_poly_t res, const ca_poly_t f, const ca_poly_t g, slong len, ca_ctx_t ctx);
0230
0231 /* Elementary functions */
0232
0233 void _ca_poly_exp_series(ca_ptr res, ca_srcptr f, slong flen, slong len, ca_ctx_t ctx);
0234 void ca_poly_exp_series(ca_poly_t res, const ca_poly_t f, slong len, ca_ctx_t ctx);
0235
0236 void _ca_poly_log_series(ca_ptr res, ca_srcptr f, slong flen, slong len, ca_ctx_t ctx);
0237 void ca_poly_log_series(ca_poly_t res, const ca_poly_t f, slong len, ca_ctx_t ctx);
0238
0239 /* Vectors of polynomials */
0240
0241 ca_poly_struct * _ca_poly_vec_init(slong len, ca_ctx_t ctx);
0242 void ca_poly_vec_init(ca_poly_vec_t res, slong len, ca_ctx_t ctx);
0243
0244 void _ca_poly_vec_fit_length(ca_poly_vec_t vec, slong len, ca_ctx_t ctx);
0245 void ca_poly_vec_set_length(ca_poly_vec_t vec, slong len, ca_ctx_t ctx);
0246
0247 void _ca_poly_vec_clear(ca_poly_struct * v, slong len, ca_ctx_t ctx);
0248 void ca_poly_vec_clear(ca_poly_vec_t vec, ca_ctx_t ctx);
0249
0250 void ca_poly_vec_append(ca_poly_vec_t vec, const ca_poly_t f, ca_ctx_t ctx);
0251
0252 /* Roots and factorization */
0253
0254 int ca_poly_factor_squarefree(ca_t c, ca_poly_vec_t fac, ulong * exp, const ca_poly_t F, ca_ctx_t ctx);
0255 int ca_poly_squarefree_part(ca_poly_t res, const ca_poly_t poly, ca_ctx_t ctx);
0256
0257 void _ca_poly_set_roots(ca_ptr poly, ca_srcptr roots, const ulong * exp, slong len, ca_ctx_t ctx);
0258 void ca_poly_set_roots(ca_poly_t poly, ca_vec_t roots, const ulong * exp, ca_ctx_t ctx);
0259
0260 int _ca_poly_roots(ca_ptr roots, ca_srcptr poly, slong len, ca_ctx_t ctx);
0261 int ca_poly_roots(ca_vec_t roots, ulong * exp, const ca_poly_t poly, ca_ctx_t ctx);
0262
0263
0264 #ifdef __cplusplus
0265 }
0266 #endif
0267
0268 #endif