Annotation of OpenXM_contrib/gmp/doc/projects.html, Revision 1.1
1.1 ! maekawa 1: <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
! 2: <html>
! 3: <head>
! 4: <title>
! 5: GMP Development Projects
! 6: </title>
! 7: </head>
! 8: <body bgcolor=pink>
! 9:
! 10: <center>
! 11: <h1>
! 12: GMP Development Projects
! 13: </h1>
! 14: </center>
! 15:
! 16: <comment>
! 17: An up-to-date version of this file is available at
! 18: <a href="http://www.swox.com/gmp/projects.html">http://www.swox.com/gmp/projects.html</a>.
! 19: </comment>
! 20:
! 21: <p> This file lists projects suitable for volunteers. Please see the
! 22: <a href="tasks.html">tasks file</a> for smaller tasks.
! 23:
! 24: <p> If you want to work on any of the projects below, please let tege@swox.com
! 25: know. If you want to help with a project that already somebody else is
! 26: working on, please talk to that person too, tege@swox.com can put you in
! 27: touch. (There are no email addresses of volunteers below, due to spamming
! 28: problems.)
! 29:
! 30: <ul>
! 31: <li> <strong>C++ wrapper</strong>
! 32:
! 33: <p> A C++ wrapper for GMP is highly desirable. Several people have started
! 34: writing one, but nobody has so far finished it. For a wrapper to be useful,
! 35: one needs to pay attention to efficiency.
! 36:
! 37: <ol>
! 38: <li> Write arithmetic functions for direct applications of most
! 39: elementary C++ types. This might be necessary to avoid
! 40: ambiguities, but it is also desirable from an efficiency
! 41: standpoint.
! 42: <li> Avoid running constructors/destructors when not necessary.
! 43: For example, implement <code>a += b</code> by directly applying mpz_add.
! 44: </ol>
! 45:
! 46: <p> <li> <strong>Faster multiplication</strong>
! 47:
! 48: <p> The current multiplication code uses Karatsuba, 3-way Toom-Cook,
! 49: or Fermat FFT. Several new developments are desirable:
! 50:
! 51: <ol>
! 52: <li> Handle multiplication of operands with different digit count
! 53: better than today. We now split the operands in a very
! 54: inefficient way, see mpn/generic/mul.c.
! 55:
! 56: <li> Consider N-way Toom-Cook. See Knuth's Seminumerical
! 57: Algorithms for details on the method. Code implementing it
! 58: exists. This is asymptotically inferior to FFTs, but is finer
! 59: grained. A toom-4 might fit in between toom-3 and the FFTs
! 60: (or it might not).
! 61:
! 62: <li> It's possible CPU dependent effects like cache locality will
! 63: have a greater impact on speed than algorithmic improvements.
! 64:
! 65: </ol>
! 66:
! 67:
! 68: <p> <li> <strong>Assembly routines</strong>
! 69:
! 70: <p> Write new and tune existing assembly routines. The programs in mpn/tests
! 71: and the tune/speed.c program are useful for testing and timing the routines
! 72: you write. See the README files in those directories for more information.
! 73:
! 74: <p> Please make sure your new routines are fast for these three situations:
! 75: <ol>
! 76: <li> Operands that fit into the cache.
! 77: <li> Small operands of less than, say, 10 limbs.
! 78: <li> Huge operands that does not fit into the cache.
! 79: </ol>
! 80:
! 81: <p> The most important routines are mpn_addmul_1, mpn_mul_basecase and
! 82: mpn_sqr_basecase. The latter two don't exist for all machines, while
! 83: mpn_addmul_1 exists for almost all machines.
! 84:
! 85: <p> Standard techniques for these routines are unrolling, software
! 86: pipelining, and specialization for common operand values. For machines with
! 87: poor integer multiplication, it is often possible to improve the performance
! 88: using floating-point operations, or SIMD operations such as MMX or Sun's VIS.
! 89:
! 90: <p> Using floating-point operations is interesting but somewhat tricky.
! 91: Since IEEE double has 53 bit of mantissa, one has to split the operands in
! 92: small prices, so that no result is greater than 2^53. For 32-bit computers,
! 93: splitting one operand into 16-bit pieces works. For 64-bit machines, one
! 94: operand can be split into 21-bit pieces and the other into 32-bit pieces. (A
! 95: 64-bit operand can be split into just three 21-bit pieces if one allows the
! 96: split operands to be negative!)
! 97:
! 98:
! 99: <p> <li> <strong>Faster extended GCD</strong>
! 100:
! 101: <p> We currently have extended GCD based on Lehmer's method.
! 102: But the binary method can quite easily be improved for bignums
! 103: in a similar way Lehmer improved Euclid's algorithm. The result should
! 104: beat Lehmer's method by about a factor of 2. Furthermore, the multiprecision
! 105: step of Lehmer's method and the binary method will be identical, so the
! 106: current code can mostly be reused. It should be possible to share code
! 107: between GCD and GCDEXT, and probably with Jacobi symbols too.
! 108:
! 109: <p> <li> <strong>Math functions for the mpf layer</strong>
! 110:
! 111: <p> Implement the functions of math.h for the GMP mpf layer! Check the book
! 112: "Pi and the AGM" by Borwein and Borwein for ideas how to do this. These
! 113: functions are desirable: acos, acosh, asin, asinh, atan, atanh, atan2, cos,
! 114: cosh, exp, log, log10, pow, sin, sinh, tan, tanh.
! 115:
! 116: <p> <li> <strong>Faster sqrt</strong>
! 117:
! 118: <p> The current code for computing square roots use a Newton iteration that
! 119: rely on division. It is possible to avoid using division by computing
! 120: 1/sqrt(A) using this formula:
! 121: <pre>
! 122: 2
! 123: x = x (3 - A x )/2.
! 124: i+1 i i </pre>
! 125: The final result is then computed without division using,
! 126: <pre>
! 127: sqrt(A) = A x .
! 128: n </pre>
! 129: The resulting code should be substantially faster than the current code.
! 130:
! 131: <p> <li> <strong>Nth root</strong>
! 132:
! 133: <p> Implement, at the mpn level, a routine for computing the nth root of a
! 134: number. The routine should use Newton's method, preferably without using
! 135: division.
! 136:
! 137: <p> If the routine becomes fast enough, perhaps square roots could be computed
! 138: using this function.
! 139:
! 140: <p> <li> <strong>More random number generators</strong>
! 141:
! 142: <p> Implement some more pseudo random number generator algorithms.
! 143: Today there's only Linear Congruential.
! 144:
! 145:
! 146: <p> <li> <strong>Test Suite</strong>
! 147:
! 148: <p> Add a test suite for old bugs. These tests wouldn't loop or use
! 149: random numbers, but just test for specific bugs found in the
! 150: past.
! 151:
! 152: <p> More importantly, improve the random number controls for test
! 153: collections:
! 154:
! 155: <ol>
! 156: <li> Use the new random number framework.
! 157: <li> Have every test accept a seed parameter.
! 158: <li> Allow `make check' to set the seed parameter.
! 159: <li> Add more tests for important, now untested functions.
! 160: </ol>
! 161:
! 162: <p> With this in place, it should be possible to rid GMP of
! 163: practically all bugs by having some dedicated GMP test machines
! 164: running "make check" with ever increasing seeds (and
! 165: periodically updating to the latest GMP).
! 166:
! 167: <p> If a few more ASSERTs were sprinkled through the code, running
! 168: some tests with --enable-assert might be useful, though not a
! 169: substitute for tests on the normal build.
! 170:
! 171: <p> An important feature of any random tests will be to record the
! 172: seeds used, and perhaps to snapshot operands before performing
! 173: each test, so any problem exposed can be reproduced.
! 174:
! 175: </ul>
! 176:
! 177: <hr>
! 178:
! 179: <table width="100%">
! 180: <tr>
! 181: <td>
! 182: <font size=2>
! 183: Please send comments about this page to
! 184: <a href="mailto:tege@swox.com">tege@swox.com</a>.<br>
! 185: Copyright (C) 1999, 2000 Torbjörn Granlund.
! 186: </font>
! 187: </td>
! 188: <td align=right>
! 189: </td>
! 190: </tr>
! 191: </table>
! 192:
! 193: </body>
! 194: </html>
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to projects.html CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / gmp / doc