Summer of Code 2006

[Joppe Bos]

Hello all,

This summer Google organizes the Summer of Code for the second time, see
http://code.google.com/soc. One of the participating mentor organizations
is the GNU Project. I submitted a proposal related to the GNU MP Library,
the technical details are attached to this e-mail (I removed my bio).

The deadline for submitting proposals has been expired and the selection
procedure has been started. People from the GNU Project contacted me this
week to tell me they are interested in my proposal. Every project needs a
mentor and a backup mentor, Simon Josefsson (also from the GNU Project) is
willing to become a mentor for my project but he is not part of the GMP
team. I would like to ask if someone is interested in becoming my (backup)
mentor since it would be more preferable to have a GMP developer as my
mentor.
Furthermore I would be interested about the opinions of the developers
here about my project proposal and the chances of my code, if done
correctly, to be included in the distribution.

Feel free to e-mail me private or contact James Youngman or Karl Berry at
summer-of-code at gnu.org who are answering questions related to the SoC. If
someone is interested in becoming my mentor the signup is at
http://code.google.com/soc/mentor_step1.html.

With kind regards,

Joppe Bos
-------------- next part --------------
          Project proposal for the Summer of Code 2006
          ============================================

Project title:           Improving the GNU Multiple Precision Library
Mentoring Organization:  The GNU Project
Name:                    Joppe Bos
E-mail:                  jwbos at science.uva.nl
Homepage of GNU MP:      www.swox.com/gmp/

Synopsis
---------
The GNU Multiple Precision Library is widely known to be the fastest MP
library available. Fortunately performance can always be improved. This project
proposes to improve some of the functionalities of GNU MP as described on the
larger project list by switching from algorithm. The library will also be
extended with some new functionalities, i.e. specific integer functions, to
boost the performance in specific circumstances.

Project Description
--------------------
GNU MP keeps a list of larger projects (www.swox.com/gmp/projects.html) which
indicate what functionalities in the library could theoretically be improved,
read run faster, by switching from algorithm. I am interested in implementing
a subset of these projects and in this way verify if the theoretical
optimizations result in a practical performance increase and hereby increase
the performance of the library. Here the functions from GNU MP together with a
brief description about the proposed new algorithm.

    * mpz_fac_ui   - Computing the Factorial and
    * mpz_bin_uiui - Computing the Binomial Coefficient.
      These two related function could be improved by using techniques to
      decomposite the numbers in powers of prime values and using simultaneous
      powering as per Handbook of Applied Cryptography algorithm 14.88. A start
      has been made for this new implementation and the results look very
      promising.

    * void mpf_sqrt* - Computing the square root.
      As described on the project list it is possible to compute the square root
      using only multiplications with a variant of Newton iteration
      (en.wikipedia.org/wiki/Newton%27s_method). This variant converges to the
      reciprocal of the square root of input number so one final multiplication
      is needed when this reciprocal has converged.

    * void mpz_probab_prime_p - Performing some probability prime tests.
      Currently the Miller-Rabin test is implemented with a chance a composite
      being marked as a pseudo-prime (1/4)^x, where x is the number of rounds.
      With the Frobenius test [1], which is about three times slower, this
      chance is (1/7710)^x. A fast and practical instantiation of this algorithm
      is described in [2] as Algorithm 3.5.9. This function could be extended or,
      to be more compatible, a new prime probability test function could be
      created. When implementing such a functionality all the remarks as stated
      on the project list will be kept in mind.

    * mpz_remove* - Remove all occurrences of a given factor from a given number
                    and give the result as well as the number of removed
                    occurrences back.
      This function is not on the project list but since my personal interest
      are in the field of factoring it would be fun to see if the performance
      could be improved even further, for instance with techniques as described
      in [3]. It makes sense to extend the library with a function working on
      integers (mpz_remove_ui) since this will probably result in significant
      performance increase.

When the implementation of the projects as described above goes well the above
projects will be finished before the deadline, this gives some time to complete
some smaller tasks from www.swox.com/gmp/tasks.html, for example:

    * mpz_and_ui, mpz_ior_ui, mpz_xor_ui
      Extend the library with functions working on integers for the
      bitwise operations.

    * mpz_andn, mpz_iorn, mpz_nand, mpz_nior, mpz_xnor
      Extend the library with these extra functionalities, possibly sharing
      code with the existing other binary operations.

Project Schedule
----------------
Every improved or new functionality will be delivered in the form of commented
C-code under the GNU LGPL. New functionalities will be accompanied with
documentation. When working on a specific function the work will be divided
into four parts:

(1) Reading relevant work to understand the new techniques.
(2) Searching for work that has already been done on such an implementation
    under the GNU LGPL.
(3) The actual implementation, from scratch or improving existing code.
(4) Writing a test-suite which compares the speed of the new implementation
    with the current one in GNU MP.

May 23 - May 31
  Begin project, get familiar with the GNU MP code and read the GNU coding
  conventions. When questions arise contact the mentor.

June 1 - June 16
  Working on the binomial and factorial functions simultaneously.

June 17 - June 26
  Improving mpz_remove and create mpz_remove_ui.

June 26
  Mid-program mentor evaluations of student progress. 
   - Are there any serious problems?
   - Are the new functionalities successful implemented?
   - Is there a significant performance increase?

June 27 - August 10
  Implementing the Frobenius probability prime test.

August 11 - August 20
  Improving the performance for the mpf square function.

August 21
  End, all the implementation work must be done and the performance
  of the GNU MP Library should be increased.

Brief Biography
----------------
<Removed>

Bibliography
-----------
[1] J. Grantham, "A probable prime test with high confidence",
    J. Number Theory, 72 (1998) 32-47.
[2] R. Crandall and C. Pomerance, "Prime numbers: a computational perspective",
    Springer-Verlag, New York, 2001. ISBN 0-387-94777-9.
[3] D. J. Bernstein, "Factoring into coprimes in essentially linear time",
    Journal of Algorithms 54 (2005), 1-30. URL: http://cr.yp.to/papers.html#dcba.