| <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> |
| <html> |
| <head> |
| <title>GMP Development Projects</title> |
| <link rel="shortcut icon" href="favicon.ico"> |
| <link rel="stylesheet" href="gmp.css"> |
| <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> |
| </head> |
| |
| <center> |
| <h1> |
| GMP Development Projects |
| </h1> |
| </center> |
| |
| <font size=-1> |
| <pre> |
| Copyright 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2008, 2009 Free Software |
| Foundation, Inc. |
| |
| This file is part of the GNU MP Library. |
| |
| The GNU MP Library is free software; you can redistribute it and/or modify |
| it under the terms of the GNU Lesser General Public License as published |
| by the Free Software Foundation; either version 3 of the License, or (at |
| your option) any later version. |
| |
| The GNU MP Library is distributed in the hope that it will be useful, but |
| WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
| or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public |
| License for more details. |
| |
| You should have received a copy of the GNU Lesser General Public License |
| along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. |
| </pre> |
| </font> |
| |
| <hr> |
| <!-- NB. timestamp updated automatically by emacs --> |
| This file current as of 1 May 2009. An up-to-date version is available at |
| <a href="http://gmplib.org/projects.html">http://gmplib.org/projects.html</a>. |
| Please send comments about this page to gmp-devel<font>@</font>gmplib.org. |
| |
| <p> This file lists projects suitable for volunteers. Please see the |
| <a href="tasks.html">tasks file</a> for smaller tasks. |
| |
| <p> If you want to work on any of the projects below, please let |
| gmp-devel<font>@</font>gmplib.org know. If you want to help with a project |
| that already somebody else is working on, you will get in touch through |
| gmp-devel<font>@</font>gmplib.org. (There are no email addresses of |
| volunteers below, due to spamming problems.) |
| |
| <ul> |
| <li> <strong>Faster multiplication</strong> |
| |
| <p> The current multiplication code uses Karatsuba, 3-way and 4-way Toom, and |
| Fermat FFT. Several new developments are desirable: |
| |
| <ol> |
| |
| <li> Write more toom multiply functions for unbalanced operands. We now have |
| toom22, toom32, toom42, toom62, toom33, toom53, and toom44. Most |
| desirable is toom43, which will require a new toom_interpolate_6pts |
| function. Writing toom52 will then be straightforward. See also |
| <a href="http://bodrato.it/software/toom.html">Marco Bodrato's |
| site</a> |
| |
| <li> Perhaps consider N-way Toom, N > 4. See Knuth's Seminumerical |
| Algorithms for details on the method, as well as Bodrato's site. Code |
| implementing it exists. This is asymptotically inferior to FFTs, but |
| is finer grained. |
| |
| <li> The mpn_mul call now (from GMP 4.3) uses toom22, toom32, and toom42 |
| for unbalanced operations. We don't use any of the other new toom |
| functions currently. Write new clever code for choosing the best toom |
| function from an m-limb and an n-limb operand. |
| |
| <li> Implement an FFT variant computing the coefficients mod m different |
| limb size primes of the form l*2^k+1. i.e., compute m separate FFTs. |
| The wanted coefficients will at the end be found by lifting with CRT |
| (Chinese Remainder Theorem). If we let m = 3, i.e., use 3 primes, we |
| can split the operands into coefficients at limb boundaries, and if |
| our machine uses b-bit limbs, we can multiply numbers with close to |
| 2^b limbs without coefficient overflow. For smaller multiplication, |
| we might perhaps let m = 1, and instead of splitting our operands at |
| limb boundaries, split them in much smaller pieces. We might also use |
| 4 or more primes, and split operands into bigger than b-bit chunks. |
| By using more primes, the gain in shorter transform length, but lose |
| in having to do more FFTs, but that is a slight total save. We then |
| lose in more expensive CRT. <br><br> |
| |
| <p> [We now have two implementations of this algorithm, one by Tommy |
| Färnqvist and one by Niels Möller.] |
| |
| <li> Add support for short products, either a given number of low limbs, a |
| given number of high limbs, or perhaps the middle limbs of the result. |
| High short product can be used by <code>mpf_mul</code>, by |
| left-to-right Newton approximations, and for quotient approximation. |
| Low half short product can be of use in sub-quadratic REDC and for |
| right-to-left Newton approximations. On small sizes a short product |
| will be faster simply through fewer cross-products, similar to the way |
| squaring is faster. But work by Thom Mulders shows that for Karatsuba |
| and higher order algorithms the advantage is progressively lost, so |
| for large sizes shows products turn out to be no faster. |
| |
| </ol> |
| |
| <p> Another possibility would be an optimized cube. In the basecase that |
| should definitely be able to save cross-products in a similar fashion to |
| squaring, but some investigation might be needed for how best to adapt |
| the higher-order algorithms. Not sure whether cubing or further small |
| powers have any particularly important uses though. |
| |
| |
| <li> <strong>Assembly routines</strong> |
| |
| <p> Write new and improve existing assembly routines. The tests/devel |
| programs and the tune/speed.c and tune/many.pl programs are useful for |
| testing and timing the routines you write. See the README files in those |
| directories for more information. |
| |
| <p> Please make sure your new routines are fast for these three situations: |
| <ol> |
| <li> Operands that fit into the cache. |
| <li> Small operands of less than, say, 10 limbs. |
| <li> Huge operands that does not fit into the cache. |
| </ol> |
| |
| <p> The most important routines are mpn_addmul_1, mpn_mul_basecase and |
| mpn_sqr_basecase. The latter two don't exist for all machines, while |
| mpn_addmul_1 exists for almost all machines. |
| |
| <p> Standard techniques for these routines are unrolling, software |
| pipelining, and specialization for common operand values. For machines |
| with poor integer multiplication, it is often possible to improve the |
| performance using floating-point operations, or SIMD operations such as |
| MMX or Sun's VIS. |
| |
| <p> Using floating-point operations is interesting but somewhat tricky. |
| Since IEEE double has 53 bit of mantissa, one has to split the operands |
| in small pieces, so that no result is greater than 2^53. For 32-bit |
| computers, splitting one operand into 16-bit pieces works. For 64-bit |
| machines, one operand can be split into 21-bit pieces and the other into |
| 32-bit pieces. (A 64-bit operand can be split into just three 21-bit |
| pieces if one allows the split operands to be negative!) |
| |
| |
| <li> <strong>Math functions for the mpf layer</strong> |
| |
| <p> Implement the functions of math.h for the GMP mpf layer! Check the book |
| "Pi and the AGM" by Borwein and Borwein for ideas how to do this. These |
| functions are desirable: acos, acosh, asin, asinh, atan, atanh, atan2, |
| cos, cosh, exp, log, log10, pow, sin, sinh, tan, tanh. |
| |
| |
| <li> <strong>Faster sqrt</strong> |
| |
| <p> The current code uses divisions, which are reasonably fast, but it'd be |
| possible to use only multiplications by computing 1/sqrt(A) using this |
| formula: |
| <pre> |
| 2 |
| x = x (3 − A x )/2 |
| i+1 i i </pre> |
| The square root can then be computed like this: |
| <pre> |
| sqrt(A) = A x |
| n </pre> |
| <p> That final multiply might be the full size of the input (though it might |
| only need the high half of that), so there may or may not be any speedup |
| overall. |
| |
| <p> We should probably allow a special exponent-like parameter, to speed |
| computations of a precise square root of a small number in mpf. |
| |
| |
| <li> <strong>Nth root</strong> |
| |
| <p> Improve mpn_rootrem. The current code is not to bad, but its average |
| time complexity is a function of the input, while it is possible to |
| make it a function of the output. |
| |
| |
| <li> <strong>Exceptions</strong> |
| |
| <p> Some sort of scheme for exceptions handling would be desirable. |
| Presently the only thing documented is that divide by zero in GMP |
| functions provokes a deliberate machine divide by zero (on those systems |
| where such a thing exists at least). The global <code>gmp_errno</code> |
| is not actually documented, except for the old <code>gmp_randinit</code> |
| function. Being currently just a plain global means it's not |
| thread-safe. |
| |
| <p> The basic choices for exceptions are returning an error code or having a |
| handler function to be called. The disadvantage of error returns is they |
| have to be checked, leading to tedious and rarely executed code, and |
| strictly speaking such a scheme wouldn't be source or binary compatible. |
| The disadvantage of a handler function is that a <code>longjmp</code> or |
| similar recovery from it may be difficult. A combination would be |
| possible, for instance by allowing the handler to return an error code. |
| |
| <p> Divide-by-zero, sqrt-of-negative, and similar operand range errors can |
| normally be detected at the start of functions, so exception handling |
| would have a clean state. What's worth considering though is that the |
| GMP function detecting the exception may have been called via some third |
| party library or self contained application module, and hence have |
| various bits of state to be cleaned up above it. It'd be highly |
| desirable for an exceptions scheme to allow for such cleanups. |
| |
| <p> The C++ destructor mechanism could help with cleanups both internally and |
| externally, but being a plain C library we don't want to depend on that. |
| |
| <p> A C++ <code>throw</code> might be a good optional extra exceptions |
| mechanism, perhaps under a build option. For |
| GCC <code>-fexceptions</code> will add the necessary frame information to |
| plain C code, or GMP could be compiled as C++. |
| |
| <p> Out-of-memory exceptions are expected to be handled by the |
| <code>mp_set_memory_functions</code> routines, rather than being a |
| prospective part of divide-by-zero etc. Some similar considerations |
| apply but what differs is that out-of-memory can arise deep within GMP |
| internals. Even fundamental routines like <code>mpn_add_n</code> and |
| <code>mpn_addmul_1</code> can use temporary memory (for instance on Cray |
| vector systems). Allowing for an error code return would require an |
| awful lot of checking internally. Perhaps it'd still be worthwhile, but |
| it'd be a lot of changes and the extra code would probably be rather |
| rarely executed in normal usages. |
| |
| <p> A <code>longjmp</code> recovery for out-of-memory will currently, in |
| general, lead to memory leaks and may leave GMP variables operated on in |
| inconsistent states. Maybe it'd be possible to record recovery |
| information for use by the relevant allocate or reallocate function, but |
| that too would be a lot of changes. |
| |
| <p> One scheme for out-of-memory would be to note that all GMP allocations go |
| through the <code>mp_set_memory_functions</code> routines. So if the |
| application has an intended <code>setjmp</code> recovery point it can |
| record memory activity by GMP and abandon space allocated and variables |
| initialized after that point. This might be as simple as directing the |
| allocation functions to a separate pool, but in general would have the |
| disadvantage of needing application-level bookkeeping on top of the |
| normal system <code>malloc</code>. An advantage however is that it needs |
| nothing from GMP itself and on that basis doesn't burden applications not |
| needing recovery. Note that there's probably some details to be worked |
| out here about reallocs of existing variables, and perhaps about copying |
| or swapping between "permanent" and "temporary" variables. |
| |
| <p> Applications desiring a fine-grained error control, for instance a |
| language interpreter, would very possibly not be well served by a scheme |
| requiring <code>longjmp</code>. Wrapping every GMP function call with a |
| <code>setjmp</code> would be very inconvenient. |
| |
| <p> Another option would be to let <code>mpz_t</code> etc hold a sort of NaN, |
| a special value indicating an out-of-memory or other failure. This would |
| be similar to NaNs in mpfr. Unfortunately such a scheme could only be |
| used by programs prepared to handle such special values, since for |
| instance a program waiting for some condition to be satisfied could |
| become an infinite loop if it wasn't also watching for NaNs. The work to |
| implement this would be significant too, lots of checking of inputs and |
| intermediate results. And if <code>mpn</code> routines were to |
| participate in this (which they would have to internally) a lot of new |
| return values would need to be added, since of course there's no |
| <code>mpz_t</code> etc structure for them to indicate failure in. |
| |
| <p> Stack overflow is another possible exception, but perhaps not one that |
| can be easily detected in general. On i386 GNU/Linux for instance GCC |
| normally doesn't generate stack probes for an <code>alloca</code>, but |
| merely adjusts <code>%esp</code>. A big enough <code>alloca</code> can |
| miss the stack redzone and hit arbitrary data. GMP stack usage is |
| normally a function of operand size, which might be enough for some |
| applications to know they'll be safe. Otherwise a fixed maximum usage |
| can probably be obtained by building with |
| <code>--enable-alloca=malloc-reentrant</code> (or |
| <code>notreentrant</code>). Arranging the default to be |
| <code>alloca</code> only on blocks up to a certain size and |
| <code>malloc</code> thereafter might be a better approach and would have |
| the advantage of not having calculations limited by available stack. |
| |
| <p> Actually recovering from stack overflow is of course another problem. It |
| might be possible to catch a <code>SIGSEGV</code> in the stack redzone |
| and do something in a <code>sigaltstack</code>, on systems which have |
| that, but recovery might otherwise not be possible. This is worth |
| bearing in mind because there's no point worrying about tight and careful |
| out-of-memory recovery if an out-of-stack is fatal. |
| |
| <p> Operand overflow is another exception to be addressed. It's easy for |
| instance to ask <code>mpz_pow_ui</code> for a result bigger than an |
| <code>mpz_t</code> can possibly represent. Currently overflows in limb |
| or byte count calculations will go undetected. Often they'll still end |
| up asking the memory functions for blocks bigger than available memory, |
| but that's by no means certain and results are unpredictable in general. |
| It'd be desirable to tighten up such size calculations. Probably only |
| selected routines would need checks, if it's assumed say that no input |
| will be more than half of all memory and hence size additions like say |
| <code>mpz_mul</code> won't overflow. |
| |
| |
| <li> <strong>Performance Tool</strong> |
| |
| <p> It'd be nice to have some sort of tool for getting an overview of |
| performance. Clearly a great many things could be done, but some primary |
| uses would be, |
| |
| <ol> |
| <li> Checking speed variations between compilers. |
| <li> Checking relative performance between systems or CPUs. |
| </ol> |
| |
| <p> A combination of measuring some fundamental routines and some |
| representative application routines might satisfy these. |
| |
| <p> The tune/time.c routines would be the easiest way to get good accurate |
| measurements on lots of different systems. The high level |
| <code>speed_measure</code> may or may not suit, but the basic |
| <code>speed_starttime</code> and <code>speed_endtime</code> would cover |
| lots of portability and accuracy questions. |
| |
| |
| <li> <strong>Using <code>restrict</code></strong> |
| |
| <p> There might be some value in judicious use of C99 style |
| <code>restrict</code> on various pointers, but this would need some |
| careful thought about what it implies for the various operand overlaps |
| permitted in GMP. |
| |
| <p> Rumour has it some pre-C99 compilers had <code>restrict</code>, but |
| expressing tighter (or perhaps looser) requirements. Might be worth |
| investigating that before using <code>restrict</code> unconditionally. |
| |
| <p> Loops are presumably where the greatest benefit would be had, by allowing |
| the compiler to advance reads ahead of writes, perhaps as part of loop |
| unrolling. However critical loops are generally coded in assembler, so |
| there might not be very much to gain. And on Cray systems the explicit |
| use of <code>_Pragma</code> gives an equivalent effect. |
| |
| <p> One thing to note is that Microsoft C headers (on ia64 at least) contain |
| <code>__declspec(restrict)</code>, so a <code>#define</code> of |
| <code>restrict</code> should be avoided. It might be wisest to setup a |
| <code>gmp_restrict</code>. |
| |
| |
| <li> <strong>Nx1 Division</strong> |
| |
| <p> The limb-by-limb dependencies in the existing Nx1 division (and |
| remainder) code means that chips with multiple execution units or |
| pipelined multipliers are not fully utilized. |
| |
| <p> One possibility is to follow the current preinv method but taking two |
| limbs at a time. That means a 2x2->4 and a 2x1->2 multiply for |
| each two limbs processed, and because the 2x2 and 2x1 can each be done in |
| parallel the latency will be not much more than 2 multiplies for two |
| limbs, whereas the single limb method has a 2 multiply latency for just |
| one limb. A version of <code>mpn_divrem_1</code> doing this has been |
| written in C, but not yet tested on likely chips. Clearly this scheme |
| would extend to 3x3->9 and 3x1->3 etc, though with diminishing |
| returns. |
| |
| <p> For <code>mpn_mod_1</code>, Peter L. Montgomery proposes the following |
| scheme. For a limb R=2^<code>bits_per_mp_limb</code>, pre-calculate |
| values R mod N, R^2 mod N, R^3 mod N, R^4 mod N. Then take dividend |
| limbs and multiply them by those values, thereby reducing them (moving |
| them down) by the corresponding factor. The products can be added to |
| produce an intermediate remainder of 2 or 3 limbs to be similarly |
| included in the next step. The point is that such multiplies can be done |
| in parallel, meaning as little as 1 multiply worth of latency for 4 |
| limbs. If the modulus N is less than R/4 (or is it R/5?) the summed |
| products will fit in 2 limbs, otherwise 3 will be required, but with the |
| high only being small. Clearly this extends to as many factors of R as a |
| chip can efficiently apply. |
| |
| <p> The logical conclusion for powers R^i is a whole array "p[i] = R^i mod N" |
| for i up to k, the size of the dividend. This could then be applied at |
| multiplier throughput speed like an inner product. If the powers took |
| roughly k divide steps to calculate then there'd be an advantage any time |
| the same N was used three or more times. Suggested by Victor Shoup in |
| connection with chinese-remainder style decompositions, but perhaps with |
| other uses. |
| |
| <p> <code>mpn_modexact_1_odd</code> calculates an x in the range 0<=x<d |
| satisfying a = q*d + x*b^n, where b=2^bits_per_limb. The factor b^n |
| needed to get the true remainder r could be calculated by a powering |
| algorithm, allowing <code>mpn_modexact_1_odd</code> to be pressed into |
| service for an <code>mpn_mod_1</code>. <code>modexact_1</code> is |
| simpler and on some chips can run noticeably faster than plain |
| <code>mod_1</code>, on Athlon for instance 11 cycles/limb instead of 17. |
| Such a difference could soon overcome the time to calculate b^n. The |
| requirement for an odd divisor in <code>modexact</code> can be handled by |
| some shifting on-the-fly, or perhaps by an extra partial-limb step at the |
| end. |
| |
| |
| <li> <strong>Factorial</strong> |
| |
| <p> The removal of twos in the current code could be extended to factors of 3 |
| or 5. Taking this to its logical conclusion would be a complete |
| decomposition into powers of primes. The power for a prime p is of |
| course floor(n/p)+floor(n/p^2)+... Conrad Curry found this is quite fast |
| (using simultaneous powering as per Handbook of Applied Cryptography |
| algorithm 14.88). |
| |
| <p> A difficulty with using all primes is that quite large n can be |
| calculated on a system with enough memory, larger than we'd probably want |
| for a table of primes, so some sort of sieving would be wanted. Perhaps |
| just taking out the factors of 3 and 5 would give most of the speedup |
| that a prime decomposition can offer. |
| |
| |
| <li> <strong>Binomial Coefficients</strong> |
| |
| <p> An obvious improvement to the current code would be to strip factors of 2 |
| from each multiplier and divisor and count them separately, to be applied |
| with a bit shift at the end. Factors of 3 and perhaps 5 could even be |
| handled similarly. |
| |
| <p> Conrad Curry reports a big speedup for binomial coefficients using a |
| prime powering scheme, at least for k near n/2. Of course this is only |
| practical for moderate size n since again it requires primes up to n. |
| |
| <p> When k is small the current (n-k+1)...n/1...k will be fastest. Some sort |
| of rule would be needed for when to use this or when to use prime |
| powering. Such a rule will be a function of both n and k. Some |
| investigation is needed to see what sort of shape the crossover line will |
| have, the usual parameter tuning can of course find machine dependent |
| constants to fill in where necessary. |
| |
| <p> An easier possibility also reported by Conrad Curry is that it may be |
| faster not to divide out the denominator (1...k) one-limb at a time, but |
| do one big division at the end. Is this because a big divisor in |
| <code>mpn_bdivmod</code> trades the latency of |
| <code>mpn_divexact_1</code> for the throughput of |
| <code>mpn_submul_1</code>? Overheads must hurt though. |
| |
| <p> Another reason a big divisor might help is that |
| <code>mpn_divexact_1</code> won't be getting a full limb in |
| <code>mpz_bin_uiui</code>. It's called when the n accumulator is full |
| but the k may be far from full. Perhaps the two could be decoupled so k |
| is applied when full. It'd be necessary to delay consideration of k |
| terms until the corresponding n terms had been applied though, since |
| otherwise the division won't be exact. |
| |
| |
| <li> <strong>Perfect Power Testing</strong> |
| |
| <p> <code>mpz_perfect_power_p</code> could be improved in a number of ways, |
| for instance p-adic arithmetic to find possible roots. |
| |
| <p> Non-powers can be quickly identified by checking for Nth power residues |
| modulo small primes, like <code>mpn_perfect_square_p</code> does for |
| squares. The residues to each power N for a given remainder could be |
| grouped into a bit mask, the masks for the remainders to each divisor |
| would then be "and"ed together to hopefully leave only a few candidate |
| powers. Need to think about how wide to make such masks, ie. how many |
| powers to examine in this way. |
| |
| <p> Any zero remainders found in residue testing reveal factors which can be |
| divided out, with the multiplicity restricting the powers that need to be |
| considered, as per the current code. Further prime dividing should be |
| grouped into limbs like <code>PP</code>. Need to think about how much |
| dividing to do like that, probably more for bigger inputs, less for |
| smaller inputs. |
| |
| <p> <code>mpn_gcd_1</code> would probably be better than the current private |
| GCD routine. The use it's put to isn't time-critical, and it might help |
| ensure correctness to just use the main GCD routine. |
| |
| <p> [There is work-in-progress with a very fast function.] |
| |
| |
| <li> <strong>Prime Testing</strong> |
| |
| <p> GMP is not really a number theory library and probably shouldn't have |
| large amounts of code dedicated to sophisticated prime testing |
| algorithms, but basic things well-implemented would suit. Tests offering |
| certainty are probably all too big or too slow (or both!) to justify |
| inclusion in the main library. Demo programs showing some possibilities |
| would be good though. |
| |
| <p> The present "repetitions" argument to <code>mpz_probab_prime_p</code> is |
| rather specific to the Miller-Rabin tests of the current implementation. |
| Better would be some sort of parameter asking perhaps for a maximum |
| chance 1/2^x of a probable prime in fact being composite. If |
| applications follow the advice that the present reps gives 1/4^reps |
| chance then perhaps such a change is unnecessary, but an explicitly |
| described 1/2^x would allow for changes in the implementation or even for |
| new proofs about the theory. |
| |
| <p> <code>mpz_probab_prime_p</code> always initializes a new |
| <code>gmp_randstate_t</code> for randomized tests, which unfortunately |
| means it's not really very random and in particular always runs the same |
| tests for a given input. Perhaps a new interface could accept an rstate |
| to use, so successive tests could increase confidence in the result. |
| |
| <p> <code>mpn_mod_34lsub1</code> is an obvious and easy improvement to the |
| trial divisions. And since the various prime factors are constants, the |
| remainder can be tested with something like |
| <pre> |
| #define MP_LIMB_DIVISIBLE_7_P(n) \ |
| ((n) * MODLIMB_INVERSE_7 <= MP_LIMB_T_MAX/7) |
| </pre> |
| Which would help compilers that don't know how to optimize divisions by |
| constants, and is even an improvement on current gcc 3.2 code. This |
| technique works for any modulus, see Granlund and Montgomery "Division by |
| Invariant Integers" section 9. |
| |
| <p> The trial divisions are done with primes generated and grouped at |
| runtime. This could instead be a table of data, with pre-calculated |
| inverses too. Storing deltas, ie. amounts to add, rather than actual |
| primes would save space. <code>udiv_qrnnd_preinv</code> style inverses |
| can be made to exist by adding dummy factors of 2 if necessary. Some |
| thought needs to be given as to how big such a table should be, based on |
| how much dividing would be profitable for what sort of size inputs. The |
| data could be shared by the perfect power testing. |
| |
| <p> Jason Moxham points out that if a sqrt(-1) mod N exists then any factor |
| of N must be == 1 mod 4, saving half the work in trial dividing. (If |
| x^2==-1 mod N then for a prime factor p we have x^2==-1 mod p and so the |
| jacobi symbol (-1/p)=1. But also (-1/p)=(-1)^((p-1)/2), hence must have |
| p==1 mod 4.) But knowing whether sqrt(-1) mod N exists is not too easy. |
| A strong pseudoprime test can reveal one, so perhaps such a test could be |
| inserted part way though the dividing. |
| |
| <p> Jon Grantham "Frobenius Pseudoprimes" (www.pseudoprime.com) describes a |
| quadratic pseudoprime test taking about 3x longer than a plain test, but |
| with only a 1/7710 chance of error (whereas 3 plain Miller-Rabin tests |
| would offer only (1/4)^3 == 1/64). Such a test needs completely random |
| parameters to satisfy the theory, though single-limb values would run |
| faster. It's probably best to do at least one plain Miller-Rabin before |
| any quadratic tests, since that can identify composites in less total |
| time. |
| |
| <p> Some thought needs to be given to the structure of which tests (trial |
| division, Miller-Rabin, quadratic) and how many are done, based on what |
| sort of inputs we expect, with a view to minimizing average time. |
| |
| <p> It might be a good idea to break out subroutines for the various tests, |
| so that an application can combine them in ways it prefers, if sensible |
| defaults in <code>mpz_probab_prime_p</code> don't suit. In particular |
| this would let applications skip tests it knew would be unprofitable, |
| like trial dividing when an input is already known to have no small |
| factors. |
| |
| <p> For small inputs, combinations of theory and explicit search make it |
| relatively easy to offer certainty. For instance numbers up to 2^32 |
| could be handled with a strong pseudoprime test and table lookup. But |
| it's rather doubtful whether a smallnum prime test belongs in a bignum |
| library. Perhaps if it had other internal uses. |
| |
| <p> An <code>mpz_nthprime</code> might be cute, but is almost certainly |
| impractical for anything but small n. |
| |
| |
| <li> <strong>Intra-Library Calls</strong> |
| |
| <p> On various systems, calls within libgmp still go through the PLT, TOC or |
| other mechanism, which makes the code bigger and slower than it needs to |
| be. |
| |
| <p> The theory would be to have all GMP intra-library calls resolved directly |
| to the routines in the library. An application wouldn't be able to |
| replace a routine, the way it can normally, but there seems no good |
| reason to do that, in normal circumstances. |
| |
| <p> The <code>visibility</code> attribute in recent gcc is good for this, |
| because it lets gcc omit unnecessary GOT pointer setups or whatever if it |
| finds all calls are local and there's no global data references. |
| Documented entrypoints would be <code>protected</code>, and purely |
| internal things not wanted by test programs or anything can be |
| <code>internal</code>. |
| |
| <p> Unfortunately, on i386 it seems <code>protected</code> ends up causing |
| text segment relocations within libgmp.so, meaning the library code can't |
| be shared between processes, defeating the purpose of a shared library. |
| Perhaps this is just a gremlin in binutils (debian packaged |
| 2.13.90.0.16-1). |
| |
| <p> The linker can be told directly (with a link script, or options) to do |
| the same sort of thing. This doesn't change the code emitted by gcc of |
| course, but it does mean calls are resolved directly to their targets, |
| avoiding a PLT entry. |
| |
| <p> Keeping symbols private to libgmp.so is probably a good thing in general |
| too, to stop anyone even attempting to access them. But some |
| undocumented things will need or want to be kept visible, for use by |
| mpfr, or the test and tune programs. Libtool has a standard option for |
| selecting public symbols (used now for libmp). |
| |
| |
| </ul> |
| <hr> |
| |
| </body> |
| </html> |
| |
| <!-- |
| Local variables: |
| eval: (add-hook 'write-file-hooks 'time-stamp) |
| time-stamp-start: "This file current as of " |
| time-stamp-format: "%:d %3b %:y" |
| time-stamp-end: "\\." |
| time-stamp-line-limit: 50 |
| End: |
| --> |
