include/flint/arith.h

0001 /*
0002     Copyright (C) 2010-2012 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 ARITH_H
0013 #define ARITH_H
0014
0015 #include "fmpq_types.h"
0016
0017 #ifdef __cplusplus
0018  extern "C" {
0019 #endif
0020
0021 /* Various arithmetic functions **********************************************/
0022
0023 void _arith_harmonic_number(fmpz_t num, fmpz_t den, slong n);
0024 void arith_harmonic_number(fmpq_t x, slong n);
0025
0026 void arith_ramanujan_tau(fmpz_t res, const fmpz_t n);
0027 void arith_ramanujan_tau_series(fmpz_poly_t res, slong n);
0028
0029 void arith_divisors(fmpz_poly_t res, const fmpz_t n);
0030
0031 /* Stirling numbers **********************************************************/
0032
0033 void arith_stirling_number_1u(fmpz_t s, ulong n, ulong k);
0034 void arith_stirling_number_1(fmpz_t s, ulong n, ulong k);
0035 void arith_stirling_number_2(fmpz_t s, ulong n, ulong k);
0036
0037 void arith_stirling_number_1u_vec(fmpz * row, ulong n, slong klen);
0038 void arith_stirling_number_1_vec(fmpz * row, ulong n, slong klen);
0039 void arith_stirling_number_2_vec(fmpz * row, ulong n, slong klen);
0040
0041 void arith_stirling_matrix_1u(fmpz_mat_t mat);
0042 void arith_stirling_matrix_1(fmpz_mat_t mat);
0043 void arith_stirling_matrix_2(fmpz_mat_t mat);
0044
0045 /* Bell numbers **************************************************************/
0046
0047 #if FLINT64
0048 #define BELL_NUMBER_TAB_SIZE 26
0049 #else
0050 #define BELL_NUMBER_TAB_SIZE 16
0051 #endif
0052
0053 FLINT_DLL extern const ulong bell_number_tab[];
0054
0055 double arith_bell_number_size(ulong n);
0056
0057 void arith_bell_number(fmpz_t b, ulong n);
0058 void arith_bell_number_dobinski(fmpz_t res, ulong n);
0059 void arith_bell_number_multi_mod(fmpz_t res, ulong n);
0060
0061 void arith_bell_number_vec(fmpz * b, slong n);
0062 void arith_bell_number_vec_recursive(fmpz * b, slong n);
0063 void arith_bell_number_vec_multi_mod(fmpz * b, slong n);
0064
0065 ulong arith_bell_number_nmod(ulong n, nmod_t mod);
0066
0067 void arith_bell_number_nmod_vec(nn_ptr b, slong n, nmod_t mod);
0068 void arith_bell_number_nmod_vec_recursive(nn_ptr b, slong n, nmod_t mod);
0069 int arith_bell_number_nmod_vec_series(nn_ptr b, slong n, nmod_t mod);
0070 void arith_bell_number_nmod_vec_ogf(nn_ptr res, slong len, nmod_t mod);
0071
0072
0073 /* Euler numbers *************************************************************/
0074
0075 #if FLINT64
0076 #define SMALL_EULER_LIMIT 25
0077 #else
0078 #define SMALL_EULER_LIMIT 15
0079 #endif
0080
0081 static const ulong euler_number_small[] = {
0082     UWORD(1), UWORD(1), UWORD(5), UWORD(61), UWORD(1385), UWORD(50521), UWORD(2702765),
0083     UWORD(199360981),
0084 #if FLINT64
0085     UWORD(19391512145), UWORD(2404879675441), UWORD(370371188237525),
0086     UWORD(69348874393137901), UWORD(15514534163557086905)
0087 #endif
0088 };
0089
0090 double arith_euler_number_size(ulong n);
0091 void arith_euler_number_vec(fmpz * res, slong n);
0092 void arith_euler_number(fmpz_t res, ulong n);
0093
0094 void arith_euler_polynomial(fmpq_poly_t poly, ulong n);
0095
0096 /* Bernoulli numbers *********************************************************/
0097
0098 #if FLINT64
0099 #define BERNOULLI_SMALL_NUMER_LIMIT 35
0100 #else
0101 #define BERNOULLI_SMALL_NUMER_LIMIT 27
0102 #endif
0103
0104 static const slong _bernoulli_numer_small[] = {
0105     WORD(1), WORD(1), WORD(-1), WORD(1), WORD(-1), WORD(5), WORD(-691), WORD(7), WORD(-3617), WORD(43867), WORD(-174611), WORD(854513),
0106     WORD(-236364091), WORD(8553103),
0107 #if FLINT64
0108     WORD(-23749461029), WORD(8615841276005), WORD(-7709321041217), WORD(2577687858367)
0109 #endif
0110 };
0111
0112 void _arith_bernoulli_number(fmpz_t num, fmpz_t den, ulong n);
0113 void arith_bernoulli_number(fmpq_t x, ulong n);
0114
0115 void _arith_bernoulli_number_vec(fmpz * num, fmpz * den, slong n);
0116 void arith_bernoulli_number_vec(fmpq * num, slong n);
0117
0118 void arith_bernoulli_number_denom(fmpz_t den, ulong n);
0119 double arith_bernoulli_number_size(ulong n);
0120
0121 void arith_bernoulli_polynomial(fmpq_poly_t poly, ulong n);
0122
0123 void _arith_bernoulli_number_vec_multi_mod(fmpz * num, fmpz * den, slong n);
0124 void _arith_bernoulli_number_vec_recursive(fmpz * num, fmpz * den, slong n);
0125
0126 /* Landau function ***********************************************************/
0127
0128 void arith_landau_function_vec(fmpz * res, slong len);
0129
0130 /* Exponential sums **********************************************************/
0131
0132 typedef struct
0133 {
0134     int n;
0135     int prefactor;
0136     ulong sqrt_p;
0137     ulong sqrt_q;
0138     slong cos_p[FLINT_BITS];
0139     ulong cos_q[FLINT_BITS];
0140 } trig_prod_struct;
0141
0142 typedef trig_prod_struct trig_prod_t[1];
0143
0144 FLINT_FORCE_INLINE
0145 void trig_prod_init(trig_prod_t sum)
0146 {
0147     sum->n = 0;
0148     sum->prefactor = 1;
0149     sum->sqrt_p = 1;
0150     sum->sqrt_q = 1;
0151 }
0152
0153 void arith_hrr_expsum_factored(trig_prod_t prod, ulong k, ulong n);
0154
0155 /* Number of partitions ******************************************************/
0156
0157 FLINT_DLL extern const unsigned int partitions_lookup[128];
0158
0159 void arith_number_of_partitions_nmod_vec(nn_ptr res, slong len, nmod_t mod);
0160 void arith_number_of_partitions_vec(fmpz * res, slong len);
0161 void arith_number_of_partitions(fmpz_t x, ulong n);
0162
0163 /* Number of sums of squares representations *********************************/
0164
0165 void arith_sum_of_squares(fmpz_t r, ulong k, const fmpz_t n);
0166 void arith_sum_of_squares_vec(fmpz * r, ulong k, slong n);
0167
0168 /* to be deprecated **********************************************************/
0169
0170 #define arith_primorial fmpz_primorial
0171 #define arith_divisor_sigma fmpz_divisor_sigma
0172 #define arith_moebius_mu fmpz_moebius_mu
0173 #define arith_euler_phi fmpz_euler_phi
0174 #define _arith_cyclotomic_polynomial _fmpz_poly_cyclotomic
0175 #define arith_cyclotomic_polynomial fmpz_poly_cyclotomic
0176 #define _arith_chebyshev_t_polynomial _fmpz_poly_chebyshev_t
0177 #define arith_chebyshev_t_polynomial fmpz_poly_chebyshev_t
0178 #define _arith_chebyshev_u_polynomial _fmpz_poly_chebyshev_u
0179 #define arith_chebyshev_u_polynomial fmpz_poly_chebyshev_u
0180 #define arith_legendre_polynomial fmpq_poly_legendre_p
0181 #define _arith_swinnerton_dyer_polynomial _fmpz_poly_swinnerton_dyer
0182 #define arith_swinnerton_dyer_polynomial fmpz_poly_swinnerton_dyer
0183 #define arith_dedekind_sum_naive fmpq_dedekind_sum_naive
0184 #define arith_dedekind_sum fmpq_dedekind_sum
0185
0186 #ifdef __cplusplus
0187 }
0188 #endif
0189
0190 #endif