| 1 |
|
| 2 |
|
| 3 |
libmpdec |
| 4 |
======== |
| 5 |
|
| 6 |
libmpdec is a fast C/C++ library for correctly-rounded arbitrary precision |
| 7 |
decimal floating point arithmetic. It is a complete implementation of |
| 8 |
Mike Cowlishaw/IBM's General Decimal Arithmetic Specification. |
| 9 |
|
| 10 |
|
| 11 |
Files required for the Python _decimal module |
| 12 |
============================================= |
| 13 |
|
| 14 |
Core files for small and medium precision arithmetic |
| 15 |
---------------------------------------------------- |
| 16 |
|
| 17 |
basearith.{c,h} -> Core arithmetic in base 10**9 or 10**19. |
| 18 |
bits.h -> Portable detection of least/most significant one-bit. |
| 19 |
constants.{c,h} -> Constants that are used in multiple files. |
| 20 |
context.c -> Context functions. |
| 21 |
io.{c,h} -> Conversions between mpd_t and ASCII strings, |
| 22 |
mpd_t formatting (allows UTF-8 fill character). |
| 23 |
mpalloc.{c,h} -> Allocation handlers with overflow detection |
| 24 |
and functions for switching between static |
| 25 |
and dynamic mpd_t. |
| 26 |
mpdecimal.{c,h} -> All (quiet) functions of the specification. |
| 27 |
typearith.h -> Fast primitives for double word multiplication, |
| 28 |
division etc. |
| 29 |
|
| 30 |
Visual Studio only: |
| 31 |
~~~~~~~~~~~~~~~~~~~ |
| 32 |
vcdiv64.asm -> Double word division used in typearith.h. VS 2008 does |
| 33 |
not allow inline asm for x64. Also, it does not provide |
| 34 |
an intrinsic for double word division. |
| 35 |
|
| 36 |
Files for bignum arithmetic: |
| 37 |
---------------------------- |
| 38 |
|
| 39 |
The following files implement the Fast Number Theoretic Transform |
| 40 |
used for multiplying coefficients with more than 1024 words (see |
| 41 |
mpdecimal.c: _mpd_fntmul()). |
| 42 |
|
| 43 |
umodarith.h -> Fast low level routines for unsigned modular arithmetic. |
| 44 |
numbertheory.{c,h} -> Routines for setting up the Number Theoretic Transform. |
| 45 |
difradix2.{c,h} -> Decimation in frequency transform, used as the |
| 46 |
"base case" by the following three files: |
| 47 |
|
| 48 |
fnt.{c,h} -> Transform arrays up to 4096 words. |
| 49 |
sixstep.{c,h} -> Transform larger arrays of length 2**n. |
| 50 |
fourstep.{c,h} -> Transform larger arrays of length 3 * 2**n. |
| 51 |
|
| 52 |
convolute.{c,h} -> Fast convolution using one of the three transform |
| 53 |
functions. |
| 54 |
transpose.{c,h} -> Transpositions needed for the sixstep algorithm. |
| 55 |
crt.{c,h} -> Chinese Remainder Theorem: use information from three |
| 56 |
transforms modulo three different primes to get the |
| 57 |
final result. |
| 58 |
|
| 59 |
|
| 60 |
Pointers to literature, proofs and more |
| 61 |
======================================= |
| 62 |
|
| 63 |
literature/ |
| 64 |
----------- |
| 65 |
|
| 66 |
REFERENCES.txt -> List of relevant papers. |
| 67 |
bignum.txt -> Explanation of the Fast Number Theoretic Transform (FNT). |
| 68 |
fnt.py -> Verify constants used in the FNT; Python demo for the |
| 69 |
O(N**2) discrete transform. |
| 70 |
|
| 71 |
matrix-transform.txt -> Proof for the Matrix Fourier Transform used in |
| 72 |
fourstep.c. |
| 73 |
six-step.txt -> Show that the algorithm used in sixstep.c is |
| 74 |
a variant of the Matrix Fourier Transform. |
| 75 |
mulmod-64.txt -> Proof for the mulmod64 algorithm from |
| 76 |
umodarith.h. |
| 77 |
mulmod-ppro.txt -> Proof for the x87 FPU modular multiplication |
| 78 |
from umodarith.h. |
| 79 |
umodarith.lisp -> ACL2 proofs for many functions from umodarith.h. |
| 80 |
|
| 81 |
|
| 82 |
Library Author |
| 83 |
============== |
| 84 |
|
| 85 |
Stefan Krah <[email protected]> |
| 86 |
|
| 87 |
|
| 88 |
|