[Gmp-commit] /var/hg/www: 6 new changesets
mercurial at gmplib.org
mercurial at gmplib.org
Fri Aug 30 14:59:24 CEST 2013
details: /var/hg/www/rev/faf1e85f147c
changeset: 88:faf1e85f147c
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Aug 30 14:15:18 2013 +0200
description:
Update to reflect that many systems are now offline.
details: /var/hg/www/rev/0337109dcb9c
changeset: 89:0337109dcb9c
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Aug 30 14:55:17 2013 +0200
description:
Many updates.
details: /var/hg/www/rev/aab0070f0f80
changeset: 90:aab0070f0f80
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Aug 30 14:56:26 2013 +0200
description:
More on division anomalies.
details: /var/hg/www/rev/a8a578222136
changeset: 91:a8a578222136
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Aug 30 14:57:19 2013 +0200
description:
Remove obsolete file.
details: /var/hg/www/rev/4e358d6345dc
changeset: 92:4e358d6345dc
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Aug 30 14:57:58 2013 +0200
description:
Update for major machines.
details: /var/hg/www/rev/cbb337e68558
changeset: 93:cbb337e68558
user: Torbjorn Granlund <tege at gmplib.org>
date: Fri Aug 30 14:59:14 2013 +0200
description:
Updates reflecting past months' work.
diffstat:
devel/GMPng.html | 189 ++++++++++++++++++++++----------------
devel/asm.html | 238 ++++++++++++++++++++++++------------------------
devel/index.html | 85 +++++++++++++---
devel/testsystems.html | 28 ++--
gmpbench-0.1.tar.gz | Bin
gmpbench.html | 155 ++++++++++++++++---------------
6 files changed, 390 insertions(+), 305 deletions(-)
diffs (truncated from 1274 to 300 lines):
diff -r 43b808ecb7c7 -r cbb337e68558 devel/GMPng.html
--- a/devel/GMPng.html Tue Jul 30 15:43:35 2013 +0200
+++ b/devel/GMPng.html Fri Aug 30 14:59:14 2013 +0200
@@ -41,24 +41,25 @@
<p> This is an attempt at defining a development target for the next major GMP
release, to be released in 2014. We might not implement every item here for
-that release, and we will surely make some developments missing from this list.
+that release, and we will surely make some developments missing from this
+list. </p>
</p>
<h4> Colour codes</h4>
<font color="#a00000">
- <p> [1] This really ought to be done before release
+ <p> [1] This really ought to be done before release </p>
</font>
<font color="#808000">
- <p> [2] Try to get this done before release
+ <p> [2] Try to get this done before release </p>
</font>
<font color="#00a000">
- <p> [n] Done!
+ <p> [n] Done! </p>
</font>
<font color="#0000a0">
- <p> [n] Leave for subsequent releases!
+ <p> [n] Leave for subsequent releases! </p>
</font>
<hr>
@@ -78,7 +79,7 @@
<font color="#a00000">
<p> Handle very unbalanced multiplication by "transforming" the smaller
operand, then multiply using toomX2, toomX3, using the transformed value.
- Similarly in FFT range.
+ Similarly in FFT range. </p>
</font>
@@ -87,59 +88,58 @@
<font color="#a00000">
<p> Merge <a href="http://gmplib.org:8000/gcd-nisse/" style="color:
rgb(160,0,0)">Niels' small-primes FFT code</a>. Make sure it is memory
- efficient.
+ efficient. </p>
</font>
<font color="#a00000">
<p> Merge new mul_fft.c. [Stalls on SFLC analysis.] Alternatively, improve
- the present code ourselves, or perhaps reimplement the algorithm from scratch.
+ the present code ourselves, or perhaps reimplement the algorithm from
+ scratch. </p>
</font>
<font color="#a00000">
<p> Extend SS FFT table more intelligently, taking 'goodness' into account.
- (For both plain and fat builds.)
+ (For both plain and fat builds.) </p>
</font>
<font color="#a00000">
- <p> Implement &sqrt;2 trick: 2<sup>3n/4</sup>-2<sup>n/4</sup> is a square root of 2 mod (2n+1).
- This allows for smaller coeffients.
- </font>
-
-
-<h2> Finish mulmod_bnm1 </h2>
-
- <font color="#808000">
- <p> Write assembly basecase mulmod_bnm1.
+ <p> Implement the
+ <span style="white-space: nowrap; font-size:larger">
+ √<span style="text-decoration:overline;"> 2 </span>
+ </span>
+ trick: 2<sup>3n/4</sup>-2<sup>n/4</sup> is a square
+ root of 2 mod (2n+1). This allows for smaller coeffients. </p>
</font>
<h2> Short products </h2>
<p> <font color="#00a000"> Merge David's mpn_mulmid code,</font>
- <font color="#a00000"> use it at least for mpn_binvert.</font>
+ <font color="#a00000"> use it at least for mpn_binvert.</font> </p>
<h2> Division m,n </h2>
<font color="#808000">
- <p> Implement van der Hoeven's MU generalisation.
+ <p> Implement van der Hoeven's MU generalisation. </p>
</font>
<font color="#808000">
- <p> Perfect algorithm selection for nn-limb by dn-limb division.
+ <p> Perfect algorithm selection for nn-limb by dn-limb division. </p>
</font>
<font color="#a00000">
<p> Improve MU strategy for Q > D. We currently have serious performance
- anomalies.
+ anomalies. </p>
</font>
<font color="#a00000">
- <p> Add pi/preinv variants for all mu functions. [2h]
+ <p> Add pi/preinv variants for all mu functions. [2h] </p>
</font>
<font color="#a00000">
- <p> We still use mpn_tdiv_qr or even mpn_divrem in many files. Replace by current division functions:
+ <p> We still use mpn_tdiv_qr or even mpn_divrem in many files. Replace by
+ current division functions: </p>
</font>
<blockquote>
<table fgcolor="#a00000">
@@ -167,7 +167,7 @@
</blockquote>
<font color="#808000">
- <p> These files also use mpn_tdiv_qr, but just for nails:
+ <p> These files also use mpn_tdiv_qr, but just for nails: </p>
<blockquote>
mpz/cdiv_q_ui.c
mpz/cdiv_qr_ui.c
@@ -189,7 +189,7 @@
<font color="#a00000">
<p> Complete set of bdiv_1, bdiv_2 and div_1, div_2 functions, using 1-limb,
- 2-limb inverses.
+ 2-limb inverses. </p>
</font>
<font color="#a00000">
@@ -197,22 +197,14 @@
abstractions, since this is something all processors will need. This loop
will in almost all cases be used just for very small n, since mod_1s-family
functions will take over very quickly. Selection mechanisms between the mod
- functions could still be in C.
- </font>
-
- <font color="#a00000">
- <p> Commit lots of new assembly code for div_1_*.
- </font>
-
- <font color="#a00000">
- <p> Commit lots of new assembly code for div_2_*.
+ functions could still be in C. </p>
</font>
<h2> mpz_remove, mpn_remove </h2>
<font color="#a00000">
- <p> Call mpn_remove from mpn/generic/perfpow.c.
+ <p> Call mpn_remove from mpn/generic/perfpow.c. </p>
</font>
@@ -220,14 +212,14 @@
<font color="#a00000">
<p> Finish unification of bdiv/redc. The internal (sorry!) repo
- ~hg/gmp-proj/gmp-bdiv has a good start.
+ ~hg/gmp-proj/gmp-bdiv has a good start. </p>
</font>
<h2> mpn_broot, mpn_binvroot, mpn_bsqrt, mpn_binvsqrt </h2>
<font color="#a00000">
- <p> Implement wrap-around trick for the <i></i>-adic root code.
+ <p> Implement wrap-around trick for the <i></i>-adic root code. </p>
</font>
<h2> Exact powers </h2>
@@ -236,7 +228,7 @@
<p> Add companion for mpz_perfect_power_p that returns the exponent and
optionally the root. Possible name mpz_rootexact. Marco suggested some
alternative functions, which could test a number and extract its nth power.
- (Sept/Oct 2012).
+ (Sept/Oct 2012). </p>
</font>
@@ -244,39 +236,51 @@
<font color="#a00000">
<p> We have an ugly mpn_divexact using Jebelean's bidirectional algorithm.
- Clean it up, and probably permit even divisors.
+ Clean it up, and probably permit even divisors. </p>
</font>
<h2> GCD </h2>
<font color="#808000">
- <p> Use mulmod_bnm1 for cancelling operand updates. [Partly done]
+ <p> Use mulmod_bnm1 for cancelling operand updates. [Partly done] </p>
</font>
- <font color="#808000">
- <p> Replace gcd_1 by gcd_11, and implement gcd_22. Implement gcd_1 in C,
- calling an abstract gcd-modulo function (see <b>Divide-by-fewlimb and
- modulo-by-fewlimb</b> above).
+ <p> Unlike most basic functions in GMP, GCD depends on C code and thus on
+ compilers. Furthermore, extended GCD lacks proper basecase code, and instead
+ invoke the heavy machinery. </p>
+
+ <font color="#a00000">
+ <p> Replace gcd_1 by gcd_11, accepting two limbs. Implement gcd_1 in C for
+ compatibility. </p>
+ </font>
+
+ <font color="#a00000">
+ <p> Implement gcd_22 in C, also in assembly using compiler generation. </p>
+ </font>
+
+ <font color="#a00000">
+ <p> Implement gcdext_22. </p>
</font>
<h2> Modexp, <i>b</i><sup><i>d</i></sup> mod <i>m</i> </h2>
- See also <a href=".">the top-level developers' corner page</a> for a deeper
- discussion on this subject.
+ <p> See also <a href=".">the top-level developers' corner page</a> for a
+ deeper discussion on this subject. </p>
<font color="#a00000">
- <p> Use special code for when <i>b</i> is much smaller than <i>m</i>, avoiding REDC
- representation and table precomputation. New pseudo-code at the
- <a href=".">top devel page</a>.
+ <p> Use special code for when <i>b</i> is much smaller than <i>m</i>,
+ avoiding REDC representation and table precomputation. New pseudo-code at
+ the
+ <a href=".">top devel page</a>. </p>
</font>
<h2> Side-channel silent functions </h2>
<font color="#a00000">
- <p> Make user interface to multiply, divide.
+ <p> Make user interface to multiply, divide. </p>
</font>
@@ -287,38 +291,38 @@
needed, and at least in ELF we may suppress them using attributes such as
"protected" and "hidden". (It seems something similar exists also on Darwin;
here the compiler adds a .private_extern to the declaration of a function,
- but does not change calls [until supposedly in the final link].)
+ but does not change calls [until supposedly in the final link].) </p>
- <p> This can also be used to enforce the policy that certain functions ae
+ <p> This can also be used to enforce the policy that certain functions are
really internal to the library. Depending on how one sees such policies,
such enforcing might be good or bad. We should probably use it with care.
Calls that are declared with attribute "internal" will be the fastest, since
- then the GOT pointer can be assumed correct, which is a technical reaon XXX
+ then the GOT pointer can be assumed correct. </p>
<font color="#a00000">
<p> Fix calls to strictly internal routines, using the "internal" attribute,
e.g. allowing compiler suppression of GOT setup code. <br> Fix references to
- strictly internal variables (e.g., alloc func pointers).
+ strictly internal variables (e.g., alloc func pointers). </p>
</font>
<font color="#a00000">
- <p> Fix calls to remaining mpn routines (perhaps using hidden+alias).
+ <p> Fix calls to remaining mpn routines (perhaps using hidden+alias). </p>
</font>
<font color="#a00000">
<p> Fix calls via gmpn_cpuvec (x86/fat/fat_entry.asm, x86_64/fat/fat_entry.asm).
- The table itself needs a GOT and each entry points to a PLT entry...
+ The table itself needs a GOT and each entry points to a PLT entry... </p>
</font>
<font color="#a00000">
- <p> Use <code>restrict</code> keyword in most <code>mpn</code> functions.
+ <p> Use <code>restrict</code> keyword in most <code>mpn</code> functions. </p>
</font>
<font color="#a00000">
<p> Use <code>visibility hidden</code> for <b>all</b> symbols used
internally, then make documented symbols visible with alias. See star
hacker <a href="http://www.airs.com/blog/archives/307" style="color:
- rgb(160,0,0)">Ian Lance Taylor's explanations</a>.
+ rgb(160,0,0)">Ian Lance Taylor's explanations</a>. </p>
</font>
More information about the gmp-commit
mailing list