=gmp

gmp is library providing Ruby bindings to GMP library. Here is the introduction
paragraph at http://gmplib.org/#WHAT :

* "GMP is a free library for arbitrary precision arithmetic, operating on
  signed integers, rational numbers, and floating point numbers. There is no
  practical limit to the precision except the ones implied by the available
  memory in the machine GMP runs on. GMP has a rich set of functions, and the
  functions have a regular interface.

* The main target applications for GMP are cryptography applications and
  research, Internet security applications, algebra systems, computational
  algebra research, etc.

* GMP is carefully designed to be as fast as possible, both for small operands
  and for huge operands. The speed is achieved by using fullwords as the basic
  arithmetic type, by using fast algorithms, with highly optimised assembly
  code for the most common inner loops for a lot of CPUs, and by a general
  emphasis on speed.

* GMP is faster than any other bignum library. The advantage for GMP increases
  with the operand sizes for many operations, since GMP uses asymptotically
  faster algorithms.

* The first GMP release was made in 1991. It is continually developed and
  maintained, with a new release about once a year.

* GMP is distributed under the GNU LGPL. This license makes the library free to
  use, share, and improve, and allows you to pass on the result. The license
  gives freedoms, but also sets firm restrictions on the use with non-free
  programs.

* GMP is part of the GNU project. For more information about the GNU project,
  please see the official GNU web site.

* GMP's main target platforms are Unix-type systems, such as GNU/Linux,
  Solaris, HP-UX, Mac OS X/Darwin, BSD, AIX, etc. It also is known to work on
  Windoze in 32-bit mode.

* GMP is brought to you by a team listed in the manual.

* GMP is carefully developed and maintained, both technically and legally. We
  of course inspect and test contributed code carefully, but equally
  importantly we make sure we have the legal right to distribute the
  contributions, meaning users can safely use GMP. To achieve this, we will ask
  contributors to sign paperwork where they allow us to distribute their work."

Only GMP 4 or newer is supported. The following environments have been tested
by me: gmp gem 0.4.0 on:
  +-------------------------------------+-------------------+-----------+
  |    Platform                         |       Ruby        |    GMP    |
  +-------------------------------------+-------------------+-----------+
  | Cygwin 1.7 on x86                   | (MRI) Ruby 1.8.7  | GMP 4.3.1 |
  |                                     |                   | GMP 4.3.2 |
  |                                     |                   | GMP 5.0.0 |
  |-------------------------------------+-------------------+-----------|
  | Windows XP on x86                   | (MRI) Ruby 1.9.1  | GMP 5.0.1 |
  |-------------------------------------+-------------------+-----------|
  | Linux (LinuxMint 7) on x86 (32-bit) | (MRI) Ruby 1.8.7  | GMP 4.3.1 |
  |-------------------------------------+-------------------+-----------|
  | Mac OS X 10.5.7 on x86 (32-bit)     | (MRI) Ruby 1.8.6  | GMP 4.3.1 |
  |                                     | (MRI) Ruby 1.9.1  |           |
  +-------------------------------------+-------------------+-----------+

<b>Note:</b> To get this running on Mac OS X (32-bit), I compiled GMP 4.3.1
with:
  ./configure ABI=32 --disable-dependency-tracking

=Authors

* Tomasz Wegrzanowski
* srawlins

=Constants

The GMP module includes the following constants. Mathematical constants, such
as pi, are defined under class methods of GMP::F, listed below.

  GMP::GMP_VERSION        #=> A string like "5.0.1"
  GMP::GMP_CC             #=> The compiler used to compile GMP
  GMP::GMP_CFLAGS         #=> The CFLAGS used to compile GMP
  GMP::GMP_BITS_PER_LIMB  #=> The number of bits per limb
  (if MPFR is available)
  GMP::MPFR_VERSION       #=> A string like "2.4.2"
  GMP::GMP_RNDN           #=> The constant representing "round to nearest"
  GMP::GMP_RNDZ           #=> The constant representing "round toward zero"
  GMP::GMP_RNDU           #=> The constant representing "round toward plus infinity"
  GMP::GMP_RNDD           #=> The constant representing "round toward minus infinity"

=Classes

The GMP module is provided with following classes:
* GMP::Z - infinite precision integer numbers
* GMP::Q - infinite precision rational numbers
* GMP::F - arbitrary precision floating point numbers
* GMP::RandState - states of individual random number generators

Numbers are created by using new().
Constructors can take following arguments:

  GMP::Z.new()
  GMP::Z.new(GMP::Z)
  GMP::Z.new(Fixnum)
  GMP::Z.new(Bignum)
  GMP::Z.new(String)
  GMP::Q.new()
  GMP::Q.new(GMP::Q)
  GMP::Q.new(String)
  GMP::Q.new(any GMP::Z initializer)
  GMP::Q.new(any GMP::Z initializer, any GMP::Z initializer)
  GMP::F.new()
  GMP::F.new(GMP::Z, precision=0)
  GMP::F.new(GMP::Q, precision=0)
  GMP::F.new(GMP::F)
  GMP::F.new(GMP::F, precision)
  GMP::F.new(String, precision=0)
  GMP::F.new(Fixnum, precision=0)
  GMP::F.new(Bignum, precision=0)
  GMP::F.new(Float,  precision=0)
  GMP::RandState.new([algorithm] [, algorithm_args])

You can also call them as:
  GMP.Z(args)
  GMP.Q(args)
  GMP.F(args)
  GMP.RandState()

=Methods

  GMP::Z, GMP::Q and GMP::F
    +                        addition
    -                        substraction
    *                        multiplication
    to_s                     convert to string. For GMP::Z, this method takes
                             one optional argument, a base. The base can be a
                             Fixnum in the ranges [2, 62] or [-36, -2] or a
                             Symbol: :bin, :oct, :dec, or :hex.
    -@                       negation
    neg!                     in-place negation
    abs                      absolute value
    asb!                     in-place absolute value
    coerce                   promotion of arguments
    ==                       equality test
    <=>,>=,>,<=,<            comparisions
  class methods of GMP::Z
    fac(n)                   factorial of n
    fib(n)                   nth fibonacci number
    pow(n,m)                 n to mth power
  GMP::Z and GMP::Q
    swap                     efficiently swap contents of two objects, there
                             is no GMP::F.swap because various GMP::F objects
                             may have different precisions, which would make
                             them unswapable
  GMP::Z
    add!                     in-place addition
    sub!                     in-place subtraction
    tdiv,fdiv,cdiv           truncate, floor and ceil division
    tmod,fmod,cmod           truncate, floor and ceil modulus
    [],[]=                   testing and setting bits (as booleans)
    scan0,scan1              starting at bitnr (1st arg), scan for a 0 or 1
                             (respectively), then return the index of the
                             first instance.
    com                      2's complement
    com!                     in-place 2's complement
    &,|,^                    logical operations: and, or, xor
    **                       power
    powmod                   power modulo
    even?                    is even
    odd?                     is odd
    <<                       shift left
    >>                       shift right, floor
    tshr                     shift right, truncate
    lastbits_pos(n)          last n bits of object, modulo if negative
    lastbits_sgn(n)          last n bits of object, preserve sign
    power?                   is perfect power
    square?                  is perfect square
    sqrt                     square root
    sqrt!                    change the object into its square root
    sqrtrem                  square root, remainder
    root(n)                  nth root
    probab_prime?            0 if composite, 1 if probably prime, 2 if
                             certainly prime
    nextprime                next *probable* prime
    nextprime!               change the object into its next *probable* prime
    gcd                      greatest common divisor
    invert(m)                invert mod m
    jacobi                   jacobi symbol
    legendre                 legendre symbol
    remove(n)                remove all occurences of factor n
    popcount                 the number of bits equal to 1
    sizeinbase(b)            digits in base b
    size_in_bin              digits in binary
    to_i                     convert to Fixnum or Bignum
  GMP::Q and GMP::F
    /                        division
  GMP::Q
    num                      numerator
    den                      denominator
    inv                      inversion
    inv!                     in-place inversion
    floor,ceil,trunc         nearest integer
  class methods of GMP::F
    default_prec             get default precision
    default_prec=            set default precision
  GMP::F
    prec                     get precision
    floor,ceil,trunc         nearest integer, GMP::F is returned, not GMP::Z
    floor!,ceil!,trunc!      in-place nearest integer
  GMP::RandState
    seed(integer)            seed the generator with a Fixnum or GMP::Z
    urandomb(fixnum)         get uniformly distributed random number between 0
                             and 2^fixnum-1, inclusive
    urandomm(integer)        get uniformly distributed random number between 0
                             and integer-1, inclusive
  GMP (timing functions for GMPbench (0.2))
    cputime                  milliseconds of cpu time since Ruby start
    time                     times the execution of a block
  
  *only if MPFR is available*
  class methods of GMP::F
    const_log2               returns the natural log of 2
    const_pi                 returns pi
    const_euler              returns euler
    const_catalan            returns catalan
  GMP::F
    sqrt                     square root of the object
    **                       power
    log                      natural logarithm of object
    log2                     binary logarithm of object
    log10                    decimal logarithm of object
    exp                      e^object
    log1p                    the same as (object + 1).log, with better
                             precision
    expm1                    the same as (object.exp) - 1, with better
                             precision
    cos                      \
    sin                      |
    tan                      |
    sec                      |
    csc                      |
    cot                      |
    acos                     |
    asin                     |
    atan                     | trigonometric functions
    cosh                     | of the object
    sinh                     |
    tanh                     |
    aconh                    |
    asinh                    |
    atanh                    /
    nan?                     \
    infinite?                | type of floating point number
    finite?                  |
    number?                  /
  GMP::RandState
    mpfr_urandomb(fixnum)    get uniformly distributed random floating-point
                             number within 0 <= rop < 1
    

=Testing

Tests can be run with:

  cd test
  ruby unit_tests.rb

If you have the unit_test gem installed, all tests should pass. Otherwise, one
test may error. I imagine there is a bug in Ruby's built-in Test::Unit package
that is fixed with the unit_test gem.

=Known Issues

* GMP::Z#pow does not appear to be working at all. Looking at the code, I don't
  think it ever did.
* Don't call GMP::RandState(:lc_2exp_size). Give a 2nd arg.

=Precision

Precision can be explicitely set as second argument for GMP::F.new().

If there is no explicit precision, highest precision of all GMP::F arguments is
used. That doesn't ensure that result will be exact. For details, consult any
paper about floating point arithmetics.

Default precision can be explicitely set by passing 0 as the second argument
for to GMP::F.new(). In particular, you can set precision of copy of GMP::F
object by:
  new_obj = GMP::F.new(old_obj, 0)

Precision argument, and default_precision will be rounded up to whatever GMP
thinks is appropriate.

=Benchmarking

"GMP is carefully designed to be as fast as possible." Therefore, I believe it
is very important for GMP, and its various language bindings to be benchmarked.
In recent years, the GMP team developed GMPbench, an elegant, weighted
benchmark. Currently, at http://www.gmplib.org/gmpbench.html they maintain a
list of recent benchmark results, broken down by CPU, CPU freq, ABI, and
compiler flags; GMPbench compares different processor's performance against
eachother, rather than GMP against other bignum libraries, or comparing
different versions of GMP.

I intend to build a plug-in to GMPbench that will test the ruby gmp gem. The
results of this benchmark should be directly comparable with the results of GMP
(on same CPU, etc.). Rather than write a benchmark from the ground up, or try
to emulate what GMPbench does, a plug-in will allow for this type of
comparison. And in fact, GMPbench is (perhaps intentionally) written perfectly
to allow for plugging in.

Various scores are derived from GMPbench by running the <tt>runbench</tt>
script. This script compiles and runs various individual programs that
measure the performance of base functions, such as multiply, and app functions
such as rsa.

The gmp gem benchmark uses the GMPbench framework (that is, runbench, gexpr,
and the timing methods), and plugs in ruby scripts as the individual programs.
Right now, there are only three such plugged in ruby scripts:

* multiply - measures performance of multiplying (or squaring) GMP::Z objects
  whose size (in bits) is given by 1 or 2 operands.
* divide - measures performance of dividing two GMP::Z objects (using tdiv)
  whose size (in bits) is given by 2 operands.
* rsa - measures performance of using RSA to sign messages. The size of pq, the
  product of the two co-prime GMP::Z objects, p and q, is given by 1 operand.
  
Results: on my little Intel Core Duo T2400 @ 1.83GHz:
  +---------------------------------------------------------+
  | GMP 4.3.1* compiled with GCC 3.4.4, I think (cygwin did |
  | it)                                                     |
  +------------+-----------+--------------------------------+
  |  test      |  GMP      |  ruby gmp gem                  |
  |  multiply  |  4660     |        2473.8  (47% overhead)  |
  |  divide    |  2744     |        2253.1  (18% overhead)  |
  |  gcd       |  1004.5   |         865.13 (14% overhead)  |
  |  rsa       |   515.49  |         506.69 ( 2% overhead)  |
  +------------+-----------+--------------------------------+
  | GMP 5.0.0 compiled with GCC 3.4.4, I think (cygwin did  |
  | it)                                                     |
  +------------+-----------+--------------------------------+
  |  test      |  GMP      |  ruby gmp gem                  |
  |  multiply  |  4905     |        2572.1  (48% overhead)  |
  |  divide    |  4873     |        3427.4  (30% overhead)  |
  |  gcd       |  1083.5   |         931.75 (14% overhead)  |
  |  rsa       |   520.20  |         506.14 ( 3% overhead)  |
  +------------+--------+-----------------------------------+
  | GMP 5.0.1 compiled with GCC 3.4.5 in MinGW              |
  +------------+-----------+--------------------------------+
  |  test      |  GMP      |  ruby gmp gem                  |
  |  multiply  |  4950     |        xxxx.x  (xx% overhead)  |
  |  divide    |  4809     |        xxxx.x  (xx% overhead)  |
  |  gcd       |  1071.3   |         xxx.xx (xx% overhead)  |
  |  rsa       |   524.96  |         xxx.xx ( x% overhead)  |
  +------------+--------+-----------------------------------+
\* GMP 4.3.2 evaluated to almost the same benchmarks.

My guess is that the increase in ruby gmp gem overhead is caused by increased
efficiency in GMP; the inefficiencies of the gmp gem are relatively greater.

=Todo

These are inherited from Tomasz. I will go through these and see which are
still relevant.

* mpz_fits_* and 31 vs. 32 integer variables
* fix all sign issues (don't know what these are)
* floats with precision control
* to_s vs. inspect
* check if mpz_addmul_ui would optimize some statements
* some system that allows using denref and numref as normal ruby objects (?)
* should we allocate global temporary variables like Perl GMP does?
* takeover code that replaces all Bignums with GMP::Z
* better bignum parser
* zero-copy method for strings generation
* put rb_raise into nice macros
* benchmarks against Python GMP (gmpy? Is this still active?) and Perl GMP
* dup methods
* integrate F into system
* should Z.[] bits be 0/1 or true/false, 0 is true, what might badly surprise users
* any2small_integer()
* check asm output, especially local memory efficiency
* it might be better to use `register' for some local variables
* powm with negative exponents
* check if different sorting of operatations gives better cache usage
* GMP::* op RubyFloat and RubyFloat op GMP::*
* sort checks
* GMP::Q.to_s(base), GMP::F.to_s(base)
* benchmark gcdext, pi