include/flint/qqbar.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 QQBAR_H
0013 #define QQBAR_H
0014
0015 #ifdef QQBAR_INLINES_C
0016 #define QQBAR_INLINE
0017 #else
0018 #define QQBAR_INLINE static inline
0019 #endif
0020
0021 #include "fmpz_types.h"
0022 #include "fmpq_types.h"
0023 #include "mpoly_types.h"
0024 #include "acb.h"
0025
0026 #ifdef __cplusplus
0027 extern "C" {
0028 #endif
0029
0030 typedef struct
0031 {
0032     fmpz_poly_struct poly;
0033     acb_struct enclosure;
0034 }
0035 qqbar_struct;
0036
0037 typedef qqbar_struct qqbar_t[1];
0038 typedef qqbar_struct * qqbar_ptr;
0039 typedef const qqbar_struct * qqbar_srcptr;
0040
0041 #define QQBAR_POLY(x) (&((x)->poly))
0042 #define QQBAR_COEFFS(x) ((&((x)->poly))->coeffs)
0043 #define QQBAR_ENCLOSURE(x) (&((x)->enclosure))
0044
0045 #define QQBAR_DEFAULT_PREC 128
0046
0047 /* Memory management */
0048 void qqbar_init(qqbar_t res);
0049 void qqbar_clear(qqbar_t res);
0050
0051 QQBAR_INLINE qqbar_ptr
0052 _qqbar_vec_init(slong len)
0053 {
0054     slong i;
0055     qqbar_ptr vec = (qqbar_ptr) flint_malloc(len * sizeof(qqbar_struct));
0056     for (i = 0; i < len; i++)
0057         qqbar_init(vec + i);
0058     return vec;
0059 }
0060
0061 QQBAR_INLINE void
0062 _qqbar_vec_clear(qqbar_ptr vec, slong len)
0063 {
0064     slong i;
0065     for (i = 0; i < len; i++)
0066         qqbar_clear(vec + i);
0067     flint_free(vec);
0068 }
0069
0070 /* Assignment */
0071 void qqbar_swap(qqbar_t x, qqbar_t y);
0072 void qqbar_set(qqbar_t res, const qqbar_t x);
0073 void qqbar_set_si(qqbar_t res, slong x);
0074 void qqbar_set_ui(qqbar_t res, ulong x);
0075 void qqbar_set_fmpz(qqbar_t res, const fmpz_t x);
0076 void qqbar_set_fmpq(qqbar_t res, const fmpq_t x);
0077 void qqbar_set_re_im(qqbar_t res, const qqbar_t x, const qqbar_t y);
0078 int qqbar_set_d(qqbar_t res, double x);
0079 int qqbar_set_re_im_d(qqbar_t res, double x, double y);
0080
0081 /* Properties */
0082 QQBAR_INLINE slong
0083 qqbar_degree(const qqbar_t x)
0084 {
0085     return QQBAR_POLY(x)->length - 1;
0086 }
0087
0088 QQBAR_INLINE int
0089 qqbar_is_rational(const qqbar_t x)
0090 {
0091     return (qqbar_degree(x) == 1);
0092 }
0093
0094 QQBAR_INLINE int
0095 qqbar_is_integer(const qqbar_t x)
0096 {
0097     return qqbar_is_rational(x) && fmpz_is_one(QQBAR_COEFFS(x) + 1);
0098 }
0099
0100 QQBAR_INLINE int
0101 qqbar_is_algebraic_integer(const qqbar_t x)
0102 {
0103     return fmpz_is_one(QQBAR_COEFFS(x) + qqbar_degree(x));
0104 }
0105
0106 QQBAR_INLINE int
0107 qqbar_is_zero(const qqbar_t x)
0108 {
0109     return qqbar_is_integer(x) && fmpz_is_zero(QQBAR_COEFFS(x));
0110 }
0111
0112 QQBAR_INLINE int
0113 qqbar_is_one(const qqbar_t x)
0114 {
0115     return qqbar_is_integer(x) && (fmpz_equal_si(QQBAR_COEFFS(x), -1));
0116 }
0117
0118 QQBAR_INLINE int
0119 qqbar_is_neg_one(const qqbar_t x)
0120 {
0121     return qqbar_is_integer(x) && fmpz_is_one(QQBAR_COEFFS(x));
0122 }
0123
0124 QQBAR_INLINE int
0125 qqbar_is_i(const qqbar_t x)
0126 {
0127     return (qqbar_degree(x) == 2) && fmpz_is_one(QQBAR_COEFFS(x)) &&
0128         fmpz_is_zero(QQBAR_COEFFS(x) + 1) && fmpz_is_one(QQBAR_COEFFS(x) + 2) &&
0129             arf_sgn(arb_midref(acb_imagref(QQBAR_ENCLOSURE(x)))) > 0;
0130 }
0131
0132 QQBAR_INLINE int
0133 qqbar_is_neg_i(const qqbar_t x)
0134 {
0135     return (qqbar_degree(x) == 2) && fmpz_is_one(QQBAR_COEFFS(x)) &&
0136         fmpz_is_zero(QQBAR_COEFFS(x) + 1) && fmpz_is_one(QQBAR_COEFFS(x) + 2) &&
0137             arf_sgn(arb_midref(acb_imagref(QQBAR_ENCLOSURE(x)))) < 0;
0138 }
0139
0140 int qqbar_sgn_re(const qqbar_t x);
0141 int qqbar_sgn_im(const qqbar_t x);
0142
0143 QQBAR_INLINE int
0144 qqbar_is_real(const qqbar_t x)
0145 {
0146     return qqbar_sgn_im(x) == 0;
0147 }
0148
0149 slong qqbar_height_bits(const qqbar_t x);
0150 void qqbar_height(fmpz_t res, const qqbar_t x);
0151
0152 QQBAR_INLINE int
0153 qqbar_within_limits(const qqbar_t x, slong deg_limit, slong bits_limit)
0154 {
0155     return (deg_limit == 0 || (qqbar_degree(x) <= deg_limit)) &&
0156            (bits_limit == 0 || (qqbar_height_bits(x) <= bits_limit));
0157 }
0158
0159 QQBAR_INLINE int
0160 qqbar_binop_within_limits(const qqbar_t x, const qqbar_t y, slong deg_limit, slong bits_limit)
0161 {
0162     return (deg_limit == 0 || (qqbar_degree(x) * qqbar_degree(y) <= deg_limit)) &&
0163            (bits_limit == 0 || (qqbar_height_bits(x) + qqbar_height_bits(y) <= bits_limit));
0164 }
0165
0166 /* Conversions */
0167 void _qqbar_get_fmpq(fmpz_t num, fmpz_t den, const qqbar_t x);
0168 void qqbar_get_fmpq(fmpq_t res, const qqbar_t x);
0169 void qqbar_get_fmpz(fmpz_t res, const qqbar_t x);
0170
0171 /* Special values */
0172 QQBAR_INLINE void
0173 qqbar_zero(qqbar_t res)
0174 {
0175     qqbar_set_ui(res, 0);
0176 }
0177
0178 QQBAR_INLINE void
0179 qqbar_one(qqbar_t res)
0180 {
0181     qqbar_set_ui(res, 1);
0182 }
0183
0184 void qqbar_i(qqbar_t res);
0185 void qqbar_phi(qqbar_t res);
0186
0187 /* Random generation */
0188 void qqbar_randtest(qqbar_t res, flint_rand_t state, slong deg, slong bits);
0189 void qqbar_randtest_real(qqbar_t res, flint_rand_t state, slong deg, slong bits);
0190 void qqbar_randtest_nonreal(qqbar_t res, flint_rand_t state, slong deg, slong bits);
0191
0192 /* Input and output */
0193 void qqbar_print(const qqbar_t x);
0194 void qqbar_printn(const qqbar_t x, slong n);
0195 void qqbar_printnd(const qqbar_t x, slong n);
0196 char * qqbar_get_str_nd(const qqbar_t x, slong n);
0197
0198 /* Comparisons */
0199 int qqbar_equal(const qqbar_t x, const qqbar_t y);
0200 int qqbar_equal_fmpq_poly_val(const qqbar_t x, const fmpq_poly_t f, const qqbar_t y);
0201 int qqbar_cmp_re(const qqbar_t x, const qqbar_t y);
0202 int qqbar_cmp_im(const qqbar_t x, const qqbar_t y);
0203 int qqbar_cmpabs_re(const qqbar_t x, const qqbar_t y);
0204 int qqbar_cmpabs_im(const qqbar_t x, const qqbar_t y);
0205 int qqbar_cmpabs(const qqbar_t x, const qqbar_t y);
0206 int qqbar_cmp_root_order(const qqbar_t x, const qqbar_t y);
0207
0208 ulong qqbar_hash(const qqbar_t x);
0209
0210 /* Complex parts */
0211 void qqbar_conj(qqbar_t res, const qqbar_t x);
0212 void qqbar_re(qqbar_t res, const qqbar_t x);
0213 void qqbar_im(qqbar_t res, const qqbar_t x);
0214 void qqbar_re_im(qqbar_t res1, qqbar_t res2, const qqbar_t x);
0215 void qqbar_abs(qqbar_t res, const qqbar_t x);
0216 void qqbar_abs2(qqbar_t res, const qqbar_t x);
0217 void qqbar_sgn(qqbar_t res, const qqbar_t x);
0218 int qqbar_csgn(const qqbar_t x);
0219
0220 /* Integer parts */
0221 void qqbar_floor(fmpz_t res, const qqbar_t x);
0222 void qqbar_ceil(fmpz_t res, const qqbar_t x);
0223 void qqbar_numerator(qqbar_t res, const qqbar_t y);
0224 void qqbar_denominator(fmpz_t res, const qqbar_t y);
0225
0226 /* Arithmetic */
0227 void qqbar_neg(qqbar_t res, const qqbar_t x);
0228
0229 void qqbar_add(qqbar_t res, const qqbar_t x, const qqbar_t y);
0230 void qqbar_add_fmpq(qqbar_t res, const qqbar_t x, const fmpq_t y);
0231 void qqbar_add_fmpz(qqbar_t res, const qqbar_t x, const fmpz_t y);
0232 void qqbar_add_ui(qqbar_t res, const qqbar_t x, ulong y);
0233 void qqbar_add_si(qqbar_t res, const qqbar_t x, slong y);
0234
0235 void qqbar_sub(qqbar_t res, const qqbar_t x, const qqbar_t y);
0236 void qqbar_sub_fmpq(qqbar_t res, const qqbar_t x, const fmpq_t y);
0237 void qqbar_sub_fmpz(qqbar_t res, const qqbar_t x, const fmpz_t y);
0238 void qqbar_sub_ui(qqbar_t res, const qqbar_t x, ulong y);
0239 void qqbar_sub_si(qqbar_t res, const qqbar_t x, slong y);
0240 void qqbar_fmpq_sub(qqbar_t res, const fmpq_t x, const qqbar_t y);
0241 void qqbar_fmpz_sub(qqbar_t res, const fmpz_t x, const qqbar_t y);
0242 void qqbar_ui_sub(qqbar_t res, ulong x, const qqbar_t y);
0243 void qqbar_si_sub(qqbar_t res, slong x, const qqbar_t y);
0244
0245 void qqbar_mul(qqbar_t res, const qqbar_t x, const qqbar_t y);
0246 void qqbar_mul_fmpq(qqbar_t res, const qqbar_t x, const fmpq_t y);
0247 void qqbar_mul_fmpz(qqbar_t res, const qqbar_t x, const fmpz_t y);
0248 void qqbar_mul_ui(qqbar_t res, const qqbar_t x, ulong y);
0249 void qqbar_mul_si(qqbar_t res, const qqbar_t x, slong y);
0250
0251 void qqbar_div(qqbar_t res, const qqbar_t x, const qqbar_t y);
0252 void qqbar_div_fmpq(qqbar_t res, const qqbar_t x, const fmpq_t y);
0253 void qqbar_div_fmpz(qqbar_t res, const qqbar_t x, const fmpz_t y);
0254 void qqbar_div_ui(qqbar_t res, const qqbar_t x, ulong y);
0255 void qqbar_div_si(qqbar_t res, const qqbar_t x, slong y);
0256 void qqbar_fmpq_div(qqbar_t res, const fmpq_t x, const qqbar_t y);
0257 void qqbar_fmpz_div(qqbar_t res, const fmpz_t x, const qqbar_t y);
0258 void qqbar_ui_div(qqbar_t res, ulong x, const qqbar_t y);
0259 void qqbar_si_div(qqbar_t res, slong x, const qqbar_t y);
0260
0261
0262 QQBAR_INLINE void
0263 qqbar_sqr(qqbar_t res, const qqbar_t x)
0264 {
0265     qqbar_mul(res, x, x);
0266 }
0267
0268 void qqbar_inv(qqbar_t res, const qqbar_t x);
0269
0270 void qqbar_mul_2exp_si(qqbar_t res, const qqbar_t x, slong exp);
0271
0272 void qqbar_pow_ui(qqbar_t res, const qqbar_t x, ulong e);
0273 void qqbar_pow_si(qqbar_t res, const qqbar_t x, slong n);
0274 void qqbar_pow_fmpz(qqbar_t res, const qqbar_t x, const fmpz_t n);
0275 void qqbar_pow_fmpq(qqbar_t res, const qqbar_t x, const fmpq_t n);
0276
0277 int qqbar_pow(qqbar_t res, const qqbar_t x, const qqbar_t e);
0278
0279 /* Check if x = (p/q)^(1/n), p > 0 */
0280 int _qqbar_fast_detect_simple_principal_surd(const qqbar_t x);
0281
0282 void qqbar_root_ui(qqbar_t res, const qqbar_t x, ulong n);
0283
0284 QQBAR_INLINE void
0285 qqbar_sqrt(qqbar_t res, const qqbar_t x)
0286 {
0287     qqbar_root_ui(res, x, 2);
0288 }
0289
0290 QQBAR_INLINE void
0291 qqbar_sqrt_ui(qqbar_t res, ulong x)
0292 {
0293     qqbar_set_ui(res, x);
0294     qqbar_sqrt(res, res);
0295 }
0296
0297 QQBAR_INLINE void
0298 qqbar_rsqrt(qqbar_t res, const qqbar_t x)
0299 {
0300     qqbar_sqrt(res, x);
0301     qqbar_inv(res, res);
0302 }
0303
0304 void qqbar_fmpq_root_ui(qqbar_t res, const fmpq_t x, ulong b);
0305 void qqbar_fmpq_pow_si_ui(qqbar_t res, const fmpq_t x, slong a, ulong b);
0306
0307 /* Numerical enclosure */
0308 void qqbar_cache_enclosure(qqbar_t res, slong prec);
0309
0310 void qqbar_get_arb(arb_t res, const qqbar_t x, slong prec);
0311 void qqbar_get_acb(acb_t res, const qqbar_t x, slong prec);
0312 void qqbar_get_arb_re(arb_t res, const qqbar_t x, slong prec);
0313 void qqbar_get_arb_im(arb_t res, const qqbar_t x, slong prec);
0314
0315 /* Conjugates */
0316 void qqbar_conjugates(qqbar_ptr res, const qqbar_t x);
0317
0318 /* Polynomial operations */
0319 void _qqbar_evaluate_fmpq_poly(qqbar_t res, const fmpz * poly, const fmpz_t den, slong len, const qqbar_t x);
0320 void qqbar_evaluate_fmpq_poly(qqbar_t res, const fmpq_poly_t poly, const qqbar_t x);
0321 void _qqbar_evaluate_fmpz_poly(qqbar_t res, const fmpz * poly, slong len, const qqbar_t x);
0322 void qqbar_evaluate_fmpz_poly(qqbar_t res, const fmpz_poly_t poly, const qqbar_t x);
0323 int qqbar_evaluate_fmpz_mpoly_iter(qqbar_t res, const fmpz_mpoly_t f, qqbar_srcptr x, slong deg_limit, slong bits_limit, const fmpz_mpoly_ctx_t ctx);
0324 int qqbar_evaluate_fmpz_mpoly_horner(qqbar_t res, const fmpz_mpoly_t f, qqbar_srcptr x, slong deg_limit, slong bits_limit, const fmpz_mpoly_ctx_t ctx);
0325 int qqbar_evaluate_fmpz_mpoly(qqbar_t res, const fmpz_mpoly_t f, qqbar_srcptr x, slong deg_limit, slong bits_limit, const fmpz_mpoly_ctx_t ctx);
0326
0327 #define QQBAR_ROOTS_IRREDUCIBLE 1
0328 #define QQBAR_ROOTS_UNSORTED 2
0329
0330 void qqbar_roots_fmpz_poly(qqbar_ptr res, const fmpz_poly_t poly, int flags);
0331 void qqbar_roots_fmpq_poly(qqbar_ptr res, const fmpq_poly_t poly, int flags);
0332 int _qqbar_roots_poly_squarefree(qqbar_ptr roots, qqbar_srcptr coeffs, slong len, slong deg_limit, slong bits_limit);
0333
0334 void qqbar_eigenvalues_fmpz_mat(qqbar_ptr res, const fmpz_mat_t mat, int flags);
0335 void qqbar_eigenvalues_fmpq_mat(qqbar_ptr res, const fmpq_mat_t mat, int flags);
0336
0337 /* Roots of unity and trigonometric functions */
0338
0339 void qqbar_root_of_unity(qqbar_t res, slong p, ulong q);
0340
0341 int qqbar_is_root_of_unity(slong * p, ulong * q, const qqbar_t x);
0342
0343 void qqbar_exp_pi_i(qqbar_t res, slong p, ulong q);
0344 void qqbar_cos_pi(qqbar_t res, slong p, ulong q);
0345 void qqbar_sin_pi(qqbar_t res, slong p, ulong q);
0346 int qqbar_tan_pi(qqbar_t res, slong p, ulong q);
0347 int qqbar_cot_pi(qqbar_t res, slong p, ulong q);
0348 int qqbar_sec_pi(qqbar_t res, slong p, ulong q);
0349 int qqbar_csc_pi(qqbar_t res, slong p, ulong q);
0350 int qqbar_log_pi_i(slong * p, ulong * q, const qqbar_t x);
0351 int qqbar_atan_pi(slong * p, ulong * q, const qqbar_t x);
0352 int qqbar_asin_pi(slong * p, ulong * q, const qqbar_t x);
0353 int qqbar_acos_pi(slong * p, ulong * q, const qqbar_t x);
0354 int qqbar_acot_pi(slong * p, ulong * q, const qqbar_t x);
0355 int qqbar_asec_pi(slong * p, ulong * q, const qqbar_t x);
0356 int qqbar_acsc_pi(slong * p, ulong * q, const qqbar_t x);
0357
0358 /* Guessing and simplification */
0359 int qqbar_guess(qqbar_t res, const acb_t z, slong max_deg, slong max_bits, int flags, slong prec);
0360 int qqbar_express_in_field(fmpq_poly_t res, const qqbar_t alpha, const qqbar_t x, slong max_bits, int flags, slong prec);
0361
0362 /* Conversions to radicals and expressions */
0363 void qqbar_get_quadratic(fmpz_t res_a, fmpz_t res_b, fmpz_t res_c, fmpz_t res_q, const qqbar_t x, int factoring);
0364
0365 #ifdef FEXPR_H
0366 void qqbar_get_fexpr_repr(fexpr_t res, const qqbar_t x);
0367 void qqbar_get_fexpr_root_nearest(fexpr_t res, const qqbar_t x);
0368 void qqbar_get_fexpr_root_indexed(fexpr_t res, const qqbar_t x);
0369 int qqbar_get_fexpr_formula(fexpr_t res, const qqbar_t x, ulong flags);
0370
0371 #define QQBAR_FORMULA_GAUSSIANS    1
0372 #define QQBAR_FORMULA_QUADRATICS   2
0373 #define QQBAR_FORMULA_CYCLOTOMICS  4
0374 #define QQBAR_FORMULA_CUBICS       8
0375 #define QQBAR_FORMULA_QUARTICS     16
0376 #define QQBAR_FORMULA_QUINTICS     32
0377 #define QQBAR_FORMULA_DEPRESSION   64
0378 #define QQBAR_FORMULA_DEFLATION    128
0379 #define QQBAR_FORMULA_SEPARATION   256
0380
0381 #define QQBAR_FORMULA_EXP_FORM        2048
0382 #define QQBAR_FORMULA_TRIG_FORM       4096
0383 #define QQBAR_FORMULA_RADICAL_FORM    8192
0384 #define QQBAR_FORMULA_AUTO_FORM       0
0385
0386 #define QQBAR_FORMULA_ALL ((2 * QQBAR_FORMULA_SEPARATION - 1) | QQBAR_FORMULA_AUTO_FORM)
0387
0388 int qqbar_set_fexpr(qqbar_t res, const fexpr_t expr);
0389 #endif
0390
0391 /* Internal functions */
0392 void qqbar_scalar_op(qqbar_t res, const qqbar_t x, const fmpz_t a, const fmpz_t b, const fmpz_t c);
0393 void qqbar_fmpz_poly_composed_op(fmpz_poly_t res, const fmpz_poly_t A, const fmpz_poly_t B, int op);
0394 void qqbar_binary_op(qqbar_t res, const qqbar_t x, const qqbar_t y, int op);
0395 int _qqbar_validate_uniqueness(acb_t res, const fmpz_poly_t poly, const acb_t z, slong max_prec);
0396 int _qqbar_validate_existence_uniqueness(acb_t res, const fmpz_poly_t poly, const acb_t z, slong prec);
0397 void _qqbar_enclosure_raw(acb_t res, const fmpz_poly_t poly, const acb_t zin, slong prec);
0398 void qqbar_enclosure_raw(acb_t res, const qqbar_t x, slong prec);
0399 int _qqbar_acb_lindep(fmpz * rel, acb_srcptr vec, slong len, int check, slong prec);
0400
0401 #ifdef __cplusplus
0402 }
0403 #endif
0404
0405 #endif