README.html

<h1>gmp</h1>

<p>gmp is library providing Ruby bindings to GMP library. Here is the introduction
paragraph at <a href="http://gmplib.org/#WHAT">their homepage</a>:</p>

<blockquote>
<p>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.</p>

<p>The main target applications for GMP are cryptography applications and
research, Internet security applications, algebra systems, computational
algebra research, etc.</p>

<p>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.</p>

<p>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.</p>

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

<p>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.</p>

<p>GMP is part of the GNU project. For more information about the GNU project,
please see the official GNU web site.</p>

<p>GMP&#39;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.</p>

<p>GMP is brought to you by a team listed in the manual.</p>

<p>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.&quot;</p>
</blockquote>

<p>Only GMP 4 or newer is supported. The following environments have been tested
by me: gmp gem 0.5.47 on:</p>

<table border="1">
  <tr>
    <th>Platform</th>
    <th>Ruby</th>
    <th>GMP (MPFR)</th>
  </tr>
  <tr>
    <td rowspan="3">Linux (Ubuntu NR 10.04) on x86 (32-bit)</td>
    <td>(MRI) Ruby 1.8.7</td>
    <td>GMP 4.3.1 (2.4.2)<br />
        GMP 4.3.2 (2.4.2)<br />
        GMP 5.0.1 (3.0.0)</td>
  </tr>
  <tr>
    <td>(MRI) Ruby 1.9.1</td>
    <td>GMP 4.3.1 (2.4.2)<br />
        GMP 4.3.2 (2.4.2)<br />
        GMP 5.0.1 (3.0.0)</td>
  </tr>
  <tr>
    <td>(MRI) Ruby 1.9.2</td>
    <td>GMP 4.3.1 (2.4.2)<br />
        GMP 4.3.2 (2.4.2)<br />
        GMP 5.0.1 (3.0.0)</td>
  </tr>
  <tr>
    <td rowspan="4">Linux (Ubuntu 10.04) on x86_64 (64-bit)</td>
    <td>(MRI) Ruby 1.8.7</td>
    <td>GMP 4.3.2 (2.4.2)<br />
        GMP 5.0.1 (3.0.0)</td>
  </tr>
  <tr>
    <td>(MRI) Ruby 1.9.1</td>
    <td>GMP 4.3.2 (2.4.2)<br />
        GMP 5.0.1 (3.0.0)</td>
  </tr>
  <tr>
    <td>(MRI) Ruby 1.9.2</td>
    <td>GMP 4.3.2 (2.4.2)<br />
        GMP 5.0.1 (3.0.0)</td>
  </tr>
  <tr>
    <td>(RBX) Rubinius 1.1.0</td>
    <td>GMP 4.3.2 (2.4.2)<br />
        GMP 5.0.1 (3.0.0)</td>
  </tr>
  <tr>
    <td rowspan="3">Mac OS X 10.6.8 on x86_64 (64-bit)</td>
    <td>(MRI) Ruby 1.8.7</td>
    <td>GMP 4.3.2 (2.4.2)<br />
        GMP 5.0.5 (3.1.1)</td>
  </tr>
  <tr>
    <td>(MRI) Ruby 1.9.3</td>
    <td>GMP 4.3.2 (2.4.2)<br />
        GMP 5.0.5 (3.1.1)</td>
  </tr>
  <tr>
    <td>(RBX) Rubinius 1.1.0</td>
    <td>GMP 4.3.2 (2.4.2)<br />
        GMP 5.0.1 (3.0.0)</td>
  </tr>
  <tr>
    <td rowspan="3">Windows 7 on x86_64 (64-bit)</td>
    <td>(MRI) Ruby 1.8.7</td>
    <td>GMP 4.3.2 (2.4.2)<br />
        GMP 5.0.1 (3.0.0)</td>
  </tr>
  <tr>
    <td>(MRI) Ruby 1.9.1</td>
    <td>GMP 4.3.2 (2.4.2)<br />
        GMP 5.0.1 (3.0.0)</td>
  </tr>
  <tr>
    <td>(MRI) Ruby 1.9.2</td>
    <td>GMP 4.3.2 (2.4.2)<br />
        GMP 5.0.1 (3.0.0)</td>
  </tr>
  <tr>
    <td>Windows XP on x86 (32-bit)</td>
    <td>(MRI) Ruby 1.9.1</td>
    <td>GMP 4.3.2 (2.4.2)<br />
        GMP 5.0.1 (3.0.0)</td>
  </tr>
</table>

<h2>Authors</h2>

<ul>
<li>Tomasz Wegrzanowski</li>
<li>srawlins</li>
</ul>

<h2>Constants</h2>

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

<ul>
<li><code>GMP::GMP_VERSION</code> - A string like &quot;5.0.1&quot;</li>
<li><code>GMP::GMP_CC</code> - The compiler used to compile GMP</li>
<li><code>GMP::GMP_CFLAGS</code> - The CFLAGS used to compile GMP</li>
<li><code>GMP::GMP\_BITS_PER_LIMB</code> The number of bits per limb</li>
<li><code>GMP::GMP_NUMB_MAX</code> - The maximum value that can be stored in the number part of a limb</li>
</ul>

<p>if MPFR is available:
* <code>GMP::MPFR_VERSION</code> - A string like &quot;2.4.2&quot;
* <code>GMP::MPFR\_PREC_MIN</code> - The minimum precision available
* <code>GMP::MPFR_PREC_MAX</code> - The maximum precision available
* <code>GMP::GMP_RNDN</code> - The constant representing &quot;round to nearest&quot;
* <code>GMP::GMP_RNDZ</code> - The constant representing &quot;round toward zero&quot;
* <code>GMP::GMP_RNDU</code> - The constant representing &quot;round toward plus infinity&quot;
* <code>GMP::GMP_RNDD</code> - The constant representing &quot;round toward minus infinity&quot;</p>

<p>New in MPFR 3.0.0:
* <code>GMP::MPFR_RNDN</code>
* <code>GMP::MPFR_RNDZ</code>
* <code>GMP::MPFR_RNDU</code>
* <code>GMP::MPFR_RNDD</code>
* <code>GMP::MPFR_RNDA</code> - The constant representing &quot;round away from zero&quot;</p>

<h2>Classes</h2>

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

<p>Numbers are created by using <code>new()</code>. Constructors can take following arguments:</p>

<pre><code>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\])
</code></pre>

<p>You can also call them as:</p>

<pre><code>GMP.Z(args)
GMP.Q(args)
GMP.F(args)
GMP.RandState()
</code></pre>

<h2>Methods</h2>

<pre><code>GMP::Z, GMP::Q and GMP::F
  +                        addition
  -                        substraction
  *                        multiplication
  /                        division
  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
  &lt;=&gt;,&gt;=,&gt;,&lt;=,&lt;            comparisons
class methods of GMP::Z
  fac(n)                   factorial of n
  2fac(n), double_fac(n)   double factorial of n
  mfac(n)                  m-multi-factorial of n
  primorial(n)             primorial 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
  to_i                     convert to Fixnum or Bignum
  add!                     in-place addition
  sub!                     in-place subtraction
  addmul!(b,c)             in-place += b*c
  submul!(b,c)             in-place -= b*c
  tdiv,fdiv,cdiv           truncate, floor and ceil division
  tmod,fmod,cmod           truncate, floor and ceil modulus
  &gt;&gt;                       shift right, floor
  divisible?(b)            true if divisible by b
  congruent?(c,d)          true if congruent to c modulus d
  **                       power
  powmod                   power modulo
  \[\],\[\]=                   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.
  cmpabs                   comparison of absolute value
  com                      2&#39;s complement
  com!                     in-place 2&#39;s complement
  &amp;,|,^                    logical operations: and, or, xor
  even?                    is even
  odd?                     is odd
  &lt;&lt;                       shift left
  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, gcdext, gcdext2     greatest common divisor
  lcm                      least common multiple
  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
  hamdist                  the hamming distance between two integers
  out_raw                  output to IO object
  inp_raw                  input from IO object
  export                   export to a byte array (String)
  import                   import from a byte array (String)
  sizeinbase(b)            digits in base b
  size_in_bin              digits in binary
  size                     number of limbs
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
  mpfr_buildopt_tls_p      returns whether MPFR was built as thread safe
  mpfr_buildopt_decimal_p  returns whether MPFR was compiled with decimal
                           float support
GMP::F
  sqrt                     square root of the object
  rec_sqrt                 square root of the recprical of the object
  cbrt                     cube root of the object
  **                       power
  log                      natural logarithm of object
  log2                     binary logarithm of object
  log10                    decimal logarithm of object
  exp                      e^object
  exp2                     2^object
  exp10                    10^object
  log1p                    the same as (object + 1).log, with better
                           precision
  expm1                    the same as (object.exp) - 1, with better
                           precision
  eint                     exponential integral of object
  li2                      real part of the dilogarithm of object
  gamma                    Gamma fucntion of object
  lngamma                  logarithm of the Gamma function of object
  digamma                  Digamma function of object (MPFR_VERSION &gt;= &quot;3.0.0&quot;)
  zeta                     Reimann Zeta function of object
  erf                      error function of object
  erfc                     complementary error function of object
  j0                       first kind Bessel function of order 0 of object
  j1                       first kind Bessel function of order 1 of object
  jn                       first kind Bessel function of order n of object
  y0                       second kind Bessel function of order 0 of object
  y1                       second kind Bessel function of order 1 of object
  yn                       second kind Bessel function of order n of object
  agm                      arithmetic-geometric mean
  hypot
  cos                      \
  sin                      |
  tan                      |
  sin_cos                  |
  sec                      |
  csc                      |
  cot                      |
  acos                     |
  asin                     |
  atan                     | trigonometric functions
  atan2                    |
  cosh                     | of the object
  sinh                     |
  tanh                     |
  sinh_cosh                |
  sec                      |
  csc                      |
  cot                      |
  acosh                    |
  asinh                    |
  atanh                    /
  nan?                     \
  infinite?                | type of floating point number
  finite?                  |
  number?                  |
  regular?                 / (MPFR_VERSION &gt;= &quot;3.0.0&quot;)
GMP::RandState
  mpfr_urandomb(fixnum)    get uniformly distributed random floating-point
                           number within 0 &lt;= rop &lt; 1
</code></pre>

<h2>Functional Mappings</h2>

<p>In order to align better with the GMP paradigms of using return arguments, I have started creating &quot;functional mappings&quot;, singleton methods that map directly to functions in GMP. These methods take return arguments, so that passing an object to a functional mapping may change the object itself. For example:</p>

<pre><code>a = GMP::Z(0)
b = GMP::Z(13)
c = GMP::Z(17)
GMP::Z.add(a, b, c)
a  #=&gt; 30
</code></pre>

<p>Here&#39;s a fun list of all of the functional mappings written so far:</p>

<pre><code>GMP::Z
  .abs          .add          .addmul       .cdiv_q_2exp  .cdiv_r_2exp  .com
  .congruent?   .divexact     .divisible?   .fdiv_q_2exp  .fdiv_r_2exp  .lcm
  .mul          .mul_2exp
  .neg          .nextprime    .sqrt         .sub          .submul       .tdiv_q_2exp
  .tdiv_r_2exp
</code></pre>

<h2>Documentation</h2>

<ul>
<li><a href="https://github.com/srawlins/gmp">This README</a></li>
<li>Loren Segal and the guys at RubyGems.org are awesome: <a href="http://rubydoc.info/gems/gmp/frames">YARDoc</a>.</li>
<li>There should be a manual.pdf <a href="https://github.com/srawlins/gmp/blob/master/manual.pdf">here</a>. I spend waaay too much time working on this, but it looks very pretty.</li>
<li><a href="https://github.com/srawlins/gmp/blob/master/CHANGELOG">CHANGELOG</a></li>
</ul>

<h2>Testing</h2>

<p>Tests can be run with:</p>

<pre><code>cd test
ruby unit_tests.rb
</code></pre>

<p>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&#39;s built-in <code>Test::Unit</code> package that is fixed with the unit_test gem.</p>

<p>You can also use the following shiny new rake tasks:</p>

<pre><code>rake test
rake report
MPFR=no-mpfr rake report
</code></pre>

<h2>Known Issues</h2>

<p>Don&#39;t call <code>GMP::RandState(:lc_2exp_size)</code>. Give a 2nd arg.
Don&#39;t use multiple assignment (<code>a = b = GMP::Z(0)</code>) with functional mappings:</p>

<p><code>ruby
    &gt;&gt; a = b = GMP::Z(0)
    =&gt; 0
    &gt;&gt; GMP::Z.mul(a, GMP::Z(2), GMP::Z(3))
    =&gt; nil
    &gt;&gt; a
    =&gt; 6
    &gt;&gt; b
    =&gt; 6
</code></p>

<p>JRuby has some interesting bugs and flickering tests. GMP::Z(GMP::GMP<em>NUMB</em>MAX) for example, blows up.</p>

<h2>Precision</h2>

<p>Precision can be explicitely set as second argument for <code>GMP::F.new()</code>. If there is no explicit precision, highest precision of all <code>GMP::F</code> arguments is used. That doesn&#39;t ensure that result will be exact. For details, consult any paper about floating point arithmetics.</p>

<p>Default precision can be explicitely set by passing <code>0</code> as the second argument for to <code>GMP::F.new()</code>. In particular, you can set precision of copy of <code>GMP::F</code> object by:</p>

<pre><code>new_obj = GMP::F.new(old_obj, 0)
</code></pre>

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

<h2>Benchmarking</h2>

<p>Please see <a href="performance.md">performance</a></p>

<h2>Todo</h2>

<ul>
<li><code>GMP::Z#to_d_2exp</code>, <code>#rootrem</code>, <code>#kronecker</code>, <code>#bin</code>, <code>#fib2</code>, <code>#lucnum</code>, <code>#lucnum2</code>, <code>#combit</code>, <code>#fits_x?</code></li>
<li><code>GMP::Q#to_s(base)</code>, <code>GMP::F#to_s(base)</code> (test it!)</li>
<li>benchmark pi</li>
<li>a butt-load of functional mappings. 47-ish sets.</li>
<li>investigate possible memory leaks when using <code>GMP::Q(22/7)</code> for example</li>
<li>beef up <code>r_gmpq_initialize</code>; I don&#39;t like to rely on <code>mpz_set_value</code>.</li>
<li>finish compile-results.rb</li>
<li>New in MPFR 3.1.0: mpfr<em>frexp, mpfr</em>grandom, mpfr<em>z</em>sub, divide-by-zero exception (?)</li>
<li>benchmark different orderings of type checks</li>
</ul>

<p>The below are inherited from Tomasz. I will go through these and see which are
still relevant, and which I understand.</p>

<ul>
<li><code>mpz_fits_*</code> and 31 vs. 32 integer variables</li>
<li>fix all sign issues (don&#39;t know what these are)</li>
<li><code>to_s</code> vs. <code>inspect</code></li>
<li>check if <code>mpz_addmul_ui</code> would optimize some statements</li>
<li>some system that allows using denref and numref as normal ruby objects</li>
<li>takeover code that replaces all <code>Bignums</code> with <code>GMP::Z</code></li>
<li>better bignum parser (crawling into the Bignum extension)</li>
<li>zero-copy method for strings generation</li>
<li>benchmarks against Python GMP and Perl GMP</li>
<li><code>dup</code> methods for GMP::Q and GMP::F</li>
<li>integrate <code>F</code> into system</li>
<li>should <code>Z.\[\]</code> bits be 0/1 or true/false, 0 is true, which might surprise users</li>
<li><code>any2small_integer()</code></li>
<li>powm with negative exponents</li>
<li>check if different sorting of operations gives better cache usage</li>
<li><code>GMP::\*</code> op <code>RubyFloat</code> and <code>RubyFloat</code> op <code>GMP::\*</code></li>
</ul>