Annotation of OpenXM_contrib/gmp/doc/projects.html, Revision 1.1.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