include/flint/fmpq.h

0001 /*
0002     Copyright (C) 2011 Fredrik Johansson
0003     Copyright (C) 2011 Sebastian Pancratz
0004     Copyright (C) 2024 Albin Ahlbäck
0005
0006     This file is part of FLINT.
0007
0008     FLINT is free software: you can redistribute it and/or modify it under
0009     the terms of the GNU Lesser General Public License (LGPL) as published
0010     by the Free Software Foundation; either version 3 of the License, or
0011     (at your option) any later version.  See <https://www.gnu.org/licenses/>.
0012 */
0013
0014 #ifndef FMPQ_H
0015 #define FMPQ_H
0016
0017 #ifdef FMPQ_INLINES_C
0018 #define FMPQ_INLINE
0019 #else
0020 #define FMPQ_INLINE static inline
0021 #endif
0022
0023 #include "fmpz.h"
0024
0025 #ifdef __cplusplus
0026 extern "C" {
0027 #endif
0028
0029 #define FMPQ_RECONSTRUCT_HGCD_CUTOFF 500
0030
0031 /* memory management *********************************************************/
0032
0033 FMPQ_INLINE void fmpq_init(fmpq_t x)
0034 {
0035     x->num = WORD(0);
0036     x->den = WORD(1);
0037 }
0038
0039 FMPQ_INLINE void fmpq_clear(fmpq_t x)
0040 {
0041     fmpz_clear(fmpq_numref(x));
0042     fmpz_clear(fmpq_denref(x));
0043 }
0044
0045 FMPQ_INLINE void fmpq_swap(fmpq_t op1, fmpq_t op2)
0046 {
0047     FLINT_SWAP(fmpq, *op1, *op2);
0048 }
0049
0050 void _fmpq_canonicalise(fmpz_t num, fmpz_t den);
0051 void fmpq_canonicalise(fmpq_t res);
0052
0053 int _fmpq_is_canonical(const fmpz_t num, const fmpz_t den);
0054 int fmpq_is_canonical(const fmpq_t x);
0055
0056 /* assignments ***************************************************************/
0057
0058 FMPQ_INLINE void fmpq_zero(fmpq_t res)
0059 {
0060     fmpz_zero(fmpq_numref(res));
0061     fmpz_one(fmpq_denref(res));
0062 }
0063
0064 FMPQ_INLINE void fmpq_one(fmpq_t res)
0065 {
0066     fmpz_one(fmpq_numref(res));
0067     fmpz_one(fmpq_denref(res));
0068 }
0069
0070 FMPQ_INLINE void fmpq_set(fmpq_t dest, const fmpq_t src)
0071 {
0072     fmpz_set(fmpq_numref(dest), fmpq_numref(src));
0073     fmpz_set(fmpq_denref(dest), fmpq_denref(src));
0074 }
0075
0076 #ifdef __GMP_H__
0077 void flint_mpq_init_set_readonly(mpq_t z, const fmpq_t f);
0078 void flint_mpq_clear_readonly(mpq_t z);
0079 void fmpq_init_set_readonly(fmpq_t f, const mpq_t z);
0080 #endif
0081 void fmpq_clear_readonly(fmpq_t f);
0082
0083 /* conversions ***************************************************************/
0084
0085 void _fmpq_set_si(fmpz_t rnum, fmpz_t rden, slong p, ulong q);
0086 void _fmpq_set_ui(fmpz_t rnum, fmpz_t rden, ulong p, ulong q);
0087
0088 void fmpq_set_si(fmpq_t res, slong p, ulong q);
0089 void fmpq_set_ui(fmpq_t res, ulong p, ulong q);
0090 void fmpq_set_fmpz_frac(fmpq_t res, const fmpz_t p, const fmpz_t q);
0091 #ifdef __GMP_H__
0092 void fmpq_set_mpq(fmpq_t dest, const mpq_t src);
0093 #endif
0094
0095 FMPQ_INLINE void fmpq_set_fmpz(fmpq_t q, const fmpz_t n)
0096 {
0097     fmpz_set(fmpq_numref(q), n);
0098     fmpz_one(fmpq_denref(q));
0099 }
0100
0101 double fmpq_get_d(const fmpq_t a);
0102 #ifdef __GMP_H__
0103 void fmpq_get_mpz_frac(mpz_t a, mpz_t b, fmpq_t c);
0104 void fmpq_get_mpq(mpq_t dest, const fmpq_t src);
0105 #endif
0106 #ifdef __MPFR_H
0107 int fmpq_get_mpfr(mpfr_t r, const fmpq_t x, mpfr_rnd_t rnd);
0108 #endif
0109
0110 int fmpq_set_str(fmpq_t res, const char * str, int base);
0111
0112 char * _fmpq_get_str(char * str, int b, const fmpz_t num, const fmpz_t den);
0113 char * fmpq_get_str(char * str, int b, const fmpq_t x);
0114
0115 /* comparisons ***************************************************************/
0116
0117 FMPQ_INLINE int fmpq_is_zero(const fmpq_t x)
0118 {
0119     return fmpz_is_zero(fmpq_numref(x));
0120 }
0121
0122 FMPQ_INLINE int fmpq_is_one(const fmpq_t x)
0123 {
0124     return fmpz_is_one(fmpq_numref(x)) && fmpz_is_one(fmpq_denref(x));
0125 }
0126
0127 FMPQ_INLINE int fmpq_is_pm1(const fmpq_t x)
0128 {
0129     return fmpz_is_pm1(fmpq_numref(x)) && fmpz_is_one(fmpq_denref(x));
0130 }
0131
0132 FMPQ_INLINE int fmpq_sgn(const fmpq_t x)
0133 {
0134     return fmpz_sgn(fmpq_numref(x));
0135 }
0136
0137 FMPQ_INLINE int fmpq_equal_si(fmpq_t q, slong n)
0138 {
0139     return fmpz_is_one(fmpq_denref(q)) && fmpz_equal_si(fmpq_numref(q), n);
0140 }
0141 FMPQ_INLINE int fmpq_equal_ui(fmpq_t q, ulong n)
0142 {
0143     return fmpz_is_one(fmpq_denref(q)) && fmpz_equal_ui(fmpq_numref(q), n);
0144 }
0145 FMPQ_INLINE int fmpq_equal(const fmpq_t x, const fmpq_t y)
0146 {
0147     return fmpz_equal(fmpq_numref(x), fmpq_numref(y)) && fmpz_equal(fmpq_denref(x), fmpq_denref(y));
0148 }
0149
0150 int _fmpq_cmp_si(const fmpz_t p, const fmpz_t q, slong c);
0151 int _fmpq_cmp_ui(const fmpz_t p, const fmpz_t q, ulong c);
0152 int _fmpq_cmp_fmpz(const fmpz_t p, const fmpz_t q, const fmpz_t r);
0153 int _fmpq_cmp(const fmpz_t p, const fmpz_t q, const fmpz_t r, const fmpz_t s);
0154
0155 int fmpq_cmp_si(const fmpq_t x, slong c);
0156 int fmpq_cmp_ui(const fmpq_t x, ulong c);
0157 int fmpq_cmp_fmpz(const fmpq_t x, const fmpz_t y);
0158 int fmpq_cmp(const fmpq_t x, const fmpq_t y);
0159
0160 flint_bitcnt_t fmpq_height_bits(const fmpq_t x);
0161
0162 void fmpq_height(fmpz_t height, const fmpq_t x);
0163
0164 /* arithmetic ****************************************************************/
0165
0166 FMPQ_INLINE void fmpq_neg(fmpq_t dest, const fmpq_t src)
0167 {
0168     fmpz_neg(fmpq_numref(dest), fmpq_numref(src));
0169     fmpz_set(fmpq_denref(dest), fmpq_denref(src));
0170 }
0171
0172 FMPQ_INLINE void fmpq_abs(fmpq_t dest, const fmpq_t src)
0173 {
0174     fmpz_abs(fmpq_numref(dest), fmpq_numref(src));
0175     fmpz_set(fmpq_denref(dest), fmpq_denref(src));
0176 }
0177
0178 void _fmpq_add_si(fmpz_t rnum, fmpz_t rden, const fmpz_t p, const fmpz_t q, slong r);
0179 void _fmpq_add_ui(fmpz_t rnum, fmpz_t rden, const fmpz_t p, const fmpz_t q, ulong r);
0180 void _fmpq_add_fmpz(fmpz_t rnum, fmpz_t rden, const fmpz_t p, const fmpz_t q, const fmpz_t r);
0181 void _fmpq_add_small(fmpz_t rnum, fmpz_t rden, slong p1, ulong q1, slong p2, ulong q2);
0182 void _fmpq_add(fmpz_t rnum, fmpz_t rden, const fmpz_t op1num, const fmpz_t op1den, const fmpz_t op2num, const fmpz_t op2den);
0183
0184 void fmpq_add_si(fmpq_t res, const fmpq_t op1, slong c);
0185 void fmpq_add_ui(fmpq_t res, const fmpq_t op1, ulong c);
0186 void fmpq_add_fmpz(fmpq_t res, const fmpq_t op1, const fmpz_t c);
0187 void fmpq_add(fmpq_t res, const fmpq_t op1, const fmpq_t op2);
0188
0189 void _fmpq_sub_si(fmpz_t rnum, fmpz_t rden, const fmpz_t p, const fmpz_t q, slong r);
0190 void _fmpq_sub_ui(fmpz_t rnum, fmpz_t rden, const fmpz_t p, const fmpz_t q, ulong r);
0191 void _fmpq_sub_fmpz(fmpz_t rnum, fmpz_t rden, const fmpz_t p, const fmpz_t q, const fmpz_t r);
0192 void _fmpq_sub(fmpz_t rnum, fmpz_t rden, const fmpz_t op1num, const fmpz_t op1den, const fmpz_t op2num, const fmpz_t op2den);
0193
0194 void fmpq_sub_si(fmpq_t res, const fmpq_t op1, slong c);
0195 void fmpq_sub_ui(fmpq_t res, const fmpq_t op1, ulong c);
0196 void fmpq_sub_fmpz(fmpq_t res, const fmpq_t op1, const fmpz_t c);
0197 void fmpq_sub(fmpq_t res, const fmpq_t op1, const fmpq_t op2);
0198
0199 void _fmpq_mul_si(fmpz_t rnum, fmpz_t rden, const fmpz_t p, const fmpz_t q, slong r);
0200 void _fmpq_mul_ui(fmpz_t rnum, fmpz_t rden, const fmpz_t p, const fmpz_t q, ulong r);
0201 void _fmpq_mul_small(fmpz_t rnum, fmpz_t rden, slong p1, ulong q1, slong p2, ulong q2);
0202 void _fmpq_mul(fmpz_t rnum, fmpz_t rden, const fmpz_t op1num, const fmpz_t op1den, const fmpz_t op2num, const fmpz_t op2den);
0203
0204 void fmpq_mul_si(fmpq_t res, const fmpq_t op1, slong c);
0205 void fmpq_mul_ui(fmpq_t res, const fmpq_t op1, ulong c);
0206 void fmpq_mul_fmpz(fmpq_t res, const fmpq_t op, const fmpz_t x);
0207 void fmpq_mul_2exp(fmpq_t res, const fmpq_t x, flint_bitcnt_t exp);
0208 void fmpq_mul(fmpq_t res, const fmpq_t op1, const fmpq_t op2);
0209
0210 void fmpq_inv(fmpq_t dest, const fmpq_t src);
0211
0212 void _fmpq_div(fmpz_t rnum, fmpz_t rden, const fmpz_t op1num, const fmpz_t op1den, const fmpz_t op2num, const fmpz_t op2den);
0213
0214 void fmpq_div_fmpz(fmpq_t res, const fmpq_t op, const fmpz_t x);
0215 void fmpq_div_2exp(fmpq_t res, const fmpq_t x, flint_bitcnt_t exp);
0216 void fmpq_div(fmpq_t res, const fmpq_t op1, const fmpq_t op2);
0217
0218 void _fmpq_pow_si(fmpz_t rnum, fmpz_t rden, const fmpz_t opnum, const fmpz_t opden, slong e);
0219
0220 void fmpq_pow_si(fmpq_t rop, const fmpq_t op, slong e);
0221 int fmpq_pow_fmpz(fmpq_t a, const fmpq_t b, const fmpz_t e);
0222
0223 void _fmpq_addmul(fmpz_t rnum, fmpz_t rden, const fmpz_t op1num, const fmpz_t op1den, const fmpz_t op2num, const fmpz_t op2den);
0224 void _fmpq_submul(fmpz_t rnum, fmpz_t rden, const fmpz_t op1num, const fmpz_t op1den, const fmpz_t op2num, const fmpz_t op2den);
0225
0226 void fmpq_addmul(fmpq_t res, const fmpq_t op1, const fmpq_t op2);
0227 void fmpq_submul(fmpq_t res, const fmpq_t op1, const fmpq_t op2);
0228
0229 /* I/O ***********************************************************************/
0230
0231 #ifdef FLINT_HAVE_FILE
0232 int _fmpq_fprint(FILE * file, const fmpz_t num, const fmpz_t den);
0233 int fmpq_fprint(FILE * file, const fmpq_t x);
0234 #endif
0235
0236 int _fmpq_print(const fmpz_t num, const fmpz_t den);
0237 int fmpq_print(const fmpq_t x);
0238
0239 /* randomisation *************************************************************/
0240
0241 void _fmpq_randtest(fmpz_t num, fmpz_t den, flint_rand_t state, flint_bitcnt_t bits);
0242 void _fmpq_randbits(fmpz_t num, fmpz_t den, flint_rand_t state, flint_bitcnt_t bits);
0243
0244 void fmpq_randtest(fmpq_t res, flint_rand_t state, flint_bitcnt_t bits);
0245 void fmpq_randtest_not_zero(fmpq_t res, flint_rand_t state, flint_bitcnt_t bits);
0246 void fmpq_randbits(fmpq_t res, flint_rand_t state, flint_bitcnt_t bits);
0247
0248 /* modular arithmetic ********************************************************/
0249
0250 int _fmpq_mod_fmpz(fmpz_t res, const fmpz_t num, const fmpz_t den, const fmpz_t mod);
0251 int fmpq_mod_fmpz(fmpz_t res, const fmpq_t x, const fmpz_t mod);
0252
0253 void _fmpq_gcd(fmpz_t rnum, fmpz_t rden, const fmpz_t p, const fmpz_t q, const fmpz_t r, const fmpz_t s);
0254 void fmpq_gcd(fmpq_t res, const fmpq_t op1, const fmpq_t op2);
0255
0256 void _fmpq_gcd_cofactors(fmpz_t ng, fmpz_t dg, fmpz_t A, fmpz_t B, const fmpz_t na, const fmpz_t da, const fmpz_t nb, const fmpz_t db);
0257 void fmpq_gcd_cofactors(fmpq_t g, fmpz_t A, fmpz_t B, const fmpq_t a, const fmpq_t b);
0258
0259 int _fmpq_reconstruct_fmpz(fmpz_t num, fmpz_t den, const fmpz_t a, const fmpz_t m);
0260 int fmpq_reconstruct_fmpz(fmpq_t res, const fmpz_t a, const fmpz_t m);
0261
0262 int _fmpq_reconstruct_fmpz_2_naive(fmpz_t n, fmpz_t d, const fmpz_t a, const fmpz_t m, const fmpz_t N, const fmpz_t D);
0263 int _fmpq_reconstruct_fmpz_2(fmpz_t n, fmpz_t d, const fmpz_t a, const fmpz_t m, const fmpz_t N, const fmpz_t D);
0264 int fmpq_reconstruct_fmpz_2(fmpq_t res, const fmpz_t a, const fmpz_t m, const fmpz_t N, const fmpz_t D);
0265
0266 /* rational enumeration ******************************************************/
0267
0268 void _fmpq_next_calkin_wilf(fmpz_t rnum, fmpz_t rden, const fmpz_t num, const fmpz_t den);
0269 void fmpq_next_calkin_wilf(fmpq_t res, const fmpq_t x);
0270
0271 void _fmpq_next_signed_calkin_wilf(fmpz_t rnum, fmpz_t rden, const fmpz_t num, const fmpz_t den);
0272 void fmpq_next_signed_calkin_wilf(fmpq_t res, const fmpq_t x);
0273
0274 void _fmpq_next_minimal(fmpz_t rnum, fmpz_t rden, const fmpz_t num, const fmpz_t den);
0275 void fmpq_next_minimal(fmpq_t res, const fmpq_t x);
0276
0277 void _fmpq_next_signed_minimal(fmpz_t rnum, fmpz_t rden, const fmpz_t num, const fmpz_t den);
0278 void fmpq_next_signed_minimal(fmpq_t res, const fmpq_t x);
0279
0280 void fmpq_farey_neighbors(fmpq_t left, fmpq_t right, const fmpq_t mid, const fmpz_t Q);
0281
0282 void _fmpq_simplest_between(fmpz_t mid_num, fmpz_t mid_den, const fmpz_t l_num, const fmpz_t l_den, const fmpz_t r_num, const fmpz_t r_den);
0283 void fmpq_simplest_between(fmpq_t mid, const fmpq_t l, const fmpq_t r);
0284
0285 /* continued fractions *******************************************************/
0286
0287 slong fmpq_get_cfrac_naive(fmpz * c, fmpq_t rem, const fmpq_t x, slong n);
0288 slong fmpq_get_cfrac(fmpz * c, fmpq_t rem, const fmpq_t x, slong n);
0289
0290 void fmpq_set_cfrac(fmpq_t x, const fmpz * c, slong n);
0291
0292 slong fmpq_cfrac_bound(const fmpq_t x);
0293
0294 /* miscellaneous *************************************************************/
0295
0296 void fmpq_dedekind_sum_naive(fmpq_t s, const fmpz_t h, const fmpz_t k);
0297 void fmpq_dedekind_sum(fmpq_t s, const fmpz_t h, const fmpz_t k);
0298
0299 void _fmpq_harmonic_ui(fmpz_t num, fmpz_t den, ulong n);
0300 void fmpq_harmonic_ui(fmpq_t x, ulong n);
0301
0302 /*********************** 2x2 integer matrix **********************************/
0303
0304 typedef struct {
0305     fmpz_t _11, _12, _21, _22;
0306     int det;    /* 0,1,or,-1: 0 -> don't know, 1 -> 1, -1 -> -1 */
0307 } _fmpz_mat22_struct;
0308
0309 typedef _fmpz_mat22_struct _fmpz_mat22_t[1];
0310
0311 typedef struct {
0312     ulong _11, _12, _21, _22;
0313     int det;    /* ditto */
0314 } _ui_mat22_struct;
0315
0316 typedef _ui_mat22_struct _ui_mat22_t[1];
0317
0318 void _fmpz_mat22_init(_fmpz_mat22_t M);
0319 void _fmpz_mat22_clear(_fmpz_mat22_t M);
0320
0321 void _fmpz_mat22_one(_fmpz_mat22_t M);
0322
0323 int _fmpz_mat22_is_one(_fmpz_mat22_t M);
0324
0325 flint_bitcnt_t _fmpz_mat22_bits(const _fmpz_mat22_t N);
0326
0327 void _fmpz_mat22_rmul(_fmpz_mat22_t M, const _fmpz_mat22_t N);
0328 void _fmpz_mat22_rmul_ui(_fmpz_mat22_t M, const _ui_mat22_t N);
0329 void _fmpz_mat22_rmul_inv_ui(_fmpz_mat22_t M, const _ui_mat22_t N);
0330
0331 void _fmpz_mat22_rmul_elem(_fmpz_mat22_t M, const fmpz_t q);
0332 void _fmpz_mat22_lmul_elem(_fmpz_mat22_t M, const fmpz_t q);
0333
0334 void _fmpz_mat22_rmul_inv_elem(_fmpz_mat22_t M, const fmpz_t q);
0335
0336 void _fmpz_mat22_addmul_inv_vec(fmpz_t ya, fmpz_t yb, _fmpz_mat22_t N, fmpz_t xa, fmpz_t xb);
0337 void _fmpz_mat22_addmul_inv_mat(fmpz_t A11, fmpz_t A12, fmpz_t A21, fmpz_t A22, _fmpz_mat22_t M, fmpz_t B11, fmpz_t B12, fmpz_t B21, fmpz_t B22);
0338
0339 /******** resizable integer vector specific to cfrac functionality ***********/
0340
0341 typedef struct
0342 {
0343     fmpz * array;
0344     slong length;
0345     slong alloc;
0346     slong limit;
0347     fmpz_t alt_sum;
0348     int want_alt_sum;
0349 } _fmpq_cfrac_list_struct;
0350
0351 typedef _fmpq_cfrac_list_struct _fmpq_cfrac_list_t[1];
0352
0353 void _fmpq_cfrac_list_init(_fmpq_cfrac_list_t v);
0354 void _fmpq_cfrac_list_clear(_fmpq_cfrac_list_t v);
0355
0356 void _fmpq_cfrac_list_fit_length(_fmpq_cfrac_list_t v, slong len);
0357
0358 void _fmpq_cfrac_list_push_back(_fmpq_cfrac_list_t v, const fmpz_t a);
0359 void _fmpq_cfrac_list_push_back_zero(_fmpq_cfrac_list_t v);
0360
0361 void _fmpq_cfrac_list_append_ui(_fmpq_cfrac_list_t v, const ulong * a, slong n);
0362
0363 /*************** ball for closed interval [left, right] **********************/
0364
0365 typedef struct {
0366     fmpz_t left_num, left_den, right_num, right_den;
0367     int exact;
0368 } _fmpq_ball_struct;
0369
0370 typedef _fmpq_ball_struct _fmpq_ball_t[1];
0371
0372 void _fmpq_ball_init(_fmpq_ball_t x);
0373 void _fmpq_ball_clear(_fmpq_ball_t x);
0374
0375 FLINT_FORCE_INLINE void _fmpq_ball_swap(_fmpq_ball_t x, _fmpq_ball_t y)
0376 {
0377     FLINT_SWAP(_fmpq_ball_struct, *x, *y);
0378 }
0379
0380 int _fmpq_ball_gt_one(const _fmpq_ball_t x);
0381
0382 void _fmpq_hgcd(_fmpq_cfrac_list_t s, _fmpz_mat22_t M, fmpz_t x_num, fmpz_t x_den);
0383
0384 void _fmpq_ball_get_cfrac(_fmpq_cfrac_list_t s, _fmpz_mat22_t M, int needM, _fmpq_ball_t x);
0385
0386 /* Inlines *******************************************************************/
0387
0388 void fmpq_numerator(fmpz_t n, const fmpq_t q);
0389 void fmpq_denominator(fmpz_t n, const fmpq_t q);
0390 fmpz * fmpq_numerator_ptr(fmpq_t q);
0391 fmpz * fmpq_denominator_ptr(fmpq_t q);
0392 int fmpq_equal_fmpz(fmpq_t q, fmpz_t n);
0393
0394 #ifdef __cplusplus
0395 }
0396 #endif
0397
0398 #endif