float.tex

精确小数算法库,可以实现任意长度的精确小数算法,用c语言实现,主要用于密码学中小数计算,验证可用

\documentclass[b5paper]{book}
\usepackage{hyperref}
\usepackage{makeidx}
\usepackage{amssymb}
\usepackage{color}
\usepackage{alltt}
\usepackage{graphicx}
\usepackage{layout}
\def\union{\cup}
\def\intersect{\cap}
\def\getsrandom{\stackrel{\rm R}{\gets}}
\def\cross{\times}
\def\cat{\hspace{0.5em} \| \hspace{0.5em}}
\def\catn{$\|$}
\def\divides{\hspace{0.3em} | \hspace{0.3em}}
\def\nequiv{\not\equiv}
\def\approx{\raisebox{0.2ex}{\mbox{\small $\sim$}}}
\def\lcm{{\rm lcm}}
\def\gcd{{\rm gcd}}
\def\log{{\rm log}}
\def\ord{{\rm ord}}
\def\abs{{\mathit abs}}
\def\rep{{\mathit rep}}
\def\mod{{\mathit\ mod\ }}
\renewcommand{\pmod}[1]{\ ({\rm mod\ }{#1})}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\def\Or{{\rm\ or\ }}
\def\And{{\rm\ and\ }}
\def\iff{\hspace{1em}\Longleftrightarrow\hspace{1em}}
\def\implies{\Rightarrow}
\def\undefined{{\rm ``undefined"}}
\def\Proof{\vspace{1ex}\noindent {\bf Proof:}\hspace{1em}}
\let\oldphi\phi
\def\phi{\varphi}
\def\Pr{{\rm Pr}}
\newcommand{\str}[1]{{\mathbf{#1}}}
\def\F{{\mathbb F}}
\def\N{{\mathbb N}}
\def\Z{{\mathbb Z}}
\def\R{{\mathbb R}}
\def\C{{\mathbb C}}
\def\Q{{\mathbb Q}}
\definecolor{DGray}{gray}{0.5}
\newcommand{\emailaddr}[1]{\mbox{$<${#1}$>$}}
\def\twiddle{\raisebox{0.3ex}{\mbox{\tiny $\sim$}}}
\def\gap{\vspace{0.5ex}}
\makeindex
\begin{document}
\frontmatter
\pagestyle{empty}
\title{LibTomFloat User Manual \\ v0.02}
\author{Tom St Denis \\ [e-mail]}
\maketitle
This text and the library are hereby placed in the public domain.  This book has been formatted for B5 [176x250] paper using the \LaTeX{} {\em book} 
macro package.

\vspace{10cm}

\begin{flushright}Open Source.  Open Academia.  Open Minds.

\mbox{ }

Tom St Denis,

Ontario, Canada
\end{flushright}

\tableofcontents
\listoffigures
\mainmatter
\pagestyle{headings}
\chapter{Introduction}
\section{What is LibTomFloat?}
LibTomFloat is a library of source code that provides multiple precision floating point arithmetic.  It allows developers to manipulate floating
point numbers of variable precision.  The library was written in portable ISO C source code and depends upon the public domain
LibTomMath package.

Along with providing the core mathematical operations such as addition and subtraction LibTomFloat also provides various complicated algorithms
such as trigonometry's sine, cosine and tangent operators as well as Calculus's square root, inverse square root, exponential and logarithm
operators.  

LibTomFloat has been written for portability and numerical stability and is not particularly optimized for any given platform.  It uses optimal
algorithms for manipulating the mantissa by using LibTomMath and uses numerically stable series for the various trig and calculus functions.

\section{License}
LibTomFloat is public domain.

\section{Building LibTomFloat}
LibTomFloat requires version 0.30 or higher of LibTomMath to be installed in order to build.  Once LibTomMath is installed building LibTomFloat
is as simple as:

\begin{alltt}
make
\end{alltt}

Which will build ``libtomfloat.a'' and along with ``tomfloat.h'' complete an installation of LibTomFloat.  You can also use the make target
``install'' to automatically build and copy the files (into *NIX specific) locations.  

\begin{alltt}
make install
\end{alltt}

\textbf{Note}: LibTomFloat does not use ISO C's native floating point types which means that the standard math library does not have to be
linked in.  This also means that LibTomFloat will work decently on platforms that do not have a floating point unit.


\section{Purpose of LibTomFloat}
LibTomFloat is as much as an exercise in hardcore math for myself as it is a service to any programmer who needs high precision float point
data types.  ISO C provides for fairly reasonable precision floating point data types but is limited.  A proper analogy is LibTomFloat solves
ISO C's floating point problems in the same way LibTomMath solves ISO C's integer data type problems.

A classic example of a good use for large precision floats is long simulations where the numbers are not perfectly stable.  A $128$--bit mantissa
(for example) can provide for exceptional precision.

That and knowing the value of $e$ to 512 bits is fun.

\section{How the types work}

\index{mantissa} \index{exponent}
The floating point types are emulated with three components.  The \textbf{mantissa}, the \textbf{exponent} and the \textbf{radix}.
The mantissa forms the digits of number being represented.  The exponent scales the number to give it a larger range.  The radix controls
how many bits there are in the mantissa.  The larger the radix the more precise the types become.  

The representation of a number is given by the simple product $m \cdot 2^e$ where $m$ is the mantissa and $e$ the exponent.  Numbers are
always normalized such that there are $radix$ bits per mantissa.  For example, with $radix = 16$ the number $2$ is represented by 
$32768 \cdot 2^{-14}$.  A zero is represented by a mantissa of zero and an exponent of one and is a special case.

The sign flag is a standard ISO C ``long'' which gives it the range $2^{-31} \le e < 2^{31}$ which is considerably large.  

Technically, LibTomFloat does not implement IEEE standard floating point types.  The exponent is not normalized and the sign flag does not 
count as a bit in the radix.  There is also no ``implied'' bit in this system.  The mantissa explicitly dictates the digits.

\chapter{Getting Started with LibTomFloat}
\section{Building Programs}
In order to use libTomFloat you must include ``tomfloat.h'' and link against the appropriate library file (typically 
libtomfloat.a).  There is no library initialization required and the entire library is thread safe.

\section{Return Codes}
There are three possible return codes a function may return.

\index{MP\_OKAY}\index{MP\_YES}\index{MP\_NO}\index{MP\_VAL}\index{MP\_MEM}
\begin{figure}[here!]
\begin{center}
\begin{small}
\begin{tabular}{|l|l|}
\hline \textbf{Code} & \textbf{Meaning} \\
\hline MP\_OKAY & The function succeeded. \\
\hline MP\_VAL  & The function input was invalid. \\
\hline MP\_MEM  & Heap memory exhausted. \\
\hline &\\
\hline MP\_YES  & Response is yes. \\
\hline MP\_NO   & Response is no. \\
\hline
\end{tabular}
\end{small}
\end{center}
\caption{Return Codes}
\end{figure}

The last two codes listed are not actually ``return'ed'' by a function.  They are placed in an integer (the caller must
provide the address of an integer it can store to) which the caller can access.  To convert one of the three return codes
to a string use the following function.

\index{mp\_error\_to\_string}
\begin{alltt}
char *mp_error_to_string(int code);
\end{alltt}

This will return a pointer to a string which describes the given error code.  It will not work for the return codes 
MP\_YES and MP\_NO.  

\section{Data Types}

To better work with LibTomFloat it helps to know what makes up the primary data type within LibTomFloat.

\begin{alltt}
typedef struct \{
     mp_int mantissa;
     long   radix,
            exp;
\} mp_float;
\end{alltt}

The mp\_float data type is what all LibTomFloat functions will operate with and upon.  The members of the structre are as follows:

\begin{enumerate}
   \item The \textbf{mantissa} variable is a LibTomMath mp\_int that represents the digits of the float.  Since it's a mp\_int it can accomodate
         any practical range of numbers.
   \item The \textbf{radix} variable is the precision desired for the mp\_float in bits.  The higher the value the more precise (and slow) the 
         calculations are.  This value must be larger than two and ideally shouldn't be lower than what a ``double'' provides (55-bits of mantissa).
   \item The \textbf{exp} variable is the exponent associated with the number.  
\end{enumerate}

\section{Function Organization}

Many of the functions operate as their LibTomMath counterparts.  That is the source operands are on the left and the destination is on the 
right.  For instance:

\begin{alltt}
mpf_add(&a, &b, &c);       /* c = a + b */
mpf_mul(&a, &a, &c);       /* c = a * a */
mpf_div(&a, &b, &c);       /* c = a / b */
\end{alltt}

One major difference (and similar to LibTomPoly) is that the radix of the destination operation controls the radix of the internal computation and 
the final result.  For instance, if $a$ and $b$ have a $24$--bit mantissa and $c$ has a $96$--bit mantissa then all three operations are performed
with $96$--bits of precision.  

This is non--issue for algorithms such as addition or multiplication but more important for the series calculations such as division, inversion,
square roots, etc.

All functions normalize the result before returning.  

\section{Initialization}
\subsection{Single Initializers}

To initialize or clear a single mp\_float use the following two functions.

\index{mpf\_init} \index{mpf\_clear}
\begin{alltt}
int  mpf_init(mp_float *a, long radix);
void mpf_clear(mp_float *a);
\end{alltt}

mpf\_init will initialize $a$ with the given radix to the default value of zero.  mpf\_clear will free the memory used by the 
mp\_float.

\begin{alltt}
int main(void)
\{
   mp_float a;
   int err;

   /* initialize a mp_float with a 96-bit mantissa */
   if ((err = mpf_init(&a, 96)) != MP_OKAY) \{
      // error handle
   \}

   /* we now have a 96-bit mp_float ready ... do work */

   /* done */
   mpf_clear(&a);

   return EXIT_SUCCESS;
\}
\end{alltt}

\subsection{Multiple Initializers}

To initialize or clear multiple mp\_floats simultaneously use the following two functions.

\index{mpf\_init\_multi} \index{mpf\_clear\_multi}
\begin{alltt}
int  mpf_init_multi(long radix, mp_float *a, ...);
void mpf_clear_multi(mp_float *a, ...);
\end{alltt}

mpf\_init\_multi will initialize a \textbf{NULL} terminated list of mp\_floats with the same given radix.  mpf\_clear\_multi will free 
up a \textbf{NULL} terminated list of mp\_floats.

\begin{alltt}
int main(void)
\{
   mp_float a, b;
   int err;

   /* initialize two mp_floats with a 96-bit mantissa */
   if ((err = mpf_init_multi(96, &a, &b, NULL)) != MP_OKAY) \{
      // error handle
   \}

   /* we now have two 96-bit mp_floats ready ... do work */

   /* done */
   mpf_clear_multi(&a, &b, NULL);

   return EXIT_SUCCESS;
\}
\end{alltt}

\subsection{Initialization of Copies}

In order to initialize an mp\_float and make a copy of a source mp\_float the following function has been provided.

\index{mpf\_init\_copy}
\begin{alltt}
int  mpf_init_copy(mp_float *a, mp_float *b);
\end{alltt}

This will initialize $b$ and make it a copy of $a$.  

\begin{alltt}
int main(void)
\{
   mp_float a, b;
   int err;

   /* initialize a mp_float with a 96-bit mantissa */
   if ((err = mpf_init(&a, 96)) != MP_OKAY) \{
      // error handle
   \}

   /* we now have a 96-bit mp_float ready ... do work */

   /* now make our copy */
   if ((err = mpf_init_copy(&a, &b)) != MP_OKAY) \{
      // error handle
   \}

   /* now b is a copy of a */

   /* done */
   mpf_clear_multi(&a, &b, NULL);

   return EXIT_SUCCESS;
\}
\end{alltt}