include/flint/gr_ore_poly.h

0001 /*
0002     Copyright (C) 2025 Ricardo Buring
0003     Copyright (C) 2025 Marc Mezzarobba
0004
0005     This file is part of FLINT.
0006
0007     FLINT is free software: you can redistribute it and/or modify it under
0008     the terms of the GNU Lesser General Public License (LGPL) as published
0009     by the Free Software Foundation; either version 3 of the License, or
0010     (at your option) any later version.  See <https://www.gnu.org/licenses/>.
0011 */
0012
0013 #ifndef GR_ORE_POLY_H
0014 #define GR_ORE_POLY_H
0015
0016 #ifdef GR_ORE_POLY_INLINES_C
0017 #define GR_ORE_POLY_INLINE
0018 #else
0019 #define GR_ORE_POLY_INLINE static inline
0020 #endif
0021
0022 #include "gr.h"
0023
0024 #ifdef __cplusplus
0025 extern "C" {
0026 #endif
0027
0028 /* Ore polynomial rings */
0029
0030 typedef enum {
0031     ORE_ALGEBRA_CUSTOM,
0032     ORE_ALGEBRA_COMMUTATIVE,
0033     ORE_ALGEBRA_DERIVATIVE,
0034     ORE_ALGEBRA_EULER_DERIVATIVE,
0035     ORE_ALGEBRA_FORWARD_SHIFT,
0036     ORE_ALGEBRA_FORWARD_DIFFERENCE,
0037     ORE_ALGEBRA_BACKWARD_SHIFT,
0038     ORE_ALGEBRA_BACKWARD_DIFFERENCE,
0039     ORE_ALGEBRA_Q_SHIFT,
0040     ORE_ALGEBRA_MAHLER,
0041     /* todo: q-derivative? general substitution?... */
0042     ORE_ALGEBRA_FROBENIUS,
0043
0044     ORE_POLY_NUM_ALGEBRAS
0045 }
0046 ore_algebra_t;
0047
0048 ore_algebra_t ore_algebra_randtest(flint_rand_t state);
0049
0050 /* Compatible with gr_poly_struct */
0051 typedef struct
0052 {
0053     gr_ptr coeffs;
0054     slong alloc;
0055     slong length;
0056 }
0057 gr_ore_poly_struct;
0058
0059 typedef gr_ore_poly_struct gr_ore_poly_t[1];
0060
0061 typedef gr_ctx_struct gr_ore_poly_ctx_struct;
0062
0063 typedef gr_ore_poly_ctx_struct gr_ore_poly_ctx_t[1];
0064
0065 typedef int (* gr_ore_poly_sigma_delta_t) (gr_ptr, gr_ptr, gr_srcptr, gr_ore_poly_ctx_struct *);
0066
0067 typedef struct
0068 {
0069     slong base_var;
0070     gr_ptr sigma_x;
0071     union {
0072         gr_ptr q;
0073         slong mahler_base;
0074     };
0075 }
0076 gr_ore_poly_ore_data_t;
0077
0078 /* Compatible with polynomial_ctx_t */
0079 typedef struct
0080 {
0081     gr_ctx_struct * base_ring;
0082     slong degree_limit;
0083     char * var;
0084     ore_algebra_t which_algebra;
0085     gr_ore_poly_sigma_delta_t sigma_delta;
0086     void * ore_data;
0087 }
0088 _gr_ore_poly_ctx_struct;
0089
0090 #define GR_ORE_POLY_CTX(ring_ctx) ((_gr_ore_poly_ctx_struct *)((ring_ctx)))
0091 #define GR_ORE_POLY_ELEM_CTX(ring_ctx) (GR_ORE_POLY_CTX(ring_ctx)->base_ring)
0092 #define GR_ORE_POLY_ORE_DATA(ring_ctx) ((gr_ore_poly_ore_data_t *)(GR_ORE_POLY_CTX(ring_ctx)->ore_data))
0093
0094 GR_ORE_POLY_INLINE void *
0095 gr_ore_poly_ctx_data_ptr(gr_ore_poly_ctx_t ctx)
0096 {
0097     return GR_ORE_POLY_CTX(ctx)->ore_data;
0098 }
0099
0100 /* Context object */
0101
0102 void gr_ctx_init_gr_ore_poly(gr_ctx_t ctx, gr_ctx_t base_ring, slong base_var, const ore_algebra_t which_algebra);
0103
0104 void gr_ore_poly_ctx_init(gr_ore_poly_ctx_t ctx, gr_ctx_t base_ring, slong base_var, const ore_algebra_t which_algebra);
0105 int gr_ore_poly_ctx_init_q_shift(gr_ore_poly_ctx_t ctx, gr_ctx_t base_ring, slong base_var, gr_srcptr q);
0106 int gr_ore_poly_ctx_init_mahler(gr_ore_poly_ctx_t ctx, gr_ctx_t base_ring, slong base_var, slong mahler_base);
0107 void gr_ore_poly_ctx_init_custom(gr_ore_poly_ctx_t ctx, gr_ctx_t base_ring, const gr_ore_poly_sigma_delta_t sigma_delta, void * ore_data);
0108 void gr_ore_poly_ctx_clear(gr_ore_poly_ctx_t ctx);
0109
0110 void gr_ore_poly_ctx_init_randtest(gr_ore_poly_ctx_t ctx, flint_rand_t state, gr_ctx_t base_ring);
0111 void gr_ore_poly_ctx_init_randtest2(gr_ctx_t base_ring, gr_ore_poly_ctx_t ctx, flint_rand_t state);
0112
0113 WARN_UNUSED_RESULT int _gr_ore_poly_ctx_set_gen_name(gr_ctx_t ctx, const char * s);
0114 WARN_UNUSED_RESULT int _gr_ore_poly_ctx_set_gen_names(gr_ctx_t ctx, const char ** s);
0115 WARN_UNUSED_RESULT int gr_ore_poly_gens_recursive(gr_vec_t vec, gr_ore_poly_ctx_t ctx);
0116
0117 int gr_ore_poly_ctx_write(gr_stream_t out, gr_ore_poly_ctx_t ctx);
0118
0119 truth_t gr_ore_poly_ctx_is_ring(gr_ore_poly_ctx_t ctx);
0120 truth_t gr_ore_poly_ctx_is_zero_ring(gr_ore_poly_ctx_t ctx);
0121 truth_t gr_ore_poly_ctx_is_commutative_ring(gr_ore_poly_ctx_t ctx);
0122 truth_t gr_ore_poly_ctx_is_integral_domain(gr_ore_poly_ctx_t ctx);
0123 truth_t gr_ore_poly_ctx_is_threadsafe(gr_ore_poly_ctx_t ctx);
0124
0125 /* Memory management */
0126
0127 void gr_ore_poly_init(gr_ore_poly_t poly, gr_ore_poly_ctx_t ctx);
0128 void gr_ore_poly_init2(gr_ore_poly_t poly, slong len, gr_ore_poly_ctx_t ctx);
0129 void gr_ore_poly_clear(gr_ore_poly_t poly, gr_ore_poly_ctx_t ctx);
0130
0131 GR_ORE_POLY_INLINE gr_ptr
0132 gr_ore_poly_coeff_ptr(gr_ore_poly_t poly, slong i, gr_ore_poly_ctx_t ctx)
0133 {
0134     return GR_ENTRY(poly->coeffs, i, GR_ORE_POLY_ELEM_CTX(ctx)->sizeof_elem);
0135 }
0136
0137 GR_ORE_POLY_INLINE gr_srcptr
0138 gr_ore_poly_coeff_srcptr(const gr_ore_poly_t poly, slong i, gr_ore_poly_ctx_t ctx)
0139 {
0140     return GR_ENTRY(poly->coeffs, i, GR_ORE_POLY_ELEM_CTX(ctx)->sizeof_elem);
0141 }
0142
0143 GR_ORE_POLY_INLINE slong gr_ore_poly_length(const gr_ore_poly_t poly, gr_ore_poly_ctx_t FLINT_UNUSED(ctx))
0144 {
0145     return poly->length;
0146 }
0147
0148 GR_ORE_POLY_INLINE void
0149 gr_ore_poly_swap(gr_ore_poly_t poly1, gr_ore_poly_t poly2, gr_ore_poly_ctx_t FLINT_UNUSED(ctx))
0150 {
0151     FLINT_SWAP(gr_ore_poly_struct, *poly1, *poly2);
0152 }
0153
0154 GR_ORE_POLY_INLINE void
0155 gr_ore_poly_set_shallow(gr_ore_poly_t res, const gr_ore_poly_t x, const gr_ore_poly_ctx_t FLINT_UNUSED(ctx))
0156 {
0157     *res = *x;
0158 }
0159
0160 void gr_ore_poly_fit_length(gr_ore_poly_t poly, slong len, gr_ore_poly_ctx_t ctx);
0161 void _gr_ore_poly_set_length(gr_ore_poly_t poly, slong len, gr_ore_poly_ctx_t ctx);
0162 void _gr_ore_poly_normalise(gr_ore_poly_t poly, gr_ore_poly_ctx_t ctx);
0163
0164 /* Basic manipulation */
0165
0166 WARN_UNUSED_RESULT int gr_ore_poly_set(gr_ore_poly_t res, const gr_ore_poly_t src, gr_ore_poly_ctx_t ctx);
0167
0168 WARN_UNUSED_RESULT int gr_ore_poly_truncate(gr_ore_poly_t poly, const gr_ore_poly_t src, slong newlen, gr_ore_poly_ctx_t ctx);
0169
0170 GR_ORE_POLY_INLINE WARN_UNUSED_RESULT int
0171 gr_ore_poly_zero(gr_ore_poly_t poly, gr_ore_poly_ctx_t ctx)
0172 {
0173     _gr_ore_poly_set_length(poly, 0, ctx);
0174     return GR_SUCCESS;
0175 }
0176
0177 WARN_UNUSED_RESULT int gr_ore_poly_one(gr_ore_poly_t poly, gr_ore_poly_ctx_t ctx);
0178 WARN_UNUSED_RESULT int gr_ore_poly_neg_one(gr_ore_poly_t poly, gr_ore_poly_ctx_t ctx);
0179 WARN_UNUSED_RESULT int gr_ore_poly_gen(gr_ore_poly_t poly, gr_ore_poly_ctx_t ctx);
0180
0181 truth_t _gr_ore_poly_equal(gr_srcptr poly1, slong len1, gr_srcptr poly2, slong len2, gr_ore_poly_ctx_t ctx);
0182 truth_t gr_ore_poly_equal(const gr_ore_poly_t poly1, const gr_ore_poly_t poly2, gr_ore_poly_ctx_t ctx);
0183
0184 truth_t gr_ore_poly_is_zero(const gr_ore_poly_t poly, gr_ore_poly_ctx_t ctx);
0185 truth_t gr_ore_poly_is_one(const gr_ore_poly_t poly, gr_ore_poly_ctx_t ctx);
0186 truth_t gr_ore_poly_is_gen(const gr_ore_poly_t poly, gr_ore_poly_ctx_t ctx);
0187
0188 /* Input and output */
0189
0190 int _gr_ore_poly_write(gr_stream_t out, gr_srcptr poly, slong len, gr_ore_poly_ctx_t ctx);
0191 int gr_ore_poly_write(gr_stream_t out, const gr_ore_poly_t poly, gr_ore_poly_ctx_t ctx);
0192 int _gr_ore_poly_get_str(char ** res, gr_srcptr f, slong len, gr_ore_poly_ctx_t ctx);
0193 int gr_ore_poly_get_str(char ** res, const gr_ore_poly_t poly, gr_ore_poly_ctx_t ctx);
0194 int _gr_ore_poly_set_str(gr_ptr res, const char * s, slong len, gr_ore_poly_ctx_t ctx);
0195 int gr_ore_poly_set_str(gr_ore_poly_t res, const char * s, gr_ore_poly_ctx_t ctx);
0196 int gr_ore_poly_print(const gr_ore_poly_t poly, gr_ore_poly_ctx_t ctx);
0197
0198 /* Random generation */
0199
0200 int gr_ore_poly_randtest(gr_ore_poly_t poly, flint_rand_t state, slong len, gr_ore_poly_ctx_t ctx);
0201
0202 GR_ORE_POLY_INLINE WARN_UNUSED_RESULT int
0203 _gr_ore_poly_randtest_default(gr_ore_poly_t res, flint_rand_t state, gr_ore_poly_ctx_t ctx)
0204 {
0205     return gr_ore_poly_randtest(res, state, n_randint(state, 5), ctx);
0206 }
0207
0208 /* Constants */
0209
0210 WARN_UNUSED_RESULT int gr_ore_poly_set_si(gr_ore_poly_t poly, slong x, gr_ore_poly_ctx_t ctx);
0211 WARN_UNUSED_RESULT int gr_ore_poly_set_ui(gr_ore_poly_t poly, ulong x, gr_ore_poly_ctx_t ctx);
0212 WARN_UNUSED_RESULT int gr_ore_poly_set_fmpz(gr_ore_poly_t poly, const fmpz_t x, gr_ore_poly_ctx_t ctx);
0213 WARN_UNUSED_RESULT int gr_ore_poly_set_fmpq(gr_ore_poly_t poly, const fmpq_t x, gr_ore_poly_ctx_t ctx);
0214 WARN_UNUSED_RESULT int gr_ore_poly_set_other(gr_ore_poly_t poly, gr_srcptr x, gr_ctx_t x_ctx, gr_ore_poly_ctx_t ctx);
0215
0216 /* Action on the base ring */
0217
0218 WARN_UNUSED_RESULT int sigma_delta_unable(gr_ptr sigma, gr_ptr delta, gr_srcptr a, gr_ore_poly_ctx_struct * ctx);
0219 WARN_UNUSED_RESULT int sigma_delta_commutative(gr_ptr sigma, gr_ptr delta, gr_srcptr a, gr_ore_poly_ctx_struct * ctx);
0220 WARN_UNUSED_RESULT int sigma_delta_derivative(gr_ptr sigma, gr_ptr delta, gr_srcptr a, gr_ore_poly_ctx_struct * ctx);
0221 WARN_UNUSED_RESULT int sigma_delta_euler_derivative(gr_ptr sigma, gr_ptr delta, gr_srcptr a, gr_ore_poly_ctx_struct * ctx);
0222 WARN_UNUSED_RESULT int sigma_delta_forward_shift(gr_ptr sigma, gr_ptr delta, gr_srcptr a, gr_ore_poly_ctx_struct * ctx);
0223 WARN_UNUSED_RESULT int sigma_delta_backward_shift(gr_ptr sigma, gr_ptr delta, gr_srcptr a, gr_ore_poly_ctx_struct * ctx);
0224 WARN_UNUSED_RESULT int sigma_delta_forward_difference(gr_ptr sigma, gr_ptr delta, gr_srcptr a, gr_ore_poly_ctx_struct * ctx);
0225 WARN_UNUSED_RESULT int sigma_delta_backward_difference(gr_ptr sigma, gr_ptr delta, gr_srcptr a, gr_ore_poly_ctx_struct * ctx);
0226 WARN_UNUSED_RESULT int sigma_delta_compose(gr_ptr sigma, gr_ptr delta, gr_srcptr a, gr_ore_poly_ctx_struct * ctx);
0227 WARN_UNUSED_RESULT int sigma_delta_mahler(gr_ptr sigma, gr_ptr delta, gr_srcptr a, gr_ore_poly_ctx_struct * ctx);
0228 WARN_UNUSED_RESULT int sigma_delta_frobenius(gr_ptr sigma, gr_ptr delta, gr_srcptr a, gr_ore_poly_ctx_struct * ctx);
0229
0230 GR_ORE_POLY_INLINE WARN_UNUSED_RESULT int
0231 gr_ore_poly_sigma_delta(gr_ptr sigma, gr_ptr delta, gr_srcptr a, gr_ore_poly_ctx_t ctx)
0232 {
0233     return GR_ORE_POLY_CTX(ctx)->sigma_delta(sigma, delta, a, ctx);
0234 }
0235
0236 GR_ORE_POLY_INLINE WARN_UNUSED_RESULT int
0237 gr_ore_poly_sigma(gr_ptr res, gr_srcptr a, gr_ore_poly_ctx_t ctx)
0238 {
0239     return GR_ORE_POLY_CTX(ctx)->sigma_delta(res, NULL, a, ctx);
0240 }
0241
0242 GR_ORE_POLY_INLINE WARN_UNUSED_RESULT int
0243 gr_ore_poly_delta(gr_ptr res, gr_srcptr a, gr_ore_poly_ctx_t ctx)
0244 {
0245     return GR_ORE_POLY_CTX(ctx)->sigma_delta(NULL, res, a, ctx);
0246 }
0247
0248 extern const gr_ore_poly_sigma_delta_t _gr_ore_poly_default_sigma_delta[];
0249
0250 /* Arithmetic */
0251
0252 WARN_UNUSED_RESULT int gr_ore_poly_neg(gr_ore_poly_t res, const gr_ore_poly_t src, gr_ore_poly_ctx_t ctx);
0253
0254 WARN_UNUSED_RESULT int _gr_ore_poly_add(gr_ptr res, gr_srcptr poly1, slong len1, gr_srcptr poly2, slong len2, gr_ore_poly_ctx_t ctx);
0255 WARN_UNUSED_RESULT int gr_ore_poly_add(gr_ore_poly_t res, const gr_ore_poly_t poly1, const gr_ore_poly_t poly2, gr_ore_poly_ctx_t ctx);
0256
0257 WARN_UNUSED_RESULT int _gr_ore_poly_sub(gr_ptr res, gr_srcptr poly1, slong len1, gr_srcptr poly2, slong len2, gr_ore_poly_ctx_t ctx);
0258 WARN_UNUSED_RESULT int gr_ore_poly_sub(gr_ore_poly_t res, const gr_ore_poly_t poly1, const gr_ore_poly_t poly2, gr_ore_poly_ctx_t ctx);
0259
0260 WARN_UNUSED_RESULT int gr_ore_poly_add_ui(gr_ore_poly_t res, const gr_ore_poly_t poly, ulong c, gr_ore_poly_ctx_t ctx);
0261 WARN_UNUSED_RESULT int gr_ore_poly_add_si(gr_ore_poly_t res, const gr_ore_poly_t poly, slong c, gr_ore_poly_ctx_t ctx);
0262 WARN_UNUSED_RESULT int gr_ore_poly_add_fmpz(gr_ore_poly_t res, const gr_ore_poly_t poly, const fmpz_t c, gr_ore_poly_ctx_t ctx);
0263 WARN_UNUSED_RESULT int gr_ore_poly_add_fmpq(gr_ore_poly_t res, const gr_ore_poly_t poly, const fmpq_t c, gr_ore_poly_ctx_t ctx);
0264 WARN_UNUSED_RESULT int gr_ore_poly_add_other(gr_ore_poly_t res, const gr_ore_poly_t poly, gr_srcptr x, gr_ctx_t x_ctx, gr_ore_poly_ctx_t ctx);
0265
0266 WARN_UNUSED_RESULT int gr_ore_poly_sub_ui(gr_ore_poly_t res, const gr_ore_poly_t poly, ulong c, gr_ore_poly_ctx_t ctx);
0267 WARN_UNUSED_RESULT int gr_ore_poly_sub_si(gr_ore_poly_t res, const gr_ore_poly_t poly, slong c, gr_ore_poly_ctx_t ctx);
0268 WARN_UNUSED_RESULT int gr_ore_poly_sub_fmpz(gr_ore_poly_t res, const gr_ore_poly_t poly, const fmpz_t c, gr_ore_poly_ctx_t ctx);
0269 WARN_UNUSED_RESULT int gr_ore_poly_sub_fmpq(gr_ore_poly_t res, const gr_ore_poly_t poly, const fmpq_t c, gr_ore_poly_ctx_t ctx);
0270 WARN_UNUSED_RESULT int gr_ore_poly_sub_other(gr_ore_poly_t res, const gr_ore_poly_t poly, gr_srcptr x, gr_ctx_t x_ctx, gr_ore_poly_ctx_t ctx);
0271
0272 WARN_UNUSED_RESULT int gr_ore_poly_mul_ui(gr_ore_poly_t res, const gr_ore_poly_t poly, ulong c, gr_ore_poly_ctx_t ctx);
0273 WARN_UNUSED_RESULT int gr_ore_poly_mul_si(gr_ore_poly_t res, const gr_ore_poly_t poly, slong c, gr_ore_poly_ctx_t ctx);
0274 WARN_UNUSED_RESULT int gr_ore_poly_mul_fmpz(gr_ore_poly_t res, const gr_ore_poly_t poly, const fmpz_t c, gr_ore_poly_ctx_t ctx);
0275 WARN_UNUSED_RESULT int gr_ore_poly_mul_fmpq(gr_ore_poly_t res, const gr_ore_poly_t poly, const fmpq_t c, gr_ore_poly_ctx_t ctx);
0276 WARN_UNUSED_RESULT int gr_ore_poly_other_mul(gr_ore_poly_t res, gr_srcptr x, gr_ctx_t x_ctx, const gr_ore_poly_t poly, gr_ore_poly_ctx_t ctx);
0277
0278 WARN_UNUSED_RESULT int _gr_ore_poly_lmul_gen(gr_ptr res, gr_srcptr poly, slong len, gr_ore_poly_ctx_t ctx);
0279 WARN_UNUSED_RESULT int gr_ore_poly_lmul_gen(gr_ore_poly_t res, const gr_ore_poly_t poly, gr_ore_poly_ctx_t ctx);
0280 WARN_UNUSED_RESULT int _gr_ore_poly_mul(gr_ptr res, gr_srcptr poly1, slong len1, gr_srcptr poly2, slong len2, gr_ore_poly_ctx_t ctx);
0281 WARN_UNUSED_RESULT int gr_ore_poly_mul(gr_ore_poly_t res, const gr_ore_poly_t poly1, const gr_ore_poly_t poly2, gr_ore_poly_ctx_t ctx);
0282
0283 WARN_UNUSED_RESULT int _gr_ore_poly_divrem(gr_ptr Q, gr_ptr R, gr_srcptr U, slong lenU, gr_srcptr V, slong lenV, gr_ore_poly_ctx_t ctx);
0284 WARN_UNUSED_RESULT int gr_ore_poly_divrem(gr_ore_poly_t Q, gr_ore_poly_t R, const gr_ore_poly_t U, gr_ore_poly_t V, gr_ore_poly_ctx_t ctx);
0285 WARN_UNUSED_RESULT int gr_ore_poly_div(gr_ore_poly_t Q, const gr_ore_poly_t U, gr_ore_poly_t V, gr_ore_poly_ctx_t ctx);
0286 WARN_UNUSED_RESULT int gr_ore_poly_rem(gr_ore_poly_t R, const gr_ore_poly_t U, gr_ore_poly_t V, gr_ore_poly_ctx_t ctx);
0287
0288 #ifdef __cplusplus
0289 }
0290 #endif
0291
0292 #endif