diff -Nru gmp-doc-6.2.1+ndfsg/debian/changelog gmp-doc-6.3.0+ndfsg/debian/changelog --- gmp-doc-6.2.1+ndfsg/debian/changelog 2020-11-16 20:17:05.000000000 +0000 +++ gmp-doc-6.3.0+ndfsg/debian/changelog 2023-08-13 20:34:35.000000000 +0000 @@ -1,3 +1,14 @@ +gmp-doc (6.3.0+ndfsg-1) unstable; urgency=medium + + * New upstream version. + * Debianzation: + - d/copyright: + - copyright year tuple, update; + - d/control: + - Standards Version, bump to 4.6.2 (no change). + + -- Jerome Benoit Sun, 13 Aug 2023 20:34:35 +0000 + gmp-doc (6.2.1+ndfsg-1) unstable; urgency=medium * New upstream version. diff -Nru gmp-doc-6.2.1+ndfsg/debian/control gmp-doc-6.3.0+ndfsg/debian/control --- gmp-doc-6.2.1+ndfsg/debian/control 2020-11-16 20:16:58.000000000 +0000 +++ gmp-doc-6.3.0+ndfsg/debian/control 2023-08-13 20:30:12.000000000 +0000 @@ -5,7 +5,7 @@ Uploaders: Steve M. Robbins , Jerome Benoit Rules-Requires-Root: no Build-Depends: debhelper-compat (= 13), texinfo, texlive -Standards-Version: 4.5.0 +Standards-Version: 4.6.2 Homepage: https://gmplib.org/ Vcs-Browser: https://salsa.debian.org/science-team/gmp-doc Vcs-Git: https://salsa.debian.org/science-team/gmp-doc.git diff -Nru gmp-doc-6.2.1+ndfsg/debian/copyright gmp-doc-6.3.0+ndfsg/debian/copyright --- gmp-doc-6.2.1+ndfsg/debian/copyright 2020-11-16 20:08:21.000000000 +0000 +++ gmp-doc-6.3.0+ndfsg/debian/copyright 2023-08-13 20:22:33.000000000 +0000 @@ -15,12 +15,12 @@ Files: * Copyright: - 1991, 1993-2016 The GMP team + 1991, 1993-2023 The GMP team License: GFDL-1.3+-no-invariant Files: debian/* Copyright: - 2019 Jerome Benoit + 2019-2023 Jerome Benoit 2007-2019 Steve M. Robbins License: GPL-3+ diff -Nru gmp-doc-6.2.1+ndfsg/doc/gmp.info gmp-doc-6.3.0+ndfsg/doc/gmp.info --- gmp-doc-6.2.1+ndfsg/doc/gmp.info 2020-11-16 20:09:45.000000000 +0000 +++ gmp-doc-6.3.0+ndfsg/doc/gmp.info 2023-08-13 20:21:18.000000000 +0000 @@ -1,7 +1,7 @@ This is gmp.info, produced by makeinfo version 6.7 from gmp.texi. This manual describes how to install and use the GNU multiple precision -arithmetic library, version 6.2.1. +arithmetic library, version 6.3.0. Copyright 1991, 1993-2016, 2018-2020 Free Software Foundation, Inc. @@ -20,156 +20,156 @@  Indirect: gmp.info-1: 863 -gmp.info-2: 303737 +gmp.info-2: 301246  Tag Table: (Indirect) Node: Top863 Node: Copying2941 Node: Introduction to GMP5288 -Node: Installing GMP8004 -Node: Build Options8736 -Node: ABI and ISA24445 -Node: Notes for Package Builds34286 -Node: Notes for Particular Systems37373 -Node: Known Build Problems45124 -Node: Performance optimization48656 -Node: GMP Basics49785 -Node: Headers and Libraries50433 -Node: Nomenclature and Types51838 -Node: Function Classes53834 -Node: Variable Conventions55369 -Node: Parameter Conventions57609 -Node: Memory Management59416 -Node: Reentrancy60544 -Node: Useful Macros and Constants62412 -Node: Compatibility with older versions63403 -Node: Demonstration Programs64313 -Node: Efficiency66172 -Node: Debugging73778 -Node: Profiling80553 -Node: Autoconf84544 -Node: Emacs86325 -Node: Reporting Bugs86931 -Node: Integer Functions89557 -Node: Initializing Integers90333 -Node: Assigning Integers92709 -Node: Simultaneous Integer Init & Assign94320 -Node: Converting Integers95967 -Node: Integer Arithmetic98907 -Node: Integer Division100643 -Node: Integer Exponentiation107402 -Node: Integer Roots108899 -Node: Number Theoretic Functions110616 -Node: Integer Comparisons118111 -Node: Integer Logic and Bit Fiddling119549 -Node: I/O of Integers122189 -Node: Integer Random Numbers125180 -Node: Integer Import and Export127803 -Node: Miscellaneous Integer Functions131819 -Node: Integer Special Functions133733 -Node: Rational Number Functions137906 -Node: Initializing Rationals139099 -Node: Rational Conversions141572 -Node: Rational Arithmetic143594 -Node: Comparing Rationals145006 -Node: Applying Integer Functions146477 -Node: I/O of Rationals147996 -Node: Floating-point Functions150355 -Node: Initializing Floats153400 -Node: Assigning Floats157492 -Node: Simultaneous Float Init & Assign160080 -Node: Converting Floats161630 -Node: Float Arithmetic164895 -Node: Float Comparison167048 -Node: I/O of Floats168619 -Node: Miscellaneous Float Functions171308 -Node: Low-level Functions173310 -Node: Random Number Functions207558 -Node: Random State Initialization208626 -Node: Random State Seeding211491 -Node: Random State Miscellaneous212896 -Node: Formatted Output213538 -Node: Formatted Output Strings213783 -Node: Formatted Output Functions219178 -Node: C++ Formatted Output223242 -Node: Formatted Input225942 -Node: Formatted Input Strings226178 -Node: Formatted Input Functions230838 -Node: C++ Formatted Input233807 -Node: C++ Class Interface235710 -Node: C++ Interface General236661 -Node: C++ Interface Integers239730 -Node: C++ Interface Rationals243963 -Node: C++ Interface Floats247987 -Node: C++ Interface Random Numbers254004 -Node: C++ Interface Limitations256404 -Node: Custom Allocation259979 -Node: Language Bindings264198 -Node: Algorithms267511 -Node: Multiplication Algorithms268211 -Node: Basecase Multiplication269300 -Node: Karatsuba Multiplication271208 -Node: Toom 3-Way Multiplication274832 -Node: Toom 4-Way Multiplication281251 -Node: Higher degree Toom'n'half282630 -Node: FFT Multiplication283922 -Node: Other Multiplication289258 -Node: Unbalanced Multiplication291732 -Node: Division Algorithms292520 -Node: Single Limb Division292899 -Node: Basecase Division295787 -Node: Divide and Conquer Division296990 -Node: Block-Wise Barrett Division299058 -Node: Exact Division299710 -Node: Exact Remainder303737 -Node: Small Quotient Division305987 -Node: Greatest Common Divisor Algorithms307585 -Node: Binary GCD307882 -Node: Lehmer's Algorithm310732 -Node: Subquadratic GCD312962 -Node: Extended GCD315431 -Node: Jacobi Symbol316749 -Node: Powering Algorithms318658 -Node: Normal Powering Algorithm318921 -Node: Modular Powering Algorithm319449 -Node: Root Extraction Algorithms320231 -Node: Square Root Algorithm320546 -Node: Nth Root Algorithm322687 -Node: Perfect Square Algorithm323472 -Node: Perfect Power Algorithm325559 -Node: Radix Conversion Algorithms326180 -Node: Binary to Radix326556 -Node: Radix to Binary330177 -Node: Other Algorithms332265 -Node: Prime Testing Algorithm332617 -Node: Factorial Algorithm333801 -Node: Binomial Coefficients Algorithm336201 -Node: Fibonacci Numbers Algorithm337095 -Node: Lucas Numbers Algorithm339569 -Node: Random Number Algorithms340290 -Node: Assembly Coding342410 -Node: Assembly Code Organisation343370 -Node: Assembly Basics344337 -Node: Assembly Carry Propagation345487 -Node: Assembly Cache Handling347317 -Node: Assembly Functional Units349478 -Node: Assembly Floating Point351091 -Node: Assembly SIMD Instructions354870 -Node: Assembly Software Pipelining355852 -Node: Assembly Loop Unrolling356915 -Node: Assembly Writing Guide359130 -Node: Internals361895 -Node: Integer Internals362407 -Node: Rational Internals364871 -Node: Float Internals366109 -Node: Raw Output Internals373509 -Node: C++ Interface Internals374703 -Node: Contributors378024 -Node: References384255 -Node: GNU Free Documentation License390174 -Node: Concept Index415316 -Node: Function Index463130 +Node: Installing GMP8006 +Node: Build Options8738 +Node: ABI and ISA24450 +Node: Notes for Package Builds34296 +Node: Notes for Particular Systems37383 +Node: Known Build Problems45134 +Node: Performance optimization48667 +Node: GMP Basics49795 +Node: Headers and Libraries50443 +Node: Nomenclature and Types52054 +Node: Function Classes56262 +Node: Variable Conventions57797 +Node: Parameter Conventions60151 +Node: Memory Management62103 +Node: Reentrancy63231 +Node: Useful Macros and Constants65099 +Node: Compatibility with older versions66090 +Node: Demonstration Programs67000 +Node: Efficiency68859 +Node: Debugging76461 +Node: Profiling83236 +Node: Autoconf87227 +Node: Emacs89008 +Node: Reporting Bugs89614 +Node: Integer Functions92311 +Node: Initializing Integers93087 +Node: Assigning Integers95463 +Node: Simultaneous Integer Init & Assign97076 +Node: Converting Integers98723 +Node: Integer Arithmetic101663 +Node: Integer Division103399 +Node: Integer Exponentiation110158 +Node: Integer Roots111655 +Node: Number Theoretic Functions113372 +Node: Integer Comparisons121149 +Node: Integer Logic and Bit Fiddling122587 +Node: I/O of Integers125385 +Node: Integer Random Numbers128378 +Node: Integer Import and Export131002 +Node: Miscellaneous Integer Functions135018 +Node: Integer Special Functions136932 +Node: Rational Number Functions141105 +Node: Initializing Rationals142298 +Node: Rational Conversions144771 +Node: Rational Arithmetic146793 +Node: Comparing Rationals148205 +Node: Applying Integer Functions149674 +Node: I/O of Rationals151380 +Node: Floating-point Functions153739 +Node: Initializing Floats156790 +Node: Assigning Floats160882 +Node: Simultaneous Float Init & Assign163472 +Node: Converting Floats165022 +Node: Float Arithmetic168287 +Node: Float Comparison170440 +Node: I/O of Floats172011 +Node: Miscellaneous Float Functions174700 +Node: Low-level Functions176702 +Node: Random Number Functions210955 +Node: Random State Initialization212023 +Node: Random State Seeding214889 +Node: Random State Miscellaneous216289 +Node: Formatted Output216931 +Node: Formatted Output Strings217176 +Node: Formatted Output Functions222572 +Node: C++ Formatted Output226636 +Node: Formatted Input229337 +Node: Formatted Input Strings229573 +Node: Formatted Input Functions234233 +Node: C++ Formatted Input237202 +Node: C++ Class Interface239105 +Node: C++ Interface General240056 +Node: C++ Interface Integers243125 +Node: C++ Interface Rationals247358 +Node: C++ Interface Floats251382 +Node: C++ Interface Random Numbers257398 +Node: C++ Interface Limitations259798 +Node: Custom Allocation263373 +Node: Language Bindings267592 +Node: Algorithms270905 +Node: Multiplication Algorithms271605 +Node: Basecase Multiplication272694 +Node: Karatsuba Multiplication274602 +Node: Toom 3-Way Multiplication278226 +Node: Toom 4-Way Multiplication284650 +Node: Higher degree Toom'n'half286028 +Node: FFT Multiplication287316 +Node: Other Multiplication292651 +Node: Unbalanced Multiplication295125 +Node: Division Algorithms295913 +Node: Single Limb Division296292 +Node: Basecase Division299180 +Node: Divide and Conquer Division301246 +Node: Block-Wise Barrett Division303314 +Node: Exact Division303966 +Node: Exact Remainder307130 +Node: Small Quotient Division309380 +Node: Greatest Common Divisor Algorithms310978 +Node: Binary GCD311275 +Node: Lehmer's Algorithm314127 +Node: Subquadratic GCD316363 +Node: Extended GCD318833 +Node: Jacobi Symbol320152 +Node: Powering Algorithms322061 +Node: Normal Powering Algorithm322324 +Node: Modular Powering Algorithm322852 +Node: Root Extraction Algorithms323634 +Node: Square Root Algorithm323949 +Node: Nth Root Algorithm326090 +Node: Perfect Square Algorithm326875 +Node: Perfect Power Algorithm328962 +Node: Radix Conversion Algorithms329583 +Node: Binary to Radix329959 +Node: Radix to Binary333580 +Node: Other Algorithms335668 +Node: Prime Testing Algorithm336020 +Node: Factorial Algorithm337204 +Node: Binomial Coefficients Algorithm339606 +Node: Fibonacci Numbers Algorithm340500 +Node: Lucas Numbers Algorithm342974 +Node: Random Number Algorithms343695 +Node: Assembly Coding345815 +Node: Assembly Code Organisation346775 +Node: Assembly Basics347742 +Node: Assembly Carry Propagation348892 +Node: Assembly Cache Handling350722 +Node: Assembly Functional Units352883 +Node: Assembly Floating Point354502 +Node: Assembly SIMD Instructions358281 +Node: Assembly Software Pipelining359263 +Node: Assembly Loop Unrolling360324 +Node: Assembly Writing Guide362539 +Node: Internals365304 +Node: Integer Internals365816 +Node: Rational Internals368282 +Node: Float Internals369520 +Node: Raw Output Internals376925 +Node: C++ Interface Internals378120 +Node: Contributors381441 +Node: References387669 +Node: GNU Free Documentation License393588 +Node: Concept Index418730 +Node: Function Index466824  End Tag Table diff -Nru gmp-doc-6.2.1+ndfsg/doc/gmp.info-1 gmp-doc-6.3.0+ndfsg/doc/gmp.info-1 --- gmp-doc-6.2.1+ndfsg/doc/gmp.info-1 2020-11-16 20:09:45.000000000 +0000 +++ gmp-doc-6.3.0+ndfsg/doc/gmp.info-1 2023-08-13 20:21:18.000000000 +0000 @@ -1,7 +1,7 @@ This is gmp.info, produced by makeinfo version 6.7 from gmp.texi. This manual describes how to install and use the GNU multiple precision -arithmetic library, version 6.2.1. +arithmetic library, version 6.3.0. Copyright 1991, 1993-2016, 2018-2020 Free Software Foundation, Inc. @@ -24,7 +24,7 @@ ****** This manual describes how to install and use the GNU multiple precision -arithmetic library, version 6.2.1. +arithmetic library, version 6.3.0. Copyright 1991, 1993-2016, 2018-2020 Free Software Foundation, Inc. @@ -101,7 +101,7 @@ (The reason for this dual licensing is to make it possible to use the library with programs which are licensed under GPL version 2, but which for historical or other reasons do not allow use under later versions of -the GPL). +the GPL.) Programs which are not part of the library itself, such as demonstration programs and the GMP testsuite, are licensed under the @@ -134,11 +134,11 @@ There is assembly code for these CPUs: ARM Cortex-A9, Cortex-A15, and generic ARM, DEC Alpha 21064, 21164, and 21264, AMD K8 and K10 (sold -under many brands, e.g. Athlon64, Phenom, Opteron) Bulldozer, and +under many brands, e.g. Athlon64, Phenom, Opteron), Bulldozer, and Bobcat, Intel Pentium, Pentium Pro/II/III, Pentium 4, Core2, Nehalem, Sandy bridge, Haswell, generic x86, Intel IA-64, Motorola/IBM PowerPC 32 and 64 such as POWER970, POWER5, POWER6, and POWER7, MIPS 32-bit and -64-bit, SPARC 32-bit ad 64-bit with special support for all UltraSPARC +64-bit, SPARC 32-bit and 64-bit with special support for all UltraSPARC models. There is also assembly code for many obsolete CPUs. For up-to-date information on GMP, please see the GMP web pages at @@ -230,7 +230,7 @@ directory. For example cd /my/build/dir - /my/sources/gmp-6.2.1/configure + /my/sources/gmp-6.3.0/configure Not all 'make' programs have the necessary features ('VPATH') to support this. In particular, SunOS and Slowaris 'make' have bugs @@ -283,9 +283,9 @@ plain 'ranlib'. This makes it possible for a set of cross-compiling tools to co-exist with native tools. The prefix is the argument to '--host', and this can be an alias, such as - 'm68k-linux'. But note that tools don't have to be setup this way, - it's enough to just have a 'PATH' with a suitable cross-compiling - 'cc' etc. + 'm68k-linux'. But note that tools don't have to be set up this + way, it's enough to just have a 'PATH' with a suitable + cross-compiling 'cc' etc. Compiling for a different CPU in the same family as the build system is a form of cross-compilation, though very possibly this @@ -324,7 +324,7 @@ details of what code and compiler options they select. * Alpha: alpha, alphaev5, alphaev56, alphapca56, alphapca57, - alphaev6, alphaev67, alphaev68 alphaev7 + alphaev6, alphaev67, alphaev68, alphaev7 * Cray: c90, j90, t90, sv1 @@ -528,8 +528,8 @@ 'MPN_PATH' Various assembly versions of each mpn subroutines are provided. - For a given CPU, a search is made though a path to choose a version - of each. For example 'sparcv8' has + For a given CPU, a search is made through a path to choose a + version of each. For example 'sparcv8' has MPN_PATH="sparc32/v8 sparc32 generic" @@ -592,7 +592,7 @@ This will probably only matter when installing multiple builds of GMP, and it might be as simple as configuring with a special 'libdir', or it might require more than that. Note that builds for different ABIs need -to done separately, with a fresh './configure' and 'make' each. +to be done separately, with a fresh './configure' and 'make' each. AMD64 ('x86_64') @@ -645,7 +645,7 @@ gcc [built for 2.0n] cc +DA2.0 +e - Note that current versions of GCC (eg. 3.2) don't generate + Note that current versions of GCC (e.g. 3.2) don't generate 64-bit instructions for 'long long' operations and so may be slower than for 2.0w. (The GMP assembly code is the same though.) @@ -698,7 +698,7 @@ 'ABI=o32' The o32 ABI is 32-bit pointers and integers, and no 64-bit operations. GMP will be slower than in n32 or 64, this option - only exists to support old compilers, eg. GCC 2.7.2. + only exists to support old compilers, e.g. GCC 2.7.2. Applications can be compiled with no special flags on an old compiler, or on a newer compiler with @@ -1063,7 +1063,7 @@ 'config.log'. Use 'bash' 2.04 or higher. 'make all' was found to run out of memory during the final - 'libgmp.la' link on one system tested, despite having 64Mb + 'libgmp.la' link on one system tested, despite having 64MiB available. Running 'make libgmp.la' directly helped, perhaps recursing into the various subdirectories uses up memory. @@ -1137,7 +1137,7 @@ In particular for long-running GMP applications, and applications demanding extremely large numbers, building and running the 'tuneup' -program in the 'tune' subdirectory, can be important. For example, +program in the 'tune' subdirectory can be important. For example, cd tune make tuneup @@ -1188,12 +1188,14 @@ ========================= All declarations needed to use GMP are collected in the include file -'gmp.h'. It is designed to work with both C and C++ compilers. +'gmp.h', except for the *note C++ Class Interface:: which comes with its +own separate header 'gmpxx.h'. 'gmp.h' is designed to work with both C +and C++ compilers. #include Note however that prototypes for GMP functions with 'FILE *' -parameters are only provided if '' is included too. +parameters are only provided if '' is included before. #include #include @@ -1208,9 +1210,10 @@ gcc myprogram.c -lgmp - GMP C++ functions are in a separate 'libgmpxx' library. This is -built and installed if C++ support has been enabled (*note Build -Options::). For example, + GMP C++ functions are in a separate 'libgmpxx' library, including the +*note C++ Class Interface:: but also *note C++ Formatted Output:: for +regular GMP types. This is built and installed if C++ support has been +enabled (*note Build Options::). For example, g++ mycxxprog.cc -lgmpxx -lgmp @@ -1275,6 +1278,52 @@ Also, in general 'mp_bitcnt_t' is used for bit counts and ranges, and 'size_t' is used for byte or character counts. + + Internally, GMP data types such as 'mpz_t' are defined as one-element +arrays, whose element type is part of the GMP internals (*note +Internals::). + + When an array is used as a function argument in C, it is not passed +by value, instead its value is a pointer to the first element. In C +jargon, this is sometimes referred to as the array "decaying" to a +pointer. For GMP types like 'mpz_t', that means that the function +called gets a pointer to the caller's 'mpz_t' value, which is why no +explicit '&' operator is needed when passing output arguments (*note +Parameter Conventions::). + + GMP defines names for these pointer types, e.g., 'mpz_ptr' +corresponding to 'mpz_t', and 'mpz_srcptr' corresponding to 'const +mpz_t'. Most functions don't need to use these pointer types directly; +it works fine to declare a function using the 'mpz_t' or 'const mpz_t' +as the argument types, the same "pointer decay" happens in the +background regardless. + + Occasionally, it is useful to manipulate pointers directly, e.g., to +conditionally swap _references_ to a function's inputs without changing +the _values_ as seen by the caller, or returning a pointer to an 'mpz_t' +which is part of a larger structure. For these cases, the pointer types +are necessary. And a 'mpz_ptr' can be passed as argument to any GMP +function declared to take an 'mpz_t' argument. + + Their definition is equivalent to the following code, which is given +for illustratory purposes only: + + typedef foo_internal foo_t[1]; + typedef foo_internal * foo_ptr; + typedef const foo_internal * foo_srcptr; + + The following pointer types are defined by GMP: + * 'mpz_ptr' for pointers to the element type in 'mpz_t' + * 'mpz_srcptr' for 'const' pointers to the element type in 'mpz_t' + * 'mpq_ptr' for pointers to the element type in 'mpq_t' + * 'mpq_srcptr' for 'const' pointers to the element type in 'mpq_t' + * 'mpf_ptr' for pointers to the element type in 'mpf_t' + * 'mpf_srcptr' for 'const' pointers to the element type in 'mpf_t' + * 'gmp_randstate_ptr' for pointers to the element type in + 'gmp_randstate_t' + * 'gmp_randstate_srcptr' for 'const' pointers to the element type in + 'gmp_randstate_t' +  File: gmp.info, Node: Function Classes, Next: Variable Conventions, Prev: Nomenclature and Types, Up: GMP Basics @@ -1295,7 +1344,7 @@ 3. Functions for floating-point arithmetic, with names beginning with 'mpf_'. The associated type is 'mpf_t'. There are about 70 - functions is this class. (*note Floating-point Functions::) + functions in this class. (*note Floating-point Functions::) 4. Fast low-level functions that operate on natural numbers. These are used by the functions in the preceding groups, and you can also @@ -1356,14 +1405,15 @@ GMP types like 'mpz_t' are implemented as one-element arrays of certain structures. Declaring a variable creates an object with the fields GMP needs, but variables are normally manipulated by using the -pointer to the object. For both behavior and efficiency reasons, it is -discouraged to make copies of the GMP object itself (either directly or -via aggregate objects containing such GMP objects). If copies are done, -all of them must be used read-only; using a copy as the output of some -function will invalidate all the other copies. Note that the actual -fields in each 'mpz_t' etc are for internal use only and should not be -accessed directly by code that expects to be compatible with future GMP -releases. +pointer to the object. The appropriate pointer types (*note +Nomenclature and Types::) may be used to explicitly manipulate the +pointer. For both behavior and efficiency reasons, it is discouraged to +make copies of the GMP object itself (either directly or via aggregate +objects containing such GMP objects). If copies are done, all of them +must be used read-only; using a copy as the output of some function will +invalidate all the other copies. Note that the actual fields in each +'mpz_t' etc are for internal use only and should not be accessed +directly by code that expects to be compatible with future GMP releases.  File: gmp.info, Node: Parameter Conventions, Next: Memory Management, Prev: Variable Conventions, Up: GMP Basics @@ -1414,7 +1464,10 @@ Since GMP types are implemented as one-element arrays, using a GMP variable as a parameter passes a pointer to the object. Hence the -call-by-reference. +call-by-reference. A more explicit (and equivalent) prototype for our +function 'foo' could be: + + void foo (mpz_ptr result, mpz_srcptr param, unsigned long n);  File: gmp.info, Node: Memory Management, Next: Reentrancy, Prev: Parameter Conventions, Up: GMP Basics @@ -1503,7 +1556,7 @@ -- Global Constant: const char * const gmp_version The GMP version number, as a null-terminated string, in the form - "i.j.k". This release is "6.2.1". Note that the format "i.j" was + "i.j.k". This release is "6.3.0". Note that the format "i.j" was used, before version 4.3.0, when k was zero. -- Macro: __GMP_CC @@ -1571,7 +1624,7 @@ something minimal quickly leads to matters like user-defined functions, looping, fixnums for control variables, etc, which are considered outside the scope of GMP (much closer to language interpreters or -compilers, *Note Language Bindings::.) Something simple for program +compilers, *Note Language Bindings::). Something simple for program input convenience may yet be a possibility, a combination of the 'expr' demo and the 'pexpr' tree back-end perhaps. But for now the above evaluators are offered as illustrations. @@ -1629,8 +1682,8 @@ The 'ui' functions and the small number of 'si' functions exist for convenience and should be used where applicable. But if for example an 'mpz_t' contains a value that fits in an 'unsigned long' - there's no need extract it and call a 'ui' function, just use the - regular 'mpz' function. + there's no need to extract it and call a 'ui' function, just use + the regular 'mpz' function. In-Place Operations 'mpz_abs', 'mpq_abs', 'mpf_abs', 'mpz_neg', 'mpq_neg' and 'mpf_neg' @@ -1676,8 +1729,8 @@ However when testing divisibility by several small integers, it's best to take a remainder modulo their product, to save multi-precision operations. For instance to test whether a number - is divisible by any of 23, 29 or 31 take a remainder modulo - 23*29*31 = 20677 and then test that. + is divisible by 23, 29 or 31 take a remainder modulo 23*29*31 = + 20677 and then test that. The division functions like 'mpz_tdiv_q_ui' which give a quotient as well as a remainder are generally a little slower than the @@ -1805,7 +1858,7 @@ to the source directory. cd /my/build/dir - /my/source/dir/gmp-6.2.1/configure + /my/source/dir/gmp-6.3.0/configure This works via 'VPATH', and might require GNU 'make'. Alternately it might be possible to change the '.c.lo' rules appropriately. @@ -2055,9 +2108,10 @@ Before you report a bug, check it's not already addressed in *note Known Build Problems::, or perhaps *note Notes for Particular Systems::. You may also want to check for patches for this -release. +release, or try a recent snapshot from +. - Please include the following in any report, + Please include the following in any report: * The GMP version number, and if pre-packaged or patched then say so. @@ -2237,9 +2291,9 @@ for binary, '0' for octal, or decimal otherwise. For bases up to 36, case is ignored; upper-case and lower-case - letters have the same value. For bases 37 to 62, upper-case letter - represent the usual 10..35 while lower-case letter represent - 36..61. + letters have the same value. For bases 37 to 62, upper-case + letters represent the usual 10..35 while lower-case letters + represent 36..61. This function returns 0 if the entire string is a valid number in base BASE. Otherwise it returns -1. @@ -2412,7 +2466,7 @@ Division is undefined if the divisor is zero. Passing a zero divisor to the division or modulo functions (including the modular powering -functions 'mpz_powm' and 'mpz_powm_ui'), will cause an intentional +functions 'mpz_powm' and 'mpz_powm_ui') will cause an intentional division by zero. This lets a program handle arithmetic exceptions in these functions the same way as for normal C 'int' arithmetic. @@ -2506,8 +2560,8 @@ For positive N both 'mpz_fdiv_q_2exp' and 'mpz_tdiv_q_2exp' are simple bitwise right shifts. For negative N, 'mpz_fdiv_q_2exp' is - effectively an arithmetic right shift treating N as twos complement - the same as the bitwise logical functions do, whereas + effectively an arithmetic right shift treating N as two's + complement the same as the bitwise logical functions do, whereas 'mpz_tdiv_q_2exp' effectively treats N as sign and magnitude. -- Function: void mpz_mod (mpz_t R, const mpz_t N, const mpz_t D) @@ -2657,7 +2711,16 @@ -- Function: void mpz_nextprime (mpz_t ROP, const mpz_t OP) Set ROP to the next prime greater than OP. - This function uses a probabilistic algorithm to identify primes. + -- Function: int mpz_prevprime (mpz_t ROP, const mpz_t OP) + Set ROP to the greatest prime less than OP. + + If a previous prime doesn't exist (i.e. OP < 3), rop is unchanged + and 0 is returned. + + Return 1 if ROP is a probably prime, and 2 if ROP is definitely + prime. + + These functions use a probabilistic algorithm to identify primes. For practical purposes it's adequate, the chance of a composite passing will be extremely small. @@ -2768,7 +2831,7 @@ -- Function: void mpz_fib_ui (mpz_t FN, unsigned long int N) -- Function: void mpz_fib2_ui (mpz_t FN, mpz_t FNSUB1, unsigned long int N) - 'mpz_fib_ui' sets FN to to F[n], the N'th Fibonacci number. + 'mpz_fib_ui' sets FN to F[n], the Nth Fibonacci number. 'mpz_fib2_ui' sets FN to F[n], and FNSUB1 to F[n-1]. These functions are designed for calculating isolated Fibonacci @@ -2779,7 +2842,7 @@ -- Function: void mpz_lucnum_ui (mpz_t LN, unsigned long int N) -- Function: void mpz_lucnum2_ui (mpz_t LN, mpz_t LNSUB1, unsigned long int N) - 'mpz_lucnum_ui' sets LN to to L[n], the N'th Lucas number. + 'mpz_lucnum_ui' sets LN to L[n], the Nth Lucas number. 'mpz_lucnum2_ui' sets LN to L[n], and LNSUB1 to L[n-1]. These functions are designed for calculating isolated Lucas @@ -2832,7 +2895,7 @@ 5.11 Logical and Bit Manipulation Functions =========================================== -These functions behave as if twos complement arithmetic were used +These functions behave as if two's complement arithmetic were used (although sign-magnitude is the actual implementation). The least significant bit is number 0. @@ -2889,6 +2952,10 @@ -- Function: int mpz_tstbit (const mpz_t OP, mp_bitcnt_t BIT_INDEX) Test bit BIT_INDEX in OP and return 0 or 1 accordingly. + Shifting is also possible using multiplication (*note Integer +Arithmetic::) and division (*note Integer Division::), in particular the +'2exp' functions. +  File: gmp.info, Node: I/O of Integers, Next: Integer Random Numbers, Prev: Integer Logic and Bit Fiddling, Up: Integer Functions @@ -2928,9 +2995,9 @@ for binary, '0' for octal, or decimal otherwise. For bases up to 36, case is ignored; upper-case and lower-case - letters have the same value. For bases 37 to 62, upper-case letter - represent the usual 10..35 while lower-case letter represent - 36..61. + letters have the same value. For bases 37 to 62, upper-case + letters represent the usual 10..35 while lower-case letters + represent 36..61. Return the number of bytes read, or if an error occurred, return 0. @@ -2965,7 +3032,7 @@ 5.13 Random Number Functions ============================ -The random number functions of GMP come in two groups; older function +The random number functions of GMP come in two groups; older functions that rely on a global state, and newer functions that accept a state parameter that is read and modified. Please see the *note Random Number Functions:: for more information on how to use and not to use random @@ -3444,7 +3511,7 @@ NUM2 and DEN2 are allowed to have common factors. - These functions are implemented as a macros and evaluate their + These functions are implemented as macros and evaluate their arguments multiple times. -- Macro: int mpq_sgn (const mpq_t OP) @@ -3473,11 +3540,13 @@ chapter (*note Rational Number Functions::) then 'mpq_canonicalize' must be called before any other 'mpq' functions are applied to that 'mpq_t'. - -- Macro: mpz_t mpq_numref (const mpq_t OP) - -- Macro: mpz_t mpq_denref (const mpq_t OP) + -- Macro: mpz_ptr mpq_numref (const mpq_t OP) + -- Macro: mpz_ptr mpq_denref (const mpq_t OP) Return a reference to the numerator and denominator of OP, respectively. The 'mpz' functions can be used on the result of - these macros. + these macros. Such calls may modify the numerator or denominator. + However, care should be taken so that OP remains in canonical form + prior to a possible later call to an 'mpq' function. -- Function: void mpq_get_num (mpz_t NUMERATOR, const mpq_t RATIONAL) -- Function: void mpq_get_den (mpz_t DENOMINATOR, const mpq_t RATIONAL) @@ -3595,8 +3664,8 @@ different word size. New projects should consider using the GMP extension library MPFR -() instead. MPFR provides well-defined precision and -accurate rounding, and thereby naturally extends IEEE P754. +() instead. MPFR provides well-defined precision +and accurate rounding, and thereby naturally extends IEEE P754. * Menu: @@ -3736,8 +3805,8 @@ decimal. For bases up to 36, case is ignored; upper-case and lower-case - letters have the same value; for bases 37 to 62, upper-case letter - represent the usual 10..35 while lower-case letter represent + letters have the same value; for bases 37 to 62, upper-case letters + represent the usual 10..35 while lower-case letters represent 36..61. Unlike the corresponding 'mpz' function, the base will not be @@ -4164,7 +4233,7 @@ -- Function: mp_limb_t mpn_neg (mp_limb_t *RP, const mp_limb_t *SP, mp_size_t N) Perform the negation of {SP, N}, and write the result to {RP, N}. - This is equivalent to calling 'mpn_sub_n' with a N-limb zero + This is equivalent to calling 'mpn_sub_n' with an N-limb zero minuend and passing {SP, N} as subtrahend. Return borrow, either 0 or 1. @@ -4340,7 +4409,7 @@ significant COUNT bits of the return value (the rest of the return value is zero). - COUNT must be in the range 1 to mp_bits_per_limb-1. The regions + COUNT must be in the range 1 to mp_bits_per_limb{}-1. The regions {SP, N} and {RP, N} may overlap, provided RP >= SP. This function is written in assembly for most CPUs. @@ -4352,7 +4421,7 @@ significant COUNT bits of the return value (the rest of the return value is zero). - COUNT must be in the range 1 to mp_bits_per_limb-1. The regions + COUNT must be in the range 1 to mp_bits_per_limb{}-1. The regions {SP, N} and {RP, N} may overlap, provided RP <= SP. This function is written in assembly for most CPUs. @@ -4892,7 +4961,7 @@ choice is 'GMP_RAND_ALG_LC', which is 'gmp_randinit_lc_2exp_size' described above. A third parameter of type 'unsigned long' is required, this is the SIZE for that function. - 'GMP_RAND_ALG_DEFAULT' or 0 are the same as 'GMP_RAND_ALG_LC'. + 'GMP_RAND_ALG_DEFAULT' and 0 are the same as 'GMP_RAND_ALG_LC'. 'gmp_randinit' sets bits in the global variable 'gmp_errno' to indicate an error. 'GMP_ERROR_UNSUPPORTED_ARGUMENT' if ALG is @@ -4916,8 +4985,8 @@ Set an initial seed value into STATE. The size of a seed determines how many different sequences of - random numbers that it's possible to generate. The "quality" of - the seed is the randomness of a given seed compared to the previous + random numbers it's possible to generate. The "quality" of the + seed is the randomness of a given seed compared to the previous seed used, and this affects the randomness of separate number sequences. The method for choosing a seed is critical if the generated numbers are to be used for important applications, such @@ -5066,8 +5135,8 @@ 'M' is a proxy for the C library 'l' or 'L', according to the size of 'mp_limb_t'. Unsigned conversions will be usual, but a signed -conversion can be used and will interpret the value as a twos complement -negative. +conversion can be used and will interpret the value as a two's +complement negative. 'n' can be used with any type, even the GMP types. @@ -5168,7 +5237,7 @@ Form a null-terminated string in a block of memory obtained from the current memory allocation function (*note Custom Allocation::). The block will be the size of the string and null-terminator. The - address of the block in stored to *PP. The return value is the + address of the block is stored to *PP. The return value is the number of characters produced, excluding the null-terminator. Unlike the C library 'asprintf', 'gmp_asprintf' doesn't return -1 @@ -5206,7 +5275,7 @@ In hex or octal, OP is printed as a signed number, the same as for decimal. This is unlike the standard 'operator<<' routines on - 'int' etc, which instead give twos complement. + 'int' etc, which instead give two's complement. -- Function: ostream& operator<< (ostream& STREAM, const mpq_t OP) Print OP to STREAM, using its 'ios' formatting settings. @@ -5938,7 +6007,7 @@ The restrictions described for 'mpf_set_prec_raw' (*note Initializing Floats::) apply to 'mpf_class::set_prec_raw'. Note in - particular that the 'mpf_class' must be restored to it's allocated + particular that the 'mpf_class' must be restored to its allocated precision before being destroyed. This must be done by application code, there's no automatic mechanism for it. @@ -6528,7 +6597,7 @@ The w[i] are going to be determined, and when they are they'll give the final result using w=W(b), since x*y=X(b)*Y(b)=W(b). The coefficients will be roughly b^2 each, and the final W(b) will be an -addition like, +addition like this: high low +-------+-------+ @@ -6554,7 +6623,7 @@ approach is used. X(t) and Y(t) are evaluated and multiplied at 5 points, giving values -of W(t) at those points. In GMP the following points are used, +of W(t) at those points. In GMP the following points are used: Point Value t=0 x0 * y0, which gives w0 immediately @@ -6659,7 +6728,7 @@ The number of additions and subtractions for Toom-4 is much larger than for Toom-3. But several subexpressions occur multiple times, for -example x2+x0, occurs for both t=1 and t=-1. +example x2+x0 occurs for both t=1 and t=-1. Toom-4 is asymptotically O(N^1.404), the exponent being log(7)/log(4), representing 7 recursive multiplies of 1/4 the original @@ -6672,19 +6741,18 @@ -------------------------------- The Toom algorithms described above (*note Toom 3-Way Multiplication::, -*note Toom 4-Way Multiplication::) generalizes to split into an -arbitrary number of pieces. In general a split of two equally long -operands into r pieces leads to evaluations and pointwise -multiplications done at 2*r-1 points. To fully exploit symmetries it -would be better to have a multiple of 4 points, that's why for higher -degree Toom'n'half is used. +*note Toom 4-Way Multiplication::) generalize to split into an arbitrary +number of pieces. In general a split of two equally long operands into +r pieces leads to evaluations and pointwise multiplications done at +2*r-1 points. To fully exploit symmetries it would be better to have a +multiple of 4 points, that's why for higher degree Toom'n'half is used. Toom'n'half means that the existence of one more piece is considered for a single operand. It can be virtual, i.e. zero, or real, when the -two operand are not exactly balanced. By choosing an even r, Toom-r+1/2 -requires 2r points, a multiple of four. +two operands are not exactly balanced. By choosing an even r, +Toom-r+1/2 requires 2r points, a multiple of four. - The quadruplets of points include 0, inf, +1, -1 and +-2^i, +-2^-i . + The quadruplets of points include 0, inf, +1, and +-2^i, +-2^-i. Each of them giving shortcuts for the evaluation phase and for some steps in the interpolation phase. Further tricks are used to reduce the memory footprint of the whole multiplication algorithm to a memory @@ -6716,9 +6784,9 @@ (2^k)*mp_bits_per_limb so the split falls on limb boundaries, avoiding bit shifts in the split and combine stages. - The evaluations, pointwise multiplications, and interpolation, are -all done modulo 2^N'+1 where N' is 2M+k+3 rounded up to a multiple of -2^k and of 'mp_bits_per_limb'. The results of interpolation will be the + The evaluations, pointwise multiplications, and interpolation are all +done modulo 2^N'+1 where N' is 2M+k+3 rounded up to a multiple of 2^k +and of 'mp_bits_per_limb'. The results of interpolation will be the following negacyclic convolution of the input pieces, and the choice of N' ensures these sums aren't truncated. @@ -6856,7 +6924,7 @@ For operands between these sizes, we use Toom inspired algorithms suggested by Alberto Zanoni and Marco Bodrato. The idea is to split the operands into polynomials of different degree. GMP currently splits the -smaller operand onto 2 coefficients, i.e., a polynomial of degree 1, but +smaller operand into 2 coefficients, i.e., a polynomial of degree 1, but the larger operand can be split into 2, 3, or 4 coefficients, i.e., a polynomial of degree 1 to 3. @@ -6955,117 +7023,3 @@ multiplication, differing in fact only in the extra multiply and divide for each of the Q quotient limbs. - -File: gmp.info, Node: Divide and Conquer Division, Next: Block-Wise Barrett Division, Prev: Basecase Division, Up: Division Algorithms - -15.2.3 Divide and Conquer Division ----------------------------------- - -For divisors larger than 'DC_DIV_QR_THRESHOLD', division is done by -dividing. Or to be precise by a recursive divide and conquer algorithm -based on work by Moenck and Borodin, Jebelean, and Burnikel and Ziegler -(*note References::). - - The algorithm consists essentially of recognising that a 2NxN -division can be done with the basecase division algorithm (*note -Basecase Division::), but using N/2 limbs as a base, not just a single -limb. This way the multiplications that arise are (N/2)x(N/2) and can -take advantage of Karatsuba and higher multiplication algorithms (*note -Multiplication Algorithms::). The two "digits" of the quotient are -formed by recursive Nx(N/2) divisions. - - If the (N/2)x(N/2) multiplies are done with a basecase multiplication -then the work is about the same as a basecase division, but with more -function call overheads and with some subtractions separated from the -multiplies. These overheads mean that it's only when N/2 is above -'MUL_TOOM22_THRESHOLD' that divide and conquer is of use. - - 'DC_DIV_QR_THRESHOLD' is based on the divisor size N, so it will be -somewhere above twice 'MUL_TOOM22_THRESHOLD', but how much above depends -on the CPU. An optimized 'mpn_mul_basecase' can lower -'DC_DIV_QR_THRESHOLD' a little by offering a ready-made advantage over -repeated 'mpn_submul_1' calls. - - Divide and conquer is asymptotically O(M(N)*log(N)) where M(N) is the -time for an NxN multiplication done with FFTs. The actual time is a sum -over multiplications of the recursed sizes, as can be seen near the end -of section 2.2 of Burnikel and Ziegler. For example, within the Toom-3 -range, divide and conquer is 2.63*M(N). With higher algorithms the M(N) -term improves and the multiplier tends to log(N). In practice, at -moderate to large sizes, a 2NxN division is about 2 to 4 times slower -than an NxN multiplication. - - -File: gmp.info, Node: Block-Wise Barrett Division, Next: Exact Division, Prev: Divide and Conquer Division, Up: Division Algorithms - -15.2.4 Block-Wise Barrett Division ----------------------------------- - -For the largest divisions, a block-wise Barrett division algorithm is -used. Here, the divisor is inverted to a precision determined by the -relative size of the dividend and divisor. Blocks of quotient limbs are -then generated by multiplying blocks from the dividend by the inverse. - - Our block-wise algorithm computes a smaller inverse than in the plain -Barrett algorithm. For a 2n/n division, the inverse will be just -ceil(n/2) limbs. - - -File: gmp.info, Node: Exact Division, Next: Exact Remainder, Prev: Block-Wise Barrett Division, Up: Division Algorithms - -15.2.5 Exact Division ---------------------- - -A so-called exact division is when the dividend is known to be an exact -multiple of the divisor. Jebelean's exact division algorithm uses this -knowledge to make some significant optimizations (*note References::). - - The idea can be illustrated in decimal for example with 368154 -divided by 543. Because the low digit of the dividend is 4, the low -digit of the quotient must be 8. This is arrived at from 4*7 mod 10, -using the fact 7 is the modular inverse of 3 (the low digit of the -divisor), since 3*7 == 1 mod 10. So 8*543=4344 can be subtracted from -the dividend leaving 363810. Notice the low digit has become zero. - - The procedure is repeated at the second digit, with the next quotient -digit 7 (7 == 1*7 mod 10), subtracting 7*543=3801, leaving 325800. And -finally at the third digit with quotient digit 6 (8*7 mod 10), -subtracting 6*543=3258 leaving 0. So the quotient is 678. - - Notice however that the multiplies and subtractions don't need to -extend past the low three digits of the dividend, since that's enough to -determine the three quotient digits. For the last quotient digit no -subtraction is needed at all. On a 2NxN division like this one, only -about half the work of a normal basecase division is necessary. - - For an NxM exact division producing Q=N-M quotient limbs, the saving -over a normal basecase division is in two parts. Firstly, each of the Q -quotient limbs needs only one multiply, not a 2x1 divide and multiply. -Secondly, the crossproducts are reduced when Q>M to Q*M-M*(M+1)/2, or -when Q<=M to Q*(Q-1)/2. Notice the savings are complementary. If Q is -big then many divisions are saved, or if Q is small then the -crossproducts reduce to a small number. - - The modular inverse used is calculated efficiently by 'binvert_limb' -in 'gmp-impl.h'. This does four multiplies for a 32-bit limb, or six -for a 64-bit limb. 'tune/modlinv.c' has some alternate implementations -that might suit processors better at bit twiddling than multiplying. - - The sub-quadratic exact division described by Jebelean in "Exact -Division with Karatsuba Complexity" is not currently implemented. It -uses a rearrangement similar to the divide and conquer for normal -division (*note Divide and Conquer Division::), but operating from low -to high. A further possibility not currently implemented is -"Bidirectional Exact Integer Division" by Krandick and Jebelean which -forms quotient limbs from both the high and low ends of the dividend, -and can halve once more the number of crossproducts needed in a 2NxN -division. - - A special case exact division by 3 exists in 'mpn_divexact_by3', -supporting Toom-3 multiplication and 'mpq' canonicalizations. It forms -quotient digits with a multiply by the modular inverse of 3 (which is -'0xAA..AAB') and uses two comparisons to determine a borrow for the next -limb. The multiplications don't need to be on the dependent chain, as -long as the effect of the borrows is applied, which can help chips with -pipelined multipliers. - diff -Nru gmp-doc-6.2.1+ndfsg/doc/gmp.info-2 gmp-doc-6.3.0+ndfsg/doc/gmp.info-2 --- gmp-doc-6.2.1+ndfsg/doc/gmp.info-2 2020-11-16 20:09:45.000000000 +0000 +++ gmp-doc-6.3.0+ndfsg/doc/gmp.info-2 2023-08-13 20:21:18.000000000 +0000 @@ -1,7 +1,7 @@ This is gmp.info, produced by makeinfo version 6.7 from gmp.texi. This manual describes how to install and use the GNU multiple precision -arithmetic library, version 6.2.1. +arithmetic library, version 6.3.0. Copyright 1991, 1993-2016, 2018-2020 Free Software Foundation, Inc. @@ -18,6 +18,120 @@ END-INFO-DIR-ENTRY  +File: gmp.info, Node: Divide and Conquer Division, Next: Block-Wise Barrett Division, Prev: Basecase Division, Up: Division Algorithms + +15.2.3 Divide and Conquer Division +---------------------------------- + +For divisors larger than 'DC_DIV_QR_THRESHOLD', division is done by +dividing. Or to be precise by a recursive divide and conquer algorithm +based on work by Moenck and Borodin, Jebelean, and Burnikel and Ziegler +(*note References::). + + The algorithm consists essentially of recognising that a 2NxN +division can be done with the basecase division algorithm (*note +Basecase Division::), but using N/2 limbs as a base, not just a single +limb. This way the multiplications that arise are (N/2)x(N/2) and can +take advantage of Karatsuba and higher multiplication algorithms (*note +Multiplication Algorithms::). The two "digits" of the quotient are +formed by recursive Nx(N/2) divisions. + + If the (N/2)x(N/2) multiplies are done with a basecase multiplication +then the work is about the same as a basecase division, but with more +function call overheads and with some subtractions separated from the +multiplies. These overheads mean that it's only when N/2 is above +'MUL_TOOM22_THRESHOLD' that divide and conquer is of use. + + 'DC_DIV_QR_THRESHOLD' is based on the divisor size N, so it will be +somewhere above twice 'MUL_TOOM22_THRESHOLD', but how much above depends +on the CPU. An optimized 'mpn_mul_basecase' can lower +'DC_DIV_QR_THRESHOLD' a little by offering a ready-made advantage over +repeated 'mpn_submul_1' calls. + + Divide and conquer is asymptotically O(M(N)*log(N)) where M(N) is the +time for an NxN multiplication done with FFTs. The actual time is a sum +over multiplications of the recursed sizes, as can be seen near the end +of section 2.2 of Burnikel and Ziegler. For example, within the Toom-3 +range, divide and conquer is 2.63*M(N). With higher algorithms the M(N) +term improves and the multiplier tends to log(N). In practice, at +moderate to large sizes, a 2NxN division is about 2 to 4 times slower +than an NxN multiplication. + + +File: gmp.info, Node: Block-Wise Barrett Division, Next: Exact Division, Prev: Divide and Conquer Division, Up: Division Algorithms + +15.2.4 Block-Wise Barrett Division +---------------------------------- + +For the largest divisions, a block-wise Barrett division algorithm is +used. Here, the divisor is inverted to a precision determined by the +relative size of the dividend and divisor. Blocks of quotient limbs are +then generated by multiplying blocks from the dividend by the inverse. + + Our block-wise algorithm computes a smaller inverse than in the plain +Barrett algorithm. For a 2n/n division, the inverse will be just +ceil(n/2) limbs. + + +File: gmp.info, Node: Exact Division, Next: Exact Remainder, Prev: Block-Wise Barrett Division, Up: Division Algorithms + +15.2.5 Exact Division +--------------------- + +A so-called exact division is when the dividend is known to be an exact +multiple of the divisor. Jebelean's exact division algorithm uses this +knowledge to make some significant optimizations (*note References::). + + The idea can be illustrated in decimal for example with 368154 +divided by 543. Because the low digit of the dividend is 4, the low +digit of the quotient must be 8. This is arrived at from 4*7 mod 10, +using the fact 7 is the modular inverse of 3 (the low digit of the +divisor), since 3*7 == 1 mod 10. So 8*543=4344 can be subtracted from +the dividend leaving 363810. Notice the low digit has become zero. + + The procedure is repeated at the second digit, with the next quotient +digit 7 (7 == 1*7 mod 10), subtracting 7*543=3801, leaving 325800. And +finally at the third digit with quotient digit 6 (8*7 mod 10), +subtracting 6*543=3258 leaving 0. So the quotient is 678. + + Notice however that the multiplies and subtractions don't need to +extend past the low three digits of the dividend, since that's enough to +determine the three quotient digits. For the last quotient digit no +subtraction is needed at all. On a 2NxN division like this one, only +about half the work of a normal basecase division is necessary. + + For an NxM exact division producing Q=N-M quotient limbs, the saving +over a normal basecase division is in two parts. Firstly, each of the Q +quotient limbs needs only one multiply, not a 2x1 divide and multiply. +Secondly, the crossproducts are reduced when Q>M to Q*M-M*(M+1)/2, or +when Q<=M to Q*(Q-1)/2. Notice the savings are complementary. If Q is +big then many divisions are saved, or if Q is small then the +crossproducts reduce to a small number. + + The modular inverse used is calculated efficiently by 'binvert_limb' +in 'gmp-impl.h'. This does four multiplies for a 32-bit limb, or six +for a 64-bit limb. 'tune/modlinv.c' has some alternate implementations +that might suit processors better at bit twiddling than multiplying. + + The sub-quadratic exact division described by Jebelean in "Exact +Division with Karatsuba Complexity" is not currently implemented. It +uses a rearrangement similar to the divide and conquer for normal +division (*note Divide and Conquer Division::), but operating from low +to high. A further possibility not currently implemented is +"Bidirectional Exact Integer Division" by Krandick and Jebelean which +forms quotient limbs from both the high and low ends of the dividend, +and can halve once more the number of crossproducts needed in a 2NxN +division. + + A special case exact division by 3 exists in 'mpn_divexact_by3', +supporting Toom-3 multiplication and 'mpq' canonicalizations. It forms +quotient digits with a multiply by the modular inverse of 3 (which is +'0xAA..AAB') and uses two comparisons to determine a borrow for the next +limb. The multiplications don't need to be on the dependent chain, as +long as the effect of the borrows is applied, which can help chips with +pipelined multipliers. + + File: gmp.info, Node: Exact Remainder, Next: Small Quotient Division, Prev: Exact Division, Up: Division Algorithms 15.2.6 Exact Remainder @@ -148,7 +262,7 @@ iterations per bit. For optimum performance some attention needs to be paid to the way the factors of 2 are stripped from a. - Firstly it may be noted that in twos complement the number of low + Firstly it may be noted that in two's complement the number of low zero bits on a-b is the same as b-a, so counting or testing can begin on a-b without waiting for abs(a-b) to be determined. @@ -157,7 +271,7 @@ few low zeros, so an option is to strip one or two bits arithmetically then loop for more (as done for AMD K6). Or use a lookup table to get a count for several bits then loop for more (as done for AMD K7). An -alternative approach is to keep just one of a or b odd and iterate +alternative approach is to keep just one of a and b odd and iterate a,b = abs(a-b), min(a,b) a = a/2 if even @@ -209,11 +323,11 @@ for the two large numbers; the final quotient may sometimes be one off. - * It takes advantage of the fact the quotients are usually small. - The division operator is not used, since the corresponding + * It takes advantage of the fact that the quotients are usually + small. The division operator is not used, since the corresponding assembler instruction is very slow on most architectures. (This code could probably be improved further, it uses many branches that - are unfriendly to prediction). + are unfriendly to prediction.) * It switches from double-limb calculations to single-limb calculations half-way through, when the input numbers have been @@ -264,7 +378,7 @@ 'mpn_hgcd2', and applies the resulting matrix to the full numbers, the sub-quadratic GCD chops off the most significant third of the limbs (the proportion is a tuning parameter, and 1/3 seems to be more efficient -than, e.g, 1/2), calls 'mpn_hgcd', and applies the resulting matrix. +than, e.g., 1/2), calls 'mpn_hgcd', and applies the resulting matrix. Once the input numbers are reduced to size below 'GCD_DC_THRESHOLD', Lehmer's algorithm is used for the rest of the work. @@ -284,7 +398,7 @@ up to 'GCDEXT_DC_THRESHOLD'. Above this threshold, GCDEXT is implemented as a loop around HGCD, but with more book-keeping to keep track of the cofactors. This gives the same asymptotic running time as -for GCD and HGCD, O(M(N)*log(N)) +for GCD and HGCD, O(M(N)*log(N)). One difference to plain GCD is that while the inputs a and b are reduced as the algorithm proceeds, the cofactors x and y grow in size. @@ -314,7 +428,7 @@ 'mpz_legendre' and 'mpz_kronecker' are computed via the HGCD (Half GCD) function, as a generalization to Lehmer's algorithm. - Most GCD algorithms reduce a and b by repeatatily computing the + Most GCD algorithms reduce a and b by repeatedly computing the quotient q = floor(a/b) and iteratively replacing a, b = b, a - q * b @@ -339,7 +453,7 @@ fast bit twiddling which avoids conditional jumps. The final result is calculated after verifying the inputs are coprime -(GCD = 1) by raising (-1)^e +(GCD = 1) by raising (-1)^e. Much of the HGCD code is shared directly with the HGCD implementations, such as the 2x2 matrix calculation, *Note Lehmer's @@ -725,10 +839,10 @@ 23! = (23.21.19.17.15.13.11.9.7.5.3)(11.9.7.5.3)(5.3)2^{19} Current code collects all the factors in a single list, with a loop -and no recursion, and compute the product, with no special care for +and no recursion, and computes the product, with no special care for repeated chunks. - When n is larger, computation pass trough prime sieving. An helper + When n is larger, computations pass through prime sieving. A helper function is used, as suggested by Peter Luschny: n @@ -1082,10 +1196,10 @@ The final loop control cost can be amortised by processing several limbs in each iteration (*note Assembly Loop Unrolling::). This at -least ensures loop control isn't a big fraction the work done. +least ensures loop control isn't a big fraction of the work done. Memory throughput is always a limit. If perhaps only one load or one -store can be done per cycle then 3 cycles/limb will the top speed for +store can be done per cycle then 3 cycles/limb will be the top speed for "binary" operations like 'mpn_add_n', and any code achieving that is optimal. @@ -1238,7 +1352,7 @@ If the latency of some instruction is greater than the loop time then it will be necessary to unroll, so one register has a result ready to -use while another (or multiple others) are still in progress. (*note +use while another (or multiple others) are still in progress (*note Assembly Loop Unrolling::).  @@ -1404,12 +1518,12 @@ See *note Integer Special Functions:: for details. The various bitwise logical functions like 'mpz_and' behave as if -negative values were twos complement. But sign and magnitude is always +negative values were two's complement. But sign and magnitude is always used internally, and necessary adjustments are made during the calculations. Sometimes this isn't pretty, but sign and magnitude are best for other routines. - Some internal temporary variables are setup with 'MPZ_TMP_INIT' and + Some internal temporary variables are set up with 'MPZ_TMP_INIT' and these have '_mp_d' space obtained from 'TMP_ALLOC' rather than the memory allocation functions. Care is taken to ensure that these are big enough that no reallocation is necessary (since it would have @@ -1605,7 +1719,7 @@ 10 limbs allocated. Reading back with 'mpf_get_prec' will take '_mp_prec' subtract 1 limb and multiply by 32, giving 256 bits. - Strictly speaking, the fact the high limb has at least one bit + Strictly speaking, the fact that the high limb has at least one bit means that a float with, say, 3 limbs of 32-bits each will be holding at least 65 bits, but for the purposes of 'mpf_t' it's considered simply to be 64 bits, a nice multiple of the limb size. @@ -1623,9 +1737,9 @@ +------+------------------------+ The size is 4 bytes written most significant byte first, being the -number of subsequent data bytes, or the twos complement negative of that -when a negative integer is represented. The data bytes are the absolute -value of the integer, written most significant byte first. +number of subsequent data bytes, or the two's complement negative of +that when a negative integer is represented. The data bytes are the +absolute value of the integer, written most significant byte first. The most significant data byte is always non-zero, so the output is the same on all systems, irrespective of limb size. @@ -1741,7 +1855,7 @@ *********************** Torbjörn Granlund wrote the original GMP library and is still the main -developer. Code not explicitly attributed to others, was contributed by +developer. Code not explicitly attributed to others was contributed by Torbjörn. Several other individuals and organizations have contributed GMP. Here is a list in chronological order on first contribution: @@ -1788,7 +1902,7 @@ highly optimized Karatsuba and 3-way Toom multiplication functions for GMP 3, and contributed the ARM assembly code. - Torsten Ekedahl of the Mathematical department of Stockholm + Torsten Ekedahl of the Mathematical Department of Stockholm University provided significant inspiration during several phases of the GMP development. His mathematical expertise helped improve several algorithms. @@ -1815,7 +1929,7 @@ Pedro Gimeno implemented the Mersenne Twister and made other random number improvements. - Niels Möller wrote the sub-quadratic GCD, extended GCD and jacobi + Niels Möller wrote the sub-quadratic GCD, extended GCD and Jacobi code, the quadratic Hensel division code, and (with Torbjörn) the new divide and conquer division code for GMP 4.3. Niels also helped implement the new Toom multiply code for GMP 4.3 and implemented helper @@ -1864,9 +1978,9 @@ have contributed to GMP but are not listed above, please tell about the omission!) - The development of floating point functions of GNU MP 2, were -supported in part by the ESPRIT-BRA (Basic Research Activities) 6846 -project POSSO (POlynomial System SOlving). + The development of floating point functions of GNU MP 2 was supported +in part by the ESPRIT-BRA (Basic Research Activities) 6846 project POSSO +(POlynomial System SOlving). The development of GMP 2, 3, and 4.0 was supported in part by the IDA Center for Computing Sciences. @@ -2547,7 +2661,7 @@ * Assembly code organisation: Assembly Code Organisation. (line 6) * Assembly coding: Assembly Coding. (line 6) -* Assembly floating Point: Assembly Floating Point. +* Assembly floating point: Assembly Floating Point. (line 6) * Assembly loop unrolling: Assembly Loop Unrolling. (line 6) @@ -2572,7 +2686,7 @@ * Binomial coefficient algorithm: Binomial Coefficients Algorithm. (line 6) * Binomial coefficient functions: Number Theoretic Functions. - (line 128) + (line 137) * Binutils strip: Known Build Problems. (line 28) * Bit manipulation functions: Integer Logic and Bit Fiddling. @@ -2691,12 +2805,12 @@ * Expression parsing demo <2>: Demonstration Programs. (line 19) * Extended GCD: Number Theoretic Functions. - (line 47) + (line 56) * Factor removal functions: Number Theoretic Functions. - (line 108) + (line 117) * Factorial algorithm: Factorial Algorithm. (line 6) * Factorial functions: Number Theoretic Functions. - (line 116) + (line 125) * Factorization demo: Demonstration Programs. (line 22) * Fast Fourier Transform: FFT Multiplication. (line 6) @@ -2706,7 +2820,7 @@ * Fibonacci number algorithm: Fibonacci Numbers Algorithm. (line 6) * Fibonacci sequence functions: Number Theoretic Functions. - (line 136) + (line 145) * Float arithmetic functions: Float Arithmetic. (line 6) * Float assignment functions: Assigning Floats. (line 6) * Float assignment functions <1>: Simultaneous Float Init & Assign. @@ -2751,9 +2865,9 @@ * GCD algorithms: Greatest Common Divisor Algorithms. (line 6) * GCD extended: Number Theoretic Functions. - (line 47) + (line 56) * GCD functions: Number Theoretic Functions. - (line 30) + (line 39) * GDB: Debugging. (line 53) * Generic C: Build Options. (line 151) * GMP Perl module: Demonstration Programs. @@ -2773,7 +2887,7 @@ * Greatest common divisor algorithms: Greatest Common Divisor Algorithms. (line 6) * Greatest common divisor functions: Number Theoretic Functions. - (line 30) + (line 39) * Hardware floating point mode: Notes for Particular Systems. (line 34) * Headers: Headers and Libraries. @@ -2856,7 +2970,7 @@ * Internals: Internals. (line 6) * Introduction: Introduction to GMP. (line 6) * Inverse modulo functions: Number Theoretic Functions. - (line 74) + (line 83) * IRIX: ABI and ISA. (line 139) * IRIX <1>: Known Build Problems. (line 38) @@ -2864,29 +2978,29 @@ * istream input: C++ Formatted Input. (line 6) * Jacobi symbol algorithm: Jacobi Symbol. (line 6) * Jacobi symbol functions: Number Theoretic Functions. - (line 83) + (line 92) * Karatsuba multiplication: Karatsuba Multiplication. (line 6) * Karatsuba square root algorithm: Square Root Algorithm. (line 6) * Kronecker symbol functions: Number Theoretic Functions. - (line 95) + (line 104) * Language bindings: Language Bindings. (line 6) * Latest version of GMP: Introduction to GMP. (line 37) * LCM functions: Number Theoretic Functions. - (line 68) + (line 77) * Least common multiple functions: Number Theoretic Functions. - (line 68) + (line 77) * Legendre symbol functions: Number Theoretic Functions. - (line 86) + (line 95) * libgmp: Headers and Libraries. - (line 22) + (line 24) * libgmpxx: Headers and Libraries. - (line 27) + (line 29) * Libraries: Headers and Libraries. - (line 22) + (line 24) * Libtool: Headers and Libraries. - (line 33) + (line 36) * Libtool versioning: Notes for Package Builds. (line 9) * License conditions: Copying. (line 6) @@ -2901,7 +3015,7 @@ * Linear congruential random numbers <1>: Random State Initialization. (line 32) * Linking: Headers and Libraries. - (line 22) + (line 24) * Logical functions: Integer Logic and Bit Fiddling. (line 6) * Low-level functions: Low-level Functions. (line 6) @@ -2909,7 +3023,7 @@ * Lucas number algorithm: Lucas Numbers Algorithm. (line 6) * Lucas number functions: Number Theoretic Functions. - (line 147) + (line 156) * MacOS X: Known Build Problems. (line 51) * Mailing lists: Introduction to GMP. (line 44) @@ -2931,7 +3045,7 @@ * MMX: Notes for Particular Systems. (line 156) * Modular inverse functions: Number Theoretic Functions. - (line 74) + (line 83) * Most significant bit: Miscellaneous Integer Functions. (line 34) * MPN_PATH: Build Options. (line 321) @@ -3000,6 +3114,8 @@ (line 28) * Perl module: Demonstration Programs. (line 28) +* Pointer types: Nomenclature and Types. + (line 55) * Postscript: Build Options. (line 336) * Power/PowerPC: Notes for Particular Systems. (line 115) @@ -3015,12 +3131,14 @@ * Precision of hardware floating point: Notes for Particular Systems. (line 34) * Prefix: Build Options. (line 32) +* Previous prime function: Number Theoretic Functions. + (line 26) * Prime testing algorithms: Prime Testing Algorithm. (line 6) * Prime testing functions: Number Theoretic Functions. (line 7) * Primorial functions: Number Theoretic Functions. - (line 121) + (line 130) * printf formatted output: Formatted Output. (line 6) * Probable prime testing functions: Number Theoretic Functions. (line 7) @@ -3066,7 +3184,7 @@ * Reentrancy: Reentrancy. (line 6) * References: References. (line 5) * Remove factor functions: Number Theoretic Functions. - (line 108) + (line 117) * Reporting bugs: Reporting Bugs. (line 6) * Root extraction algorithm: Nth Root Algorithm. (line 6) * Root extraction algorithms: Root Extraction Algorithms. @@ -3120,9 +3238,9 @@ * Stack overflow <1>: Debugging. (line 7) * Static linking: Efficiency. (line 14) * stdarg.h: Headers and Libraries. - (line 17) + (line 19) * stdio.h: Headers and Libraries. - (line 11) + (line 13) * Stripped libraries: Known Build Problems. (line 28) * Sun: ABI and ISA. (line 204) @@ -3280,6 +3398,10 @@ (line 6) * gmp_randseed_ui: Random State Seeding. (line 8) +* gmp_randstate_ptr: Nomenclature and Types. + (line 55) +* gmp_randstate_srcptr: Nomenclature and Types. + (line 55) * gmp_randstate_t: Nomenclature and Types. (line 46) * GMP_RAND_ALG_DEFAULT: Random State Initialization. @@ -3433,6 +3555,8 @@ * mpf_neg: Float Arithmetic. (line 43) * mpf_out_str: I/O of Floats. (line 17) * mpf_pow_ui: Float Arithmetic. (line 39) +* mpf_ptr: Nomenclature and Types. + (line 55) * mpf_random2: Miscellaneous Float Functions. (line 35) * mpf_reldiff: Float Comparison. (line 28) @@ -3449,6 +3573,8 @@ * mpf_sgn: Float Comparison. (line 33) * mpf_sqrt: Float Arithmetic. (line 35) * mpf_sqrt_ui: Float Arithmetic. (line 36) +* mpf_srcptr: Nomenclature and Types. + (line 55) * mpf_sub: Float Arithmetic. (line 11) * mpf_sub_ui: Float Arithmetic. (line 14) * mpf_swap: Assigning Floats. (line 50) @@ -3584,9 +3710,9 @@ * mpq_get_d: Rational Conversions. (line 6) * mpq_get_den: Applying Integer Functions. - (line 22) + (line 24) * mpq_get_num: Applying Integer Functions. - (line 21) + (line 23) * mpq_get_str: Rational Conversions. (line 21) * mpq_init: Initializing Rationals. @@ -3601,16 +3727,18 @@ * mpq_numref: Applying Integer Functions. (line 15) * mpq_out_str: I/O of Rationals. (line 17) +* mpq_ptr: Nomenclature and Types. + (line 55) * mpq_set: Initializing Rationals. (line 23) * mpq_set_d: Rational Conversions. (line 16) * mpq_set_den: Applying Integer Functions. - (line 24) + (line 26) * mpq_set_f: Rational Conversions. (line 17) * mpq_set_num: Applying Integer Functions. - (line 23) + (line 25) * mpq_set_si: Initializing Rationals. (line 29) * mpq_set_str: Initializing Rationals. @@ -3620,13 +3748,15 @@ * mpq_set_z: Initializing Rationals. (line 24) * mpq_sgn: Comparing Rationals. (line 27) +* mpq_srcptr: Nomenclature and Types. + (line 55) * mpq_sub: Rational Arithmetic. (line 10) * mpq_swap: Initializing Rationals. (line 54) * mpq_t: Nomenclature and Types. (line 16) * mpz_2fac_ui: Number Theoretic Functions. - (line 113) + (line 122) * mpz_abs: Integer Arithmetic. (line 44) * mpz_add: Integer Arithmetic. (line 6) * mpz_addmul: Integer Arithmetic. (line 24) @@ -3637,9 +3767,9 @@ * mpz_array_init: Integer Special Functions. (line 9) * mpz_bin_ui: Number Theoretic Functions. - (line 124) + (line 133) * mpz_bin_uiui: Number Theoretic Functions. - (line 126) + (line 135) * mpz_cdiv_q: Integer Division. (line 12) * mpz_cdiv_qr: Integer Division. (line 14) * mpz_cdiv_qr_ui: Integer Division. (line 21) @@ -3723,7 +3853,7 @@ * mpz_export: Integer Import and Export. (line 43) * mpz_fac_ui: Number Theoretic Functions. - (line 112) + (line 121) * mpz_fdiv_q: Integer Division. (line 33) * mpz_fdiv_qr: Integer Division. (line 35) * mpz_fdiv_qr_ui: Integer Division. (line 42) @@ -3734,9 +3864,9 @@ * mpz_fdiv_r_ui: Integer Division. (line 40) * mpz_fdiv_ui: Integer Division. (line 44) * mpz_fib2_ui: Number Theoretic Functions. - (line 134) + (line 143) * mpz_fib_ui: Number Theoretic Functions. - (line 133) + (line 142) * mpz_fits_sint_p: Miscellaneous Integer Functions. (line 9) * mpz_fits_slong_p: Miscellaneous Integer Functions. @@ -3750,11 +3880,11 @@ * mpz_fits_ushort_p: Miscellaneous Integer Functions. (line 10) * mpz_gcd: Number Theoretic Functions. - (line 29) + (line 38) * mpz_gcdext: Number Theoretic Functions. - (line 45) + (line 54) * mpz_gcd_ui: Number Theoretic Functions. - (line 35) + (line 44) * mpz_getlimbn: Integer Special Functions. (line 22) * mpz_get_d: Converting Integers. (line 26) @@ -3785,23 +3915,23 @@ * mpz_inp_raw: I/O of Integers. (line 61) * mpz_inp_str: I/O of Integers. (line 30) * mpz_invert: Number Theoretic Functions. - (line 72) + (line 81) * mpz_ior: Integer Logic and Bit Fiddling. (line 13) * mpz_jacobi: Number Theoretic Functions. - (line 82) + (line 91) * mpz_kronecker: Number Theoretic Functions. - (line 90) + (line 99) * mpz_kronecker_si: Number Theoretic Functions. - (line 91) + (line 100) * mpz_kronecker_ui: Number Theoretic Functions. - (line 92) + (line 101) * mpz_lcm: Number Theoretic Functions. - (line 65) + (line 74) * mpz_lcm_ui: Number Theoretic Functions. - (line 66) + (line 75) * mpz_legendre: Number Theoretic Functions. - (line 85) + (line 94) * mpz_limbs_finish: Integer Special Functions. (line 47) * mpz_limbs_modify: Integer Special Functions. @@ -3811,11 +3941,11 @@ * mpz_limbs_write: Integer Special Functions. (line 39) * mpz_lucnum2_ui: Number Theoretic Functions. - (line 145) + (line 154) * mpz_lucnum_ui: Number Theoretic Functions. - (line 144) + (line 153) * mpz_mfac_uiui: Number Theoretic Functions. - (line 114) + (line 123) * mpz_mod: Integer Division. (line 112) * mpz_mod_ui: Integer Division. (line 113) * mpz_mul: Integer Arithmetic. (line 18) @@ -3841,10 +3971,14 @@ (line 8) * mpz_pow_ui: Integer Exponentiation. (line 29) +* mpz_prevprime: Number Theoretic Functions. + (line 25) * mpz_primorial_ui: Number Theoretic Functions. - (line 120) + (line 129) * mpz_probab_prime_p: Number Theoretic Functions. (line 6) +* mpz_ptr: Nomenclature and Types. + (line 55) * mpz_random: Integer Random Numbers. (line 41) * mpz_random2: Integer Random Numbers. @@ -3852,7 +3986,7 @@ * mpz_realloc2: Initializing Integers. (line 56) * mpz_remove: Number Theoretic Functions. - (line 106) + (line 115) * mpz_roinit_n: Integer Special Functions. (line 67) * MPZ_ROINIT_N: Integer Special Functions. @@ -3880,9 +4014,11 @@ * mpz_sizeinbase: Miscellaneous Integer Functions. (line 22) * mpz_si_kronecker: Number Theoretic Functions. - (line 93) + (line 102) * mpz_sqrt: Integer Roots. (line 17) * mpz_sqrtrem: Integer Roots. (line 20) +* mpz_srcptr: Nomenclature and Types. + (line 55) * mpz_sub: Integer Arithmetic. (line 11) * mpz_submul: Integer Arithmetic. (line 30) * mpz_submul_ui: Integer Arithmetic. (line 32) @@ -3902,7 +4038,7 @@ * mpz_tstbit: Integer Logic and Bit Fiddling. (line 60) * mpz_ui_kronecker: Number Theoretic Functions. - (line 94) + (line 103) * mpz_ui_pow_ui: Integer Exponentiation. (line 31) * mpz_ui_sub: Integer Arithmetic. (line 14) diff -Nru gmp-doc-6.2.1+ndfsg/doc/gmp.texi gmp-doc-6.3.0+ndfsg/doc/gmp.texi --- gmp-doc-6.2.1+ndfsg/doc/gmp.texi 2020-11-16 20:09:45.000000000 +0000 +++ gmp-doc-6.3.0+ndfsg/doc/gmp.texi 2023-08-13 20:21:18.000000000 +0000 @@ -25,7 +25,7 @@ @ref{GNU Free Documentation License}. @end copying @c Note the @ref above must be on one line, a line break in an @ref within -@c @copying will bomb in recent texinfo.tex (eg. 2004-04-07.08 which comes +@c @copying will bomb in recent texinfo.tex (e.g. 2004-04-07.08 which comes @c with texinfo 4.7), with messages about missing @endcsname. @@ -59,7 +59,7 @@ @c HTML: @c @c Nothing special is done for links to external manuals, they just come out -@c in the usual makeinfo style, eg. "../libc/Locales.html". If you have +@c in the usual makeinfo style, e.g. "../libc/Locales.html". If you have @c local copies of such manuals then this is a good thing, if not then you @c may want to search-and-replace to some online source. @c @@ -410,7 +410,7 @@ @c on printing a particular section, GMPreftop gives just the title. @c @c The texinfo manual recommends putting a likely section name in references -@c like this, eg. "Introduction", but it seems better to just give the title. +@c like this, e.g. "Introduction", but it seems better to just give the title. @c @iftex @macro GMPreftop{info,title} @@ -470,7 +470,7 @@ the additional option of applying later versions of these licenses. (The reason for this dual licensing is to make it possible to use the library with programs which are licensed under GPL version 2, but which for historical or -other reasons do not allow use under later versions of the GPL). +other reasons do not allow use under later versions of the GPL.) Programs which are not part of the library itself, such as demonstration programs and the GMP testsuite, are licensed under the terms of the GNU @@ -502,13 +502,13 @@ @cindex CPU types ARM Cortex-A9, Cortex-A15, and generic ARM, DEC Alpha 21064, 21164, and 21264, -AMD K8 and K10 (sold under many brands, e.g. Athlon64, Phenom, Opteron) +AMD K8 and K10 (sold under many brands, e.g. Athlon64, Phenom, Opteron), Bulldozer, and Bobcat, Intel Pentium, Pentium Pro/II/III, Pentium 4, Core2, Nehalem, Sandy bridge, Haswell, generic x86, Intel IA-64, Motorola/IBM PowerPC 32 and 64 such as POWER970, POWER5, POWER6, and POWER7, MIPS 32-bit and 64-bit, -SPARC 32-bit ad 64-bit with special support for all UltraSPARC models. +SPARC 32-bit and 64-bit with special support for all UltraSPARC models. There is also assembly code for many obsolete CPUs. @@ -695,7 +695,7 @@ @command{ranlib}. This makes it possible for a set of cross-compiling tools to co-exist with native tools. The prefix is the argument to @samp{--host}, and this can be an alias, such as @samp{m68k-linux}. But note that tools -don't have to be setup this way, it's enough to just have a @env{PATH} with a +don't have to be set up this way, it's enough to just have a @env{PATH} with a suitable cross-compiling @command{cc} etc. Compiling for a different CPU in the same family as the build system is a form @@ -745,7 +745,7 @@ @nisamp{alphapca57}, @nisamp{alphaev6}, @nisamp{alphaev67}, -@nisamp{alphaev68} +@nisamp{alphaev68}, @nisamp{alphaev7} @item @@ -1061,7 +1061,7 @@ @item @option{MPN_PATH} @cindex @code{MPN_PATH} Various assembly versions of each mpn subroutines are provided. For a given -CPU, a search is made though a path to choose a version of each. For example +CPU, a search is made through a path to choose a version of each. For example @samp{sparcv8} has @example @@ -1138,7 +1138,7 @@ installing library or header files built for a particular ABI@. This will probably only matter when installing multiple builds of GMP, and it might be as simple as configuring with a special @samp{libdir}, or it might require -more than that. Note that builds for different ABIs need to done separately, +more than that. Note that builds for different ABIs need to be done separately, with a fresh @command{./configure} and @command{make} each. @sp 1 @@ -1207,7 +1207,7 @@ cc +DA2.0 +e @end example -Note that current versions of GCC (eg.@: 3.2) don't generate 64-bit +Note that current versions of GCC (e.g.@: 3.2) don't generate 64-bit instructions for @code{long long} operations and so may be slower than for 2.0w. (The GMP assembly code is the same though.) @@ -1269,7 +1269,7 @@ @item @samp{ABI=o32} The o32 ABI is 32-bit pointers and integers, and no 64-bit operations. GMP will be slower than in n32 or 64, this option only exists to support old -compilers, eg.@: GCC 2.7.2. Applications can be compiled with no special +compilers, e.g.@: GCC 2.7.2. Applications can be compiled with no special flags on an old compiler, or on a newer compiler with @example @@ -1715,7 +1715,7 @@ @file{config.log}. Use @command{bash} 2.04 or higher. @samp{make all} was found to run out of memory during the final -@file{libgmp.la} link on one system tested, despite having 64Mb available. +@file{libgmp.la} link on one system tested, despite having 64MiB available. Running @samp{make libgmp.la} directly helped, perhaps recursing into the various subdirectories uses up memory. @@ -1806,7 +1806,7 @@ In particular for long-running GMP applications, and applications demanding extremely large numbers, building and running the @code{tuneup} program in the -@file{tune} subdirectory, can be important. For example, +@file{tune} subdirectory can be important. For example, @example cd tune @@ -1860,7 +1860,9 @@ @cindex Include files @cindex @code{#include} All declarations needed to use GMP are collected in the include file -@file{gmp.h}. It is designed to work with both C and C++ compilers. +@file{gmp.h}, except for the @ref{C++ Class Interface} which comes with its +own separate header @file{gmpxx.h}. @file{gmp.h} is designed to work with +both C and C++ compilers. @example #include @@ -1868,7 +1870,7 @@ @cindex @code{stdio.h} Note however that prototypes for GMP functions with @code{FILE *} parameters -are only provided if @code{} is included too. +are only provided if @code{} is included before. @example #include @@ -1892,9 +1894,10 @@ @end example @cindex @code{libgmpxx} -GMP C++ functions are in a separate @file{libgmpxx} library. This is built -and installed if C++ support has been enabled (@pxref{Build Options}). For -example, +GMP C++ functions are in a separate @file{libgmpxx} library, including the +@ref{C++ Class Interface} but also @ref{C++ Formatted Output} for regular +GMP types. This is built and installed if C++ support has been enabled +(@pxref{Build Options}). For example, @example g++ mycxxprog.cc -lgmpxx -lgmp @@ -1982,6 +1985,60 @@ Also, in general @code{mp_bitcnt_t} is used for bit counts and ranges, and @code{size_t} is used for byte or character counts. +@sp 1 + +@cindex Pointer types +@tindex @code{mpz_ptr} +@tindex @code{mpz_srcptr} +@tindex @code{mpq_ptr} +@tindex @code{mpq_srcptr} +@tindex @code{mpf_ptr} +@tindex @code{mpf_srcptr} +@tindex @code{gmp_randstate_ptr} +@tindex @code{gmp_randstate_srcptr} +Internally, GMP data types such as @code{mpz_t} are defined as one-element +arrays, whose element type is part of the GMP internals (@pxref{Internals}). + +When an array is used as a function argument in C, it is not passed by value, +instead its value is a pointer to the first element. In C jargon, this is +sometimes referred to as the array "decaying" to a pointer. For GMP types like +@code{mpz_t}, that means that the function called gets a pointer to the +caller's @code{mpz_t} value, which is why no explicit @code{&} operator is +needed when passing output arguments (@pxref{Parameter Conventions}). + +GMP defines names for these pointer types, e.g., @code{mpz_ptr} corresponding +to @code{mpz_t}, and @code{mpz_srcptr} corresponding to @code{const mpz_t}. +Most functions don't need to use these pointer types directly; it works fine to +declare a function using the @code{mpz_t} or @code{const mpz_t} as the argument +types, the same "pointer decay" happens in the background regardless. + +Occasionally, it is useful to manipulate pointers directly, e.g., to +conditionally swap @emph{references} to a function's inputs without changing +the @emph{values} as seen by the caller, or returning a pointer to an +@code{mpz_t} which is part of a larger structure. For these cases, the pointer +types are necessary. And a @code{mpz_ptr} can be passed as argument to any GMP +function declared to take an @code{mpz_t} argument. + +Their definition is equivalent to the following code, which is given for +illustratory purposes only: + +@example + typedef foo_internal foo_t[1]; + typedef foo_internal * foo_ptr; + typedef const foo_internal * foo_srcptr; +@end example + +The following pointer types are defined by GMP: +@itemize +@item @code{mpz_ptr} for pointers to the element type in @code{mpz_t} +@item @code{mpz_srcptr} for @code{const} pointers to the element type in @code{mpz_t} +@item @code{mpq_ptr} for pointers to the element type in @code{mpq_t} +@item @code{mpq_srcptr} for @code{const} pointers to the element type in @code{mpq_t} +@item @code{mpf_ptr} for pointers to the element type in @code{mpf_t} +@item @code{mpf_srcptr} for @code{const} pointers to the element type in @code{mpf_t} +@item @code{gmp_randstate_ptr} for pointers to the element type in @code{gmp_randstate_t} +@item @code{gmp_randstate_srcptr} for @code{const} pointers to the element type in @code{gmp_randstate_t} +@end itemize @node Function Classes, Variable Conventions, Nomenclature and Types, GMP Basics @section Function Classes @@ -2005,7 +2062,7 @@ @item Functions for floating-point arithmetic, with names beginning with @code{mpf_}. The associated type is @code{mpf_t}. There are about 70 -functions is this class. (@pxref{Floating-point Functions}) +functions in this class. (@pxref{Floating-point Functions}) @item Fast low-level functions that operate on natural numbers. These are used by @@ -2071,7 +2128,9 @@ GMP types like @code{mpz_t} are implemented as one-element arrays of certain structures. Declaring a variable creates an object with the fields GMP needs, -but variables are normally manipulated by using the pointer to the object. For +but variables are normally manipulated by using the pointer to the +object. The appropriate pointer types (@ref{Nomenclature and Types}) may +be used to explicitly manipulate the pointer. For both behavior and efficiency reasons, it is discouraged to make copies of the GMP object itself (either directly or via aggregate objects containing such GMP objects). If copies are done, all of them must be used read-only; using a copy @@ -2129,6 +2188,13 @@ Since GMP types are implemented as one-element arrays, using a GMP variable as a parameter passes a pointer to the object. Hence the call-by-reference. +A more explicit (and equivalent) prototype for our function @code{foo} +could be: + +@example +void foo (mpz_ptr result, mpz_srcptr param, unsigned long n); +@end example + @need 1000 @@ -2380,7 +2446,7 @@ expression evaluation within the main GMP library. Going beyond something minimal quickly leads to matters like user-defined functions, looping, fixnums for control variables, etc, which are considered outside the scope of GMP -(much closer to language interpreters or compilers, @xref{Language Bindings}.) +(much closer to language interpreters or compilers, @xref{Language Bindings}). Something simple for program input convenience may yet be a possibility, a combination of the @file{expr} demo and the @file{pexpr} tree back-end perhaps. But for now the above evaluators are offered as illustrations. @@ -2442,7 +2508,7 @@ The @code{ui} functions and the small number of @code{si} functions exist for convenience and should be used where applicable. But if for example an @code{mpz_t} contains a value that fits in an @code{unsigned long} there's no -need extract it and call a @code{ui} function, just use the regular @code{mpz} +need to extract it and call a @code{ui} function, just use the regular @code{mpz} function. @item In-Place Operations @@ -2490,7 +2556,7 @@ However when testing divisibility by several small integers, it's best to take a remainder modulo their product, to save multi-precision operations. For -instance to test whether a number is divisible by any of 23, 29 or 31 take a +instance to test whether a number is divisible by 23, 29 or 31 take a remainder modulo @math{23@times{}29@times{}31 = 20677} and then test that. The division functions like @code{mpz_tdiv_q_ui} which give a quotient as well @@ -2903,9 +2969,10 @@ Before you report a bug, check it's not already addressed in @ref{Known Build Problems}, or perhaps @ref{Notes for Particular Systems}. You may also want -to check @uref{https://gmplib.org/} for patches for this release. +to check @uref{https://gmplib.org/} for patches for this release, or try a +recent snapshot from @uref{https://gmplib.org/download/snapshot/}. -Please include the following in any report, +Please include the following in any report: @itemize @bullet @item @@ -3099,8 +3166,8 @@ @code{0B} for binary, @code{0} for octal, or decimal otherwise. For bases up to 36, case is ignored; upper-case and lower-case letters have -the same value. For bases 37 to 62, upper-case letter represent the usual -10..35 while lower-case letter represent 36..61. +the same value. For bases 37 to 62, upper-case letters represent the usual +10..35 while lower-case letters represent 36..61. This function returns 0 if the entire string is a valid number in base @var{base}. Otherwise it returns @minus{}1. @@ -3300,7 +3367,7 @@ Division is undefined if the divisor is zero. Passing a zero divisor to the division or modulo functions (including the modular powering functions -@code{mpz_powm} and @code{mpz_powm_ui}), will cause an intentional division by +@code{mpz_powm} and @code{mpz_powm_ui}) will cause an intentional division by zero. This lets a program handle arithmetic exceptions in these functions the same way as for normal C @code{int} arithmetic. @@ -3387,7 +3454,7 @@ For positive @var{n} both @code{mpz_fdiv_q_2exp} and @code{mpz_tdiv_q_2exp} are simple bitwise right shifts. For negative @var{n}, @code{mpz_fdiv_q_2exp} -is effectively an arithmetic right shift treating @var{n} as twos complement +is effectively an arithmetic right shift treating @var{n} as two's complement the same as the bitwise logical functions do, whereas @code{mpz_tdiv_q_2exp} effectively treats @var{n} as sign and magnitude. @end deftypefun @@ -3563,8 +3630,19 @@ @deftypefun void mpz_nextprime (mpz_t @var{rop}, const mpz_t @var{op}) @cindex Next prime function Set @var{rop} to the next prime greater than @var{op}. +@end deftypefun + +@deftypefun int mpz_prevprime (mpz_t @var{rop}, const mpz_t @var{op}) +@cindex Previous prime function +Set @var{rop} to the greatest prime less than @var{op}. + +If a previous prime doesn't exist (i.e. @var{op} < 3), rop is unchanged and +0 is returned. -This function uses a probabilistic algorithm to identify primes. For +Return 1 if @var{rop} is a probably prime, and 2 if @var{rop} is definitely +prime. + +These functions use a probabilistic algorithm to identify primes. For practical purposes it's adequate, the chance of a composite passing will be extremely small. @end deftypefun @@ -3718,7 +3796,7 @@ @deftypefun void mpz_fib_ui (mpz_t @var{fn}, unsigned long int @var{n}) @deftypefunx void mpz_fib2_ui (mpz_t @var{fn}, mpz_t @var{fnsub1}, unsigned long int @var{n}) @cindex Fibonacci sequence functions -@code{mpz_fib_ui} sets @var{fn} to to @m{F_n,F[n]}, the @var{n}'th Fibonacci +@code{mpz_fib_ui} sets @var{fn} to @m{F_n,F[n]}, the @var{n}th Fibonacci number. @code{mpz_fib2_ui} sets @var{fn} to @m{F_n,F[n]}, and @var{fnsub1} to @m{F_{n-1},F[n-1]}. @@ -3731,7 +3809,7 @@ @deftypefun void mpz_lucnum_ui (mpz_t @var{ln}, unsigned long int @var{n}) @deftypefunx void mpz_lucnum2_ui (mpz_t @var{ln}, mpz_t @var{lnsub1}, unsigned long int @var{n}) @cindex Lucas number functions -@code{mpz_lucnum_ui} sets @var{ln} to to @m{L_n,L[n]}, the @var{n}'th Lucas +@code{mpz_lucnum_ui} sets @var{ln} to @m{L_n,L[n]}, the @var{n}th Lucas number. @code{mpz_lucnum2_ui} sets @var{ln} to @m{L_n,L[n]}, and @var{lnsub1} to @m{L_{n-1},L[n-1]}. @@ -3797,7 +3875,7 @@ @cindex Integer logical functions @cindex Integer bit manipulation functions -These functions behave as if twos complement arithmetic were used (although +These functions behave as if two's complement arithmetic were used (although sign-magnitude is the actual implementation). The least significant bit is number 0. @@ -3864,6 +3942,9 @@ Test bit @var{bit_index} in @var{op} and return 0 or 1 accordingly. @end deftypefun +Shifting is also possible using multiplication (@ref{Integer Arithmetic}) and +division (@ref{Integer Division}), in particular the @code{2exp} functions. + @node I/O of Integers, Integer Random Numbers, Integer Logic and Bit Fiddling, Integer Functions @comment node-name, next, previous, up @section Input and Output Functions @@ -3905,8 +3986,8 @@ @code{0B} for binary, @code{0} for octal, or decimal otherwise. For bases up to 36, case is ignored; upper-case and lower-case letters have -the same value. For bases 37 to 62, upper-case letter represent the usual -10..35 while lower-case letter represent 36..61. +the same value. For bases 37 to 62, upper-case letters represent the usual +10..35 while lower-case letters represent 36..61. Return the number of bytes read, or if an error occurred, return 0. @end deftypefun @@ -3943,7 +4024,7 @@ @cindex Integer random number functions @cindex Random number functions -The random number functions of GMP come in two groups; older function +The random number functions of GMP come in two groups; older functions that rely on a global state, and newer functions that accept a state parameter that is read and modified. Please see the @ref{Random Number Functions} for more information on how to use and not to use random @@ -4470,7 +4551,7 @@ @var{num2} and @var{den2} are allowed to have common factors. -These functions are implemented as a macros and evaluate their arguments +These functions are implemented as macros and evaluate their arguments multiple times. @end deftypefn @@ -4505,10 +4586,13 @@ (@pxref{Rational Number Functions}) then @code{mpq_canonicalize} must be called before any other @code{mpq} functions are applied to that @code{mpq_t}. -@deftypefn Macro mpz_t mpq_numref (const mpq_t @var{op}) -@deftypefnx Macro mpz_t mpq_denref (const mpq_t @var{op}) +@deftypefn Macro mpz_ptr mpq_numref (const mpq_t @var{op}) +@deftypefnx Macro mpz_ptr mpq_denref (const mpq_t @var{op}) Return a reference to the numerator and denominator of @var{op}, respectively. -The @code{mpz} functions can be used on the result of these macros. +The @code{mpz} functions can be used on the result of these macros. Such +calls may modify the numerator or denominator. However, care +should be taken so that @var{op} remains in canonical form prior to a +possible later call to an @code{mpq} function. @end deftypefn @deftypefun void mpq_get_num (mpz_t @var{numerator}, const mpq_t @var{rational}) @@ -4634,7 +4718,7 @@ size. New projects should consider using the GMP extension library MPFR -(@url{http://mpfr.org}) instead. MPFR provides well-defined precision and +(@url{https://www.mpfr.org/}) instead. MPFR provides well-defined precision and accurate rounding, and thereby naturally extends IEEE P754. @menu @@ -4787,8 +4871,8 @@ decimal. For bases up to 36, case is ignored; upper-case and lower-case letters have -the same value; for bases 37 to 62, upper-case letter represent the usual -10..35 while lower-case letter represent 36..61. +the same value; for bases 37 to 62, upper-case letters represent the usual +10..35 while lower-case letters represent 36..61. Unlike the corresponding @code{mpz} function, the base will not be determined from the leading characters of the string if @var{base} is 0. This is so that @@ -5281,7 +5365,7 @@ @deftypefun mp_limb_t mpn_neg (mp_limb_t *@var{rp}, const mp_limb_t *@var{sp}, mp_size_t @var{n}) Perform the negation of @{@var{sp}, @var{n}@}, and write the result to -@{@var{rp}, @var{n}@}. This is equivalent to calling @code{mpn_sub_n} with a +@{@var{rp}, @var{n}@}. This is equivalent to calling @code{mpn_sub_n} with an @var{n}-limb zero minuend and passing @{@var{sp}, @var{n}@} as subtrahend. Return borrow, either 0 or 1. @end deftypefun @@ -5457,7 +5541,7 @@ least significant @var{count} bits of the return value (the rest of the return value is zero). -@var{count} must be in the range 1 to @nicode{mp_bits_per_limb}@minus{}1. The +@var{count} must be in the range 1 to @nicode{mp_bits_per_limb}@math{{}-1}. The regions @{@var{sp}, @var{n}@} and @{@var{rp}, @var{n}@} may overlap, provided @math{@var{rp} @ge{} @var{sp}}. @@ -5470,7 +5554,7 @@ most significant @var{count} bits of the return value (the rest of the return value is zero). -@var{count} must be in the range 1 to @nicode{mp_bits_per_limb}@minus{}1. The +@var{count} must be in the range 1 to @nicode{mp_bits_per_limb}@math{{}-1}. The regions @{@var{sp}, @var{n}@} and @{@var{rp}, @var{n}@} may overlap, provided @math{@var{rp} @le{} @var{sp}}. @@ -6037,11 +6121,11 @@ Initialize @var{state} with an algorithm selected by @var{alg}. The only choice is @code{GMP_RAND_ALG_LC}, which is @code{gmp_randinit_lc_2exp_size} described above. A third parameter of type @code{unsigned long} is required, -this is the @var{size} for that function. @code{GMP_RAND_ALG_DEFAULT} or 0 +this is the @var{size} for that function. @code{GMP_RAND_ALG_DEFAULT} and 0 are the same as @code{GMP_RAND_ALG_LC}. @c For reference, this is the only place gmp_errno has been documented, and -@c due to being non thread safe we won't be adding to it's uses. +@c due to being non thread safe we won't be adding to its uses. @findex gmp_errno @findex GMP_ERROR_UNSUPPORTED_ARGUMENT @findex GMP_ERROR_INVALID_ARGUMENT @@ -6067,7 +6151,7 @@ Set an initial seed value into @var{state}. The size of a seed determines how many different sequences of random numbers -that it's possible to generate. The ``quality'' of the seed is the randomness +it's possible to generate. The ``quality'' of the seed is the randomness of a given seed compared to the previous seed used, and this affects the randomness of separate number sequences. The method for choosing a seed is critical if the generated numbers are to be used for important applications, @@ -6231,7 +6315,7 @@ @samp{M} is a proxy for the C library @samp{l} or @samp{L}, according to the size of @code{mp_limb_t}. Unsigned conversions will be usual, but a signed -conversion can be used and will interpret the value as a twos complement +conversion can be used and will interpret the value as a two's complement negative. @samp{n} can be used with any type, even the GMP types. @@ -6334,7 +6418,7 @@ @deftypefunx int gmp_vasprintf (char **@var{pp}, const char *@var{fmt}, va_list @var{ap}) Form a null-terminated string in a block of memory obtained from the current memory allocation function (@pxref{Custom Allocation}). The block will be the -size of the string and null-terminator. The address of the block in stored to +size of the string and null-terminator. The address of the block is stored to *@var{pp}. The return value is the number of characters produced, excluding the null-terminator. @@ -6374,7 +6458,7 @@ In hex or octal, @var{op} is printed as a signed number, the same as for decimal. This is unlike the standard @code{operator<<} routines on @code{int} -etc, which instead give twos complement. +etc, which instead give two's complement. @end deftypefun @deftypefun ostream& operator<< (ostream& @var{stream}, const mpq_t @var{op}) @@ -7160,7 +7244,7 @@ The restrictions described for @code{mpf_set_prec_raw} (@pxref{Initializing Floats}) apply to @code{mpf_class::set_prec_raw}. Note in particular that the -@code{mpf_class} must be restored to it's allocated precision before being +@code{mpf_class} must be restored to its allocated precision before being destroyed. This must be done by application code, there's no automatic mechanism for it. @end deftypefun @@ -8033,7 +8117,7 @@ The @m{w_i,w[i]} are going to be determined, and when they are they'll give the final result using @math{w=W(b)}, since @m{xy=X(b)Y(b),x*y=X(b)*Y(b)=W(b)}. The coefficients will be roughly -@math{b^2} each, and the final @math{W(b)} will be an addition like, +@math{b^2} each, and the final @math{W(b)} will be an addition like this: @tex \def\GMPbox#1#2{% @@ -8091,7 +8175,7 @@ to a basecase multiply. Instead the following approach is used. @math{X(t)} and @math{Y(t)} are evaluated and multiplied at 5 points, giving -values of @math{W(t)} at those points. In GMP the following points are used, +values of @math{W(t)} at those points. In GMP the following points are used: @quotation @multitable {@m{t=\infty,t=inf}M} {MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM} @@ -8226,7 +8310,7 @@ @end quotation The number of additions and subtractions for Toom-4 is much larger than for Toom-3. -But several subexpressions occur multiple times, for example @m{x_2+x_0,x2+x0}, occurs +But several subexpressions occur multiple times, for example @m{x_2+x_0,x2+x0} occurs for both @math{t=1} and @math{t=-1}. Toom-4 is asymptotically @math{O(N^@W{1.404})}, the exponent being @@ -8239,19 +8323,19 @@ @cindex Toom multiplication The Toom algorithms described above (@pxref{Toom 3-Way Multiplication}, -@pxref{Toom 4-Way Multiplication}) generalizes to split into an arbitrary +@pxref{Toom 4-Way Multiplication}) generalize to split into an arbitrary number of pieces. In general a split of two equally long operands into @math{r} pieces leads to evaluations and pointwise multiplications done at @m{2r-1,2*r-1} points. To fully exploit symmetries it would be better to have a multiple of 4 points, that's why for higher degree Toom'n'half is used. Toom'n'half means that the existence of one more piece is considered for a -single operand. It can be virtual, i.e. zero, or real, when the two operand +single operand. It can be virtual, i.e. zero, or real, when the two operands are not exactly balanced. By choosing an even @math{r}, Toom-@m{r{1\over2},r+1/2} requires @math{2r} points, a multiple of four. -The quadruplets of points include 0, @m{\infty,inf}, +1, -1 and -@m{\pm2^i,+-2^i}, @m{\pm2^{-i},+-2^-i} . Each of them giving shortcuts for the +The quadruplets of points include 0, @m{\infty,inf}, +1, @m{-1} and +@m{\pm2^i,+-2^i}, @m{\pm2^{-i},+-2^-i}. Each of them giving shortcuts for the evaluation phase and for some steps in the interpolation phase. Further tricks are used to reduce the memory footprint of the whole multiplication algorithm to a memory buffer equal in size to the result of the product. @@ -8284,7 +8368,7 @@ the split falls on limb boundaries, avoiding bit shifts in the split and combine stages. -The evaluations, pointwise multiplications, and interpolation, are all done +The evaluations, pointwise multiplications, and interpolation are all done modulo @m{2^{N'}+1, 2^N'+1} where @math{N'} is @math{2M+k+3} rounded up to a multiple of @math{2^k} and of @code{mp_bits_per_limb}. The results of interpolation will be the following negacyclic convolution of the input @@ -8386,7 +8470,7 @@ In general a split into @math{r+1} pieces is made, and evaluations and pointwise multiplications done at @m{2r+1,2*r+1} points. A 4-way split does 7 pointwise multiplies, 5-way does 9, etc. Asymptotically an @math{(r+1)}-way -algorithm is @m{O(N^{log(2r+1)/log(r+1)}), O(N^(log(2*r+1)/log(r+1)))}. Only +algorithm is @m{O(N^{\log(2r+1)/\log(r+1)}), O(N^(log(2*r+1)/log(r+1)))}. Only the pointwise multiplications count towards big-@math{O} complexity, but the time spent in the evaluate and interpolate stages grows with @math{r} and has a significant practical impact, with the asymptotic advantage of each @math{r} @@ -8432,7 +8516,7 @@ For operands between these sizes, we use Toom inspired algorithms suggested by Alberto Zanoni and Marco Bodrato. The idea is to split the operands into polynomials of different degree. GMP currently splits the smaller operand -onto 2 coefficients, i.e., a polynomial of degree 1, but the larger operand +into 2 coefficients, i.e., a polynomial of degree 1, but the larger operand can be split into 2, 3, or 4 coefficients, i.e., a polynomial of degree 1 to 3. @@ -8780,7 +8864,7 @@ 0.68 iterations per bit. For optimum performance some attention needs to be paid to the way the factors of 2 are stripped from @math{a}. -Firstly it may be noted that in twos complement the number of low zero bits on +Firstly it may be noted that in two's complement the number of low zero bits on @math{a-b} is the same as @math{b-a}, so counting or testing can begin on @math{a-b} without waiting for @math{@abs{}(a-b)} to be determined. @@ -8789,7 +8873,7 @@ an option is to strip one or two bits arithmetically then loop for more (as done for AMD K6). Or use a lookup table to get a count for several bits then loop for more (as done for AMD K7). An alternative approach is to keep just -one of @math{a} or @math{b} odd and iterate +one of @math{a} and @math{b} odd and iterate @quotation @math{a,b = @abs{}(a-b), @min{}(a,b)} @* @@ -8841,10 +8925,10 @@ may sometimes be one off. @item -It takes advantage of the fact the quotients are usually small. The division +It takes advantage of the fact that the quotients are usually small. The division operator is not used, since the corresponding assembler instruction is very slow on most architectures. (This code could probably be improved further, it -uses many branches that are unfriendly to prediction). +uses many branches that are unfriendly to prediction.) @item It switches from double-limb calculations to single-limb calculations half-way @@ -8904,7 +8988,7 @@ @code{mpn_hgcd2}, and applies the resulting matrix to the full numbers, the sub-quadratic GCD chops off the most significant third of the limbs (the proportion is a tuning parameter, and @math{1/3} seems to be more efficient -than, e.g, @math{1/2}), calls @code{mpn_hgcd}, and applies the resulting +than, e.g., @math{1/2}), calls @code{mpn_hgcd}, and applies the resulting matrix. Once the input numbers are reduced to size below @code{GCD_DC_THRESHOLD}, Lehmer's algorithm is used for the rest of the work. @@ -8923,7 +9007,7 @@ Lehmer's algorithm is used for sizes up to @code{GCDEXT_DC_THRESHOLD}. Above this threshold, GCDEXT is implemented as a loop around HGCD, but with more book-keeping to keep track of the cofactors. This gives the same asymptotic -running time as for GCD and HGCD, @m{O(M(N)\log N),O(M(N)*log(N))} +running time as for GCD and HGCD, @m{O(M(N)\log N),O(M(N)*log(N))}. One difference to plain GCD is that while the inputs @math{a} and @math{b} are reduced as the algorithm proceeds, the cofactors @math{x} and @math{y} grow in @@ -8953,7 +9037,7 @@ @code{mpz_legendre} and @code{mpz_kronecker} are computed via the HGCD (Half GCD) function, as a generalization to Lehmer's algorithm. -Most GCD algorithms reduce @math{a} and @math{b} by repeatatily computing the +Most GCD algorithms reduce @math{a} and @math{b} by repeatedly computing the quotient @m{q = \lfloor a/b \rfloor, q = floor(a/b)} and iteratively replacing @c Couldn't figure out macros with commas. @@ -8989,7 +9073,7 @@ twiddling which avoids conditional jumps. The final result is calculated after verifying the inputs are coprime (GCD = 1) -by raising @m{(-1)^e,(-1)^e} +by raising @m{(-1)^e,(-1)^e}. Much of the HGCD code is shared directly with the HGCD implementations, such as the 2x2 matrix calculation, @xref{Lehmer's Algorithm} basecase and @@ -9393,9 +9477,9 @@ @end quotation Current code collects all the factors in a single list, with a loop and no -recursion, and compute the product, with no special care for repeated chunks. +recursion, and computes the product, with no special care for repeated chunks. -When @math{n} is larger, computation pass trough prime sieving. An helper +When @math{n} is larger, computations pass through prime sieving. A helper function is used, as suggested by Peter Luschny: @tex $$\mathop{\rm msf}(n) = {n!\over\lfloor n/2\rfloor!^2\cdot2^k} = \prod_{p=3}^{n} @@ -9807,10 +9891,10 @@ The final loop control cost can be amortised by processing several limbs in each iteration (@pxref{Assembly Loop Unrolling}). This at least ensures loop -control isn't a big fraction the work done. +control isn't a big fraction of the work done. Memory throughput is always a limit. If perhaps only one load or one store -can be done per cycle then 3 cycles/limb will the top speed for ``binary'' +can be done per cycle then 3 cycles/limb will be the top speed for ``binary'' operations like @code{mpn_add_n}, and any code achieving that is optimal. Integer resources can be freed up by having the loop counter in a float @@ -9825,7 +9909,7 @@ @node Assembly Floating Point, Assembly SIMD Instructions, Assembly Functional Units, Assembly Coding @subsection Floating Point -@cindex Assembly floating Point +@cindex Assembly floating point Floating point arithmetic is used in GMP for multiplications on CPUs with poor integer multipliers. It's mostly useful for @code{mpn_mul_1}, @@ -10067,7 +10151,7 @@ If the latency of some instruction is greater than the loop time then it will be necessary to unroll, so one register has a result ready to use while -another (or multiple others) are still in progress. (@pxref{Assembly Loop +another (or multiple others) are still in progress (@pxref{Assembly Loop Unrolling}). @@ -10228,12 +10312,12 @@ @end table The various bitwise logical functions like @code{mpz_and} behave as if -negative values were twos complement. But sign and magnitude is always used +negative values were two's complement. But sign and magnitude is always used internally, and necessary adjustments are made during the calculations. Sometimes this isn't pretty, but sign and magnitude are best for other routines. -Some internal temporary variables are setup with @code{MPZ_TMP_INIT} and these +Some internal temporary variables are set up with @code{MPZ_TMP_INIT} and these have @code{_mp_d} space obtained from @code{TMP_ALLOC} rather than the memory allocation functions. Care is taken to ensure that these are big enough that no reallocation is necessary (since it would have unpredictable consequences). @@ -10498,7 +10582,7 @@ back with @code{mpf_get_prec} will take @code{_mp_prec} subtract 1 limb and multiply by 32, giving 256 bits. -Strictly speaking, the fact the high limb has at least one bit means that a +Strictly speaking, the fact that the high limb has at least one bit means that a float with, say, 3 limbs of 32-bits each will be holding at least 65 bits, but for the purposes of @code{mpf_t} it's considered simply to be 64 bits, a nice multiple of the limb size. @@ -10539,7 +10623,7 @@ @end ifnottex The size is 4 bytes written most significant byte first, being the number of -subsequent data bytes, or the twos complement negative of that when a negative +subsequent data bytes, or the two's complement negative of that when a negative integer is represented. The data bytes are the absolute value of the integer, written most significant byte first. @@ -10667,7 +10751,7 @@ @cindex Contributors Torbj@"orn Granlund wrote the original GMP library and is still the main -developer. Code not explicitly attributed to others, was contributed by +developer. Code not explicitly attributed to others was contributed by Torbj@"orn. Several other individuals and organizations have contributed GMP. Here is a list in chronological order on first contribution: @@ -10713,7 +10797,7 @@ Karatsuba and 3-way Toom multiplication functions for GMP 3, and contributed the ARM assembly code. -Torsten Ekedahl of the Mathematical department of Stockholm University provided +Torsten Ekedahl of the Mathematical Department of Stockholm University provided significant inspiration during several phases of the GMP development. His mathematical expertise helped improve several algorithms. @@ -10739,7 +10823,7 @@ Pedro Gimeno implemented the Mersenne Twister and made other random number improvements. -Niels M@"oller wrote the sub-quadratic GCD, extended GCD and jacobi code, the +Niels M@"oller wrote the sub-quadratic GCD, extended GCD and Jacobi code, the quadratic Hensel division code, and (with Torbj@"orn) the new divide and conquer division code for GMP 4.3. Niels also helped implement the new Toom multiply code for GMP 4.3 and implemented helper functions to simplify Toom @@ -10786,7 +10870,7 @@ contributed to GMP but are not listed above, please tell @email{gmp-devel@@gmplib.org} about the omission!) -The development of floating point functions of GNU MP 2, were supported in part +The development of floating point functions of GNU MP 2 was supported in part by the ESPRIT-BRA (Basic Research Activities) 6846 project POSSO (POlynomial System SOlving). diff -Nru gmp-doc-6.2.1+ndfsg/doc/projects.html gmp-doc-6.3.0+ndfsg/doc/projects.html --- gmp-doc-6.2.1+ndfsg/doc/projects.html 2020-11-16 20:09:45.000000000 +0000 +++ gmp-doc-6.3.0+ndfsg/doc/projects.html 2023-08-13 20:21:18.000000000 +0000 @@ -456,7 +456,7 @@ functions are desirable: acos, acosh, asin, asinh, atan, atanh, atan2, cos, cosh, exp, log, log10, pow, sin, sinh, tan, tanh. -

Note that the mpfr functions already +

Note that the mpfr functions already provide these functions, and that we usually recommend new programs to use mpfr instead of mpf. diff -Nru gmp-doc-6.2.1+ndfsg/doc/stamp-vti gmp-doc-6.3.0+ndfsg/doc/stamp-vti --- gmp-doc-6.2.1+ndfsg/doc/stamp-vti 2020-11-16 20:09:45.000000000 +0000 +++ gmp-doc-6.3.0+ndfsg/doc/stamp-vti 2023-08-13 20:21:18.000000000 +0000 @@ -1,4 +1,4 @@ -@set UPDATED 14 November 2020 -@set UPDATED-MONTH November 2020 -@set EDITION 6.2.1 -@set VERSION 6.2.1 +@set UPDATED 29 July 2023 +@set UPDATED-MONTH July 2023 +@set EDITION 6.3.0 +@set VERSION 6.3.0 diff -Nru gmp-doc-6.2.1+ndfsg/doc/version.texi gmp-doc-6.3.0+ndfsg/doc/version.texi --- gmp-doc-6.2.1+ndfsg/doc/version.texi 2020-11-16 20:09:45.000000000 +0000 +++ gmp-doc-6.3.0+ndfsg/doc/version.texi 2023-08-13 20:21:18.000000000 +0000 @@ -1,4 +1,4 @@ -@set UPDATED 14 November 2020 -@set UPDATED-MONTH November 2020 -@set EDITION 6.2.1 -@set VERSION 6.2.1 +@set UPDATED 29 July 2023 +@set UPDATED-MONTH July 2023 +@set EDITION 6.3.0 +@set VERSION 6.3.0