[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index][Thread Index]

From: | John Marino <marino@xxxxxxxxxxxxxxxxxxxxxxx> |

Date: | Sat, 5 Nov 2011 14:32:54 -0700 (PDT) |

commit 390557ef83c0018508ca450f7f3eb3d0e4268f8e Author: John Marino <draco@marino.st> Date: Sat Nov 5 21:31:30 2011 +0100 libgmp: Upgrade to version 5.0.2 The GNU Multiple Precision Arithmetic Library is required for gcc44 and all newer gcc compilers. It's alway been built with the "generic" C files rather than the provided assembly. It should be possible to build gmp with a base set of assembly for x86 and x86_64, and even use more processor-specific assembly if CPU_TYPE is set, but implementing that will require some more work and a lot of testing. So for now, gmp is still built with the much slower (but more portable) C files. BUGS FIXED =================== 1. Fat builds fixed. 2. Fixed crash for huge multiplies when old FFT_TABLE2 type of parameter selection tables' sentinel was smaller than multiplied operands. 3. The solib numbers now reflect the removal of the documented but preliminary mpn_bdivmod function; we correctly flag incompatibility with GMP 4.3. 4. Many minor bugs related to portability fixed. 5. The support for HPPA 2.0N now works, after an assembly bug fix. 6. A test case type error has been fixed. The symptom of this bug was spurious 'make check' failures. SPEEDUPS =================== 1. Multiplication has been overhauled: (1) Multiplication of larger same size operands has been improved with the addition of two new Toom functions and a new internal function mpn_mulmod_bnm1 (computing U * V mod (B^n-1), B being the word base. This latter function is used for the largest products, waiting for a better Schoenhage-Strassen U * V mod (B^n+1) implementation. (2) Likewise for squaring. (3) Multiplication of different size operands has been improved with the addition of many new Toom function, and by selecting underlying functions better from the main multiply functions. 2. Division and mod have been overhauled: (1) Plain "schoolbook" division is reimplemented using faster quotient approximation. (2) Division Q = N/D, R = N mod D where both the quotient and remainder are needed now runs in time O(M(log(N))). This is an improvement of a factor log(log(N)) (3) Division where just the quotient is needed is now O(M(log(Q))) on average. (4) Modulo operations using Montgomery REDC form now take time O(M(n)) (5) Exact division Q = N/D by means of mpz_divexact has been improved for all sizes, and now runs in time O(M(log(N))). 3. The function mpz_powm is now faster for all sizes. Its complexity has gone from O(M(n)log(n)m) to O(M(n)m) where n is the size of the modulo argument and m is the size of the exponent. It is also radically faster for even modulus, since it now partially factors such modulus and performs two smaller modexp operations, then uses CRT. 4. The internal support for multiplication yielding just the lower n limbs has been improved by using Mulders' algorithm. 5. Computation of inverses, both plain 1/N and 1/N mod B^n have been improved by using well-tuned Newton iterations, and wrap-around multiplication using mpn_mulmod_bnm1. 6. A new algorithm makes mpz_perfect_power_p asymptotically faster. 7. The function mpz_remove uses a much faster algorithm, is better tuned, and also benefits from the division improvements. 8. Intel Atom and VIA Nano specific optimisations. 9. Multiplication of large numbers has indirectly been sped up through better FFT tuning and processor recognition. Since many operations depend on multiplication, there will be a general speedup. 10. Plus hundreds of smaller improvements and tweaks! NEW FEATURES =================== 1. New mpz function: mpz_powm_sec for side-channel quiet modexp computations. 2. New mpn functions: mpn_sqr, mpn_and_n, mpn_ior_n, mpn_xor_n, mpn_nand_n, mpn_nior_n, mpn_xnor_n, mpn_andn_n, mpn_iorn_n, mpn_com, mpn_neg, mpn_copyi, mpn_copyd, mpn_zero. 3. The function mpn_tdiv_qr now allows certain argument overlap. 4. Support for fat binaries for 64-bit x86 processors has been added. 5. A new type, mp_bitcnt_t for bignum bit counts, has been introduced. 6. More Core i3, i5 an Core i7 processor models are recognised. Summary of changes: contrib/gmp/README.DELETED | 25 +++++- contrib/gmp/README.DRAGONFLY | 13 ++- gnu/usr.bin/cc44/gmp/Makefile | 98 +++++++++++++------- gnu/usr.bin/cc44/gmp/Makefile.i386 | 1 + gnu/usr.bin/cc44/gmp/Makefile.x86_64 | 1 + gnu/usr.bin/cc44/gmp/config.h | 93 ++++++++++++++++--- gnu/usr.bin/cc44/gmp/gmp.h | 169 ++++++++++++++++++++++------------ 7 files changed, 284 insertions(+), 116 deletions(-) http://gitweb.dragonflybsd.org/dragonfly.git/commitdiff/390557ef83c0018508ca450f7f3eb3d0e4268f8e -- DragonFly BSD source repository

[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index][Thread Index]