DragonFly commits List (threaded) for 2011-11
git: libgmp: Upgrade to version 5.0.2
Author: John Marino <firstname.lastname@example.org>
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.
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.
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)
(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
(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
(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!
1. New mpz function: mpz_powm_sec for side-channel quiet modexp
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(-)
DragonFly BSD source repository