Changes between Version 42 and Version 43 of ReplacingGMPNotes


Ignore:
Timestamp:
Jan 4, 2007 5:11:01 AM (7 years ago)
Author:
p_tanski
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • ReplacingGMPNotes

    v42 v43  
    22 
    33= Replacing GMP: Bignum libraries, Licensing and Implementation = 
     4 
     5==== Table of Contents ==== 
     6 
     7On this page: 
     8 1. [wiki:ReplacingGMPNotes#Introduction Introduction] 
     9 1. [wiki:ReplacingGMPNotes#ReasonsforReplacingGMPastheBignumlibrary Reasons for Replacing GMP as the Bignum library] 
     10 1. [wiki:ReplacingGMPNotes#OverviewoftheCurrentGMPImplementation Overview of the Current GMP Implementation] 
     11   * [wiki:ReplacingGMPNotes#FilesrelatedtoGMPintheGHCCompilerSourceCode Files related to GMP in the GHC Compiler Source Code] 
     12   * [wiki:ReplacingGMPNotes#OptimisationOpportunities Optimisation Opportunities] 
     13 
     14Other pages: 
     15 * [wiki:ReplacingGMPNotes/PerformanceMeasurements Performance Measurements of other Multi-Precision Libraries] 
     16 * [wiki:ReplacingGMPNotes/MiscGMPDiscussion Miscellaneous GMP Discussion] 
     17 * [wiki:ReplacingGMPNotes/DesignDiscussion Design Discussion] 
     18 * [wiki:ReplacingGMPNotes/RequiredIntegerFunctions Required Integer Functions] 
     19 * [wiki:ReplacingGMPNotes/IntegerFunctionDesign Integer Function Design (C library)] 
     20 * [wiki:ReplacingGMPNotes/ReplacementLibraryIntegration Replacement Library Integration] 
    421 
    522=== Introduction === 
     
    210227}}} 
    211228If an integer add were to overflow here, the addition operation would be performed ''twice''; even if the integer add did not overflow one extra operation is performed.  Is this an acceptable price for no comparisons? 
    212  
    213 === Benchmarks for Multi-Precision Libraries === 
    214  
    215 The benchmarks below were made with unmodified multi-precision libraries for Integral Arithmetic compiled using Apple gcc 4.0.1 with optimisation settings: -O3 -ftree-vectorize -falign-loops=16.  The tests performed Multiplication, Squaring, Powers (up to 7) and Division each 1,000,000 times at the base level of bit-precision (the number of bits in the operands).  Higher levels of precision performed incrementally fewer rounds: the base level (1,000,000 / (i * 3)) where i is the number for the round, incremented from 0.  For example, at a bit-precision of 512 (second bit-precision test), the number of rounds was (1,000,000 / (1 * 3)) = (1,000,000 / 3) = 333,333 rounds.  Multi-precision libraries may use unsigned chars, unsigned ints, unsigned long ints, unsigned long long ints or doubles, so the actual number of "words" in each multi-precision array may differ; for multi-precision real numbers using doubles, integer precision was calculated at 48.3 bits of real precision per double, rounded up to 49.  (49 bits conservatively equates to about 9 decimal digits of precision, see, e.g., [http://docs.sun.com/source/806-3568/ncg_goldberg.html What Every Computer Scientist Should Know about Floating-Point Arithmetic].)  Libraries tested were: 
    216  
    217  * [http://crd.lbl.gov/~dhbailey/mpdist/ ARPREC]  
    218  * [http://www.openssl.org/ OpenSSL's BN] (part of libcrypto) 
    219  * [http://swox.com/gmp/ GMP] 
    220  * [http://math.libtomcrypt.com/ LibTomMath] 
    221  * [http://www.eskimo.com/~weidai/cryptlib.html Crypto++] a cryptographic library in C++, the Integer class 
    222  * [http://botan.randombit.net/ Botan] a cryptographic library in C++,  
    223  * [http://www.cs.dartmouth.edu/~sting/mpi/ MPI] 
    224  * [http://www.tc.umn.edu/~ringx004/mapm-main.html MAPM] 
    225  
    226 Crypto++, Botan, MPI and MAPM showed performance far below ARPREC, OpenSSL's BN, GMP and !LibTomMath, so results are only shown for the last four.  Note that there are other libraries available for arbitrary precision arithmetic other than those mentioned or tested here.  Most of those other libraries are licensed under the GPL, while the remainder, such as the [http://www2.hursley.ibm.com/decimal/decnumber.html decNumber] library (free, under the [http://www-306.ibm.com/software/globalization/icu/license.jsp ICU license]) are designed and tuned for operations that would be difficult to translate into Haskell's Integer primitive. 
    227  
    228 [[Image(Multiplication.gif)]] 
    229  
    230 [[Image(Squaring.gif)]] 
    231  
    232 [[Image(Powers_log10.gif)]] 
    233  
    234 [[Image(Division.gif)]]