Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2026-11-07 10:15:34 

0001 /*
0002     Copyright (C) 2011, 2012 Sebastian Pancratz
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 PADIC_POLY_H
0013 #define PADIC_POLY_H
0014 
0015 #ifdef PADIC_POLY_INLINES_C
0016 #define PADIC_POLY_INLINE
0017 #else
0018 #define PADIC_POLY_INLINE static inline
0019 #endif
0020 
0021 #include "fmpq_types.h"
0022 #include "padic_types.h"
0023 #include "fmpz.h"
0024 
0025 #ifdef __cplusplus
0026 extern "C" {
0027 #endif
0028 
0029 /*  Helper functions  ********************************************************/
0030 
0031 /*
0032     Returns the minimum $p$-adic valuation of \code{(vec, len)},
0033     assuming this fits into a \code{signed long}.
0034 
0035     If \code{len} is zero, returns $0$.
0036  */
0037 PADIC_POLY_INLINE slong _fmpz_vec_ord_p(const fmpz *vec, slong len, const fmpz_t p)
0038 {
0039     if (len == 0)
0040     {
0041         return 0;
0042     }
0043     else
0044     {
0045         fmpz_t t;
0046         slong i, min = WORD_MAX, v;
0047 
0048         fmpz_init(t);
0049         for (i = 0; (min > 0) && (i < len); i++)
0050         {
0051             if (!fmpz_is_zero(vec + i))
0052             {
0053                 v   = fmpz_remove(t, vec + i, p);
0054                 min = FLINT_MIN(min, v);
0055             }
0056         }
0057         fmpz_clear(t);
0058         return (min < WORD_MAX) ? min : 0;
0059     }
0060 }
0061 
0062 /*  Memory management  *******************************************************/
0063 
0064 void padic_poly_init(padic_poly_t poly);
0065 
0066 void padic_poly_init2(padic_poly_t poly, slong alloc, slong prec);
0067 
0068 void padic_poly_clear(padic_poly_t poly);
0069 
0070 void padic_poly_realloc(padic_poly_t poly, slong alloc, const fmpz_t p);
0071 
0072 void padic_poly_fit_length(padic_poly_t poly, slong len);
0073 
0074 PADIC_POLY_INLINE
0075 void _padic_poly_set_length(padic_poly_t poly, slong len)
0076 {
0077     if (poly->length > len)
0078     {
0079         slong i;
0080 
0081         for (i = len; i < poly->length; i++)
0082             _fmpz_demote(poly->coeffs + i);
0083     }
0084     poly->length = len;
0085 }
0086 
0087 void _padic_poly_normalise(padic_poly_t poly);
0088 
0089 void _padic_poly_canonicalise(fmpz *poly, slong *v, slong len, const fmpz_t p);
0090 
0091 void padic_poly_canonicalise(padic_poly_t poly, const fmpz_t p);
0092 
0093 void padic_poly_reduce(padic_poly_t poly, const padic_ctx_t ctx);
0094 
0095 PADIC_POLY_INLINE
0096 void padic_poly_truncate(padic_poly_t poly, slong n, const fmpz_t p)
0097 {
0098     if (poly->length > n)
0099     {
0100         slong i;
0101 
0102         for (i = n; i < poly->length; i++)
0103             _fmpz_demote(poly->coeffs + i);
0104         poly->length = n;
0105         _padic_poly_normalise(poly);
0106         padic_poly_canonicalise(poly, p);
0107     }
0108 }
0109 
0110 /*  Polynomial parameters  ***************************************************/
0111 
0112 PADIC_POLY_INLINE slong padic_poly_degree(const padic_poly_t poly)
0113 {
0114     return poly->length - 1;
0115 }
0116 
0117 PADIC_POLY_INLINE slong padic_poly_length(const padic_poly_t poly)
0118 {
0119     return poly->length;
0120 }
0121 
0122 PADIC_POLY_INLINE slong padic_poly_val(const padic_poly_t poly)
0123 {
0124     return poly->val;
0125 }
0126 
0127 #define padic_poly_val(poly)   ((poly)->val)
0128 
0129 #define padic_poly_prec(poly)  ((poly)->N)
0130 
0131 /*  Randomisation  ***********************************************************/
0132 
0133 void padic_poly_randtest(padic_poly_t f, flint_rand_t state,
0134                          slong len, const padic_ctx_t ctx);
0135 
0136 void padic_poly_randtest_not_zero(padic_poly_t f, flint_rand_t state,
0137                                   slong len, const padic_ctx_t ctx);
0138 
0139 void padic_poly_randtest_val(padic_poly_t f, flint_rand_t state,
0140                              slong val, slong len, const padic_ctx_t ctx);
0141 
0142 /*  Assignment and basic manipulation  ***************************************/
0143 
0144 void padic_poly_set(padic_poly_t poly1, const padic_poly_t poly2,
0145                     const padic_ctx_t ctx);
0146 
0147 void padic_poly_set_padic(padic_poly_t poly, const padic_t x,
0148                           const padic_ctx_t ctx);
0149 
0150 void padic_poly_set_si(padic_poly_t poly, slong x, const padic_ctx_t ctx);
0151 
0152 void padic_poly_set_ui(padic_poly_t poly, ulong x, const padic_ctx_t ctx);
0153 
0154 void padic_poly_set_fmpz(padic_poly_t poly, const fmpz_t x,
0155                          const padic_ctx_t ctx);
0156 
0157 void padic_poly_set_fmpq(padic_poly_t poly, const fmpq_t x,
0158                          const padic_ctx_t ctx);
0159 
0160 void padic_poly_set_fmpz_poly(padic_poly_t rop, const fmpz_poly_t op,
0161                               const padic_ctx_t ctx);
0162 
0163 void padic_poly_set_fmpq_poly(padic_poly_t rop,
0164                               const fmpq_poly_t op, const padic_ctx_t ctx);
0165 
0166 int padic_poly_get_fmpz_poly(fmpz_poly_t rop, const padic_poly_t op,
0167                              const padic_ctx_t ctx);
0168 
0169 void padic_poly_get_fmpq_poly(fmpq_poly_t rop,
0170                               const padic_poly_t op, const padic_ctx_t ctx);
0171 
0172 PADIC_POLY_INLINE void padic_poly_zero(padic_poly_t poly)
0173 {
0174     _padic_poly_set_length(poly, 0);
0175     poly->val = 0;
0176 }
0177 
0178 PADIC_POLY_INLINE void padic_poly_one(padic_poly_t poly)
0179 {
0180     if (padic_poly_prec(poly) > 0)
0181     {
0182         padic_poly_fit_length(poly, 1);
0183         fmpz_one(poly->coeffs);
0184         _padic_poly_set_length(poly, 1);
0185         poly->val = 0;
0186     }
0187     else
0188     {
0189         padic_poly_zero(poly);
0190     }
0191 }
0192 
0193 void padic_poly_swap(padic_poly_t poly1, padic_poly_t poly2);
0194 
0195 /*  Getting and setting coefficients  ****************************************/
0196 
0197 void padic_poly_get_coeff_padic(padic_t c, const padic_poly_t poly, slong n,
0198                                            const padic_ctx_t ctx);
0199 
0200 void padic_poly_set_coeff_padic(padic_poly_t poly, slong n, const padic_t c,
0201                                                 const padic_ctx_t ctx);
0202 
0203 /*  Comparison  **************************************************************/
0204 
0205 int padic_poly_equal(const padic_poly_t poly1, const padic_poly_t poly2);
0206 
0207 PADIC_POLY_INLINE int padic_poly_is_zero(const padic_poly_t poly)
0208 {
0209     return poly->length == 0;
0210 }
0211 
0212 PADIC_POLY_INLINE int padic_poly_is_one(const padic_poly_t poly)
0213 {
0214     return (poly->length == 1) && fmpz_is_one(poly->coeffs) &&
0215            (poly->val == 0);
0216 }
0217 
0218 /*  Addition and subtraction  ************************************************/
0219 
0220 void _padic_poly_add(fmpz *rop, slong *rval, slong N,
0221                      const fmpz *op1, slong val1, slong len1, slong FLINT_UNUSED(N1),
0222                      const fmpz *op2, slong val2, slong len2, slong FLINT_UNUSED(N2),
0223                      const padic_ctx_t ctx);
0224 
0225 void padic_poly_add(padic_poly_t f,
0226                     const padic_poly_t g, const padic_poly_t h,
0227                     const padic_ctx_t ctx);
0228 
0229 void _padic_poly_sub(fmpz *rop, slong *rval, slong N,
0230                      const fmpz *op1, slong val1, slong len1, slong FLINT_UNUSED(N1),
0231                      const fmpz *op2, slong val2, slong len2, slong FLINT_UNUSED(N2),
0232                      const padic_ctx_t ctx);
0233 
0234 void padic_poly_sub(padic_poly_t f,
0235                     const padic_poly_t g, const padic_poly_t h,
0236                     const padic_ctx_t ctx);
0237 
0238 void padic_poly_neg(padic_poly_t f, const padic_poly_t g,
0239                     const padic_ctx_t ctx);
0240 
0241 /*  Scalar multiplication and division  **************************************/
0242 
0243 void _padic_poly_scalar_mul_padic(fmpz *rop, slong *rval, slong N,
0244                                   const fmpz *op, slong val, slong len,
0245                                   const padic_t c, const padic_ctx_t ctx);
0246 
0247 void padic_poly_scalar_mul_padic(padic_poly_t rop, const padic_poly_t op,
0248                                  const padic_t c, const padic_ctx_t ctx);
0249 
0250 /*  Multiplication  **********************************************************/
0251 
0252 void _padic_poly_mul(fmpz *rop, slong *rval, slong N,
0253                      const fmpz *op1, slong val1, slong len1,
0254                      const fmpz *op2, slong val2, slong len2,
0255                      const padic_ctx_t ctx);
0256 
0257 void padic_poly_mul(padic_poly_t res,
0258                     const padic_poly_t poly1, const padic_poly_t poly2,
0259                     const padic_ctx_t ctx);
0260 
0261 /*  Powering  ****************************************************************/
0262 
0263 void _padic_poly_pow(fmpz *rop, slong *rval, slong N,
0264                      const fmpz *op, slong val, slong len, ulong e,
0265                      const padic_ctx_t ctx);
0266 
0267 void padic_poly_pow(padic_poly_t rop, const padic_poly_t op, ulong e,
0268                     const padic_ctx_t ctx);
0269 
0270 /*  Series inversion  ********************************************************/
0271 
0272 void padic_poly_inv_series(padic_poly_t g, const padic_poly_t f, slong n,
0273                            const padic_ctx_t ctx);
0274 
0275 /*  Derivative  **************************************************************/
0276 
0277 void _padic_poly_derivative(fmpz *rop, slong *rval, slong N,
0278                             const fmpz *op, slong val, slong len,
0279                             const padic_ctx_t ctx);
0280 
0281 void padic_poly_derivative(padic_poly_t rop,
0282                            const padic_poly_t op, const padic_ctx_t ctx);
0283 
0284 /*  Shifting  ****************************************************************/
0285 
0286 void padic_poly_shift_left(padic_poly_t rop, const padic_poly_t op, slong n,
0287                            const padic_ctx_t ctx);
0288 
0289 void padic_poly_shift_right(padic_poly_t rop, const padic_poly_t op, slong n,
0290                             const padic_ctx_t ctx);
0291 
0292 /*  Evaluation  **************************************************************/
0293 
0294 void _padic_poly_evaluate_padic(fmpz_t u, slong *v, slong N,
0295                                 const fmpz *poly, slong val, slong len,
0296                                 const fmpz_t a, slong b, const padic_ctx_t ctx);
0297 
0298 void padic_poly_evaluate_padic(padic_t y, const padic_poly_t poly,
0299                                           const padic_t a, const padic_ctx_t ctx);
0300 
0301 /*  Composition  *************************************************************/
0302 
0303 void _padic_poly_compose(fmpz *rop, slong *rval, slong N,
0304                          const fmpz *op1, slong val1, slong len1,
0305                          const fmpz *op2, slong val2, slong len2,
0306                          const padic_ctx_t ctx);
0307 
0308 void padic_poly_compose(padic_poly_t rop,
0309                         const padic_poly_t op1, const padic_poly_t op2,
0310                         const padic_ctx_t ctx);
0311 
0312 void _padic_poly_compose_pow(fmpz *rop, slong *rval, slong N,
0313                              const fmpz *op, slong val, slong len, slong k,
0314                              const padic_ctx_t ctx);
0315 
0316 void padic_poly_compose_pow(padic_poly_t rop, const padic_poly_t op, slong k,
0317                             const padic_ctx_t ctx);
0318 
0319 /*  Input and output  ********************************************************/
0320 
0321 #ifdef FLINT_HAVE_FILE
0322 int _padic_poly_fprint(FILE * file, const fmpz * poly, slong val, slong len, const padic_ctx_t ctx);
0323 int padic_poly_fprint(FILE * file, const padic_poly_t poly, const padic_ctx_t ctx);
0324 int _padic_poly_fprint_pretty(FILE * file, const fmpz * poly, slong len, slong val, const char * var, const padic_ctx_t ctx);
0325 int padic_poly_fprint_pretty(FILE * file, const padic_poly_t poly, const char * var, const padic_ctx_t ctx);
0326 #endif
0327 
0328 int _padic_poly_print(const fmpz * poly, slong val, slong len, const padic_ctx_t ctx);
0329 int padic_poly_print(const padic_poly_t poly, const padic_ctx_t ctx);
0330 int _padic_poly_print_pretty(const fmpz * poly, slong len, slong val, const char * var, const padic_ctx_t ctx);
0331 int padic_poly_print_pretty(const padic_poly_t poly, const char * var, const padic_ctx_t ctx);
0332 
0333 int padic_poly_debug(const padic_poly_t poly);
0334 
0335 /*  Testing  *****************************************************************/
0336 
0337 int _padic_poly_is_canonical(const fmpz *op, slong val, slong len,
0338                              const padic_ctx_t ctx);
0339 
0340 int padic_poly_is_canonical(const padic_poly_t op, const padic_ctx_t ctx);
0341 
0342 int _padic_poly_is_reduced(const fmpz *op, slong val, slong len, slong N,
0343                            const padic_ctx_t ctx);
0344 
0345 int padic_poly_is_reduced(const padic_poly_t op, const padic_ctx_t ctx);
0346 
0347 #ifdef __cplusplus
0348 }
0349 #endif
0350 
0351 #endif
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!