[boost] GSOC Proposal for BIGINT - Long Mail

Subject: [boost] GSOC Proposal for BIGINT - Long Mail
From: swagat konchada (swagatata_at_[hidden])
Date: 2010-03-24 19:20:52

I had a look around in the Boost Sandbox and I found a BigInt implementation
done by zeux during GSoC 07. I had a look at the code and I wanted to know
its deficiencies. I'm interested

in proposing some improvements in bigint and new bigdecimal implementation
that is building on this code. There are 2 questions that I wanted to ask
the list before moving further on this track:

1. Is there sufficient interest for a BigDecimal proposal on the lines of
the Java implementation of BigDecimal (or has there been some prior work
that can be used as a foundation?)
2. What are the deficiencies of bigint that have prevented its inclusion
into the Boost distribution so as to address the same as part of my GSoC
proposal.

I did some homework and contrasted the bigint api in Boost and Java and
found some interesting things that could be done.
Boost.bigint was written by zeux and he used GMP bigint's features writing
the Boost.bigint code around it. I think I could learn and analyse more
after having a look at GMP bigint. After all, I think Boost.bigint should be
more exhaustive.

--------------------------------------------------------------------------------------------------------------------------------------------------------------
Feature            Boost bigint            Java BigInt
--------------------------------------------------------------------------------------------------------------------------------------------------------------

Constructors from
        |    int                                 |    byte[]
#byte array with 2's complement representation of the BigInt.
        |    unsigned int                   |    int bitlen, int certainity
    #random BigInt with given bit length
        |    int64_t                           |
        |    uint64_t                         |
        |    char *, int base               |    String
        |    string& str, int base        |    String, radix
--------------------------------------------------------------------------------------------------------------------------------------------------------------

*Conversion from string of digits to bigint is present. However conversion
from/to byte-array(2's complement notation) to/from bigint isn't.

 Also the generation of a random arbitrary precision bigint should be done.
 int     bitCount()  #return the no of bits in 2's complement of the bigint;
 int    bitLength() #no of bits excluding the sign bit
 double     doubleValue() #casting bigint to double must be done. #even
casts to int, uint and int64_t, char * must be done.*

--------------------------------------------------------------------------------------------------------------------------------------------------------------

Arithmetic Operators
            +=                    In Java, add, subtract, multiply, etc.,

        |    -=
        |    *=
        |    /=
        |    %=
        |    |=
        |    &=
        |    ^=    #xor
        |    <<=
        |    >>=

        |    ++    #postfix & prefix
        |    --    #postfix & prefix

--------------------------------------------------------------------------------------------------------------------------------------------------------------

Unary Operators        +
            -                    BigInteger[]     negate()
            ~                    BigInteger[]     not()

            !    #is zero

            <                      int     compareTo(BigInteger val)
            <=                    BigInteger     max,min(BigInteger val)
            >
            >=
            ==
            !=
--------------------------------------------------------------------------------------------------------------------------------------------------------------
*These are some bit manipulators
     BigInteger     clearBit(int n) #not in Boost.bigint
                       #even setBit & toggleBit could be done, with a
feature of changing the precision of the bigint.
    BigInteger[]     testBit(int n) #also bit testers l*

--------------------------------------------------------------------------------------------------------------------------------------------------------------
Binary Operators
            +                    BigInteger     add(BigInteger val)
            -
            *                    BigInteger     multiply(BigInteger val)
{bigint lhs, int rhs}
{int lhs, bigint rhs}
            /                    BigInteger     divide(BigInteger val)

           %                   BigInteger     mod(BigInteger val) ,
BigInteger     modPower(BigInteger val)
            |                    BigInteger     or(BigInteger val)

            &                    BigInteger     and(BigInteger val)
            ^                     BigInteger     andNot(BigInteger val)

            <<                    BigInteger     shiftLeft(int n)
            >>                    BigInteger     shiftRight(int n)

--------------------------------------------------------------------------------------------------------------------------------------------------------------
Math function overloads
            abs(bigint_base)                        BigInteger     abs(int
exponent)
            pow(bigint_base, uint64_t)            BigInteger     pow(int
exponent)
            div(bigint_base lhs, bigint_base rhs, bigint_base& remainder)
BigInteger[]     divideAndRemainder(BigInteger val)
            sqrt(bigint_base)                       ----------No Java
version for BigInterger------------
--------------------------------------------------------------------------------------------------------------------------------------------------------------

     *BigInteger     gcd(BigInteger val)
                     #GCD would be one of the most important requirements
for bigint
                     #Also the Java function of bool ProbablyPrime() is very
interesting and would be challenging to implement.*
--------------------------------------------------------------------------------------------------------------------------------------------------------------

-- 
Problem is a phenomenon indicating lack of thought.
Swagat Konchada