v 1.0 -- 2-Dec-07 :
* First version of FLINT, includes fmpz_poly, fmpz and mpQS
v 1.0.1 -- 7-Dec-07 :
* Fixed a bug in _fmpz_poly_maxbits1 on 32 bit machines, reported by Michael Abshoff and Carl Witty
* Removed some instances of u_int64_t and replaced them with uint64_t, reported by Michael Abshoff
* Replaced sys/types.h with stdint.h
* Added FLINT macros to documentation
* Corrected numerous typos in documentation
v 1.0.2 -- 10-Dec-07
* Rewrote tuning code for integer multiplication functions, making it more robust and fixing a bug
which showed up on 32 bit machines (reported by Michael Abshoff and Jaap Spies). Factored the tuning
code out into a number of macros.
v 1.0.3 -- 16-Dec-07
* Fixed a bug in the polynomial memory management code which caused a segfault
* Fixed a bug in the pseudo division code which caused a block overrun
v 1.0.4 -- 04-Jan-08
* Fixed a bug in the bernoulli_zmod example program and associated polynomial zmod code which caused memory corruption.
* Fixed a bug in the fmpz-test code which manifested on 32 bit machines, reported by David Harvey.
* Fixed some bugs in the pari profiling code.
v 1.0.5 -- 05-Jan-08
* Fixed some inline issues which cause problems because of the C99 inline rules (reported by David Harvey).
* Fixed a makefile issue reported (and solved) by David Harvey when *not* linking against NTL.
v 1.0.6 -- 17-Jan-08
* Fixed an issue with FLINT_BIT_COUNT on certain machines (probably due to arithmetic shift issues)
v 1.0.7 -- 22-Jan-08
* Made F_mpn_mul binary compatible with the way mpn_mul *operates* in practice.
v 1.0.8 -- 15-Feb-08
* Fixed a bug in fmpz_poly_right_shift (reported by Kiran Kedlaya)
v 1.0.9 -- 11-Mar-08
* Fixed a memory allocation bug in fmpz_poly_power
v 1.0.10 -- 16-Jun-08:
* integer gcd (this just wraps the GMP gcd code)
* polynomial content
* convert to and from FLINT and NTL integers and polynomials
* get a coefficient of a polynomial efficiently as a read only mpz_t
* print polynomials in a prettified format with a specified variable
v 1.0.11 -- 9-Jul-08
* Fixed a bug in z_ll_mod_precomp on ia64 (reported by Michael Abshoff and William Stein)
v 1.0.12 -- 11-Jul-08
* Removed some Opteron tuning flags which cause illegal instruction errors on Pentium4
* Fixed numerous memory leaks in fmpz_poly test code
* Fixed memory leak in fmpz_poly_power_trunc_n
* Fixed major memory leaks in fmpz_poly_xgcd_modular
* Rewrote __fmpz_poly_mul_karatrunc_recursive and _fmpz_poly_mul_karatsuba_trunc to "prove code" and got rid of some dirty memory issues
* Fixed some potential illegal memory accesses to do with cache prefetching in fmpz_poly.c
v 1.0.13 -- 13-Jul-08
* Fixed memory leaks and dirty memory issues in test code for numerous modules.
* Removed further issues with cache prefetching in mpn_extras.c
v 1.0.14 -- 23-Sep-08
* Update long_extras and test code for the sake of new quadratic sieve (new functions in long_extras remain undocumented)
* Removed many bugs from tinyQS and mpQS and joined them into a single program for factoring integers
v 1.0.15 -- 15-Oct-08
* Fixed a bug which causes a segfault when setting a coefficient of the zero polynomial to zero
* Fixed build bug in longlong.h on s390 platform
v 1.0.16 -- 22-Oct-08
* Fixed a segfault when trying to truncate a polynomial to an longer length than it currently is, with the function fmpz_poly_truncate (reported by Craig Citro)
v 1.0.17 -- 30-Nov-08
* Fixed a segfault caused by left shifting of polynomials with zero limbs allocated in division and pseudo division functions.
* Fixed a bound used in fmpz_gcd_modular to use a proven bound
* Fixed a bug in fmpz_poly-profile where the top bit of random coefficients of n bits was always set
v 1.0.18 -- 05-Dec-08
* Fixed another bug in the fmpz_poly_set_coeff_* functions which resulted in dirty coefficients
v 1.0.19 -- 12-Dec-08
* Fixed a bug in z_remove_precomp
v 1.0.20 -- 13-Dec-08
* Fixed some bugs in conversion of zmod_poly's to and from strings
v 1.0.21 -- 25-Dec-08
* Fixed the Christmas bug reported by Michael Abshoff which causes a test failure in fmpz_poly_gcd_modular and a hang in fmpz_poly_invmod_modular on 32 bit machines
v 1.1.0 -- 21-Dec-08 (some of the following features were previewed in FLINT 1.0.11):
* integer gcd (this just wraps the GMP gcd code)
* polynomial content
* primitive part
* convert to and from FLINT and NTL integers and polynomials
* get a coefficient of a polynomial efficiently as a read only mpz_t
* print polynomials in a prettified format with a specified variable
* Sped up integer multiplication
* Convert to and from zmod_polys from fmpz_polys
* Chinese remainder for fmpz_polys
* Leading coeff macro
* Euclidean norm of polynomials
* Exact division testing of polynomials
* Polynomial GCD (subresultant, heuristic, modular)
* Modular inversion of polynomials
* Resultant
* XGCD (Pohst-Zassenhaus)
* Multimodular polynomial multiplication
* Rewritten karatsuba_trunc function
* Rewritten division functions
* Polynomial derivative
* Polynomial evaluation
* Polynomial composition
* Addition and subtraction of zmod_polys
* Sped up multiplication of zmod_polys
* Extended multiplication of zmod_polys to allow up to 63 bit moduli
* zmod_poly subpolynomials
* zmod_poly reverse
* Truncated multiplication for zmod_polys (left, right, classical and KS)
* Scalar multiplication
* Division for zmod_polys (divrem and div, classical, divide and conquer and newton)
* Series inversion for zmod_polys
* Series division for zmod_polys
* Resultant for zmod_polys
* GCD for zmod_polys including half-gcd
* Inversion modulo a polynomial for zmod_polys
* XGCD for zmod_polys
* Squarefree factorisation for zmod_polys
* Berlekamp factorisation for zmod_polys
* Irreducibility testing for zmod_polys
* Derivative for zmod_polys
* Middle product for zmod_polys (sped up newton division)
* addmod, submod and divmod for ulongs
* Sped up limb sized integer square root
* Partial factoring of ulongs
* z_randbits
* Pocklington-Lehmer primality testing
* BSPW pseudo-primality testing
* Fermat pseudo-primality testing
* Fast Legendre symbol computation
* Chinese remainder for fmpzs
* Square root with remainder for fmpzs
* Left and right shift for fmpzs
* Reduction modulo a ulong for fmpzs
* Montgomery redc, mulmod, divmod and mod for fmpzs
* Multimodular reduction and CRT for fmpzs
* fmpz_mulmod and fmpz_divmod
* fmpz_invert for inversion modulo an fmpz
* Dramatically sped up gcd for small fmpzs
* Computation of 1D, 2D and some 3D theta functions
* Example program for multiplying theta functions
* Test code now times test functions
* Quick and dirty timing function for profiler
* Tiny quadratic sieve for small one and two limb integers
* Completely rewritten self initialising multiple polynomial quadratic sieve
* Build fix for 64 bit OSX dylibs (reported by Michael Abshoff)
v 1.1.1 -- 11-Feb-09
* Fixed bugs in _fmpz_poly_scalar_mul_fmpz, fmpz_poly_gcd_heuristic and fmpz_poly_gcd_subresultant and fixed bugs in test__fmpz_poly_scalar_div_fmpz, test_fmpz_poly_scalar_div_fmpz and test_fmpz_poly_scalar_div_mpz.
v 1.1.2 -- 1-Mar-09
* Fixed some memory allocation slowdowns and bugs in fmpz_poly division and pseudo division functions (reported by William Stein).
v 1.1.3 -- 1-Mar-09
* Inserted some missing return values in zmod_poly test code.
v 1.2.0 -- 10-Mar-09
* made memory manager, fmpz and fmpz_poly threadsafe
* Code for running tests in parallel (not activated)
* Sped up fmpz_poly_scalar_div_ui/si when scalar is 1/-1
* Parallelise _fmpz_poly_mul_modular
* fmpz_mul_modular_packed to pack coefficients to the byte before running _fmpz_poly_mul_modular
* fmpz_poly_pseudo_rem_cohen (not documented)
* special case for leading coeff 1/-1 in fmpz_poly_pseudo_divrem_basecase
* removed a memory allocation bug which caused a massive slowdown in fmpz_poly_pseudo_divrem_basecase
* fmpz_poly_pseudo_rem_basecase (not documented)
* fmpz_poly_pseudo_rem (not asymptotically fast)
* fmpz_poly_signature (not asymptotically fast)
* basic fmpz_poly_is_squarefree function
* included zn_poly in trunk and made FLINT build zn_poly as part of its build process
* switched to using zn_poly for polynomial multiplication, newton inversion, scalar multiplication in zmod_poly
* Integer cube root of word sized integers
* Fibonacci pseudoprime test
* BSPW probable prime test
* n - 1 primality test
* Complete implementation of z_issquarefree
* Significantly improved the thetaproduct example program.
* Fixed bug in fmpz_poly_byte_pack which is triggered when trying to pack into fields a multiple of 8 bytes (could cause a segfault)
* Fixed a bug in fmpz_poly_pseudo_divrem (relied on an uninitialised poly to have length 0)
* Fixed bug in fmpz_multi_CRT_ui (could segfault)
* Fixed bug in fmpz_multi_mod_ui (could segfault)
* Fixed memory leak in zmod_poly_factor_squarefree
* Fixed memory leak in zmod_poly_from_string
v 1.2.1 -- 14-Mar-09
* Removed some FLINT 2.0 code which was interfering with the build of the NTL-interface
* Removed an omp.h from fmpz_poly.c.
v 1.2.2 -- 20-Mar-09
* Fixed a memory leak in zmod_poly_factor
* Fixed zmod_poly-profile build
v 1.2.3 -- 31-Mar-09
* Fixed bugs in all fmpz_poly evaluation functions, identified by Burcin Erocal.
v 1.2.4 -- 4-Apr-09
* Defined THREAD to be blank on Apple CC and __thread for thread local storage on other gcc's (where it's defined)
* #undef ulong in profiler.h where time.h and other system time headers are included (both reported by M. Abshoff)
v 1.2.5 -- 18-Apr-09
* Upgraded to zn_poly-0.9 to avoid a serious error in squaring of large polynomials over Z/nZ
v 1.3.0 -- 09-Jun-09
* Added new code for checking 2nd, 3rd and 5th roots
* Fixed a bug in z_factor
* Connected quadratic sieve for factoring large ulongs
* Added one line factor algorithm
* constructed best of breed factor algorithm
* Fixed termination conditions for z_intcuberoot and z_intfifthroot which were broken
* Added some code for special cases which cause infinite loops in cuberoot and fifthroot
* Went back to ceil(pow(n, 0.33333333)) and ceil(pow(n, 0.2)) for initial guesses in cube and fifth root functions as these were about 50% faster than sqrt(n) and sqrt(sqrt(n)) respectively.
* Added test code for z_intfifthroot
* Added test code for z_factor_235power
* Fixed some uninitialised data found by valgrind in intcuberoot and intfifthroot
* Fixed multiply defined PRIME_COUNT in long_extras-test
* Got rid of gotos in some functions in long_extras
* Knocked optimisation level back to -O2 because it miscompiles on sage.math
* Changed tables to use uint64_t's instead of ulongs which are not 64 bits on a 32 bit machine
* Only checked MAX_HOLF on 64 bit machine
* Changed MAX_SQUFOF to WORD(-1)
* Check constant 0x3FFFFFFFFUL only on a 64 bit machine
* Fixed a bug in z_oddprime_lt_4096 on 32 bit machines
* Fixed some TLS issues with Cygwin
* Fixed some typos in makefile
* Fixed a wrong path in fmpz.c
v 1.4.0 -- 06-Jul-09
* Sped up zmod_poly division in case where operands are the same length
* Sped up zmod_poly division in case where operands have lengths differing by 1
* Fixed a bug in zmod_poly_gcd for polynomials of zero length
* Sped up zmod_poly_gcd considerably (both euclidean and half gcd)
* Sped up zmod_poly_gcd_invert and zmod_poly_xgcd considerably
* Made zmod_poly_gcd_invert and zmod_poly_xgcd asymptotically fast
* Made zmod_poly_resultant asymptotically fast
* Added optimised zmod_poly_rem function
* Fixed a divide by zero bug in zmod_poly_factor_berlekamp
* Added test code for z_factor_tinyQS and z_factor_HOLF
* Fixed many bugs in the z_factor code, tinyQS and mpQS
* Corrected numerous typos in the documentation and added missing descriptions
* Added F_mpz_cmp function
* Added documentation to the manual for the new F_mpz module
v 1.5.0 -- 22-Sep-09
* Added multimodular reduction and CRT to F_mpz module
* Fixed some bugs in F_mpz module and numerous bugs in test code
* Added zmod_poly_compose
* Added zmod_poly_evaluate
* Added functions for reduced evaluation and composition to fmpz_poly module (contributed by Burcin Erocal)
* Fixed bugs in the primality tests in long_extras
* Removed all polynomial multimodular multiplication functions
* Added new thetaproduct code used in the 1 trillion triangles computation
* Fixed a severe bug in the fmpz_poly_pseudo_div function reported by Sebastian Pancratz
* Added fmpz_comb_temp_init/clear functions
* Fixed a normalisation buglet in fmpz_poly_pack_bytes
* Added F_mpz_pow_ui function (contributed by Andy Novocin)
* Fixed a severe bug in the FFT reported by William Stein and Mariah Lennox (fix contributed by David Harvey)
* Removed some memory leaks from F_mpz test code
* Fixed bug in zmod_poly_evaluate test code
v 1.6.0 -- 24-Dec-10
Bugs:
====
* Fixed a memory leak in mpz_poly_to_string_pretty
* Fixed a bug inherited from an old version of fpLLL
* Makefile to respect CC and CXX
* Fixed bug in F_mpz_set_si
* Fixed bug in F_mpz_equal
* Most for loops to C90 standard (for easier MSVC porting)
* Better Cygwin support
* Fixed a bug in zmod_poly_resultant
* Fixed bug in F_mpz_mul_KS/2
* Fixed bug in tinyQS
* Worked around some known bugs in older GMP/MPIR's
Major new functionality
=======================
* F_mpz_poly_factor_zassenhaus
* F_mpz_poly_factor (incl. fmpz_poly_factor wrapper) using new vH-N approach
(see the paper of van Hoeij and Novocin and the paper of van Hoeij, Novocin
and Hart)
* Implementation of new CLD bounds function for polynomial factors
(see the paper of van Hoeij, Novocin and Hart
* Restartable Hensel lifting
* Heuristic LLL implementations using doubles and mpfr
* LLL implementations optimised for knapsack lattices
* New (probably subquadratic) LLL implementation (ULLL)
* zmod_poly_factor_cantor_zassenhaus
* New F_mpz_mod_poly module for polynomials over Z/pZ for multiprec. p
Some of the other new functions added
=====================================
F_mpz:
* F_mpz_gcd
* F_mpz_smod
* F_mpz_mod_preinv
* F_mpz_fdiv_qr
* F_mpz_get/set_mpfr/2exp
* F_mpz_sscanf
* F_mpz_set_d
F_mpz_poly:
* read F_mpz_poly to_string/from_string/fprint/print/fread/pretty
* F_mpz_poly_to/from_zmod_poly
* F_mpz_poly_scalar_div_exact
* F_mpz_poly_smod
* F_mpz_poly_derivative, F_mpz_poly_content, F_mpz_poly_eval_horner_d/2exp
* F_mpz_poly_scalar_abs
* F_mpz_poly_set_d_2exp
* F_mpz_poly_div/divrem
* F_mpz_poly_gcd
* F_mpz_poly_is_squarefree
* F_mpz_poly_factor_squarefree
* F_mpz_poly_mul_trunc_left
* F_mpz_poly_pseudo_div
* F_mpz_poly_set_coeff
* F_mpz_poly_pow_ui
* Inflation/deflation trick for factorisation
zmod_poly:
* Inflation/deflation trick for factorisation
mpz_mat:
* mpz_mat_from_string/to_string/fprint/fread/pretty
mpq_mat:
* mpq_mat_init/clear
* Gramm-schmidt Orthogonalisation
F_mpz_mat:
* F_mpz_mat_print/fprint/fread/pretty
* F_mpz_mat_mul_classical
* F_mpz_mat_max_bits/2
* F_mpz_mat_scalar_mul/div_2exp
* F_mpz_mat_col_equal
* F_mpz_mat_smod
* F_mpz_vec_scalar_product/norm
* F_mpz_vec_add/submul_ui/si/F_mpz/2exp
zmod_mat:
* classical multiplication
* strassen multiplication
* scalar multiplication
* zmod_mat_equal
* zmod_mat_add/sub
* zmod_mat_addmul_classical
d_mat:
* d_vec_norm, d_vec_scalar_product
mpfr_mat:
* mpfr_vec_scalar_product/norm
v 2.0 -- 16 Jan 2011
N.B: FLINT 2 is a complete rewrite of flint from scratch
It includes the following modules:
ulong_extras: (word sized integers and modular arithmetic)
* random numbers (randint, randbits, randprime, randint)
* powering
* reverse binary
* mod, divrem, mulmod all with precomputed inverses
* gcd, invgcd, xgcd
* jacobi symbols
* addmod, submod, invmod, powmod
* prime sieve, nextprime, prime-pi, nth-prime
* primality testing (small, binary search, Pocklington-Lehmer, Pseudosquare)
* probably prime tests (strong base-a, Fermat, Fibonacci, BPSW, Lucas)
* sqrt, sqrtrem, is-square, perfect-power (2,3,5)
* remove, is-squarefree
* factorisation (trial-range, trial, power (2,3,5), one-line, SQUFOF)
* Moebius mu, Euler phi
fmpz: (memory managed multiple precision integers)
* memory management (init, clear)
* random numbers (randbits, randm)
* conversion to and from long, ulong, doubles, mpz's, strings
* read/write to file, stdin, stdout
* sizeinbase, bits, size, sgn, swap, set, zero
* cmp, cmp-ui, cmpabs, equal, is-zero, is-one
* neg, abs, add, add-ui, sub, sub-ui, mul, mul-si, mul-ui, mul-2exp
* addmul, addmul-ui, submul, submul-ui
* cdiv-q, cdiv-q-si, cdiv-q-ui
* fdiv-q, fdiv-q-si, fdiv-q-ui, fdiv-qr, fdiv-q-2exp
* tdiv-q, tdiv-q-si
* divexact, divexact-si, divexact-ui
* mod, mod-ui
* powering
* sqrt, sqrt-rem
* factorial
* gcd, invmod
* bit-pack, bit-unpack
* multimodular reduction, CRT
fmpz_vec: (vectors over fmpz's)
* memory management (init, clear)
* random vectors
* max-bits, max-limbs
* read/write to file/stdin/stdout
* set, swap, zero, neg
* equal, is-zero
* sort
* add, sub
* scalar multiplication by fmpz, ulong, long, 2exp
* exact division by fmpz, long, ulong
* fdiv-q by fmpz, long, ulong, 2exp
* tdiv-q by fmpq, long, ulong
* addmul by fmpz, long, long by 2exp
* submul by fmpz, long, long by 2exp
* Gaussian content
fmpz_poly: (polys over fmpz's)
* memory management (init, realloc, fit-length, clear)
* random polys
* normalise, set-length, truncate
* length, degree, max-limbs, max-bits
* set, set-si, set-ui, set-fmpz, set-str
* get-str, get-str-pretty
* zero, one, zero-coeffs
* swap, reverse
* get/set coeffs from fmpz, long, ulong
* get-coeff-ptr, lead
* equal, is-zero
* add, sub
* scalar multiplication by fmpz, long, ulong
* scalar addmul/submul by fmpz
* scalar fdiv by fmpz, long, ulong
* scalar tdiv by fmpz, long, ulong
* scalar divexact by fmpz, long, ulong
* bit pack, bit unpack
* multiplication (classical, karatsuba, KS)
* mullow (classical, karatsuba, KS)
* mulhigh (classical, karatsuba)
* middle product (classical)
* powering (small, binary exponent, binomial, multinomial, addition chains)
* truncated powering (binary exponent)
* shift left/right
* euclidean norm
* gcd (subresultant)
* resultant
* content, primitive part
* divrem (basecase, divide-and-conquer)
* div (basecase, divide-and-conquer)
* rem (basecase)
* invert series (basecase, Newton)
* div series
* pseudo divrem (basecase, divide-and-conquer, Cohen)
* rem (Cohen)
* div
* evaluate (Horner) at fmpz, mpq, a mod n
* composition (Horner, divide-and-conquer)
* signature
* read/write to file/stdin/stdout
fmpq_poly: (polynomials over Q stored as poly over fmpz with fmpz denominator)
* memory management (init, realloc, fit-length, clear)
* random polys
* set-length, canonicalise, normalise, truncate
* is-canonical, length, degree
* reference to numerator, denominator
* set, set-si, set-ui, set-fmpz, set-mpz, set-mpq
* set-array-mpq, set-str
* get-str, get-str-pretty
* zero, neg, swap
* invert
* set coefficient to mpq, long, ulong, fmpz, mpz
* get coefficient as mpq
* equal, cmp, is-one, is-zero
* add, sub
* scalar multiplication by long, ulong, fmpz, mpq
* scalar division by fmpz, long, ulong, mpq
* multiplication, mullow
* powering
* shift left/right
* divrem, div, rem
* invert series (Newton iteration)
* divide series
* derivative
* evaluate at fmpz, mpq
* composition, scale by constant
* content, primitive part
* make-monic, is-monic
* is-squarefree
* read/write to file/stdin/stdout
nmod_vec: (vectors over Z/nZ for n fitting in a machine word)
* memory management (init/clear)
* macros for efficient reduction of 1, 2 and 3 limb integers mod n
* macro for addmul mod n
* add/sub/neg individual coefficients mod n
* random vectors
* set, zero, swap
* reduce, max-bits
* equal
* add, sub, neg
* scalar multiplication by a value reduced mod n
* scalar addmul by a value reduced mod n
nmod_poly: (polynomials over Z/nZ for n fitting in a machine word)
* memory management (init, realloc, fit-length, clear)
* random polys
* normalise, truncate
* length, degree, modulus, max-bits
* set, swap, zero, reverse
* get/set coefficients as ulongs, strings
* read/write to file, stdin, stdout
* equal, is-zero
* shift left/right
* add, sub, neg
* scalar multiplication by a value reduced mod n
* make-monic
* bit pack, bit unpack
* multiplication (classical, KS)
* mullow (classical, KS)
* mulhigh (classical)
* powering (binary exponent)
* pow-trunc (binary exponent)
* divrem (basecase, divide-and-conquer, Newton iteration)
* div (basecase, divide-and-conquer, Newton iteration)
* invert series (basecase, Newton iteration)
* divide series (Newton iteration)
* derivative
* evaluation at a value taken mod n
* composition (Horner, divide-and-conquer)
* gcd (euclidean)
fmpz_mat: (matrices over fmpz's)
* memory management (init, clear)
* random matrices (bits, integer relations, simultaneous diophantine equations
NTRU-like, ajtai, permutation of rows and cols of a diagonal matrix, random
of given rank, random of given determinant, random elementary operations)
* set, init-set, swap, entry pointer
* write to file or stdout
* equal
* transpose
* multiplication (classical, multimodular)
* inverse
* determinant
* row reduce (Gaussian and Gauss-Jordan fraction-free elimination)
* rank
* solve Ax = b, solve AX = B
* fraction free LU decomposition
nmod_mat: (matrices over Z/nZ for n fitting in a machine word)
* memory management (init, clear)
* random matrices (uniform, full, permutations of diagonal matrix, random of
given rank, random elementary operations)
* set, equal
* print to stdout
* add
* transpose
* multiplication (classical, Strassen, A*B^T)
* row reduction (Gaussian and Gauss-Jordan)
* determinant
* rank
* solve (Ax = b, AX = B, solve with precomputed LU)
* invert
arith: (arithmetic functions)
* Bernoulli numbers
* Bernoulli polynomials
* primorials (product of primes up to n)
* harmonic numbers
* Stirling numbers
* Euler phi function
* Moebius mu function
* Sigma (sum of powers of divisors)
* Ramanujan tau function
examples: (example programs)
* compute coefficients of q-series of Delta function
mpfr_vec: (vectors over mpfr reals)
* memory management (init, clear)
* add
* set, zero
* scalar multiplication by mpfr, 2exp
* scalar product
mpfr_mat: (matrices over mpfr reals)
* memory management (init, clear)
v 2.1 -- 9 Mar 2011
fmpz
----
* Simplified interface for fast multimodular reduction and CRT reconstruction
* Fixed segmentation fault in fmpz_multi_mod_ui when the input exceeds the product of the moduli
* Added simple incremental CRT functions (fmpz_CRT_ui, fmpz_CRT_ui_unsigned) to complement the existing fast ones
* Added example programs for CRT
* Added random number generators designed for testing modular code (fmpz_randtest_mod, fmpz_randtest_mod_signed)
* Added fmpz_fdiv_ui for remainder on division by an ulong
* Added fmpz_bin_uiui for computing binomial coefficients
* Added fmpz_mul2_uiui and fmpz_divexact2_uiui for multiplying or dividing an fmpz by a pair of ulongs (efficiently when their product fits in a single limb)
fmpz_mat
--------
* Added utility functions for basic arithmetic and creating unit matrices
* Added multimodular determinant computation (certified or heuristic)
* Added support for computing right nullspaces (fmpz_mat_kernel). Fast only for small matrices.
* Some internal code cleanup and various small fixes
nmod_mat
--------
* Faster Gaussian elimination for small moduli
* Faster determinants
* Faster matrix inversion and nonsingular solving
nmod_poly
---------
* Added nmod_poly_integral for computing integrals
* Added fast square root and inverse square root of power series
* Added fast transcendental functions of power series (log, exp, sin, cos, tan, sinh, cosh, tanh, asin, atan, asinh, atanh)
* Made nmod_poly_inv_series_newton more memory efficient
fmpq_poly
---------
* Added fmpq_poly_integral for computing integrals
* Added fast transcendental functions of power series (log, exp, sin, cos, tan, sinh, cosh, tanh, asin, atan, asinh, atanh)
arith
-----
* Made computation of vectors of Bernoulli numbers faster
* Added fast computation of single Bernoulli numbers
* Added a separate function for computing denominators of Bernoulli numbers
* Added fast computation of Bell numbers (vector and single)
* Added fast computation of Euler numbers (vector and single)
* Added fast computation of Euler polynomials
* Added fast computation of Swinnerton-Dyer polynomials
* Added fast computation of Legendre polynomials
* Added fast vector computation of the partition function
* Added fast vector computation of Landau's function
ulong_extras
------------
* Added a function for computing factorials mod n
build system
------------
* Added support for building static and shared libraries
* All object files and test/profile/example binaries now build in separate build directory
documentation
-------------
* Large number of corrections
v 2.2 -- 4 Jun 2011
fmpq (multiprecision rational numbers)
--------------------------------------
* Basic arithmetic functions
* Utility functions
* Rational reconstruction
* Functions for enumerating the rationals
fmpq_mat (matrices over Q)
--------------------------
* Basic arithmetic functions
* Utility functions
* Fast multiplication
* Classical and fraction-free reduced row echelon form
* Determinants
* Fast non-singular solving
fmpz_poly_mat (matrices over Z[x]
---------------------------------
* Basic arithmetic functions
* Utility functions
* Fraction-free row reduction and determinants
* Fast determinants (experimental)
fmpz_mat
--------
* Added more utility functions (scalar multiplication, etc)
* Added Dixon's p-adic algorithm (used by fast nonsingular rational system
solving)
* Added reduced row echelon form
* Added conversions between fmpz_mat and nmod_mat
* Added CRT functions for fmpz_mats
* Faster matrix multiplication for small to medium dimensions
longlong.h
----------
* Added x86 assembly macros for accumulating sums of two limb operands
nmod_mat
--------
* Sped up arithmetic for moduli close to FLINT_BITS
arith
-----
* Changed interface of various functions to use new fmpq type
fmpz
----
* Added fmpz_set_ui_mod
* Inlined fmpz_neg, fmpz_set_si, fmpz_set_ui for better performance
* Added fmpz_lcm
* Small performance improvement to fmpz_CRT_ui
fmpz_vec
--------
* Added _fmpz_vec_lcm
fmpz_poly_q (rational functions over Q, modeled as quotients of fmpz_polys)
---------------------------------------------------------------------------
* Basic arithmetic functions
* Conversion and IO functions
* Evaluation
padic (p-adic numbers -- experimental)
-------------------------------------
* Basic arithmetic
* Data conversion and IO
* Inverse and square root using Newton iteration
* Teichmuller lifts (not optimised)
* p-adic exponential function (not optimised)
fmpz_poly
---------
* Added fmpz_poly_gcd_modular (and fmpz_poly_gcd wrapper)
* Added fmpz_poly_xgcd_modular (and fmpz_poly_xgcd wrapper)
* Added conversions between fmpz_poly and nmod_poly
* Added CRT functions
* Added multipoint evaluation and interpolation
nmod_poly
---------
* Added nmod_poly_xgcd_euclidean (and nmod_poly_xgcd wrapper)
* nmod_poly_gcd wrapper
mpn_extras
----------
* Added MPN_NORM and MPN_SWAP macros.
* Added mpn_gcd_full to remove some of the restrictions from the usual mpn_gcd
build fixes
------------
* fixed make install to create nonexistent dirs (reported by Serge Torres)
* -L use /usr instead of /usr/local by default (reported by Serge Torres)
* guards for system headers because of flint's use of ulong
v 2.3 -- 1 Jul 2012
general
-------
* many changes to the build system
* added NTL interface
* switched to custom memory allocation functions flint_malloc etc
* in addition to the entries below, fixed a large number of memory leaks,
problems with the test code, and bugs in corner cases of various functions
* added _fmpz_cleanup_mpz_content as an alternative to _fmpz_cleanup
* support MinGW32
* support Cygwin
* bugfix on ia64
* support sparc32/sparc64
* support OSX
* support Solaris, NetBSD, OpenBSD, etc (if bash, GNU Make present)
ulong_extras
------------
* implemented the improved Lehman algorithm
* added n_jacobi_unsigned to allow n > WORD_MAX
* fixed n_sqrtmod for n > WORD_MAX
* fixed bug causing n_sqrtmod to hang
* added sublinear algorithm for computing factorials mod p
* added n_sqrtmod_primepow, n_sqrtmodn and associated functions for
computing square roots modulo composite integers
* fixed bugs in n_is_prime_pocklington
* fixed UWORD_MAX case in powmod and powmod2
* fixed problems with the random number generators
* fixed rare bug in n_mod_precomp
* fixed rare bug in n_is_prime_pseudosquare
long_extras
-----------
* added z_sizeinbase
qsieve
------
* new module implementing a quadratic sieve for numbers up to two limbs
fft
---
* new module providing an efficient Schoenhage-Strassen FFT
longlong
--------
* added assembly code for ia64 and ARM
* fixed bug in fallback version of add_sssaaaaaa
fmpz
----
* added fmpz_fib_ui
* added double precision natural logarithm
* added fmpz_val2 for 2-valuation
* added mul_2exp, div_2exp, cdiv_q_2exp, tdiv_q_2exp, fdiv_r, fdiv_r_2exp,
tdiv_ui, mul_tdiv_q_2exp
* added get_d/set_d
* added fmpz_divisible, divisible_si
* optimised fmpz_powm and fmpz_powm_ui
* added clog, clog_ui, flog, flog_ui for computing logarithms
* added abs_lbound_ui_2exp, ubound_ui_2exp
* added fmpz_rfac_ui and fmpz_rfac_uiui for rising factorials
* added functions to obtain read-only fmpz_t's from mpz_t's
* added fmpz_init_set, init_set_ui
* added fmpz_gcdinv
* added fmpz_is_square
* added fmpz_tstbit, setbit, clrbit, complement, combit, and, or, xor, popcnt
* added a sign flag for CRT instead of using separate methods
* fixed bugs in fmpz_sqrtmod
* fixed a bug in fmpz_bit_unpack that could cause corruption of the global
fmpz array when compiled in single mode
* fixed a bug in fmpz_sub_ui that could cause memory corruption
fmpz_vec
--------
* added functions for obtaining the largest absolute value coefficient
* added functions for computing the sum and product of an integer vector
* made max_bits much faster
* added _fmpz_vec_mod_fmpz
* made randtest produce sparse output
fmpz_poly
---------
* added fmpz_poly_sqr, fmpz_poly_sqrlow for squaring a polynomial
* added fmpz_poly_lcm
* made multipoint interpolation faster by using the Newton basis
* added a function for fast division by a linear polynomial
* added power series composition (classical and Brent-Kung)
* added power series reversion (classical, Newton, fast Lagrange)
* added a function for obtaining the largest absolute value coefficient
* fixed quadratic memory usage and stack overflow when performing
unbalanced division or pseudo division using the divconquer algorithm
* fixed a bug in poly_zero_coeffs
* fixed a bug in xgcd_modular
* allowing +/-1 in the constant term of power series inversion
* fixed aliasing bug in divrem
* added restartable Hensel lifting and associated utility functions
* fixed rem, which used to only call the basecase algorithm
* fixed pseudo_divrem, which used to only call the basecase algorithm
* implemented Schoenhage-Strassen multiplication (mul_SS, mullow_SS)
and enabled this by default
* fixed a bug in the heuristic GCD algorithm
* added functions for Newton basis conversion
* added functions for fast Taylor shift
* added fmpz_poly_sqrt implementing a basecase algorithm
* added scalar mul_2exp, fdiv_2exp, tdiv_2exp
* made randtest produce sparse output
* added fmpz_poly_equal_fmpz
* improved performance by always using basecase multiplication
when one polynomial is short
* improved algorithm selection for fmpz_poly_gcd
* fixed several bugs in gcd_modular
* improved performance of gcd_modular
fmpz_poly_factor
----------------
* new module for factorisation of fmpz_polys
* added a naive implementation of the Zassenhaus algorithm
fmpz_mod_poly
-------------
* new module for polynomials modulo over Z/nZ for arbitrary-precision n
* multiplication, powering
* classical and divconquer division
* series inversion
* Euclidean GCD and XGCD
* invmod
* radix conversion
* divconquer composition
* GCD and division functions that test invertibility of the
leading coefficient
fmpz_mat
--------
* added det_divisor for computing a random divisor of the determinant
* faster determinant computation using divisor trick
* faster determinant computation by using multimodular updates
* fixed n x 0 x m product not zeroing the result
* various interface improvements
* faster implementation of Cramer's rule for multiple right hand sides
* added fmpz_mat_fread and read
* added multi CRT/mod functions
* added trace
fmpz_poly_mat
-------------
* fixed n x 0 x m product not zeroing the result
* added inverse
* added rank computation
* added reduced row echelon form and nullspace computation
* added more utility functions
* added squaring and exponentiation
* added balanced product of a sequence of matrices
* added truncate, mullow, sqrlow, pow_trunc
* added trace
fmpz_factor
-----------
* new module providing interface for integer factorisation
* fast expansion of a factored integer
fmpq
----
* cleaned up and improved performance of rational reconstruction code
* allow separate numerator and denominator bounds for rational
reconstruction
* added continued fraction expansion
* added functions for summation using binary splitting
* added fmpq_swap
* added fmpq_print, fmpq_get_str
* added fmpq_pow_si
* added functions to obtain read-only fmpq_t's from mpq_t's
* added fmpq_cmp
fmpq_mat
--------
* fixed n x 0 x m product not zeroing the result
* added fmpq_mat_transpose
* added trace
fmpq_poly
---------
* improved speed of multipoint interpolation using _fmpz_poly_div_root
* fmpq_poly: added power series composition (classical and Brent-Kung)
* fmpq_poly: added power series reversion (classical, Newton, fast Lagrange)
* fixed bug wherein set_array_mpq modified the input
* added gcd, xgcd, lcm, resultant
* added fmpq_poly_set_fmpq
* added fmpq_poly_get_slice, fmpq_poly_reverse
* fixed aliasing bug in divrem
* changed some functions to use FLINT scalar types instead of MPIR data types
* added fmpq_poly_get_numerator
nmod_poly
---------
* implemented the half gcd algorithm for subquadratic gcd and xgcd
* added multipoint evaluation and interpolation
* added asymptotically fast multipoint evaluation and interpolation
* added a function for forming the product of linear factors
* added a function for fast division by a linear polynomial
* added power series composition (classical and Brent-Kung)
* added power series reversion (classical, Newton, fast Lagrange)
* added nmod_poly_mulmod, powmod and related functions
(ported from flint1)
* added squarefree, irreducibility tests (ported from flint1)
* added Berlekamp and Cantor-Zassenhaus factoring (ported from flint1)
* fixed quadratic memory usage and stack overflow when performing
unbalanced division using the divconquer algorithm
* added compose_series_divconquer
* added resultant
* fixed aliasing bug in divrem
* added rem functions
* added divrem_q0, q1 for special cases of division
* added functions for fast Taylor shift
* added nmod_poly_sqrt
* made fread read the modulus from the file
* made randtest produce sparse output
* fixed bug in xgcd_euclidean with scalar inputs
nmod_vec
--------
* added functions and macros for computing dot products
* made randtest produce sparse output
nmod_mat
--------
* added addmul/submul functions
* asymptotically fast solving of triangular systems
* asymptotically fast LUP decomposition
* asymptotically fast determinant and rank computation
* asymptotically fast reduced row echelon form and nullspace
* asymptotically fast nonsingular solving
* asymptotically fast inverse
* tidied some interfaces
* fixed n x 0 x m product not zeroing the result
* added trace
* made multiplication faster for tiny moduli by means of bit packing
nmod_poly_mat
-------------
* new module for matrices over Z/nZ[x], with similar
functionality as the fmpz_poly_mat module
* determinant, rank, solving, reduced echelon form, nullspace
* fraction-free Gaussian elimination
* multiplication using bit packing
* multiplication using evaluation-interpolation
* determinant using evaluation-interpolation
padic
-----
* restructured and improved much of the code
* added padic_log
* improved log and exp using rectangular splitting
* added asymptotically fast log and exp based on binary splitting
perm
----
* added the perm module for permutation matrices
* computing the parity of a permutation
* inverting a permutation
arith
-----
* added generation of cyclotomic polynomials
* added functions for evaluating Dedekind sums
* fast computation of the partition function
* added a function for factoring a Hardy-Ramanujan-Rademacher
type exponential sum
* added Chebyshev polynomials T and U
* added computation of the minimal polynomial of cos(2pi/n)
* added asymptotically fast high-precision approximation of zeta(n)
* added asymptotically fast computation of Euler's constant
* added new algorithms and functions for computing Bell numbers
* fast computation of pi (adapting code written by Hanhong Xue)
* added functions for computing the number of sum of squares
representations of an integer
* renamed functions to have an arith_ prefix
v 2.4 -- 20 Nov 2013
* C++ expressions template wrapper
* Fast factorisation of polynomials over Z/nZ
* improved p-adics
* polynomials/matrices over p-adics
* qadics
* Finite fields (small and large F_q), polynomials/matrices over F_q
* Finite fields with Zech logarithm representation
* Fast factorisation of polynomials over F_q
* Faster Brent-Kung modular composition
* New prime sieving code
* Lambert-W function
* Precomputed inverses for polynomials and large integers
* Williams' P+1 integer factoring algorithm
* Harvey's KS2/KS4 polynomial multiplication
* Faster primality testing up to 64 bits
* Support for Cygwin64 and MinGW64
* Support for Clang
* Support for GMP
* Support for Boehm-Demers-Weiser GC
* Support for flint extension modules
v 2.4.2 -- 11 Mar 2014
* Fix bug in ARM assembly
v 2.4.3 -- 01 Apr 2014
* Fix a linker issue on Mac OSX.
v 2.4.4 -- fixed a severe bug in flint's primality code (n_is_prime() affecting n_factor())
v 2.4.5 -- fixed a severe bug in flint's fmpz_poly_gcd_heuristic, reported by
Anton Mellit.
v 2.5.0 -- 07 Aug 2015
* LLL (rational, Nguyen-Stehle, from Gram matrix, with_removal, Storjohann/ULLL)
* Hermite normal form (naive, xgcd, Domich-Kannan-Trotter, Kannan-Bachem, Pernet-Stein)
* Smith normal form (diagonal, Kannan-Bachem, Iliopoulos)
* Paterson-Stockmeyer algorithm
* modular resultant
* hgcd resultant
* polynomial discriminant
* multithreaded multimodular Taylor shift
* multithreaded Brent-Kung composition
* multithreaded Kaltofen-Shoup distinct degree factorisation
* multiplication based reduced row echelon form
* place inline functions in library for foreign function interfaces
* Primality tests for large integers (Pocklington, Morrison)
* Probable prime tests for large integers (Lucas, Baillie-PSW, strong-psp, Brillhart-Lehmer-Selfridge)
* CRT for large integers
* Dixon algorithm for nullspace
* Brent-Kung composition in irreducibility and distinct degree factorisation
* floating point QR decomposition
* Schwarz-Rutishauser Gram-Schmidt algorithm
* Ogita-Rump-Oishi dot product
* matrix window functions
* MSVC support (Brian Gladman)
* fast cube/nth-root (Newton, Kahan, magic number, Chebyshev)
* Bodrato matrix squaring
* matrix concatenation functions
* matrix content
* faster n_gcd
* faster n_sqrtmod and fmpz_sqrtmod
* additional functions for returning factor of modulus in polys over Z/nZ
* Hadamard matrix construction
* series addition/subtraction
* faster prime_pi bounds
* speedup creation of sparse polynomials
* speedup n_isprime n_nextprime
* speedup n_isprime_pocklington
* speedups to fmpq_poly and fmpz_poly arithmetic
* speedup polynomial irreducibility testing over Z/pZ
* speedup of rank computation over ZZ
* made CPimport compile time dependency only
* teach flint_printf/sprintf about explicit width format specifiers
* support relative paths in configure
* library soname versioning
* ARM64 patches
* Support MSYS2
* Progress towards supporting MIPS64
* Fix a serious bug in fmpz_poly_signature
v 2.5.1 -- 12 Aug 2015
* Fix some build bugs related to soname versioning and ldconfig
* Fix issue with Windows MSVC build
v 2.5.2 -- 13 Aug 2015
* Fix further issues with soname versioning and ldconfig
* Fix a bug when using GMP instead of MPIR.
v 2.6.0 -- 5 Jun 2020
* multivariate polynomials over most standard rings (sparse distributed)
* APR-CL primality proving
* elliptic curve integer factoring
* minpoly and charpoly
* improved quadratic sieve for integer factoring
* embeddings of finite fields
* pollard rho integer factoring
* p+1 integer factoring
* best of breed smooth integer factoring routine
* best of breed general integer factoring routine
* howell and strong echelon form
* large speedups for solve and hence inverse over Z and Q
* randprime and nextprime functions
* pernet-stein HNF improvements
* moller-granlund precomputed inverses
* resultant_modular_div
* fibonacci polynomials
* exception mechanism/flint_abort
* sqrt of series and polynomials
* division of series over Z
* power sums
* improved base cases of various power series functions
* ability to switch memory allocators
* fast recurrence for Hermite polys
* shifted Legendre polynomials
* Laguerre polynomials
* Gegenbauer polys
* sphinx documentation
* van hoeij with gradual feeding implementation of polynomial factoring over Z
* perfect power detection
* divisibility testing for polynomials
* fast block based memory manager for bundling fmpz allocations
* uniform random generation
* CMake build system
* linear algebra speedups when everything can be kept in longs
* nmod module for integers mod (small) n
* fmpz_mod_mat module for matrices over integers mod multiprecision n
* kronecker product (tensor product)
* random primitive polys (for finite fields)
* thread pool implementation
* threading of FFT for integer and polynomial multiplication over Z
* threading of quadratic sieve for integer factoring
* improved threading of factoring of polynomials mod p
* threading for multivariate polynomial multiplication, division and GCD
* threaded multiplication of matrices mod p
* Berlekamp-Massey (nmod)
* fmpz_mod module for integers mod multiprecision n
* Pohlig-Hellman (discrete log)
* farey_neighbours
* remove openMP option
* additional integer division variants
* speed up mpn_mulmod_preinv
* fft precaching
* cyclotomic polynomial detection
* polynomial root finding over finite fields
* GMP 6.2 support
* MPIR 3.0.0 support
* many small speedups and additional convenience functions added
v 2.6.1 -- 23 Jul 2020
* Fix issues on Debian major architectures
* Fix numerous reported bugs (mpoly, fq_poly, mpn_mul_1, mod 2 code, etc.)
v 2.6.2 -- 31 Jul 2020
* Fix for choice of generator in an fq finite field of degree one
* Fix an incorrectly written test
v 2.6.3 -- 12 Aug 2020
* Fix a bug in generator of finite field in characteristic 2
* Allow Flint to work with GMP 6.1.2 and 6.2.0 interchangeably
* Fix some old license headers
2.7.0 -- 18 Dec 2020
* Multivariate factorisation
* Square root and square testing for finite fields
* Square root and square testing for multivariates
* Zassenhaus factoring speedups (incl. degree pruning)
* Fast factorisation of cubic univariate polynomials
* Add context objects to fmpz_mod_poly functions
* Use BLAS for matrix multiplication over Z/nZ (small n)
* Linear solving for non-square/singular matrices (can_solve)
* Speed up factorisation over Z/nZ (for multiprecision n)
2.7.1 -- 18 Jan 2021
* Fix build bug due to missing test files
* Fix bug in fmpz_mod_poly_factor when there are more than five factors
* Fix issue when using MPIR 3.0.0 on Win64 with command line build
* Fix bug in fmpz_mod_poly_div_series
* Fix some broken asserts
* Support standard GNU installation directories in CMake build
* Fix stack overflow with ICC
2.8.0 -- 23 Jul 2021
* New fq_default module which combines existing finite fields
* Speedups for linear algebra when using BLAS and/or threading
* New series expansions with coefficients in QQ
* Faster CRT
* New fmpz_mod_mpoly module
* Polynomial factoring improvements over ZZ
* Fixed bugs in gmpcompat on Windows
* Add fmpz_mat_can_solve_fflu and fmpz_mat_can_solve
* Cleanup of the nmod_poly and nmod_poly_factor code
* Implement nmod_mat_det_howell
* Add fmpz_mod_poly_divides, fmpz_divides, n_divides, nmod_poly_divides
* Interface for multiplying matrices by vectors and arrays
* Nearest Euclidean division
* Subresultant GCD
* XGCD over ZZ with canonical Bezout coefficients
* Add fmpz_mpoly resultant and discriminant
* Add deprecations list
* Add FLINT_SGN macro
* Speedups for series computations
* Switch to GitHub Actions for CI
* Improve Taylor shift
* Numerous bug fixes and speedups
2.8.1 -- 01 Oct 2021
* Numerous bug fixes
* Adjust soname on android
* Allow disabling of dependency tracking
2.8.2 -- 15 Oct 2021
* Fix an issue with --disable-dependency-tracking on some distributions
2.8.3 -- 03 Nov 2021
* Fix a serious bug in nmod_poly_xgcd_hgcd, nmod_poly_xgcd, fmpz_poly_xgcd_modular, fmpz_poly_xgcd,
fmpq_poly_xgcd for polynomials of length >= 340.
* Fix some copyright assignments
* Fix some documentation errors
2.8.4 -- 17 Nov 2021
* Fix a serious bug in fmpz_mod_poly_xgcd for polynomials of large length
* Fix an assertion failure in fmpz_mat_solve_fflu (only relevant if asserts enabled)
* Fix some bugs on 32 bit machines
* Work around a compiler bug on Apple M1
* Fix bug in nmod_mpoly_factor (returned 0 for some factorisations)
* Fix some documentation build errors and some doc formatting issues
2.8.5 -- 25 Apr 2022
* Fix a serious bug in LLL
2.9.0 -- 24 Jun 2022
* Add fmpz_mod_poly_div function
* Add _flint_get_memory function
* Add Eulerian polynomials
* Support "multivariate" polynomials with zero variables
* Improve Stirling numbers of both kinds
* Speed up numerous fmpz functions for small inputs
* Improve Bell numbers
* Speedups to nmod arithmetic
* Improve nmod_mat LU decomposition
* Fully separate nmod module from nmod_vec
* Speed up Hermite polynomials
* Add n-th derivative for Z[x] and Q[x]
* Improve fq_default module (nmod is now used where optimal)
* Add sqrt functions for numerous polynomial/series modules and finite fields
* Add FFT matrix multiplication
* Improve CI
* Improve LLL for general use
* Add matrix-vector products over Q
* Add can_solve function for fmpq_mat, handling non-square/singular matrices
* Document fmpz_mod_vec module
* Fix and document qadic_sqrt function
* Add parallel programming helpers
Generated by dwww version 1.15 on Sun Jun 2 00:25:10 CEST 2024.