Announcement: ---------------------- The FLINT development team is pleased to announce the release of FLINT 2.0. (see http://www.flintlib.org/ )
FLINT 2 is a complete rewrite of FLINT (Fast Library for Number Theory) from scratch! The main benefits of the rewrite are: * Much tidier code * Faster implementations * Linear algebra in addition to the traditional FLINT poly arithmetic * Memory management of individual polynomial and matrix coefficients * Magic build system -- trivial to contribute to FLINT2 -- drop and run * Documentation constructed automatically from simple text files * ANSI C90 (pedantic) compliant (no C99) * FLINT 2 has a growing community! FLINT 2 was mostly written by William Hart, Sebastian Pancratz and Fredrik Johansson. Andy Novocin has also joined the FLINT2 effort after the completion of FLINT 1.6. For a full summary of the functionality provided in FLINT 2 see the relevant section of our NEWS file here: http://bit.ly/eMXiwS Full documentation (127 pp.) is available at: http://www.flintlib.org/flint-2.0.pdf (Please accept our apologies for the many typos in this initial version of the document. We recommend downloading the pdf rather than viewing in the browser -- there is a section list!) New Features: --------------------- As FLINT 2 is vast, we list only the new features and improvements over the FLINT 1 series. [Note: we consider the ulong_extras, fmpz, fmpz_vec, fmpz_poly, nmod_vec, nmod_poly and fmpq_poly modules to be stable (both from a testing and interface perspective). The matrix modules are well tested, but the interfaces are still under active development.] ulong_extras: * support for numbers all the way up to 32/64 bits * dramatic improvement in speed of primality proving * Moebius mu, Euler phi * much faster division and modular reduction with precomputed inverse fmpz: * new FLINT integer format which does automatic memory management like mpz's but has massive cache benefits for small integers * threadsafe and fast single mode versions available * fast factorial computation fmpz_vec: * new vector module for simple arrays of fmpz's fmpz_poly: * an fmpz_poly coefficient is now an fmpz and can be manipulated directly * every function has an underscore version which operates on arrays of fmpz's meaning that the basic functionality doesn't have to be duplicated everywhere in FLINT, and also giving substantial performance improvements throughout * middle product * substantial speed improvements to powering and divide-and-conquer division and across the board for small polynomials fmpq_poly: * brand new module for polynomials over Q, implemented as a polynomial over Z with single common denominator * leverages all the work in the improved fmpz_poly module and has much of the same functionality nmod_vec: * new vector module for simple arrays over Z/nZ for n fitting in a machine word * very fast macros for reduction of 1,2,3 word integers mod n nmod_poly: * supports moduli right up to 32/64 bits * substantial performance improvements across the board * extremely fast division basecase * polynomial powering * much better handling of unbalanced polynomial divisions fmpz_mat: * new module for matrices whose coefficients are fmpz's * heaps of different types of random matrices * transpose, inverse, determinant, row reduction, rank, solve Ax = b and AX = B * fraction-free LU decomposition * multiplication (classical and multimodular) nmod_mat: * new module for matrices over Z/nZ for word sized n * heaps of different types of random matrices * transpose, inverse, determinant, row reduction, rank, solve Ax = b and AB = B * multiplication (classical and Strassen) arith: * new module for computing arithmetic functions * Bernoulli numbers and polys, primorials, harmonic numbers, Stirling numbers * Euler phi, Moebius mu, Sigma, Ramanujan tau Note: some FLINT 1.6 features have not been ported to FLINT2 yet, e.g. polynomial factorisation. Some Timings: --------------------- For those who like benchmarketing pr0n, here's a couple of random timing comparisons from out development discussions. * nmod_poly_divrem len iterations flint2 flint1.6 100 1000000 7.48 9.07 300 100000 2.32 4.22 600 100000 5.26 13.0 1000 50000 5.03 11.8 2000 20000 4.72 9.88 5000 10000 7.34 14.4 10000 5000 9.23 16.2 20000 2000 8.89 15.5 30000 1000 6.84 10.3 60000 500 8.62 11.5 100000 200 5.36 9.79 200000 100 5.41 10.1 500000 100 28.6 32.7 1000000 100 60.5 46.6 <- eventually flint1.6 wins due to a trick we haven't implemented in flint2 (yet) * GCD Subresultant (flint 1.5 vs flint 2.0) https://github.com/SPancratz/flint2/wiki/Polynomial-GCD-via-subresultants * Bernoulli numbers -- computes all the Bernoulli numbers up to n: (comparing two flint2 algos with Pari via Sage -- the "series" algorithm is based on our fast fmpq_poly arithmetic) n / recursive / series / sage (pari) 100 / 100 us / - / 5.3 ms 500 / 6 ms / 30 ms / 35 ms 1000 / 50 ms / 180 ms / 114 ms 1500 / 240 ms / 560 ms / 280 ms 2000 / 720 ms / 1030 ms / 570 ms 2500 / 1.7 s / 1.8 s / 1.0 s 3000 / 3.3 s / 2.8 s / 1.9 s 3500 / 5.9 s / 4.0 s / 2.6 s 4000 / 9.7 s / 6.5 s / 3.9 s 4500 / 15 s / 8.5 s / 6.0 s 5000 / 22 s / 12 s / 7.7 s 10000 / - / 60 s / 79 s 20000 / - / 388 s / 696 s (a subsequent version of flint 2 will provide a new algorithm in the range 2000-10000 where Sage/Pari currently still wins). * Other fast combinatorial and number theoretic functions: http://fredrik-j.blogspot.com/2010/09/fast-combinatorial-and-number-theoretic.html Best Wishes, The FLINT Team. -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
