Changes between Version 16 and Version 17 of ReplacingGMPNotes/TheCurrentGMPImplementation


Ignore:
Timestamp:
Jan 15, 2007 4:25:08 AM (7 years ago)
Author:
p_tanski
Comment:

combine and clarify; add colour

Legend:

Unmodified
Added
Removed
Modified
  • ReplacingGMPNotes/TheCurrentGMPImplementation

    v16 v17  
    109109=== GMP Library Implementation === 
    110110 
    111 [general notes, not finished] The GMP library, like most multi-precision libraries has a fundamental limitation that might seem odd if you are only familiar with Haskell--not likely, but it bears mention anyway!  GMP functions require that their operands be separate entities.  (Remember: an operation such as `a + b` has three entities: the two operands and the result.)  That is, if you want to add `mpz_t a` to `mpz_t b`, and place the result in `mpz_t c`, you are fine but if you try to add `a` to `a` you will run into trouble.  (The problem is, the multi-precision integer library functions are designed so the operands cannot alias; this is more of a problem for complex operations such as multiplication than simple operations like addition.)  This limitation might be overcome by designing the API differently, i.e., compare the operands in Haskell, Cmm or whatever before you pass them to the _add function and create a separate copy of the operand if it is indeed the same then you are o.k. for the case where two operands cannot be the same.  For the case where one of the operands and the result is the same you would have to check outside the general Haskell, Cmm or whatever function wrapping the _add function--you would seem to need a higher level construct.  In any case, this is an annoying thing if you expect `Integer` to behave the same way as `Int`.  Here is an example from GHCi: 
     111[general notes, not finished] The GMP library, like most multi-precision libraries has a fundamental limitation that might seem odd if you are only familiar with Haskell--not likely, but it bears mention anyway!  GMP functions require that their operands be separate entities.  (Remember: an operation such as `a + b` has three entities: the two operands and the result.)  That is, if you want to add `mpz_t a` to `mpz_t b`, and place the result in `mpz_t c`, you are fine but if you try to add `a` to `a` you will run into trouble.  (The problem is, the multi-precision integer library functions are designed so the operands cannot alias; this is more of a problem for complex operations such as multiplication than simple operations like addition.)  This limitation might be overcome by designing the API differently, for example: 
     112 1. compare the operands in Haskell, Cmm or whatever before you pass them to the _add function;  
     113 2. if the operands are the same, create a separate copy of the operand 
     114 3. -- you are o.k. for the case where two operands cannot be the same.   
     115 
     116For the case where one of the operands and the result is the same you would have to check outside the general Haskell, Cmm or whatever function wrapping the _add function--you would seem to need a higher level construct.  This is also a problem with Ints in GHCi.  Here is an example: 
    112117{{{ 
     118#!html 
     119<pre> 
    113120  (in GHCi) 
    114   > let m_integer = 123456789 :: Integer 
    115   > let n_integer = m_integer + m_integer 
    116   -- this will show o.k., but the implementation involves *always* making extra temporaries 
    117   > n_integer 
    118   246913578 
     121  <font color=DarkOrchid>> <font color=Blue>let</font> <font color=Black>m_integer</font> <font color=Blue>=</font> <font color=DodgerBlue>123456789</font> <font color=Blue>::</font> <font color=Green>Integer</font> 
     122  <font color=DarkOrchid>></font> <font color=Blue>let</font> <font color=Black>n_integer</font> <font color=Blue>=</font> <font color=Black>m_integer</font> <font color=Blue>+</font> <font color=Black>m_integer</font> 
     123  <font color=Red>-- this will show o.k., but the implementation involves *always* making extra temporaries</font> 
     124  <font color=DarkOrchid>></font> <font color=Black>n_integer</font> 
     125  <font color=DodgerBlue>246913578</font> 
    119126 
    120   -- a = a + a 
    121   > let m_integer = m_integer + m_integer 
    122   > let n_integer = m_integer + m_integer 
     127  <font color=Red>-- a = a + a</font> 
     128  <font color=DarkOrchid>></font> <font color=Blue>let</font> <font color=Black>m_integer</font> <font color=Blue>=</font> <font color=Black>m_integer</font> <font color=Blue>+</font> <font color=Black>m_integer</font> 
     129  <font color=DarkOrchid>></font> <font color=Blue>let</font> <font color=Black>n_integer</font> <font color=Blue>=</font> <font color=Black>m_integer</font> <font color=Blue>+</font> <font color=Black>m_integer</font> 
    123130 
    124   -- this will be fine until you try to evaluate it: 
    125   > n_integer 
    126   *** Exception: stack overflow 
     131  <font color=Red>-- this will be fine until you try to evaluate it:</font> 
     132  <font color=DarkOrchid>></font> <font color=Black>n_integer</font> 
     133  <font color=Crimson>*** Exception: stack overflow</font> 
     134 
     135  <font color=Red>-- now, try the same thing with plain Ints:</font> 
     136  <font color=Red>-- this will default to an Int</font> 
     137  <font color=DarkOrchid>></font> <font color=Blue>let</font> <font color=Black>a</font> <font color=Blue>=</font> <font color=DodgerBlue>5</font> 
     138  <font color=DarkOrchid>></font> <font color=Blue>let</font> <font color=Black>a</font> <font color=Blue>=</font> <font color=Black>a</font> <font color=Blue>+</font> <font color=Black>a</font> 
     139  <font color=DarkOrchid>></font> <font color=Blue>let</font> <font color=Black>b</font> <font color=Blue>=</font> <font color=Black>a</font> <font color=Blue>+</font> <font color=Black>a</font> 
     140  <font color=DarkOrchid>></font> <font color=Black>b</font> 
     141  <font color=Crimson>*** Exception: stack overflow</font> 
     142</pre> 
    127143}}} 
    128  
    129 ''The comment on being able to do this with plain Ints is wrong.''  In fact, plain Ints in ghci (not compiled code) will also cause a stack overflow: 
    130 {{{ 
    131 Prelude> let a = 5 
    132 Prelude> let a = a + a 
    133 Prelude> let b = a + a 
    134 Prelude> b 
    135 *** Exception: stack overflow 
    136 }}}