summaryrefslogtreecommitdiff
path: root/doc/projects.html
diff options
context:
space:
mode:
authorKevin Ryde <user42@zip.com.au>2001-11-24 22:34:31 +0100
committerKevin Ryde <user42@zip.com.au>2001-11-24 22:34:31 +0100
commit4645559e74c4a502a7ed90884967fe6f238e97ba (patch)
treeb818407546a687e1c0ab6d4ac1db34de7ba61ce7 /doc/projects.html
parent53938dc12ce1fcb0205d7c898e25f192ac09b444 (diff)
downloadgmp-4645559e74c4a502a7ed90884967fe6f238e97ba.tar.gz
Remove C++ wrapper task, done.
Note Paul's sub-quadratic GCD work. Add quotient-only division. Add sub-quadratic redc and divexact.
Diffstat (limited to 'doc/projects.html')
-rw-r--r--doc/projects.html75
1 files changed, 56 insertions, 19 deletions
diff --git a/doc/projects.html b/doc/projects.html
index a0311cbe1..d295f57ea 100644
--- a/doc/projects.html
+++ b/doc/projects.html
@@ -34,7 +34,7 @@ Copyright 2000, 2001 Free Software Foundation, Inc.
<hr>
<!-- NB. timestamp updated automatically by emacs -->
<comment>
- This file current as of 17 Nov 2001. An up-to-date version is available at
+ This file current as of 25 Nov 2001. An up-to-date version is available at
<a href="http://www.swox.com/gmp/projects.html">http://www.swox.com/gmp/projects.html</a>.
Please send comments about this page to
<a href="mailto:bug-gmp@gnu.org">bug-gmp@gnu.org</a>.
@@ -50,24 +50,7 @@ Copyright 2000, 2001 Free Software Foundation, Inc.
problems.)
<ul>
-<li> <strong>C++ wrapper</strong>
-
- <p> A C++ wrapper for GMP is highly desirable.
- <a href="http://www.sissa.it/~ballabio/gmp++.html">GMP++</a> has made
- excellent progress on this.
- For a wrapper to be useful, one needs to pay attention to efficiency.
-
- <ol>
- <li> Write arithmetic functions for direct applications of most
- elementary C++ types. This might be necessary to avoid
- ambiguities, but it is also desirable from an efficiency
- standpoint.
- <li> Avoid running constructors/destructors when not necessary. For
- example, implement <code>a&nbsp+=&nbsp;b</code> by directly applying
- <code>mpz_add</code>.
- </ol>
-
-<p> <li> <strong>Faster multiplication</strong>
+<li> <strong>Faster multiplication</strong>
<p> The current multiplication code uses Karatsuba, 3-way Toom-Cook,
or Fermat FFT. Several new developments are desirable:
@@ -145,6 +128,9 @@ Copyright 2000, 2001 Free Software Foundation, Inc.
current code can mostly be reused. It should be possible to share code
between GCD and GCDEXT, and probably with Jacobi symbols too.
+ <p> Paul Zimmerman has worked on sub-quadratic GCD and GCDEXT, but it seems
+ that the most likely algorithm doesn't kick in until about 3000 limbs.
+
<p> <li> <strong>Math functions for the mpf layer</strong>
<p> Implement the functions of math.h for the GMP mpf layer! Check the book
@@ -152,6 +138,9 @@ Copyright 2000, 2001 Free Software Foundation, Inc.
functions are desirable: acos, acosh, asin, asinh, atan, atanh, atan2, cos,
cosh, exp, log, log10, pow, sin, sinh, tan, tanh.
+ <p> These are implemented in mpfr, redoing them in mpf might not be worth
+ bothering with, if the long term plan is to bring mpfr in as the new mpf.
+
<p> <li> <strong>Faster sqrt</strong>
<p> The current code uses divisions, which are reasonably fast, but it'd be
@@ -178,6 +167,54 @@ Copyright 2000, 2001 Free Software Foundation, Inc.
<p> If the routine becomes fast enough, perhaps square roots could be computed
using this function.
+<p> <li> <strong>Quotient-Only Division</strong>
+
+ <p> Some work can be saved when only the quotient is required in a division,
+ basically the necessary correction -0, -1 or -2 to the estimated
+ quotient can almost always be determined from only a few limbs of
+ multiply and subtract, rather than forming a complete remainder. The
+ greatest savings are when the quotient is small compared to the dividend
+ and divisor.
+
+ <p> Some code along these lines can be found in the current
+ <code>mpn_tdiv_qr</code>, though perhaps calculating bigger chunks of
+ remainder than might be strictly necessary. That function in its
+ current form actually then always goes on to calculate a full remainder.
+ Burnikel and Zeigler describe a similar approach for the divide and
+ conquer case.
+
+<p> <li> <strong>Sub-Quadratic REDC and Exact Division</strong>
+
+ <p> <code>mpn_bdivmod</code> and the <code>redc</code> in
+ <code>mpz_powm</code> should use some sort of divide and conquer
+ algorithm. This would benefit <code>mpz_divexact</code>, and
+ <code>mpn_gcd</code> on large unequal size operands. See "Exact
+ Division with Karatsuba Complexity" by Jebelean for a (brief)
+ description.
+
+ <p> Failing that, some sort of <code>DIVEXACT_THRESHOLD</code> could be
+ added to control whether <code>mpz_divexact</code> uses
+ <code>mpn_bdivmod</code> or <code>mpn_tdiv_qr</code>, since the latter
+ is faster on large divisors.
+
+ <p> For the REDC, basically all that's needed is Montgomery's algorithm done
+ in multi-limb integers. R is multiple limbs, and the inverse and
+ operands are multi-precision.
+
+ <p> For exact division the time to calculate a multi-limb inverse is not
+ amortized across many modular operations, but instead will probably
+ create a threshold below which the current style
+ <code>mpn_bdivmod</code> is best. There's also Krandick and Jebelean,
+ "Bidirectional Exact Integer Division" to basically use a low to high
+ exact division for the low half quotient, and a quotient-only division
+ for the high half.
+
+ <p> It will be noted that low-half and high-half multiplies, and a low-half
+ square, can be used. These ought to each take as little as half the
+ time of a full multiply, or square, though work by Thom Mulders shows
+ the advantage is progressively lost as Karatsuba and higher algorithms
+ are applied.
+
<p> <li> <strong>Test Suite</strong>
<p> Add a test suite for old bugs. These tests wouldn't loop or use