Back to home page

EIC code displayed by LXR
 
 

    

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

0001 /*
0002     Copyright (C) 2016-2017 William Hart
0003     Copyright (C) 2017-2020 Daniel Schultz
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 MPOLY_H
0014 #define MPOLY_H
0015 
0016 #ifdef MPOLY_INLINES_C
0017 #define MPOLY_INLINE
0018 #else
0019 #define MPOLY_INLINE static inline
0020 #endif
0021 
0022 #include "mpoly_types.h"
0023 
0024 #ifdef __cplusplus
0025 extern "C" {
0026 #endif
0027 
0028 /* choose m so that (m + 1)/(n - m) ~= la/lb, i.e. m = (n*la - lb)/(la + lb) */
0029 slong mpoly_divide_threads(slong n, double la, double lb);
0030 
0031 #ifndef __GMP_H__
0032 #ifdef _MSC_VER
0033 # define DECLSPEC_IMPORT __declspec(dllimport)
0034 #else
0035 # define DECLSPEC_IMPORT
0036 #endif
0037 DECLSPEC_IMPORT ulong __gmpn_add_n(nn_ptr, nn_srcptr, nn_srcptr, long int);
0038 DECLSPEC_IMPORT ulong __gmpn_sub_n(nn_ptr, nn_srcptr, nn_srcptr, long int);
0039 DECLSPEC_IMPORT ulong __gmpn_addmul_1(nn_ptr, nn_srcptr, long int, ulong);
0040 DECLSPEC_IMPORT ulong __gmpn_submul_1(nn_ptr, nn_srcptr, long int, ulong);
0041 DECLSPEC_IMPORT ulong __gmpn_rshift(nn_ptr, nn_srcptr, long int, unsigned int);
0042 DECLSPEC_IMPORT ulong __gmpn_mul_1(nn_ptr, nn_srcptr, long int, ulong);
0043 #undef DECLSPEC_IMPORT
0044 #endif
0045 
0046 /* context *******************************************************************/
0047 
0048 void mpoly_ctx_init(mpoly_ctx_t ctx, slong nvars, const ordering_t ord);
0049 
0050 void mpoly_ctx_init_rand(mpoly_ctx_t mctx, flint_rand_t state, slong max_nvars);
0051 
0052 void mpoly_monomial_randbits_fmpz(fmpz * exp, flint_rand_t state, flint_bitcnt_t exp_bits, const mpoly_ctx_t mctx);
0053 
0054 void mpoly_ctx_clear(mpoly_ctx_t FLINT_UNUSED(mctx));
0055 
0056 /*
0057     number of words used by an exponent vector packed into "bits" bits:
0058     we must have either
0059         (mp) bits > FLINT_BITS and bits % FLINT_BITS == 0, or
0060         (sp) MPOLY_MIN_BITS <= bits <= FLINT_BITS
0061 */
0062 FLINT_FORCE_INLINE
0063 slong mpoly_words_per_exp_sp(flint_bitcnt_t bits, const mpoly_ctx_t mctx)
0064 {
0065     FLINT_ASSERT(0 < bits);
0066     FLINT_ASSERT(bits <= FLINT_BITS);
0067     FLINT_ASSERT(mctx->lut_words_per_exp[bits - 1]
0068                  == (mctx->nfields - 1)/(FLINT_BITS/bits) + 1);
0069     return mctx->lut_words_per_exp[bits - 1];
0070 }
0071 
0072 FLINT_FORCE_INLINE
0073 slong mpoly_words_per_exp_mp(flint_bitcnt_t bits, const mpoly_ctx_t mctx)
0074 {
0075     FLINT_ASSERT(bits % FLINT_BITS == 0);
0076     return bits/FLINT_BITS*mctx->nfields;
0077 }
0078 
0079 FLINT_FORCE_INLINE
0080 slong mpoly_words_per_exp(flint_bitcnt_t bits, const mpoly_ctx_t mctx)
0081 {
0082     if (bits <= FLINT_BITS)
0083         return mpoly_words_per_exp_sp(bits, mctx);
0084     else
0085         return mpoly_words_per_exp_mp(bits, mctx);
0086 }
0087 
0088 /*
0089     If "bits" is simply the number of bits needed to pack an exponent vector,
0090     possibly upgrade it so that it is either
0091         (mp) a multiple of FLINT_BITS in the mp case, or
0092         (sp) as big as possible without increasing words_per_exp in the sp case
0093     The upgrade in (mp) is mandatory, while the upgrade in (sp) is simply nice.
0094 */
0095 FLINT_FORCE_INLINE
0096 flint_bitcnt_t mpoly_fix_bits(flint_bitcnt_t bits, const mpoly_ctx_t mctx)
0097 {
0098     FLINT_ASSERT(bits > 0);
0099     if (bits <= FLINT_BITS)
0100         return mctx->lut_fix_bits[bits - 1];
0101     else
0102         return (bits + FLINT_BITS - 1)/FLINT_BITS*FLINT_BITS;
0103 }
0104 
0105 
0106 /* heaps *********************************************************************/
0107 typedef struct mpoly_heap_t
0108 {
0109    ulong i;
0110    ulong j;
0111    struct mpoly_heap_t * next;
0112 } mpoly_heap_t;
0113 
0114 typedef struct mpoly_nheap_t
0115 {
0116    ulong i;
0117    ulong j;
0118    struct mpoly_nheap_t * next;
0119    slong p;
0120 } mpoly_nheap_t;
0121 
0122 typedef struct mpoly_heap1_s
0123 {
0124    ulong exp;
0125    void * next;
0126 } mpoly_heap1_s;
0127 
0128 typedef struct mpoly_heap_s
0129 {
0130    ulong * exp;
0131    void * next;
0132 } mpoly_heap_s;
0133 
0134 /* trees *********************************************************************/
0135 
0136 /* red-black with ui keys */
0137 typedef struct {
0138     ulong key;
0139     slong up;
0140     slong left;
0141     slong right;
0142     int color;
0143 } mpoly_rbnode_ui_struct;
0144 
0145 typedef struct {
0146     slong length;
0147     mpoly_rbnode_ui_struct * nodes;
0148     slong node_alloc;
0149     char * data;
0150     slong data_alloc;
0151     slong data_size;
0152 } mpoly_rbtree_ui_struct;
0153 
0154 typedef mpoly_rbtree_ui_struct mpoly_rbtree_ui_t[1];
0155 
0156 void mpoly_rbtree_ui_init(mpoly_rbtree_ui_t T, slong data_size);
0157 
0158 void mpoly_rbtree_ui_clear(mpoly_rbtree_ui_t T);
0159 
0160 void * mpoly_rbtree_ui_lookup(mpoly_rbtree_ui_t T, int * its_new, ulong key);
0161 
0162 FLINT_FORCE_INLINE slong mpoly_rbtree_ui_head(const mpoly_rbtree_ui_t T)
0163 {
0164     FLINT_ASSERT(T->nodes[1].left >= 0 || T->length < 1);
0165     return T->nodes[1].left;
0166 }
0167 
0168 /* red-black with fmpz keys */
0169 typedef struct {
0170     fmpz_t key;
0171     slong up;
0172     slong left;
0173     slong right;
0174     int color;
0175 } mpoly_rbnode_fmpz_struct;
0176 
0177 typedef struct {
0178     slong length;
0179     mpoly_rbnode_fmpz_struct * nodes;
0180     slong node_alloc;
0181     char * data;
0182     slong data_alloc;
0183     slong data_size;
0184 } mpoly_rbtree_fmpz_struct;
0185 
0186 typedef mpoly_rbtree_fmpz_struct mpoly_rbtree_fmpz_t[1];
0187 
0188 void mpoly_rbtree_fmpz_init(mpoly_rbtree_fmpz_t T, slong data_size);
0189 
0190 void mpoly_rbtree_fmpz_clear(mpoly_rbtree_fmpz_t T);
0191 
0192 void * mpoly_rbtree_fmpz_lookup(mpoly_rbtree_fmpz_t T, int * its_new,
0193                                                              const fmpz_t key);
0194 
0195 FLINT_FORCE_INLINE slong mpoly_rbtree_fmpz_head(const mpoly_rbtree_fmpz_t T)
0196 {
0197     FLINT_ASSERT(T->nodes[1].left >= 0 || T->length < 1);
0198     return T->nodes[1].left;
0199 }
0200 
0201 /* Orderings *****************************************************************/
0202 
0203 MPOLY_INLINE
0204 ordering_t mpoly_ordering_randtest(flint_rand_t state)
0205 {
0206    return (ordering_t) n_randint(state, MPOLY_NUM_ORDERINGS);
0207 }
0208 
0209 MPOLY_INLINE
0210 int mpoly_ordering_isdeg(const mpoly_ctx_t mctx)
0211 {
0212    return mctx->ord == ORD_DEGLEX || mctx->ord == ORD_DEGREVLEX;
0213 }
0214 
0215 MPOLY_INLINE
0216 int mpoly_ordering_isrev(const mpoly_ctx_t mctx)
0217 {
0218    return mctx->ord == ORD_DEGREVLEX;
0219 }
0220 
0221 void mpoly_ordering_print(ordering_t ord);
0222 
0223 /*  Monomials ****************************************************************/
0224 
0225 FLINT_FORCE_INLINE
0226 void mpoly_monomial_zero(ulong * exp_ptr, slong N)
0227 {
0228    slong i;
0229    for (i = 0; i < N; i++)
0230       exp_ptr[i] = 0;
0231 }
0232 
0233 FLINT_FORCE_INLINE
0234 void mpoly_monomial_add(ulong * exp_ptr, const ulong * exp2,
0235                                                    const ulong * exp3, slong N)
0236 {
0237    slong i;
0238    for (i = 0; i < N; i++)
0239       exp_ptr[i] = exp2[i] + exp3[i];
0240 }
0241 
0242 FLINT_FORCE_INLINE
0243 void mpoly_monomial_add_mp(ulong * exp_ptr, const ulong * exp2,
0244                                                    const ulong * exp3, slong N)
0245 {
0246     __gmpn_add_n(exp_ptr, exp2, exp3, N);
0247 }
0248 
0249 FLINT_FORCE_INLINE
0250 void mpoly_monomial_sub(ulong * exp_ptr, const ulong * exp2,
0251                                                    const ulong * exp3, slong N)
0252 {
0253    slong i;
0254    for (i = 0; i < N; i++)
0255       exp_ptr[i] = exp2[i] - exp3[i];
0256 }
0257 
0258 FLINT_FORCE_INLINE
0259 void mpoly_monomial_sub_mp(ulong * exp_ptr, const ulong * exp2,
0260                                                    const ulong * exp3, slong N)
0261 {
0262     __gmpn_sub_n(exp_ptr, exp2, exp3, N);
0263 }
0264 
0265 FLINT_FORCE_INLINE
0266 void mpoly_monomial_madd(ulong * exp1, const ulong * exp2, ulong scalar,
0267                                                    const ulong * exp3, slong N)
0268 {
0269    slong i;
0270    for (i = 0; i < N; i++)
0271       exp1[i] = exp2[i] + scalar*exp3[i];
0272 }
0273 
0274 FLINT_FORCE_INLINE
0275 void mpoly_monomial_madd_mp(ulong * exp1, const ulong * exp2, ulong scalar,
0276                                                    const ulong * exp3, slong N)
0277 {
0278     slong i;
0279     for (i = 0; i < N; i++)
0280         exp1[i] = exp2[i];
0281     __gmpn_addmul_1(exp1, exp3, N, scalar);
0282 }
0283 
0284 FLINT_FORCE_INLINE
0285 void mpoly_monomial_madd_inplace_mp(ulong * exp12, ulong scalar,
0286                                                    const ulong * exp3, slong N)
0287 {
0288     __gmpn_addmul_1(exp12, exp3, N, scalar);
0289 }
0290 
0291 FLINT_FORCE_INLINE
0292 void mpoly_monomial_msub(ulong * exp1, const ulong * exp2, ulong scalar,
0293                                                    const ulong * exp3, slong N)
0294 {
0295    slong i;
0296    for (i = 0; i < N; i++)
0297       exp1[i] = exp2[i] - scalar*exp3[i];
0298 }
0299 
0300 FLINT_FORCE_INLINE
0301 void mpoly_monomial_msub_mp(ulong * exp1, const ulong * exp2, ulong scalar,
0302                                                    const ulong * exp3, slong N)
0303 {
0304     slong i;
0305     for (i = 0; i < N; i++)
0306         exp1[i] = exp2[i];
0307     FLINT_ASSERT(N > 0);
0308     __gmpn_submul_1(exp1, exp3, N, scalar);
0309 }
0310 
0311 void mpoly_monomial_msub_ui_array(ulong * exp1, const ulong * exp2, const ulong * scalar, slong scalar_limbs, const ulong * exp3, slong N);
0312 void mpoly_monomial_madd_ui_array(ulong * exp1, const ulong * exp2, const ulong * scalar, slong scalar_limbs, const ulong * exp3, slong N);
0313 
0314 FLINT_FORCE_INLINE
0315 void mpoly_monomial_madd_fmpz(ulong * exp1, const ulong * exp2,
0316                              const fmpz_t scalar, const ulong * exp3, slong N)
0317 {
0318     if (COEFF_IS_MPZ(*scalar))
0319     {
0320         zz_ptr mpz = FMPZ_TO_ZZ(*scalar);
0321         mpoly_monomial_madd_ui_array(exp1, exp2, mpz->ptr, mpz->size, exp3, N);
0322     }
0323     else
0324     {
0325         mpoly_monomial_madd_mp(exp1, exp2, *scalar, exp3, N);
0326     }
0327 }
0328 
0329 /* mask with high bit set in each field of exponent vector */
0330 FLINT_FORCE_INLINE
0331 ulong mpoly_overflow_mask_sp(flint_bitcnt_t bits)
0332 {
0333     flint_bitcnt_t i;
0334     ulong mask = 0;
0335 
0336     FLINT_ASSERT(bits <= FLINT_BITS);
0337 
0338     mask = (UWORD(1) << (bits - 1));
0339     for (i = bits; i < FLINT_BITS; i += bits)
0340         mask = (mask << bits) + (UWORD(1) << (bits - 1));
0341 
0342     return mask;
0343 }
0344 
0345 FLINT_FORCE_INLINE
0346 ulong mpoly_monomial_max1(ulong exp2, ulong exp3, flint_bitcnt_t bits, ulong mask)
0347 {
0348     ulong s, m, exp1;
0349     s = mask + exp2 - exp3;
0350     m = mask & s;
0351     m = m - (m >> (bits - 1));
0352     exp1 = exp3 + (s & m);
0353     return exp1;
0354 }
0355 
0356 void mpoly_monomial_max(ulong * exp1, const ulong * exp2, const ulong * exp3, flint_bitcnt_t bits, slong N, ulong mask);
0357 
0358 FLINT_FORCE_INLINE
0359 ulong mpoly_monomial_min1(ulong exp2, ulong exp3, flint_bitcnt_t bits, ulong mask)
0360 {
0361     ulong s, m, exp1;
0362     s = mask + exp2 - exp3;
0363     m = mask & s;
0364     m = m - (m >> (bits - 1));
0365     exp1 = exp2 - (s & m);
0366     return exp1;
0367 }
0368 
0369 void mpoly_monomial_min(ulong * exp1, const ulong * exp2, const ulong * exp3, flint_bitcnt_t bits, slong N, ulong mask);
0370 
0371 void mpoly_monomial_max_mp(ulong * exp1, const ulong * exp2, const ulong * exp3, flint_bitcnt_t bits, slong N);
0372 void mpoly_monomial_min_mp(ulong * exp1, const ulong * exp2, const ulong * exp3, flint_bitcnt_t bits, slong N);
0373 
0374 FLINT_FORCE_INLINE
0375 int mpoly_monomial_overflows(ulong * exp2, slong N, ulong mask)
0376 {
0377    slong i;
0378    for (i = 0; i < N; i++)
0379    {
0380       if ((exp2[i] & mask) != 0)
0381          return 1;
0382    }
0383    return 0;
0384 }
0385 
0386 FLINT_FORCE_INLINE
0387 int mpoly_monomial_overflows_mp(ulong * exp_ptr, slong N, flint_bitcnt_t bits)
0388 {
0389     slong i = bits/FLINT_BITS - 1;
0390     do {
0391         if ((slong)(exp_ptr[i]) < 0)
0392             return 1;
0393         i += bits/FLINT_BITS;
0394     } while (i < N);
0395 
0396     return 0;
0397 }
0398 
0399 FLINT_FORCE_INLINE
0400 int mpoly_monomial_overflows1(ulong exp, ulong mask)
0401 {
0402    return (exp & mask) != 0;
0403 }
0404 
0405 FLINT_FORCE_INLINE
0406 int mpoly_monomial_divides(ulong * exp_ptr, const ulong * exp2,
0407                                        const ulong * exp3, slong N, ulong mask)
0408 {
0409    slong i;
0410    for (i = 0; i < N; i++)
0411    {
0412       exp_ptr[i] = exp2[i] - exp3[i];
0413 
0414       if ((exp_ptr[i] & mask) != 0)
0415          return 0;
0416    }
0417 
0418    return 1;
0419 }
0420 
0421 FLINT_FORCE_INLINE
0422 int mpoly_monomial_halves(ulong * exp_ptr, const ulong * exp2, slong N, ulong mask)
0423 {
0424     slong i;
0425     for (i = 0; i < N; i++)
0426     {
0427         if (exp2[i] & 1)
0428             return 0;
0429         exp_ptr[i] = exp2[i] >> 1;
0430         if (exp_ptr[i] & mask)
0431             return 0;
0432     }
0433     return 1;
0434 }
0435 
0436 FLINT_FORCE_INLINE
0437 int mpoly_monomial_divides_mp(ulong * exp_ptr, const ulong * exp2,
0438                                const ulong * exp3, slong N, flint_bitcnt_t bits)
0439 {
0440     slong i;
0441 
0442     __gmpn_sub_n(exp_ptr, exp2, exp3, N);
0443 
0444     i = bits/FLINT_BITS - 1;
0445     do {
0446         if ((slong)(exp_ptr[i]) < 0)
0447             return 0;
0448         i += bits/FLINT_BITS;
0449     } while (i < N);
0450 
0451     return 1;
0452 }
0453 
0454 FLINT_FORCE_INLINE
0455 int mpoly_monomial_halves_mp(ulong * exp_ptr, const ulong * exp2,
0456                                           slong N, flint_bitcnt_t bits)
0457 {
0458    slong i;
0459    ulong bw;
0460 
0461    bw = __gmpn_rshift(exp_ptr, exp2, N, 1);
0462 
0463    if (bw != 0)
0464       return 0;
0465 
0466    i = bits/FLINT_BITS - 1;
0467    do {
0468       if ((slong)(exp_ptr[i]) < 0)
0469          return 0;
0470       i += bits/FLINT_BITS;
0471    } while (i < N);
0472 
0473    return 1;
0474 }
0475 
0476 FLINT_FORCE_INLINE
0477 int mpoly_monomial_divides_test(const ulong * exp2,
0478                                        const ulong * exp3, slong N, ulong mask)
0479 {
0480    slong i;
0481    for (i = 0; i < N; i++)
0482       if (((exp2[i] - exp3[i]) & mask) != 0)
0483          return 0;
0484 
0485    return 1;
0486 }
0487 
0488 FLINT_FORCE_INLINE
0489 int mpoly_monomial_divides_mp_test(const ulong * exp2,
0490                                  const ulong * exp3, slong N, flint_bitcnt_t bits)
0491 {
0492     slong i, j;
0493 
0494     i = 0;
0495     do {
0496         for (j = bits/FLINT_BITS - 1; j >= 0; j--)
0497         {
0498             if (exp2[i + j] > exp3[i + j])
0499                 break;
0500             if (exp2[i + j] < exp3[i + j])
0501                 return 0;
0502         }
0503         i += bits/FLINT_BITS;
0504     } while (i < N);
0505 
0506     return 1;
0507 }
0508 
0509 FLINT_FORCE_INLINE
0510 int mpoly_monomial_divides1(ulong * exp_ptr, const ulong exp2,
0511                                                   const ulong exp3, ulong mask)
0512 {
0513    (*exp_ptr) = exp2 - exp3;
0514 
0515    if (((exp2 - exp3) & mask) != 0)
0516       return 0;
0517 
0518    return 1;
0519 }
0520 
0521 FLINT_FORCE_INLINE
0522 int mpoly_monomial_halves1(ulong * exp_ptr, const ulong exp2, ulong mask)
0523 {
0524    if (exp2 & 1)
0525       return 0;
0526 
0527    (*exp_ptr) = exp2 >> 1;
0528 
0529    if (((exp2 >> 1) & mask) != 0)
0530       return 0;
0531 
0532    return 1;
0533 }
0534 
0535 FLINT_FORCE_INLINE
0536 void mpoly_monomial_set(ulong * exp2, const ulong * exp3, slong N)
0537 {
0538    slong i;
0539    for (i = 0; i < N; i++)
0540       exp2[i] = exp3[i];
0541 }
0542 
0543 FLINT_FORCE_INLINE
0544 void mpoly_monomial_set_extra(ulong * exp2, const ulong * exp3,
0545                                             slong N, slong offset, ulong extra)
0546 {
0547     slong i;
0548     for (i = 0; i < N; i++)
0549     {
0550         exp2[i] = exp3[i] + (i == offset ? extra : 0);
0551     }
0552 }
0553 
0554 void mpoly_copy_monomials(ulong * exp1, const ulong * exp2, slong len, slong N);
0555 #if defined(__GNUC__)
0556 # define mpoly_copy_monomials(exp1, exp2, len, N) __builtin_memcpy(exp1, exp2, (N) * (len) * sizeof(ulong))
0557 #endif
0558 
0559 FLINT_FORCE_INLINE
0560 void mpoly_monomial_swap(ulong * exp2, ulong * exp3, slong N)
0561 {
0562     slong i;
0563     for (i = 0; i < N; i++)
0564         FLINT_SWAP(ulong, exp2[i], exp3[i]);
0565 }
0566 
0567 FLINT_FORCE_INLINE
0568 void mpoly_monomial_mul_ui(ulong * exp2, const ulong * exp3, slong N, ulong c)
0569 {
0570    slong i;
0571    for (i = 0; i < N; i++)
0572       exp2[i] = exp3[i]*c;
0573 }
0574 
0575 FLINT_FORCE_INLINE
0576 void mpoly_monomial_mul_ui_mp(ulong * exp2, const ulong * exp3, slong N, ulong c)
0577 {
0578     FLINT_ASSERT(N > 0);
0579     __gmpn_mul_1(exp2, exp3, N, c);
0580 }
0581 
0582 void mpoly_monomial_mul_fmpz(ulong * exp2, const ulong * exp3, slong N, const fmpz_t c);
0583 
0584 FLINT_FORCE_INLINE
0585 int mpoly_monomial_is_zero(const ulong * exp, slong N)
0586 {
0587    slong i;
0588    for (i = 0; i < N; i++)
0589       if (exp[i] != 0)
0590          return 0;
0591 
0592    return 1;
0593 }
0594 
0595 FLINT_FORCE_INLINE
0596 int mpoly_monomial_equal(const ulong * exp2, const ulong * exp3, slong N)
0597 {
0598    slong i;
0599 
0600    for (i = 0; i < N; i++)
0601       if (exp2[i] != exp3[i])
0602          return 0;
0603 
0604    return 1;
0605 }
0606 
0607 FLINT_FORCE_INLINE
0608 int mpoly_monomial_equal_extra(const ulong * exp2, const ulong * exp3,
0609                                             slong N, slong offset, ulong extra)
0610 {
0611    slong i;
0612 
0613    for (i = 0; i < N; i++)
0614    {
0615       ulong e3 = exp3[i] + ((i == offset) ? extra : 0);
0616       if (exp2[i] != e3)
0617          return 0;
0618    }
0619 
0620    return 1;
0621 }
0622 
0623 FLINT_FORCE_INLINE
0624 int mpoly_monomial_cmp1(ulong a, ulong b, ulong cmpmask)
0625 {
0626     if ((a^cmpmask) != (b^cmpmask))
0627     {
0628         if ((a^cmpmask) > (b^cmpmask))
0629             return 1;
0630         else
0631             return -1;
0632     }
0633     return 0;
0634 }
0635 
0636 FLINT_FORCE_INLINE
0637 int mpoly_monomial_gt1(ulong a, ulong b, ulong cmpmask)
0638 {
0639     return (a^cmpmask) > (b^cmpmask);
0640 }
0641 
0642 FLINT_FORCE_INLINE
0643 int mpoly_monomial_ge1(ulong a, ulong b, ulong cmpmask)
0644 {
0645     return (a^cmpmask) >= (b^cmpmask);
0646 }
0647 
0648 FLINT_FORCE_INLINE
0649 int mpoly_monomial_lt(const ulong * exp3, const ulong * exp2,
0650                                                 slong N, const ulong * cmpmask)
0651 {
0652     slong i = N - 1;
0653     do
0654         if (exp2[i] != exp3[i])
0655             return (exp3[i]^cmpmask[i]) < (exp2[i]^cmpmask[i]);
0656     while (--i >= 0);
0657     return 0;
0658 }
0659 
0660 FLINT_FORCE_INLINE
0661 int mpoly_monomial_gt(const ulong * exp3, const ulong * exp2,
0662                                                 slong N, const ulong * cmpmask)
0663 {
0664     slong i = N - 1;
0665     do
0666         if (exp2[i] != exp3[i])
0667             return (exp3[i]^cmpmask[i]) > (exp2[i]^cmpmask[i]);
0668     while (--i >= 0);
0669     return 0;
0670 }
0671 
0672 FLINT_FORCE_INLINE
0673 int mpoly_monomial_lt_nomask(const ulong * exp2, const ulong * exp3, slong N)
0674 {
0675     slong i = N - 1;
0676     do
0677         if (exp2[i] != exp3[i])
0678             return exp2[i] < exp3[i];
0679     while (--i >= 0);
0680     return 0;
0681 }
0682 
0683 FLINT_FORCE_INLINE
0684 int mpoly_monomial_gt_nomask(const ulong * exp2, const ulong * exp3, slong N)
0685 {
0686     slong i = N - 1;
0687     do
0688         if (exp2[i] != exp3[i])
0689             return exp2[i] > exp3[i];
0690     while (--i >= 0);
0691     return 0;
0692 }
0693 
0694 FLINT_FORCE_INLINE
0695 int mpoly_monomial_lt_nomask_extra(const ulong * exp2, const ulong * exp3,
0696                                             slong N, slong offset, ulong extra)
0697 {
0698     slong i = N - 1;
0699     do {
0700         ulong e3 = exp3[i] + ((i == offset) ? extra : 0);
0701         if (exp2[i] != e3)
0702         {
0703             return exp2[i] < e3;
0704         }
0705     } while (--i >= 0);
0706     return 0;
0707 }
0708 
0709 FLINT_FORCE_INLINE
0710 int mpoly_monomial_gt_nomask_extra(const ulong * exp2, const ulong * exp3,
0711                                             slong N, slong offset, ulong extra)
0712 {
0713     slong i = N - 1;
0714     do {
0715         ulong e3 = exp3[i] + ((i == offset) ? extra : 0);
0716         if (exp2[i] != e3)
0717         {
0718             return exp2[i] > e3;
0719         }
0720     } while (--i >= 0);
0721     return 0;
0722 }
0723 
0724 FLINT_FORCE_INLINE
0725 int mpoly_monomial_cmp(const ulong * exp2, const ulong * exp3,
0726                                                 slong N, const ulong * cmpmask)
0727 {
0728     slong i = N - 1;
0729     do {
0730         if (exp2[i] != exp3[i])
0731         {
0732             if ((exp2[i]^cmpmask[i]) > (exp3[i]^cmpmask[i]))
0733                 return 1;
0734             else
0735                 return -1;
0736         }
0737     } while (--i >= 0);
0738     return 0;
0739 }
0740 
0741 FLINT_FORCE_INLINE
0742 int mpoly_monomial_cmp_nomask(const ulong * exp2, const ulong * exp3, slong N)
0743 {
0744     slong i = N - 1;
0745     do {
0746         if (exp2[i] != exp3[i])
0747         {
0748             if (exp2[i] > exp3[i])
0749                 return 1;
0750             else
0751                 return -1;
0752         }
0753     } while (--i >= 0);
0754     return 0;
0755 }
0756 
0757 FLINT_FORCE_INLINE
0758 int mpoly_monomial_cmp_nomask_extra(const ulong * exp2, const ulong * exp3,
0759                                             slong N, slong offset, ulong extra)
0760 {
0761     slong i = N - 1;
0762     do {
0763         ulong e3 = exp3[i] + ((i == offset) ? extra : 0);
0764         if (exp2[i] != e3)
0765         {
0766             if (exp2[i] > e3)
0767                 return 1;
0768             else
0769                 return -1;
0770         }
0771     } while (--i >= 0);
0772     return 0;
0773 }
0774 
0775 FLINT_FORCE_INLINE
0776 int mpoly_monomial_divides_tight(slong e1, slong e2, slong * prods, slong num)
0777 {
0778    slong j;
0779 
0780    for (j = 0; j < num; j++)
0781    {
0782       slong d1 = (e1 % prods[j + 1])/prods[j];
0783       slong d2 = (e2 % prods[j + 1])/prods[j];
0784 
0785       if (d1 < d2)
0786          return 0;
0787    }
0788 
0789    return 1;
0790 }
0791 
0792 MPOLY_INLINE
0793 void mpoly_max_degrees_tight(slong * max_exp,
0794                              ulong * exps, slong len, slong * prods, slong num)
0795 {
0796    slong i, j;
0797 
0798    for (j = 0; j < num; j++)
0799       max_exp[j] = 0;
0800 
0801    for (i = 0; i < len; i++)
0802    {
0803       for (j = 0; j < num; j++)
0804       {
0805          slong d1 = (exps[i] % prods[j + 1])/prods[j];
0806 
0807          if (d1 > max_exp[j])
0808             max_exp[j] = d1;
0809       }
0810    }
0811 }
0812 
0813 /* single-limb packings ******************************************************/
0814 
0815 FLINT_FORCE_INLINE
0816 ulong pack_exp2(ulong e0, ulong e1)
0817 {
0818     return (e0 << (1*(FLINT_BITS/2))) +
0819            (e1 << (0*(FLINT_BITS/2)));
0820 }
0821 
0822 FLINT_FORCE_INLINE
0823 ulong pack_exp3(ulong e0, ulong e1, ulong e2)
0824 {
0825     return (e0 << (2*(FLINT_BITS/3))) +
0826            (e1 << (1*(FLINT_BITS/3))) +
0827            (e2 << (0*(FLINT_BITS/3)));
0828 }
0829 
0830 FLINT_FORCE_INLINE
0831 ulong extract_exp(ulong e, int idx, int nvars)
0832 {
0833     return (e >> (idx*(FLINT_BITS/nvars))) &
0834             ((-UWORD(1)) >> (FLINT_BITS - FLINT_BITS/nvars));
0835 }
0836 
0837 ulong _mpoly_bidegree(const ulong * Aexps, flint_bitcnt_t Abits,
0838                                                        const mpoly_ctx_t mctx);
0839 
0840 /* generators ****************************************************************/
0841 
0842 void mpoly_gen_fields_ui(ulong * exp, slong var, const mpoly_ctx_t mctx);
0843 
0844 void mpoly_gen_fields_fmpz(fmpz * exp, slong var, const mpoly_ctx_t mctx);
0845 
0846 flint_bitcnt_t mpoly_gen_bits_required(slong FLINT_UNUSED(var), const mpoly_ctx_t FLINT_UNUSED(mctx));
0847 
0848 /* return the index in the fields where the generator of index v is stored */
0849 FLINT_FORCE_INLINE slong mpoly_gen_index(slong v, const mpoly_ctx_t mctx)
0850 {
0851     return mctx->rev ? v : mctx->nvars - 1 - v;
0852 }
0853 
0854 void mpoly_gen_offset_shift_sp(slong * offset, slong * shift,
0855                           slong var, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0856 
0857 void mpoly_gen_monomial_offset_shift_sp(ulong * mexp, slong * offset,
0858            slong * shift, slong var, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0859 
0860 void mpoly_gen_monomial_sp(ulong * oneexp, slong var,
0861                                      flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0862 
0863 slong mpoly_gen_offset_mp(slong var, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0864 
0865 slong mpoly_gen_monomial_offset_mp(ulong * mexp, slong var,
0866                                      flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0867 
0868 void mpoly_compose_mat_gen(fmpz_mat_t M, const slong * c,
0869                             const mpoly_ctx_t mctxB, const mpoly_ctx_t mctxAC);
0870 
0871 void mpoly_compose_mat_fill_column(fmpz_mat_t M, const ulong * Cexp,
0872                     flint_bitcnt_t Cbits, slong Bvar, const mpoly_ctx_t mctxB,
0873                                                      const mpoly_ctx_t mctxAC);
0874 
0875 /* Monomial arrays ***********************************************************/
0876 
0877 void mpoly_get_cmpmask(ulong * cmpmask, slong N, flint_bitcnt_t bits,
0878                                                        const mpoly_ctx_t mctx);
0879 
0880 void mpoly_get_ovfmask(ulong * ovfmask, slong N, flint_bitcnt_t bits,
0881                                                        const mpoly_ctx_t mctx);
0882 
0883 int mpoly_monomials_cmp(const ulong * Aexps, flint_bitcnt_t Abits,
0884                                   const ulong * Bexps, flint_bitcnt_t Bbits,
0885                                          slong length, const mpoly_ctx_t mctx);
0886 
0887 flint_bitcnt_t mpoly_exp_bits_required_ui(const ulong * user_exp,
0888                                                        const mpoly_ctx_t mctx);
0889 flint_bitcnt_t mpoly_exp_bits_required_ffmpz(const fmpz * user_exp,
0890                                                        const mpoly_ctx_t mctx);
0891 flint_bitcnt_t mpoly_exp_bits_required_pfmpz(fmpz * const * user_exp,
0892                                                        const mpoly_ctx_t mctx);
0893 
0894 flint_bitcnt_t mpoly_gen_pow_exp_bits_required(slong FLINT_UNUSED(v), ulong e, const mpoly_ctx_t FLINT_UNUSED(mctx));
0895 
0896 int mpoly_is_poly(const ulong * Aexps, slong Alen, flint_bitcnt_t Abits, slong var, const mpoly_ctx_t mctx);
0897 
0898 void mpoly_pack_vec_ui(ulong * exp1, const ulong * exp2, flint_bitcnt_t bits, slong nfields, slong len);
0899 void mpoly_pack_vec_fmpz(ulong * exp1, const fmpz * exp2, flint_bitcnt_t bits, slong nfields, slong len);
0900 
0901 void mpoly_unpack_vec_ui(ulong * exp1, const ulong * exp2, flint_bitcnt_t bits, slong nfields, slong len);
0902 
0903 void mpoly_unpack_vec_fmpz(fmpz * exp1, const ulong * exp2, flint_bitcnt_t bits, slong nfields, slong len);
0904 
0905 void mpoly_get_monomial_ui_unpacked_ui(ulong * user_exps, const ulong * poly_exps, const mpoly_ctx_t mctx);
0906 void mpoly_get_monomial_ui_unpacked_ffmpz(ulong * user_exps, const fmpz * poly_exps, const mpoly_ctx_t mctx);
0907 void mpoly_get_monomial_ffmpz_unpacked_ffmpz(fmpz * user_exps, const fmpz * poly_exps, const mpoly_ctx_t mctx);
0908 void mpoly_get_monomial_pfmpz_unpacked_ffmpz(fmpz ** user_exps, const fmpz * poly_exps, const mpoly_ctx_t mctx);
0909 
0910 void mpoly_get_monomial_ui_sp(ulong * user_exps, const ulong * poly_exps, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0911 void mpoly_get_monomial_si_mp(slong * user_exps, const ulong * poly_exps, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0912 void mpoly_get_monomial_ui_mp(ulong * user_exps, const ulong * poly_exps, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0913 
0914 MPOLY_INLINE
0915 void mpoly_get_monomial_ui(ulong * user_exps,
0916           const ulong * poly_exps, flint_bitcnt_t bits, const mpoly_ctx_t mctx)
0917 {
0918     if (bits <= FLINT_BITS)
0919         mpoly_get_monomial_ui_sp(user_exps, poly_exps, bits, mctx);
0920     else
0921         mpoly_get_monomial_ui_mp(user_exps, poly_exps, bits, mctx);
0922 }
0923 
0924 MPOLY_INLINE void mpoly_get_monomial_si(slong * user_exps,
0925           const ulong * poly_exps, flint_bitcnt_t bits, const mpoly_ctx_t mctx)
0926 {
0927 /* if bits <= FLINT_BITS and poly_exps is canonical, everything should be ok */
0928     if (bits <= FLINT_BITS)
0929         mpoly_get_monomial_ui_sp((ulong *) user_exps, poly_exps, bits, mctx);
0930     else
0931         mpoly_get_monomial_si_mp(user_exps, poly_exps, bits, mctx);
0932 }
0933 
0934 ulong mpoly_get_monomial_var_exp_ui_sp(const ulong * poly_exps, slong var, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0935 slong mpoly_get_monomial_var_exp_si_mp(const ulong * poly_exps, slong var, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0936 ulong mpoly_get_monomial_var_exp_ui_mp(const ulong * poly_exps, slong var, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0937 
0938 MPOLY_INLINE ulong mpoly_get_monomial_var_exp_ui(const ulong * poly_exps,
0939                         slong var, flint_bitcnt_t bits, const mpoly_ctx_t mctx)
0940 {
0941     if (bits <= FLINT_BITS)
0942         return mpoly_get_monomial_var_exp_ui_sp(poly_exps, var, bits, mctx);
0943     else
0944         return mpoly_get_monomial_var_exp_ui_mp(poly_exps, var, bits, mctx);
0945 }
0946 
0947 MPOLY_INLINE slong mpoly_get_monomial_var_exp_si(const ulong * poly_exps,
0948                         slong var, flint_bitcnt_t bits, const mpoly_ctx_t mctx)
0949 {
0950     if (bits <= FLINT_BITS)
0951         return (slong) mpoly_get_monomial_var_exp_ui_sp(poly_exps, var, bits, mctx);
0952     else
0953         return mpoly_get_monomial_var_exp_si_mp(poly_exps, var, bits, mctx);
0954 }
0955 
0956 void mpoly_get_monomial_ffmpz(fmpz * exps, const ulong * poly_exps, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0957 void mpoly_get_monomial_pfmpz(fmpz ** exps, const ulong * poly_exps, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0958 
0959 void mpoly_set_monomial_ui(ulong * exp1, const ulong * exp2, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0960 void mpoly_set_monomial_ffmpz(ulong * exp1, const fmpz * exp2, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0961 void mpoly_set_monomial_pfmpz(ulong * exp1, fmpz * const * exp2, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0962 
0963 int mpoly_repack_monomials(ulong * exps1, flint_bitcnt_t bits1, const ulong * exps2, flint_bitcnt_t bits2, slong len, const mpoly_ctx_t mctx);
0964 void mpoly_pack_monomials_tight(ulong * exp1, const ulong * exp2, slong len, const slong * mults, slong num, slong bits);
0965 void mpoly_unpack_monomials_tight(ulong * e1, ulong * e2, slong len, slong * mults, slong num, slong bits);
0966 
0967 int mpoly_monomial_exists(slong * index, const ulong * poly_exps, const ulong * exp, slong len, slong N, const ulong * cmpmask);
0968 
0969 slong mpoly_monomial_index1_nomask(ulong * Aexps, slong Alen, ulong e);
0970 slong mpoly_monomial_index_ui(const ulong * Aexp, flint_bitcnt_t Abits, slong Alength, const ulong * exp, const mpoly_ctx_t mctx);
0971 slong mpoly_monomial_index_pfmpz(const ulong * Aexp, flint_bitcnt_t Abits, slong Alength, fmpz * const * exp, const mpoly_ctx_t mctx);
0972 slong mpoly_monomial_index_monomial(const ulong * Aexp, flint_bitcnt_t Abits, slong Alength, const ulong * Mexp, flint_bitcnt_t Mbits, const mpoly_ctx_t mctx);
0973 
0974 void mpoly_min_fields_ui_sp(ulong * min_fields, const ulong * poly_exps, slong len, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0975 void mpoly_min_fields_fmpz(fmpz * min_fields, const ulong * poly_exps, slong len, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0976 
0977 void mpoly_max_fields_ui_sp(ulong * max_fields, const ulong * poly_exps, slong len, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0978 void mpoly_max_fields_fmpz(fmpz * max_fields, const ulong * poly_exps, slong len, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0979 
0980 int mpoly_degrees_fit_si(const ulong * poly_exps, slong len, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0981 
0982 void mpoly_degrees_si(slong * user_degs, const ulong * poly_exps, slong len, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0983 void mpoly_degrees_si_threaded(slong * user_degs, const ulong * poly_exps, slong len,  flint_bitcnt_t bits, const mpoly_ctx_t mctx, const thread_pool_handle * handles, slong num_handles);
0984 void mpoly_degrees_ffmpz(fmpz * user_degs, const ulong * poly_exps, slong len, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0985 void mpoly_degrees_pfmpz(fmpz ** user_degs, const ulong * poly_exps, slong len, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0986 
0987 slong mpoly_degree_si(const ulong * poly_exps, slong len, flint_bitcnt_t bits, slong var, const mpoly_ctx_t mctx);
0988 void mpoly_degree_fmpz(fmpz_t deg, const ulong * poly_exps, slong len, flint_bitcnt_t bits, slong var, const mpoly_ctx_t mctx);
0989 
0990 int  mpoly_total_degree_fits_si(const ulong * exps, slong len, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0991 
0992 slong mpoly_total_degree_si(const ulong * exps, slong len, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0993 void mpoly_total_degree_fmpz(fmpz_t totdeg, const ulong * exps, slong len, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0994 void mpoly_total_degree_fmpz_ref(fmpz_t totdeg, const ulong * exps, slong len, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0995 
0996 void mpoly_used_vars_or(int * used, const ulong * exps, slong len, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
0997 
0998 int mpoly_monomial_cmp_general(ulong * Aexp, flint_bitcnt_t Abits, ulong * Bexp, flint_bitcnt_t Bbits, const mpoly_ctx_t mctx);
0999 
1000 void mpoly_search_monomials(
1001         slong ** e_ind, ulong * e, slong * e_score,
1002         slong * t1, slong * t2, slong *t3,
1003         slong lower, slong upper,
1004         const ulong * a, slong a_len, const ulong * b, slong b_len,
1005         slong N, const ulong * cmpmask);
1006 
1007 void mpoly_main_variable_split_LEX(slong * ind, ulong * pexp,
1008                                  const ulong * Aexp, slong l1, slong Alen,
1009                                   const ulong * mults, slong num, slong Abits);
1010 
1011 void mpoly_main_variable_split_DEG(slong * ind, ulong * pexp,
1012                                   const ulong * Aexp,  slong l1, slong Alen,
1013                                             ulong deg, slong num, slong Abits);
1014 
1015 int mpoly_term_exp_fits_si(ulong * exps, flint_bitcnt_t bits, slong n, const mpoly_ctx_t mctx);
1016 int mpoly_term_exp_fits_ui(ulong * exps, flint_bitcnt_t bits, slong n, const mpoly_ctx_t mctx);
1017 
1018 int mpoly_is_gen(ulong * exps, slong var, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
1019 
1020 int mpoly_monomials_valid_test(ulong * exps, slong len, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
1021 int mpoly_monomials_overflow_test(ulong * exps, slong len, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
1022 int mpoly_monomials_inorder_test(ulong * exps, slong len, flint_bitcnt_t bits, const mpoly_ctx_t mctx);
1023 
1024 void mpoly_reverse(ulong * Aexp, const ulong * Bexp, slong len, slong N);
1025 
1026 void mpoly_monomials_deflation(fmpz * shift, fmpz * stride,
1027                         const ulong * Aexps, flint_bitcnt_t Abits, slong Alength,
1028                                                        const mpoly_ctx_t mctx);
1029 
1030 void mpoly_monomials_deflate(ulong * Aexps, flint_bitcnt_t Abits,
1031                         const ulong * Bexps, flint_bitcnt_t Bbits, slong Blength,
1032               const fmpz * shift, const fmpz * stride, const mpoly_ctx_t mctx);
1033 
1034 void mpoly_monomials_inflate(ulong * Aexps, flint_bitcnt_t Abits,
1035                         const ulong * Bexps, flint_bitcnt_t Bbits, slong Blength,
1036               const fmpz * shift, const fmpz * stride, const mpoly_ctx_t mctx);
1037 
1038 void _mpoly_gen_shift_right(ulong * Aexp, flint_bitcnt_t Abits,
1039                slong Alength, slong var, ulong amount, const mpoly_ctx_t mctx);
1040 
1041 void _mpoly_gen_shift_right_fmpz(ulong * Aexp, flint_bitcnt_t Abits,
1042         slong Alength, slong var, const fmpz_t amount, const mpoly_ctx_t mctx);
1043 
1044 void _mpoly_gen_shift_left(ulong * Aexp, flint_bitcnt_t Abits,
1045                slong Alength, slong var, ulong amount, const mpoly_ctx_t mctx);
1046 
1047 void mpoly_monomials_shift_right_ui(ulong * Aexps, flint_bitcnt_t Abits,
1048                slong Alength, const ulong * user_exps, const mpoly_ctx_t mctx);
1049 
1050 void mpoly_monomials_shift_right_ffmpz(ulong * Aexps, flint_bitcnt_t Abits,
1051                 slong Alength, const fmpz * user_exps, const mpoly_ctx_t mctx);
1052 
1053 void mpoly1_fill_marks(ulong ** Dcoeffs, slong * Dlen, slong * Dalloc,
1054                         const ulong * Aexps, slong Alen, flint_bitcnt_t Abits,
1055                                                        const mpoly_ctx_t mctx);
1056 
1057 void mpoly2_fill_marks(ulong ** Dcoeffs, slong * Dlen, slong * Dalloc,
1058                         const ulong * Aexps, slong Alen, flint_bitcnt_t Abits,
1059                                                        const mpoly_ctx_t mctx);
1060 
1061 void mpoly_to_mpolyl_perm_deflate(
1062     ulong * Aexps,
1063     flint_bitcnt_t Abits,
1064     const mpoly_ctx_t Actx,
1065     ulong * Bexps,
1066     flint_bitcnt_t Bbits,
1067     const mpoly_ctx_t Bctx,
1068     slong length,
1069     const slong * perm,
1070     const ulong * shift,
1071     const ulong * stride);
1072 
1073 void mpoly_from_mpolyl_perm_inflate(
1074     ulong * Bexps,
1075     flint_bitcnt_t Bbits,
1076     const mpoly_ctx_t Bctx,
1077     ulong * Aexps,
1078     flint_bitcnt_t Abits,
1079     const mpoly_ctx_t Actx,
1080     slong length,
1081     const slong * perm,
1082     const ulong * shift,
1083     const ulong * stride);
1084 
1085 /* gcd ***********************************************************************/
1086 
1087 #define MPOLY_GCD_USE_HENSEL  1
1088 #define MPOLY_GCD_USE_BROWN   2
1089 #define MPOLY_GCD_USE_ZIPPEL  4
1090 #define MPOLY_GCD_USE_ZIPPEL2 8
1091 #define MPOLY_GCD_USE_PRS     16
1092 #define MPOLY_GCD_USE_ALL     31
1093 
1094 void mpoly_gcd_info_init(mpoly_gcd_info_t Iv, slong nvars);
1095 
1096 void mpoly_gcd_info_clear(mpoly_gcd_info_t Iv);
1097 
1098 void mpoly_gcd_info_limits(ulong * Amax_exp, ulong * Amin_exp,
1099                        slong * Amax_exp_count, slong * Amin_exp_count,
1100                        const ulong * Aexps, flint_bitcnt_t Abits, slong Alength,
1101                                                        const mpoly_ctx_t mctx);
1102 void mpoly_gcd_info_stride(ulong * strides,
1103           const ulong * Aexps, flint_bitcnt_t Abits, slong Alength,
1104                              const ulong * Amax_exp, const ulong * Amin_exp,
1105           const ulong * Bexps, flint_bitcnt_t Bbits, slong Blength,
1106                              const ulong * Bmax_exp, const ulong * Bmin_exp,
1107                                                        const mpoly_ctx_t mctx);
1108 
1109 void mpoly_gcd_info_set_perm(mpoly_gcd_info_t Iv,
1110                          slong Alength, slong Blength, const mpoly_ctx_t mctx);
1111 
1112 slong mpoly_gcd_info_get_brown_upper_limit(const mpoly_gcd_info_t Iv,
1113                                                        slong var, slong bound);
1114 
1115 void mpoly_gcd_info_measure_hensel(mpoly_gcd_info_t Iv,
1116                          slong Alength, slong Blength, const mpoly_ctx_t FLINT_UNUSED(mctx));
1117 
1118 void mpoly_gcd_info_measure_brown(mpoly_gcd_info_t Iv,
1119                          slong Alength, slong Blength, const mpoly_ctx_t FLINT_UNUSED(mctx));
1120 
1121 void mpoly_gcd_info_measure_bma(mpoly_gcd_info_t Iv,
1122                          slong Alength, slong Blength, const mpoly_ctx_t FLINT_UNUSED(mctx));
1123 
1124 void mpoly_gcd_info_measure_zippel(mpoly_gcd_info_t Iv,
1125                          slong FLINT_UNUSED(Alength), slong FLINT_UNUSED(Blength), const mpoly_ctx_t FLINT_UNUSED(mctx));
1126 
1127 void mpoly_gcd_info_measure_zippel2(mpoly_gcd_info_t Iv,
1128                          slong FLINT_UNUSED(Alength), slong FLINT_UNUSED(Blength), const mpoly_ctx_t FLINT_UNUSED(mctx));
1129 
1130 int mpoly_monomial_cofactors(fmpz * Abarexps, fmpz * Bbarexps,
1131                                     const ulong * Aexps, flint_bitcnt_t Abits,
1132                                     const ulong * Bexps, flint_bitcnt_t Bbits,
1133                                         slong length,  const mpoly_ctx_t mctx);
1134 
1135 /* factoring ****************************************************************/
1136 
1137 #define MPOLY_FACTOR_USE_ZAS  1
1138 #define MPOLY_FACTOR_USE_WANG 2
1139 #define MPOLY_FACTOR_USE_ZIP  4
1140 #define MPOLY_FACTOR_USE_ALL  7
1141 
1142 int mpoly_is_proved_not_square(const ulong * Aexps,
1143                          slong Alen, flint_bitcnt_t Abits, slong N, ulong * t);
1144 
1145 void mpoly_remove_var_powers(fmpz * var_powers, ulong * Aexps,
1146                      flint_bitcnt_t Abits, slong Alen, const mpoly_ctx_t mctx);
1147 
1148 slong _mpoly_compress_exps(slong * V, slong * D, slong * deg,
1149                                                   slong * S, slong n, slong l);
1150 
1151 int mpoly_test_irreducible(ulong * Aexps, flint_bitcnt_t Abits,
1152                                             slong Alen, const mpoly_ctx_t ctx);
1153 
1154 int _mpoly_test_irreducible(slong * Aexps, slong stride, slong Alen,
1155                             slong nvars, flint_rand_t state, slong tries_left);
1156 
1157 void mpoly_compression_init(mpoly_compression_t M);
1158 void mpoly_compression_clear(mpoly_compression_t M);
1159 
1160 void mpoly_compression_set(mpoly_compression_t M, const ulong * Aexps,
1161                      flint_bitcnt_t Abits, slong Alen, const mpoly_ctx_t mctx);
1162 
1163 void mpoly_bivar_cld_bounds(slong * l, slong n);
1164 
1165 FLINT_FORCE_INLINE
1166 void _slong_array_fit_length(slong ** array, slong * alloc, slong len)
1167 {
1168     if (len <= *alloc)
1169         return;
1170     len = FLINT_MAX(len, *alloc + *alloc/4 + 1);
1171     *alloc = len;
1172     *array = (slong *) flint_realloc(*array, len*sizeof(slong));
1173 }
1174 
1175 /* Heap **********************************************************************/
1176 
1177 #define HEAP_LEFT(i) (2*(i))
1178 #define HEAP_RIGHT(i) (2*(i) + 1)
1179 #define HEAP_PARENT(i) ((i)/2)
1180 
1181 #define HEAP_ASSIGN(h, c1, c2) \
1182    do {                                \
1183       (h).exp = (c1);                  \
1184       (h).next = (c2);                 \
1185    } while (0)
1186 
1187 void * _mpoly_heap_pop1(mpoly_heap1_s * heap, slong * heap_len, ulong maskhi);
1188 
1189 void _mpoly_heap_insert1(mpoly_heap1_s * heap, ulong exp, void * x,
1190                               slong * next_loc, slong * heap_len, ulong maskhi);
1191 
1192 void * _mpoly_heap_pop(mpoly_heap_s * heap, slong * heap_len, slong N,
1193                                                          const ulong * cmpmask);
1194 
1195 int _mpoly_heap_insert(mpoly_heap_s * heap, ulong * exp, void * x,
1196        slong * next_loc, slong * heap_len, slong N, const ulong * cmpmask);
1197 
1198 /* generic parsing ***********************************************************/
1199 
1200 typedef struct {
1201     char * coeffs;
1202     fmpz * exps;
1203     slong length;
1204     slong alloc;
1205 } mpoly_univar_struct;
1206 
1207 typedef mpoly_univar_struct mpoly_univar_t[1];
1208 
1209 void * mpoly_void_ring_elem_init(mpoly_void_ring_t R);
1210 void mpoly_void_ring_elem_clear(void * a, mpoly_void_ring_t R);
1211 
1212 void mpoly_univar_init(mpoly_univar_t A, mpoly_void_ring_t R);
1213 void mpoly_univar_init2(mpoly_univar_t A, slong len, mpoly_void_ring_t R);
1214 void mpoly_univar_clear(mpoly_univar_t A, mpoly_void_ring_t R);
1215 
1216 void mpoly_univar_swap(mpoly_univar_t A, mpoly_univar_t B);
1217 
1218 void mpoly_univar_fit_length(mpoly_univar_t A, slong len, mpoly_void_ring_t R);
1219 
1220 int mpoly_univar_pseudo_gcd_ducos(mpoly_univar_t G,
1221                       mpoly_univar_t B, mpoly_univar_t A, mpoly_void_ring_t R);
1222 
1223 int mpoly_univar_resultant(void * r, mpoly_univar_t fx,
1224                                        mpoly_univar_t gx, mpoly_void_ring_t R);
1225 
1226 int mpoly_univar_discriminant(void * d, mpoly_univar_t fx, mpoly_void_ring_t R);
1227 
1228 typedef struct {
1229     char * str;
1230     slong str_len;
1231 } string_with_length_struct;
1232 
1233 typedef struct {
1234     mpoly_void_ring_t R;
1235     slong * stack;
1236     slong stack_len;
1237     slong stack_alloc;
1238     char * estore;
1239     slong estore_len;
1240     slong estore_alloc;
1241     void * tmp;
1242     string_with_length_struct * terminal_strings;
1243     char * terminal_values;
1244     slong terminals_alloc;
1245     slong terminals_len;
1246 } mpoly_parse_struct;
1247 
1248 typedef mpoly_parse_struct mpoly_parse_t[1];
1249 
1250 void mpoly_parse_init(mpoly_parse_t E);
1251 void mpoly_parse_clear(mpoly_parse_t E);
1252 
1253 void mpoly_parse_add_terminal(mpoly_parse_t E, const char * s, const void * v);
1254 
1255 int mpoly_parse_parse(mpoly_parse_t E, void * res, const char * s, slong len);
1256 
1257 /* chunking */
1258 
1259 /*
1260    Set i1[i] to the index of the i-th "coefficient" in variable k of num
1261    variables, each taking the given number of bits in the exponent. This
1262    assumes there are l1 "coefficients" in a list of len1 exponents.
1263    Note this doesn't currently mask the relevant bits.
1264 */
1265 void mpoly_main_variable_terms1(slong * i1, slong * n1, const ulong * exp1,
1266         slong l1, slong len1, slong k, slong FLINT_UNUSED(num), slong bits);
1267 
1268 #ifdef __cplusplus
1269 }
1270 #endif
1271 
1272 #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!