Re: Multiprecision Integer Math Package

leei@canada.ai.sri.com (Lee Iverson) writes:


> Currently, I understand that the BigInt part of the libg++
> code is being rewritten to use the gmp library.


Not yet, but it will be.


> I believe that no changes are planned for its interface however.


I plan to change the implementation to use 2's complement rather than
signed magnitude. This will make a user-visible difference for logical
(bit-level) operators on negative numbers. This is desirable, I think,
since it will allow us to follow the much cleaner Common Lisp semantics.


I already have an implementation of 2's complement BigNum's, (It is used
in the implementation of my Q language; see
ftp.cygnus.com:~ftp/pub/Q.README.) This implementation needs to be
re-organized for the planned road-map, which I see as:


* THE LOWEST LEVEL: The existing mpn routines for gmp, for unsigned
arithmetic without memory management.


* THE 2'S COMPLEMENT LEVEL, written in C, using a data structure something
like the following:


    typedef unsigned long Word;
    typedef struct Bigint {
        int size;
        union {
            Word w; /* if size <= 0 */
            Word *ptr; /* if size > 1 */
        } u;
        int allocated_size; /* Specifics to be determined. */
    } BitInt;


For integers that fit in one word (which in many applications is most of
them), we store the data directly in the w field of a BigInt. For large
intgers, the data is typically stored in the heap. However, all memory
management will be done by calling a user-overrideable function:


void (*BigIntResize)(BitInt *, int new_size) = DefaultBigIntResize;


The default memory management is done by DefaultBigIntResize, which is
implemented using malloc/realloc/free (depending on the parameter and the
current size).


A typical routine at this level is:


extern void BigIntAdd(BigInt* result, const BigInt* arg1, const BigInt* arg2);


The structure (*result) is over-written with the result of the adddition
of arg1 and arg2. However, the buffer result->u.ptr (if result->size was
originally >= 1) is reused. This routine does not do any memory
management, except that (*BitIntResize) may be called to expand the size
allocated for result->u.ptr.


The algorithms at this level will use code derived from the Q
implementation.


* THE C++ LEVEL will be a simple wrapper around the 2's complement
level:


    class Integer : private BigInt {
      public:
        Integer (int i) { size = 1; u.w = i; }
        Integer(Integer& i) {size = 1; BigIntResize(this, i.size); copy the data;}
        ~Integer() { BigIntResize(this, 0); }


        friend Integer operator+(const Integer& arg1, const Integer& arg2);
        ... etc ...;
    };


    #ifdef __GNUG__
    Integer operator+(const Integer& arg1, const Integer& arg2) return r;
    { BigIntAdd(&r, &arg1, &arg2)
    #else
    Integer operator+(const Integer& arg1, const Integer& arg2)
    { Integer r;
        BigIntAdd(&r, &arg1, &arg2);
        return r;
    }
    #endif


The details (including naming conventions) of all of this still
needs to be worked out.


majid-fazal@math.yale.edu (Fazal Majid) writes:


> The FSF will not accept code that is not under the GNU license.


Not true, but code using the GPL is more likely to be accepted.


Currently gmp is under the Gnu Public License. At least the mpn
layer needs to be released under some other license (perhaps the
GNU Library Public License). We (gmp's author Torbjorn Granlund,
and I) are currently discussing this with Stallman.
--
--Per Bothner
Cygnus Support bothner@cygnus.com
[Note on that last comment, it's probably more correct to say that the FSF
won't accept code under anything that restricts copying more than the GPL
does. Flex and all of the Berkeley code going into the hurd are under
Berkeley copyrights which permit pretty much anything. -John]
--

Return to the comp.compilers page.
Search the comp.compilers archives again.