libmpdec

========

libmpdec is a fast C/C++ library for correctly-rounded arbitrary precision

decimal floating point arithmetic. It is a complete implementation of

Mike Cowlishaw/IBM's General Decimal Arithmetic Specification.

Files required for the Python _decimal module

=============================================

Core files for small and medium precision arithmetic

----------------------------------------------------

basearith.{c,h} -> Core arithmetic in base 10**9 or 10**19.

bits.h -> Portable detection of least/most significant one-bit.

constants.{c,h} -> Constants that are used in multiple files.

context.c -> Context functions.

io.{c,h} -> Conversions between mpd_t and ASCII strings,

mpd_t formatting (allows UTF-8 fill character).

mpalloc.{c,h} -> Allocation handlers with overflow detection

and functions for switching between static

and dynamic mpd_t.

mpdecimal.{c,h} -> All (quiet) functions of the specification.

typearith.h -> Fast primitives for double word multiplication,

division etc.

Visual Studio only:

~~~~~~~~~~~~~~~~~~~

vccompat.h -> snprintf <==> sprintf_s and similar things.

vcdiv64.asm -> Double word division used in typearith.h. VS 2008 does

not allow inline asm for x64. Also, it does not provide

an intrinsic for double word division.

Files for bignum arithmetic:

----------------------------

The following files implement the Fast Number Theoretic Transform

used for multiplying coefficients with more than 1024 words (see

mpdecimal.c: _mpd_fntmul()).

umodarith.h -> Fast low level routines for unsigned modular arithmetic.

numbertheory.{c,h} -> Routines for setting up the Number Theoretic Transform.

difradix2.{c,h} -> Decimation in frequency transform, used as the

"base case" by the following three files:

fnt.{c,h} -> Transform arrays up to 4096 words.

sixstep.{c,h} -> Transform larger arrays of length 2**n.

fourstep.{c,h} -> Transform larger arrays of length 3 * 2**n.

convolute.{c,h} -> Fast convolution using one of the three transform

functions.

transpose.{c,h} -> Transpositions needed for the sixstep algorithm.

crt.{c,h} -> Chinese Remainder Theorem: use information from three

transforms modulo three different primes to get the

final result.

Pointers to literature, proofs and more

=======================================

literature/

-----------

REFERENCES.txt -> List of relevant papers.

bignum.txt -> Explanation of the Fast Number Theoretic Transform (FNT).

fnt.py -> Verify constants used in the FNT; Python demo for the

O(N**2) discrete transform.

matrix-transform.txt -> Proof for the Matrix Fourier Transform used in

fourstep.c.

six-step.txt -> Show that the algorithm used in sixstep.c is

a variant of the Matrix Fourier Transform.

mulmod-64.txt -> Proof for the mulmod64 algorithm from

umodarith.h.

mulmod-ppro.txt -> Proof for the x87 FPU modular multiplication

from umodarith.h.

umodarith.lisp -> ACL2 proofs for many functions from umodarith.h.

Library Author

==============

Stefan Krah <skrah@bytereef.org>