| |
| |
| 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. |
| |
| |
| 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). |
| memory.{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. |
| vcstdint.h -> stdint.h (included in VS 2010 but not in VS 2008). |
| 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> |
| |
| |
| |
