1 Copyright 1996, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,
2 2009, 2010 Free Software Foundation, Inc.
4 Verbatim copying and distribution of this entire article is permitted
5 in any medium, provided this notice is preserved.
8 Changes between GMP version 5.0.0 and 5.0.1
13 * Fixed crash for huge multiplies when old FFT_TABLE2 type of parameter
14 selection tables' sentinel was smaller than multiplied operands.
16 * The solib numbers now reflect the removal of the documented but preliminary
17 mpn_bdivmod function; we correctly flag incompatibility with GMP 4.3.
18 GMP 5.0.0 has this wrong, and should perhaps be uninstalled to avoid
22 * Multiplicaton of large numbers has indirectly been sped up through
23 better FFT tuning and processor recognition. Since many operations
24 depend on multiplication, there will be a general speedup.
27 * More Core i3, i5 an Core i7 processor models are recognised.
29 * Fixes and workarounds for Mac OS quirks should make this GMP version
30 build using many of the different versions of "Xcode".
33 * The amount of scratch memory needed for multiplication of huge numbers
34 have been reduced substantially (but is still larger than in GMP 4.3.)
36 * Likewise, the amount of scratch memory needed for division of large
37 numbers have been reduced substantially.
39 * The FFT tuning code of tune/tuneup.c has been completely rewritten,
40 and new, large FFT parameter selection tables are provided for many
43 * Upgraded to the latest autoconf, automake, libtool.
46 Changes between GMP version 4.3.X and 5.0.0
49 * None (contains the same fixes as release 4.3.2).
52 * Multiplication has been overhauled:
53 (1) Multiplication of larger same size operands has been improved with
54 the addition of two new Toom functions and a new internal function
55 mpn_mulmod_bnm1 (computing U * V mod (B^n-1), B being the word base.
56 This latter function is used for the largest products, waiting for a
57 better Schoenhage-Strassen U * V mod (B^n+1) implementation.
58 (2) Likewise for squaring.
59 (3) Multiplication of different size operands has been improved with the
60 addition of many new Toom function, and by selecting underlying
61 functions better from the main multiply functions.
63 * Division and mod have been overhauled:
64 (1) Plain "schoolbook" division is reimplemented using faster quotient
66 (2) Division Q = N/D, R = N mod D where both the quotient and remainder
67 are needed now runs in time O(M(log(N))). This is an improvement of
69 (3) Division where just the quotient is needed is now O(M(log(Q))) on
71 (4) Modulo operations using Montgomery REDC form now take time O(M(n)).
72 (5) Exact division Q = N/D by means of mpz_divexact has been improved
73 for all sizes, and now runs in time O(M(log(N))).
75 * The function mpz_powm is now faster for all sizes. Its complexity has
76 gone from O(M(n)log(n)m) to O(M(n)m) where n is the size of the modulo
77 argument and m is the size of the exponent. It is also radically
78 faster for even modulus, since it now partially factors such modulus
79 and performs two smaller modexp operations, then uses CRT.
81 * The internal support for multiplication yielding just the lower n limbs
82 has been improved by using Mulders' algorithm.
84 * Computation of inverses, both plain 1/N and 1/N mod B^n have been
85 improved by using well-tuned Newton iterations, and wrap-around
86 multiplication using mpn_mulmod_bnm1.
88 * A new algorithm makes mpz_perfect_power_p asymptotically faster.
90 * The function mpz_remove uses a much faster algorithm, is better tuned,
91 and also benefits from the division improvements.
93 * Intel Atom and VIA Nano specific optimisations.
95 * Plus hundreds of smaller improvements and tweaks!
98 * New mpz function: mpz_powm_sec for side-channel quiet modexp
101 * New mpn functions: mpn_sqr, mpn_and_n, mpn_ior_n, mpn_xor_n, mpn_nand_n,
102 mpn_nior_n, mpn_xnor_n, mpn_andn_n, mpn_iorn_n, mpn_com, mpn_neg,
103 mpn_copyi, mpn_copyd, mpn_zero.
105 * The function mpn_tdiv_qr now allows certain argument overlap.
107 * Support for fat binaries for 64-bit x86 processors has been added.
109 * A new type, mp_bitcnt_t for bignum bit counts, has been introduced.
111 * Support for Windows64 through mingw64 has been added.
113 * The cofactors of mpz_gcdext and mpn_gcdext are now more strictly
114 normalised, returning to how GMP 4.2 worked. (Note that also release
115 4.3.2 has this change.)
118 * The mpn_mul function should no longer be used for squaring,
119 instead use the new mpn_sqr.
121 * The algorithm selection has been improved, the number of thresholds have
122 more than doubled, and the tuning and use of existing thresholds have
125 * The tune/speed program can measure many of new functions.
127 * The mpn_bdivmod function has been removed. We do not consider this an
128 incompatible change, since the function was marked as preliminary.
130 * The testsuite has been enhanced in various ways.
133 Changes between GMP version 4.3.1 and 4.3.2
136 * Fixed bug in mpf_eq.
137 * Fixed overflow issues in mpz_set_str, mpz_inp_str, mpf_set_str, and
139 * Avoid unbounded stack allocation for unbalanced multiplication.
140 * Fixed bug in FFT multiplication.
143 * None, except that proper processor recognition helps affected processors.
146 * Recognise more "Core 2" processor variants.
147 * The cofactors of mpz_gcdext and mpn_gcdext are now more strictly
148 normalised, returning to how GMP 4.2 worked.
151 Changes between GMP version 4.3.0 and 4.3.1
154 * Fixed bug in mpn_gcdext, affecting also mpz_gcdext and mpz_invert.
155 The bug could cause a cofactor to have a leading zero limb, which
156 could lead to crashes or miscomputation later on.
157 * Fixed some minor documentation issues.
163 * Workarounds for various issues with Mac OS X's build tools.
164 * Recognise more IBM "POWER" processor variants.
167 Changes between GMP version 4.2.X and 4.3.0
170 * Fixed bug in mpz_perfect_power_p with recognition of negative perfect
171 powers that can be written both as an even and odd power.
172 * We might accidentally have added bugs since there is a large amount of
173 new code in this release.
176 * Vastly improved assembly code for x86-64 processors from AMD and Intel.
177 * Major improvements also for many other processor families, such as
178 Alpha, PowerPC, and Itanium.
179 * New sub-quadratic mpn_gcd and mpn_gcdext, as well as improved basecase
181 * The multiply FFT code has been slightly improved.
182 * Balanced multiplication now uses 4-way Toom in addition to schoolbook,
183 Karatsuba, 3-way Toom, and FFT.
184 * Unbalanced multiplication has been vastly improved.
185 * Improved schoolbook division by means of faster quotient approximation.
186 * Several new algorithms for division and mod by single limbs, giving
188 * Improved nth root computations.
189 * The mpz_nextprime function uses sieving and is much faster.
190 * Countless minor tweaks.
193 * Updated support for fat binaries for x86_32 include current processors
194 * Lots of new mpn internal interfaces. Some of them will become public
195 in a future GMP release.
196 * Support for the 32-bit ABI under x86-apple-darwin.
197 * x86 CPU recognition code should now default better for future
199 * The experimental nails feature does not work in this release, but
200 it might be re-enabled in the future.
203 * The gmp_version variable now always contains three parts. For this
204 release, it is "4.3.0".
207 Changes between GMP version 4.2.3 and 4.2.4
210 * Fix bug with parsing exponent '+' sign in mpf.
211 * Fix an allocation bug in mpf_set_str, also affecting mpf_init_set_str, and
215 * None, except that proper processor recognition helps affected processors.
218 * Recognize new AMD processors.
221 Changes between GMP version 4.2.2 and 4.2.3
224 * Fix x86 CPU recognition code to properly identify recent AMD and Intel
226 * The >> operator of the C++ wrapper gmpxx.h now does floor rounding, not
228 * Inline semantics now follow the C99 standard, and works with recent GCC
230 * C++ bitwise logical operations work for more types.
231 * For C++, gmp.h now includes cstdio, improving compiler compatibility.
232 * Bases > 36 now work properly in mpf_set_str.
235 * None, except that proper processor recognition helps affected processors.
238 * The allocation functions now detect overflow of the mpz_t type. This means
239 that overflow will now cause an abort, except when the allocation
240 computation itself overflows. (Such overflow can probably only happen in
241 powering functions; we will detect powering overflow in the future.)
244 Changes between GMP version 4.2.1 and 4.2.2
246 * License is now LGPL version 3.
249 * Shared library numbers corrected for libcxx.
250 * Fixed serious bug in gmpxx.h where a=a+b*c would generate garbage.
251 Note that this only affects C++ programs.
252 * Fix crash in mpz_set_d for arguments with large negative exponent.
253 * Fix 32-bit ABI bug with Itanium assembly for popcount and hamdist.
254 * Fix assembly syntax problem for powerpc-ibm-aix with AIX native assembler.
255 * Fix problems with x86 --enable-fat, where the compiler where told to
256 generate code for the build machine, not plain i386 code as it should.
257 * Improved recognition of powerpc systems wrt Altivec/VMX capability.
258 * Misc minor fixes, mainly workarounds for compiler/assembler bugs.
261 * "Core 2" and Pentium 4 processors, running in 64-bit mode will get a
262 slight boost as they are now specifically recognized.
265 * New support for x86_64-solaris
266 * New, rudimentary support for x86-apple-darwin and x86_64-apple-darwin.
267 (Please see http://gmplib.org/macos.html for more information.)
270 Changes between GMP version 4.2 and 4.2.1
273 * Shared library numbers corrected.
274 * Broken support for 32-bit AIX fixed.
278 * Exact division (mpz_divexact) now falls back to plain division for large
282 * Support for some new systems.
285 Changes between GMP version 4.1.4 and 4.2
288 * Minor bug fixes and code generalizations.
289 * Expanded and improved test suite.
292 * Many minor optimizations, too many to mention here.
293 * Division now always subquadratic.
294 * Computation of n-factorial much faster.
295 * Added basic x86-64 assembly code.
296 * Floating-point output is now subquadratic for all bases.
297 * FFT multiply code now about 25% faster.
298 * Toom3 multiply code faster.
301 * Much improved configure.
302 * Workarounds for many more compiler bugs.
303 * Temporary allocations are now made on the stack only if small.
304 * New systems supported: HPPA-2.0 gcc, IA-64 HP-UX, PowerPC-64 Darwin,
306 * New i386 fat binaries, selecting optimised code at runtime (--enable-fat).
307 * New build option: --enable-profiling=instrument.
308 * New memory function: mp_get_memory_functions.
309 * New Mersenne Twister random numbers: gmp_randinit_mt, also now used for
310 gmp_randinit_default.
311 * New random functions: gmp_randinit_set, gmp_urandomb_ui, gmp_urandomm_ui.
312 * New integer functions: mpz_combit, mpz_rootrem.
313 * gmp_printf etc new type "M" for mp_limb_t.
314 * gmp_scanf and friends now accept C99 hex floats.
315 * Numeric input and output can now be in bases up to 62.
316 * Comparisons mpz_cmp_d, mpz_cmpabs_d, mpf_cmp_d recognise infinities.
317 * Conversions mpz_get_d, mpq_get_d, mpf_get_d truncate towards zero,
318 previously their behaviour was unspecified.
319 * Fixes for overflow issues with operands >= 2^31 bits.
322 * mpfr is gone, and will from now on be released only separately. Please see
326 Changes between GMP version 4.1.3 and 4.1.4
328 * Bug fix to FFT multiplication code (crash for huge operands).
329 * Bug fix to mpf_sub (miscomputation).
330 * Support for powerpc64-gnu-linux.
331 * Better support for AMD64 in 32-bit mode.
332 * Upwardly binary compatible with 4.1.3, 4.1.2, 4.1.1, 4.1, 4.0.1, 4.0,
336 Changes between GMP version 4.1.2 and 4.1.3
338 * Bug fix for FFT multiplication code (miscomputation).
339 * Bug fix to K6 assembly code for gcd.
340 * Bug fix to IA-64 assembly code for population count.
341 * Portability improvements, most notably functional AMD64 support.
342 * mpz_export allows NULL for countp parameter.
343 * Many minor bug fixes.
344 * mpz_export allows NULL for countp parameter.
345 * Upwardly binary compatible with 4.1.2, 4.1.1, 4.1, 4.0.1, 4.0, and 3.x
349 Changes between GMP version 4.1.1 and 4.1.2
354 Changes between GMP version 4.1 and 4.1.1
357 * New systems supported: NetBSD and OpenBSD sparc64.
360 Changes between GMP version 4.0.1 and 4.1
363 * Speed improvements.
364 * Upwardly binary compatible with 4.0, 4.0.1, and 3.x versions.
365 * Asymptotically fast conversion to/from strings (mpz, mpq, mpn levels), but
366 also major speed improvements for tiny operands.
367 * mpn_get_str parameter restrictions relaxed.
368 * Major speed improvements for HPPA 2.0 systems.
369 * Major speed improvements for UltraSPARC systems.
370 * Major speed improvements for IA-64 systems (but still sub-optimal code).
371 * Extended test suite.
372 * mpfr is back, with many bug fixes and portability improvements.
373 * New function: mpz_ui_sub.
374 * New functions: mpz_export, mpz_import.
375 * Optimization for nth root functions (mpz_root, mpz_perfect_power_p).
376 * Optimization for extended gcd (mpz_gcdext, mpz_invert, mpn_gcdext).
377 * Generalized low-level number format, reserving a `nails' part of each
378 limb. (Please note that this is really experimental; some functions
379 are likely to compute garbage when nails are enabled.)
380 * Nails-enabled Alpha 21264 assembly code, allowing up to 75% better
381 performance. (Use --enable-nails=4 to enable it.)
384 Changes between GMP version 4.0 and 4.0.1
389 Changes between GMP version 3.1.1 and 4.0
392 * Speed improvements.
393 * Upwardly binary compatible with 3.x versions.
394 * New CPU support: IA-64, Pentium 4.
395 * Improved CPU support: 21264, Cray vector systems.
396 * Support for all MIPS ABIs: o32, n32, 64.
397 * New systems supported: Darwin, SCO, Windows DLLs.
398 * New divide-and-conquer square root algorithm.
399 * New algorithms chapter in the manual.
400 * New malloc reentrant temporary memory method.
401 * New C++ class interface by Gerardo Ballabio (beta).
402 * Revamped configure, featuring ABI selection.
403 * Speed improvements for mpz_powm and mpz_powm_ui (mainly affecting small
405 * mpz_perfect_power_p now properly recognizes 0, 1, and negative perfect
407 * mpz_hamdist now supports negative operands.
408 * mpz_jacobi now accepts non-positive denominators.
409 * mpz_powm now supports negative exponents.
410 * mpn_mul_1 operand overlap requirements relaxed.
411 * Float input and output uses locale specific decimal point where available.
412 * New gmp_printf, gmp_scanf and related functions.
413 * New division functions: mpz_cdiv_q_2exp, mpz_cdiv_r_2exp, mpz_divexact_ui.
414 * New divisibility tests: mpz_divisible_p, mpz_divisible_ui_p,
415 mpz_divisible_2exp_p, mpz_congruent_p, mpz_congruent_ui_p,
416 mpz_congruent_2exp_p.
417 * New Fibonacci function: mpz_fib2_ui.
418 * New Lucas number functions: mpz_lucnum_ui, mpz_lucnum2_ui.
419 * Other new integer functions: mpz_cmp_d, mpz_cmpabs_d, mpz_get_d_2exp,
420 mpz_init2, mpz_kronecker, mpz_lcm_ui, mpz_realloc2.
421 * New rational I/O: mpq_get_str, mpq_inp_str, mpq_out_str, mpq_set_str.
422 * Other new rational functions: mpq_abs, mpq_cmp_si, mpq_div_2exp,
423 mpq_mul_2exp, mpq_set_f.
424 * New float tests: mpf_integer_p, mpf_fits_sint_p, mpf_fits_slong_p,
425 mpf_fits_sshort_p, mpf_fits_uint_p, mpf_fits_ulong_p, mpf_fits_ushort_p.
426 * Other new float functions: mpf_cmp_d, mpf_get_default_prec, mpf_get_si,
427 mpf_get_ui, mpf_get_d_2exp.
428 * New random functions: gmp_randinit_default, gmp_randinit_lc_2exp_size.
429 * New demo expression string parser (see demos/expr).
430 * New preliminary perl interface (see demos/perl).
431 * Tuned algorithm thresholds for many more CPUs.
434 Changes between GMP version 3.1 and 3.1.1
436 * Bug fixes for division (rare), mpf_get_str, FFT, and miscellaneous minor
440 Changes between GMP version 3.0 and 3.1
443 * Improved `make check' running more tests.
444 * Tuned algorithm cutoff points for many machines. This will improve speed for
445 a lot of operations, in some cases by a large amount.
446 * Major speed improvements: Alpha 21264.
447 * Some speed improvements: Cray vector computers, AMD K6 and Athlon, Intel P5
448 and Pentium Pro/II/III.
449 * The mpf_get_prec function now works as it did in GMP 2.
450 * New utilities for auto-tuning and speed measuring.
451 * Multiplication now optionally uses FFT for very large operands. (To enable
452 it, pass --enable-fft to configure.)
453 * Support for new systems: Solaris running on x86, FreeBSD 5, HP-UX 11, Cray
454 vector computers, Rhapsody, Nextstep/Openstep, MacOS.
455 * Support for shared libraries on 32-bit HPPA.
456 * New integer functions: mpz_mul_si, mpz_odd_p, mpz_even_p.
457 * New Kronecker symbol functions: mpz_kronecker_si, mpz_kronecker_ui,
458 mpz_si_kronecker, mpz_ui_kronecker.
459 * New rational functions: mpq_out_str, mpq_swap.
460 * New float functions: mpf_swap.
461 * New mpn functions: mpn_divexact_by3c, mpn_tdiv_qr.
462 * New EXPERIMENTAL function layer for accurate floating-point arithmetic, mpfr.
463 To try it, pass --enable-mpfr to configure. See the mpfr subdirectory for
464 more information; it is not documented in the main GMP manual.
467 Changes between GMP version 3.0 and 3.0.1
469 * Memory leaks in gmp_randinit and mpz_probab_prime_p fixed.
470 * Documentation for gmp_randinit fixed. Misc documentation errors fixed.
473 Changes between GMP version 2.0 and 3.0
475 * Source level compatibility with past releases (except mpn_gcd).
477 * Much improved speed thanks to both host independent and host dependent
479 * Switch to autoconf/automake/libtool.
480 * Support for building libgmp as a shared library.
481 * Multiplication and squaring using 3-way Toom-Cook.
482 * Division using the Burnikel-Ziegler method.
483 * New functions computing binomial coefficients: mpz_bin_ui, mpz_bin_uiui.
484 * New function computing Fibonacci numbers: mpz_fib_ui.
485 * New random number generators: mpf_urandomb, mpz_rrandomb, mpz_urandomb,
486 mpz_urandomm, gmp_randclear, gmp_randinit, gmp_randinit_lc_2exp,
487 gmp_randseed, gmp_randseed_ui.
488 * New function for quickly extracting limbs: mpz_getlimbn.
489 * New functions performing integer size tests: mpz_fits_sint_p,
490 mpz_fits_slong_p, mpz_fits_sshort_p, mpz_fits_uint_p, mpz_fits_ulong_p,
492 * New mpf functions: mpf_ceil, mpf_floor, mpf_pow_ui, mpf_trunc.
493 * New mpq function: mpq_set_d.
494 * New mpz functions: mpz_addmul_ui, mpz_cmpabs, mpz_cmpabs_ui, mpz_lcm,
495 mpz_nextprime, mpz_perfect_power_p, mpz_remove, mpz_root, mpz_swap,
496 mpz_tdiv_ui, mpz_tstbit, mpz_xor.
497 * New mpn function: mpn_divexact_by3.
498 * New CPU support: DEC Alpha 21264, AMD K6 and Athlon, HPPA 2.0 and 64,
499 Intel Pentium Pro and Pentium-II/III, Sparc 64, PowerPC 64.
500 * Almost 10 times faster mpz_invert and mpn_gcdext.
501 * The interface of mpn_gcd has changed.
502 * Better support for MIPS R4x000 and R5000 under Irix 6.
503 * Improved support for SPARCv8 and SPARCv9 processors.
506 Changes between GMP version 2.0 and 2.0.2
511 Changes between GMP version 1.3.2 and 2.0
513 * Division routines in the mpz class have changed. There are three classes of
514 functions, that rounds the quotient to -infinity, 0, and +infinity,
515 respectively. The first class of functions have names that begin with
516 mpz_fdiv (f is short for floor), the second class' names begin with mpz_tdiv
517 (t is short for trunc), and the third class' names begin with mpz_cdiv (c is
520 The old division routines beginning with mpz_m are similar to the new
521 mpz_fdiv, with the exception that some of the new functions return useful
524 The old function names can still be used. All the old functions names will
525 now do floor division, not trunc division as some of them used to. This was
526 changed to make the functions more compatible with common mathematical
529 The mpz_mod and mpz_mod_ui functions now compute the mathematical mod
530 function. I.e., the sign of the 2nd argument is ignored.
532 * The mpq assignment functions do not canonicalize their results. A new
533 function, mpq_canonicalize must be called by the user if the result is not
534 known to be canonical.
535 * The mpn functions are now documented. These functions are intended for
536 very time critical applications, or applications that need full control over
537 memory allocation. Note that the mpn interface is irregular and hard to
539 * New functions for arbitrary precision floating point arithmetic. Names
540 begin with `mpf_'. Associated type mpf_t.
541 * New and improved mpz functions, including much faster GCD, fast exact
542 division (mpz_divexact), bit scan (mpz_scan0 and mpz_scan1), and number
543 theoretical functions like Jacobi (mpz_jacobi) and multiplicative inverse
545 * New variable types (mpz_t and mpq_t) are available that makes syntax of
546 mpz and mpq calls nicer (no need for & before variables). The MP_INT and
547 MP_RAT types are still available for compatibility.
548 * Uses GNU configure. This makes it possible to choose target architecture
549 and CPU variant, and to compile into a separate object directory.
550 * Carefully optimized assembly for important inner loops. Support for DEC
551 Alpha, Amd 29000, HPPA 1.0 and 1.1, Intel Pentium and generic x86, Intel
552 i960, Motorola MC68000, MC68020, MC88100, and MC88110, Motorola/IBM
553 PowerPC, National NS32000, IBM POWER, MIPS R3000, R4000, SPARCv7,
554 SuperSPARC, generic SPARCv8, and DEC VAX. Some support also for ARM,
555 Clipper, IBM ROMP (RT), and Pyramid AP/XP.
556 * Faster. Thanks to the assembler code, new algorithms, and general tuning.
557 In particular, the speed on machines without GCC is improved.
558 * Support for machines without alloca.
559 * Now under the LGPL.
561 INCOMPATIBILITIES BETWEEN GMP 1 AND GMP 2
563 * mpq assignment functions do not canonicalize their results.
564 * mpz division functions round differently.
565 * mpz mod functions now really compute mod.
566 * mpz_powm and mpz_powm_ui now really use mod for reduction.