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