\documentclass[pdftex,10pt]{article}
\usepackage{amsmath,amsfonts,url}
\usepackage[pdftex]{graphicx}
\usepackage{booktabs}
\usepackage{url}
\setlength{\parindent}{0pt}
\def\cour{\fontfamily{pcr}\selectfont}
\usepackage[top=1in, bottom=0.8in, left=0.8in, right=0.8in]{geometry}
\setcounter{tocdepth}{3}
\newlength{\titrwidth}
\setlength{\titrwidth}{\textwidth}
\addtolength{\titrwidth}{-1.2in}
\newlength{\methwidth}
\setlength{\methwidth}{0.8in}
\newlength{\defnwidth}
\setlength{\defnwidth}{\textwidth}
\addtolength{\defnwidth}{-1.2in}
\addtolength{\heavyrulewidth}{\heavyrulewidth}
\def\qquad{\quad\quad}
\def\qqqquad{\quad\quad\quad\quad}
\def\cc{\colon\colon}
\def\gmpz{\textit{GMP::Z}}
\def\gmprandstate{\textit{GMP::RandState\ }}
\frenchspacing
\begin{document}

\begin{tabular}{p{1.0in} p{\titrwidth}}
\huge{gmp} &\\
\midrule[3pt]
\multicolumn{2}{r}{\large{Ruby bindings to the GMP library}}\\
\multicolumn{2}{r}{\large{Edition 0.4.1}}\\
\multicolumn{2}{r}{\large{1 March 2010}}
\end{tabular}

\vfill
\large{written by Sam Rawlins}\\
\large{with extensive quoting from the GMP Manual}
\newpage

\vfill
This manual describes how to use the gmp Ruby gem, which provides bindings to
the GNU multiple precision arithmetic library, version 4.3.x or 5.0.x.\\
\\
Copyright 2009 Sam Rawlins.\\
No license yet.
\newpage

\tableofcontents
\newpage

\section{Introduction to GNU MP}

This entire page is copied verbatim from the GMP Manual.\\\\

GNU MP is a portable library written in C for arbitrary precision arithmetic on
integers, rational numbers, and floating-point numbers. It aims to provide the
fastest possible arithmetic for all applications that need higher precision
than is directly supported by the basic C types.\\
\\
Many applications use just a few hundred bits of precision; but some
applications may need thousands or even millions of bits. GMP is designed to
give good performance for both, by choosing algorithms based on the sizes of
the operands, and by carefully keeping the overhead at a minimum.\\
\\
The speed of GMP is achieved by using fullwords as the basic arithmetic type,
by using sophisticated algorithms, by including carefully optimized assembly
code for the most common inner loops for many different CPUs, and by a general
emphasis on speed (as opposed to simplicity or elegance).\\
\\
There is assembly code for these CPUs: ARM, DEC Alpha 21064, 21164, and 21264,
AMD 29000, AMD K6, K6-2, Athlon, and Athlon64, Hitachi SuperH and SH-2, HPPA
1.0, 1.1, and 2.0, Intel Pentium, Pentium Pro/II/III, Pentium 4, generic x86,
Intel IA-64, i960, Motorola MC68000, MC68020, MC88100, and MC88110,
Motorola/IBM PowerPC 32 and 64, National NS32000, IBM POWER, MIPS R3000, R4000,
SPARCv7, SuperSPARC, generic SPARCv8, UltraSPARC, DEC VAX, and Zilog Z8000.
Some optimizations also for Cray vector systems, Clipper, IBM ROMP (RT), and
Pyramid AP/XP.\\
\\
For up-to-date information on GMP, please see the GMP web pages at\\
\setlength{\parindent}{0.25in}
\texttt{http://gmplib.org/}
\setlength{\parindent}{0in}
\\

The latest version of the library is available at\\
\setlength{\parindent}{0.25in}
\texttt{ftp://ftp.gnu.org/gnu/gmp/}\\
\setlength{\parindent}{0in}
\\

Many sites around the world mirror '\texttt{ftp.gnu.org}', please use a mirror
near you, see \texttt{http://www.gnu.org/order/ftp.html} for a full list.\\
\\
There are three public mailing lists of interest. One for release
announcements, one for general questions and discussions about usage of the GMP
library, and one for bug reports. For more information, see\\
\\
\texttt{http://gmplib.org/mailman/listinfo/}.\\
\\
The proper place for bug reports is gmp-bugs@gmplib.org. See Chapter 4
[Reporting Bugs], page 28 for information about reporting bugs.

\section{Introduction to the gmp gem}

The gmp Ruby gem is a Ruby library that provides bindings to GMP. The gem is
incomplete, and will likely only include a subset of the GMP functions. It is
built as a C extension for ruby, interacting with gmp.h. The gmp gem is not
endorsed or supported by GNU or the GMP team. The gmp gem also does not ship
with GMP, so GMP must be compiled separately.

\section{Installing the gmp gem}

\subsection{Prerequisites}
OK. First, we've got a few requirements. To install the gmp gem, you need one
of the following versions of Ruby:
\begin{itemize}
  \item (MRI) Ruby 1.8.6 - tested lightly.
  \item (MRI) Ruby 1.8.7 - tested seriously.
  \item (MRI) Ruby 1.9.1 - tested seriously.
\end{itemize}
As you can see only Matz's Ruby Interpreter (MRI) is supported. I haven't even
put a thought into trying other interpreters/VMs. I intend to look into FFI,
which supposedly will allow me to load this extension into JRuby and Rubinius,
not sure about others...\\

Next is the platform, the combination of the architecture (processor) and OS.
As far as I can tell, if you can compile GMP and Ruby on a given platform, you
can use the gmp gem there too. Please report problems with that hypothesis.\\

Lastly, GMP. GMP must be compiled and working. "and working" means you ran "make
check" while installing GMP. The following versions of GMP have been tested:
\begin{itemize}
  \item GMP 4.3.1
  \item GMP 4.3.2
  \item GMP 5.0.0
  \item GMP 5.0.1
\end{itemize}

That's all. I don't intend to test any older versions, maybe 4.3.0 for
completeness.\\

Here is a table of the exact environments on which I have tested the gmp gem:\\\\

\begin{tabular}{lrr} \hline
             Platform             &       Ruby       &    GMP    \\ \midrule[1pt]
  Cygwin on x86                   & (MRI) Ruby 1.8.7 & GMP 4.3.1 \\ \hline
  Linux (LinuxMint 7) on x86      & (MRI) Ruby 1.8.7 & GMP 4.3.1 \\ \hline
  Mac OS X 10.5.7 on x86 (32-bit) & (MRI) Ruby 1.8.6 & GMP 4.3.1 \\ \hline
  Mac OS X 10.5.7 on x86 (32-bit) & (MRI) Ruby 1.9.1 & GMP 4.3.1 \\ \hline
  Windows XP on x86 (32-bit)      & (MRI) Ruby 1.9.1 & GMP 5.0.1 \\ \hline
\end{tabular}

\subsection{Installing}
You may clone the gmp gem's git repository with:\\
\\
\texttt{git clone git://github.com/srawlins/gmp.git}\\

Or you may install the gem from gemcutter:\\
\\
\texttt{gem install gmp}\\

Or you may install the gem from github (old):\\
\\
\texttt{gem install srawlins-gmp}\\

At this time, the gem does not self-compile (how does that work?). To compile the C
extensions, do the following:\\
\\
\texttt{cd <gmp gem directory>/ext}\\
\texttt{ruby extconf.rb}\\
\texttt{make}\\

There shouldn't be any errors, or warnings.

\section{Testing the gmp gem}

Testing the gmp gem is quite simple. The test/unit\_tests.rb suite uses Unit::Test.
You can run this test suite with:\\
\\
\texttt{cd <gmp gem directory>/test}\\
\texttt{ruby unit\_tests.rb}\\

All tests should pass. If you don't have the test-unit gem installed, then you may
run into one error. I'm not sure why this is... I suspect a bug in Ruby's Test::Unit
that the test-unit gem monkey patches.

\section{GMP and gmp gem basics}

\subsection{Classes}
The gmp gem includes the namespace \texttt{GMP} and four classes within \texttt{GMP}:
\begin{itemize}
  \item \texttt{GMP::Z} - Methods for signed integer arithmetic. There are at least 45
    methods here (still accounting).
  \item \texttt{GMP::Q} - Methods for rational number arithmetic. There are at least 11
    methods here (still accounting).
  \item \texttt{GMP::F} - Methods for floating-point arithmetic. There are at least 6
    methods here (still accounting).
  \item \texttt{GMP::RandState} - Methods for random number generation. There are 3
    methods here.
\end{itemize}

In addition to the above four classes, there is also one constant within \texttt{GMP}:
\begin{itemize}
  \item \texttt{GMP::GMP\_VERSION} - The version of GMP compiled into the gmp gem.
\end{itemize}

\newpage
\section{Integer Functions}

\subsection{Initializing, Assigning Integers}

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{new} & & GMP::Z.new $\rightarrow$ \textit{integer} \\
& & GMP::Z.new(\textit{numeric = 0}) $\rightarrow$ \textit{integer} \\
& & GMP::Z.new(\textit{str}) $\rightarrow$ \textit{integer} \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  This method creates a new \textit{GMP::Z} integer. It takes one optional argument for
  the value of the integer. This argument can be one of several classes. Here are some
  examples:\newline
  
  \texttt{GMP::Z.new \qqqquad\qqqquad \#=> 0 (default) \newline
          GMP::Z.new(1) \qqqquad\qquad\  \#=> 1 (Ruby Fixnum) \newline
          GMP::Z.new("127") \qqqquad\  \#=> 127 (Ruby String)\newline
          GMP::Z.new(4294967296) \qquad \#=> 4294967296 (Ruby Bignum)\newline
          GMP::Z.new(GMP::Z.new(31))  \#=> 31 (GMP Integer)}
}
\end{tabular}
\newline\newline

There is also a convenience method available, \texttt{GMP::Z()}.\\

\subsection{Converting Integers}

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{to\_d} & & \textit{integer}.to\_d $\rightarrow$ \textit{float} \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns \textit{integer} as an Float if \textit{integer} fits in a Float.

  Otherwise returns the least significant part of \texttt{integer}, with the same sign as
  \textit{integer}.
  
  If \textit{integer} is too big to fit in a Float, the returned result is probably not
  very useful. To find out if the value will fit, use the function
  \textit{mpz\_fits\_slong\_p} (\textbf{Unimplemented}).
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{to\_i} & & \textit{integer}.to\_i $\rightarrow$ \textit{fixnum} \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns \textit{integer} as a Fixnum if \textit{integer} fits in a Fixnum.
  \newline
  
  Otherwise returns the least significant part of \textit{integer}, with the same sign as
  \textit{integer}.
  \newline
  
  If \textit{integer} is too big to fit in a Fixnum, the returned result is probably not
  very useful. To find out if the value will fit, use the function
  \textit{mpz\_fits\_slong\_p} (\textbf{Unimplemented}).
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{to\_s} & & \textit{integer}.to\_s(\textit{base = 10}) $\rightarrow$ \textit{str} \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Converts \textit{integer} to a string of digits in base \textit{base}. The
  \textit{base} argument may vary from 2 to 62 or from -2 to -36, or be a symbol, one of
  \textit{:bin}, \textit{:oct}, \textit{:dec}, or \textit{:hex}.
  \newline
  
  For \textit{base} in the range 2..36, digits and lower-case letters are used; for
  -2..-36 (and \textit{:bin}, \textit{:oct}, \textit{:dec}, and \textit{:hex}), digits
  and upper-case letters are used; for 37..62, digits, upper-case letters, and lower-case
  letters (in that significance order) are used. Here are some
  examples:\newline
  
  \texttt{GMP::Z(1).to\_s \qqqquad \#=> "1" \newline
          GMP::Z(32).to\_s(2) \qquad \#=> "100000" \newline
          GMP::Z(32).to\_s(4) \qquad \#=> "200" \newline
          GMP::Z(10).to\_s(16) \quad\  \#=> "a" \newline
          GMP::Z(10).to\_s(-16) \quad \#=> "A" \newline
          GMP::Z(255).to\_s(:bin) \#=> "11111111" \newline
          GMP::Z(255).to\_s(:oct) \#=> "377" \newline
          GMP::Z(255).to\_s(:dec) \#=> "255" \newline
          GMP::Z(255).to\_s(:hex) \#=> "ff"}
}
\end{tabular}

\subsection{Integer Arithmetic}

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{+} & & \textit{integer} + \textit{numeric} $\rightarrow$ \textit{numeric} \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns the sum of \textit{integer} and \textit{numeric}. \textit{numeric} can be an
  instance of \textit{GMP::Z}, \textit{Fixnum}, \textit{GMP::Q}, \textit{GMP::F}, or
  \textit{Bignum}.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{add!} & & \textit{integer}.add!(\textit{numeric}) $\rightarrow$
\textit{numeric} \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Sums \textit{integer} and \textit{numeric}, in place. \textit{numeric} can be an
  instance of \textit{GMP::Z}, \textit{Fixnum}, \textit{GMP::Q}, \textit{GMP::F}, or
  \textit{Bignum}.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{-} & & \textit{integer} - \textit{numeric} $\rightarrow$ \textit{numeric} \\
& & \textit{integer}.sub!(\textit{numeric}) $\rightarrow$ \textit{numeric} \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns the difference of \textit{integer} and \textit{numeric}. The destructive method
  calculates the difference in place. \textit{numeric} can be an instance of
  \textit{GMP::Z}, \textit{Fixnum}, \textit{GMP::Q}, \textit{GMP::F}, or \textit{Bignum}.
  Here are some examples:\newline
  
  \texttt{seven     = GMP::Z(7) \newline
          nine \    = GMP::Z(9) \newline
          half \    = GMP::Q(1,2) \newline
          pi \quad\ = GMP::F("3.14") \newline
          nine - 5 \qquad\quad \#=> 4 (GMP Integer) \newline
          nine - seven \quad \#=> 2 (GMP Integer) \newline
          nine - (2**32) \#=> -4294967287 (GMP Integer) \newline
          nine - nine \quad\ \#=> 0 (GMP Integer) \newline
          nine - half \quad\ \#=> 8.5 (GMP Rational) \newline
          nine - pi \qquad\  \#=> 5.86 (GMP Float)}
  
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{*} & & \textit{integer} * \textit{numeric} $\rightarrow$ \textit{numeric} \\
& & \textit{integer}.mul(\textit{numeric}) $\rightarrow$ \textit{numeric} \\
& & \textit{integer}.mul!(\textit{numeric}) $\rightarrow$ \textit{numeric} \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns the product of \textit{integer} and \textit{numeric}. The destructive method
  calculates the product in place. \textit{numeric} can be an instance of
  \textit{GMP::Z}, \textit{Fixnum}, \textit{GMP::Q}, \textit{GMP::F}, or \textit{Bignum}.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{\textless\textless} & & \textit{integer} \textless\textless \textit{numeric} $\rightarrow$ \textit{integer} \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns \textit{integer} times 2 to the \textit{numeric} power. This can also be
  defined as a left shift by \textit{numeric} bits.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{-@} & & -\textit{integer}\\
& & \textit{integer}.neg\\
& & \textit{integer}.neg!\\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns the negation, the additive inverse, of \textit{integer}. The destructive method
  negates in place.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{abs} & & \textit{integer}.abs\\
& & \textit{integer}.abs!\\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns the absolute value of \textit{integer}. The destructive method calculates the
  absolute value in place.
}
\end{tabular}

\subsection{Integer Division}

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{tdiv} & & $integer$.tdiv($numeric$) $\rightarrow$ $integer$\\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns the division of $integer$ by $numeric$, truncated. $numeric$ can be an instance
  of $GMP::Z$, $Fixnum$, $Bignum$. The return object's class is always $GMP::Z$.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{fdiv} & & $integer$.fdiv($numeric$) $\rightarrow$ $integer$\\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns the division of $integer$ by $numeric$, floored. $numeric$ can be an instance
  of $GMP::Z$, $Fixnum$, $Bignum$. The return object's class is always $GMP::Z$.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{cdiv} & & $integer$.cdiv($numeric$) $\rightarrow$ $integer$\\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns the ceiling division of $integer$ by $numeric$. $numeric$ can be an instance of
  $GMP::Z$, $Fixnum$, $Bignum$. The return object's class is always $GMP::Z$.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{tmod} & & $integer$.tmod($numeric$) $\rightarrow$ $integer$\\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns the remainder after truncated division of $integer$ by $numeric$. $numeric$ can
  be an instance of $GMP::Z$, $Fixnum$, or $Bignum$. The return object's class is always
  $GMP::Z$.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{fmod} & & $integer$.fmod($numeric$) $\rightarrow$ $integer$\\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns the remainder after floored division of $integer$ by $numeric$. $numeric$ can
  be an instance of $GMP::Z$, $Fixnum$, or $Bignum$. The return object's class is always
  $GMP::Z$.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{cmod} & & \textit{integer}.cmod(\textit{numeric}) $\rightarrow$ \textit{integer}\\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns the remainder after ceilinged division of $integer$ by $numeric$. $numeric$ can
  be an instance of $GMP::Z$, $Fixnum$, or $Bignum$. The return object's class is always
  $GMP::Z$.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{\%} & & \textit{integer} \% \textit{numeric} $\rightarrow$ \textit{integer}\\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns $integer$ modulo $numeric$. $numeric$ can be an instance of \gmpz, $Fixnum$,
  or $Bignum$. The return object's class is always \gmpz.
}
\end{tabular}

\subsection{Integer Roots}

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{root} & & \textit{integer}.root(\textit{numeric}) $\rightarrow$ \textit{numeric} \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns the integer part of the $numeric$'th root of $integer$.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{sqrt} & & \textit{integer}.sqrt $\rightarrow$ \textit{numeric} \\
& & \textit{integer}.sqrt!(\textit{numeric}) $\rightarrow$ \textit{numeric} \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns the truncated integer part of the square root of $integer$.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{sqrtrem} & & \textit{integer}.sqrtrem $\rightarrow$ \textit{sqrt}, \textit{rem} \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns the truncated integer part of the square root of $integer$ as $sqrt$ and the
  remainder, $integer - sqrt * sqrt$, as $rem$, which will be zero if $integer$ is a
  perfect square.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{power?} & & \textit{integer}.power? $\rightarrow$ \textit{true} \textbar\  \textit{false} \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns true if $integer$ is a perfect power, i.e., if there exist integers $a$ and
  $b$, with $b > 1$, such that $integer$ equals $a$ raised to the power $b$.
  \newline\newline
  Under this definition both 0 and 1 are considered to be perfect powers. Negative values
  of integers are accepted, but of course can only be odd perfect powers.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{square?} & & \textit{integer}.square? $\rightarrow$ \textit{true} \textbar\  \textit{false} \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns true if $integer$ is a perfect square, i.e., if the square root of
  $integer$ is an integer. Under this definition both 0 and 1 are considered to be
  perfect squares.
}
\end{tabular}

\subsection{Integer Exponentiation}

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{**} & & \textit{integer} ** \textit{numeric} $\rightarrow$ \textit{numeric} \\
& & \textit{integer}.pow(\textit{numeric}) $\rightarrow$ \textit{numeric} \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns $integer$ raised to the $numeric$ power.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{powmod} & & \textit{integer}.powmod(\textit{exp}, \textit{mod}) $\rightarrow$ \textit{integer} \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns $integer$ raised to the $exp$ power, modulo $mod$. Negative $exp$ is supported
  if an inverse, $integer^{-1}$ modulo $mod$, exists. If an inverse doesn't exist then a
  divide by zero exception is raised.
}
\end{tabular}

\subsection{Number Theoretic Functions}

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{is\_probab\_prime?} & & $integer$.is\_probab\_prime?($reps = 5$) $\rightarrow$ 0, 1, or 2 \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Determine whether $integer$ is prime. Returns 2 if $integer$ is definitely prime,
  returns 1 if $integer$ is probably prime (without being certain), or returns 0 if
  $integer$ is definitely composite. 
  \newline\newline
  This function does some trial divisions, then some Miller-Rabin probabilistic primality
  tests. $reps$ controls how many such tests are done, 5 to 10 is a reasonable number,
  more will reduce the chances of a composite being returned as “probably prime”.
  \newline\newline
  Miller-Rabin and similar tests can be more properly called compositeness tests. Numbers
  which fail are known to be composite but those which pass might be prime or might be
  composite. Only a few composites pass, hence those which pass are considered probably
  prime.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{next\_prime} & & $integer$.next\_prime $\rightarrow$ $prime$ \\
& & $integer$.nextprime $\rightarrow$ $prime$ \\
& & $integer$.next\_prime! $\rightarrow$ $prime$ \\
& & $integer$.nextprime! $\rightarrow$ $prime$ \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns the next prime greater than $integer$. The destructive method sets $integer$ to
  the next prime greater than $integer$.
  \newline\newline
  This function uses a probabilistic algorithm to identify primes. For practical purposes
  it's adequate, the chance of a composite passing will be extremely small.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{gcd} & & $a$.gcd($b$) $\rightarrow$ $g$ \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Computes the greatest common divisor of $a$ and $b$. $g$ will always be positive, even
  if $a$ or $b$ is negative. $b$ can be an instance of \gmpz, $Fixnum$, or $Bignum$.
  \newline\newline
  \texttt{GMP::Z(24).gcd(GMP::Z(8)) \quad \#=> GMP::Z(8) \newline
          GMP::Z(24).gcd(8) \quad \#=> GMP::Z(8) \newline
          GMP::Z(24).gcd(2**32) \quad \#=> GMP::Z(8)}
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{invert} & & $a$.invert($m$) $\rightarrow$ $integer$ \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Computes the inverse of $a$ mod $m$. $m$ can be an instance of \gmpz, $Fixnum$, or
  $Bignum$.
  \newline\newline
  \texttt{GMP::Z(2).invert(GMP::Z(11)) \quad \#=> GMP::Z(6) \newline
          GMP::Z(3).invert(11) \quad \#=> GMP::Z(4) \newline
          GMP::Z(5).invert(11) \quad \#=> GMP::Z(9)}
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{jacobi} & & $a$.jacobi($b$) $\rightarrow$ $integer$ \\
& & GMP::Z.jacobi($a$, $b$) $\rightarrow$ $integer$ \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns the Jacobi symbol $(a/b)$. This is defined only for $b$ odd. If $b$ is even, a
  range exception will be raised.
  \newline\newline
  \textit{GMP::Z.jacobi} (the instance method) requires $b$ to be an instance of \gmpz.
  \newline
  \textit{GMP::Z\#jacobi} (the class method) requires $a$ and $b$ each to be an instance of
  \gmpz, $Fixnum$, or $Bignum$.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{legendre} & & $a$.legendre($b$) $\rightarrow$ $integer$ \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns the Legendre symbol $(a/b)$. This is defined only for $p$ an odd positive
  prime. If $p$ is even, negative, or composite, a range exception will be raised.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{remove} & & $n$.remove($factor$) $\rightarrow$ ($integer$, $times$) \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Remove all occurrences of the factor $factor$ from $n$. $factor$ can be an instance of
  \gmpz, $Fixnum$, or $Bignum$. $integer$ is the resulting integer, an instance of
  \gmpz. $times$ is how many times $factor$ was removed, a $Fixnum$.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{fac} & & GMP::Z.fac($n$) $\rightarrow$ $integer$ \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns $n!$, or, $n$ factorial.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{fib} & & GMP::Z.fib($n$) $\rightarrow$ $integer$ \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns $F[n]$, or, the $n$th Fibonacci number.
}
\end{tabular}



\subsection{Integer Logic and Bit Fiddling}

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{and} & & $a$ \& $b$ $\rightarrow$ $integer$ \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns $integer$, the bitwise and of $a$ and $b$.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{ior} & & $a$ \textbar\ $b$ $\rightarrow$ $integer$ \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns $integer$, the bitwise inclusive or of $a$ and $b$.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{xor} & & $a$ \textasciicircum\ $b$ $\rightarrow$ $integer$ \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Returns $integer$, the bitwise exclusive or of $a$ and $b$.
}
\end{tabular}
\newline\newline

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{scan0} & & $n$.scan0($i$) $\rightarrow$ $integer$ \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Scans $n$, starting from bit $i$, towards more significant bits, until the first 0 bit
  is found. Return the index of the found bit.
  \newline\newline
  If the bit at $i$ is already what's sought, then $i$ is returned.
  \newline\newline
  If there's no bit found, then $INT2FIX(ULONG\_MAX)$ is returned. This will happen in
  scan0 past the end of a negative number.
}
\end{tabular}

\newpage
\section{Random Number Functions}

\subsection{Random State Initialization}

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{new} & & GMP::RandState.new $\rightarrow$ \textit{mersenne twister state} \\
& & GMP::RandState.new(:default) $\rightarrow$ \textit{mersenne twister state} \\
& & GMP::RandState(:mt) $\rightarrow$ \textit{mersenne twister random state} \\
& & GMP::RandState.new(:lc\_2exp, a, c, m2exp) $\rightarrow$ \textit{linear congruential state} \\
& & GMP::RandState.new(:lc\_2exp\_size, size) $\rightarrow$ \textit{linear congruential state} \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  This method creates a new \gmprandstate instance. The first argument defaults
  to \textit{:default} (also \textit{:mt}), which initializes the \gmprandstate for a Mersenne
  Twister algorithm. No other arguments should be given if \textit{:default} or \textit{:mt} is
  specified.
  \newline\newline
  If the first argument given is \textit{:lc\_2exp}, then the \gmprandstate is
  initialized for a linear congruential algorithm. \textit{:lc\_2exp} must be followed with $a$,
  $c$, and $m2exp$. The algorithm can then proceed as ($X = (a*X + c) \mod 2^{m2exp}$).
  \newline\newline
  \gmprandstate can also be initialized for a linear congruential algorithm with
  \textit{:lc\_2exp\_size}. This initializer instead takes just one argument, $size$. $a$, $c$,
  and $m2exp$ are then chosen from a table, with $m2exp/2 > size$. The maximum size
  currently supported is 128.\newline
  
  \texttt{GMP::RandState.new \newline
          GMP::RandState.new(:mt) \newline
          GMP::RandState.new(:lc\_2exp, 1103515245, 12345, 15) \quad \#=> Perl's old rand() \newline
          GMP::RandState.new(:lc\_2exp, 25\_214\_903\_917, 11, 48) \quad \#=> drand48}
}
\end{tabular}

\subsection{Random State Seeding}

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{seed} & & $state$.seed($integer$) $\rightarrow$ $integer$ \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Set an initial seed value into $state$. $integer$ can be an instance of \gmpz,
  $Fixnum$, or $Bignum$.
}
\end{tabular}

\subsection{Integer Random Numbers}

\begin{tabular}{p{\methwidth} l r}
\toprule
\textbf{urandomb} & & $state$.urandomb($n$) $\rightarrow$ $n$ \\
\cmidrule(r){2-3}
& \multicolumn{2}{p{\defnwidth}}{
  Generates a uniformly distributed random integer in the range $0$ to $2^n -1$,
  inclusive.
}
\end{tabular}

\end{document}