mardi 3 février 2015

Implement BigInteger division

I create a BigInteger class using an std::string. The interface is as follows:



class BigInteger
{
private:
char sign;
std::string digits;
const std::size_t base = 10;
short toDigit(int index) const {return index >= 0 && index < digits.size() ? digits[index] - '0' : 0;}

public:
BigInteger();
BigInteger(int value);
BigInteger(int64_t value);
BigInteger(const std::string &value);
BigInteger(const BigInteger &other);

inline bool isNegative() const {return sign == '-';}
inline bool isPositive() const {return sign == '+';}
inline bool isNeutral() const {return sign == '~';}

bool operator < (const BigInteger &other) const;
bool operator > (const BigInteger &other) const;
bool operator <= (const BigInteger &other) const;
bool operator >= (const BigInteger &other) const;
bool operator == (const BigInteger &other) const;
bool operator != (const BigInteger &other) const;

BigInteger& operator = (const BigInteger &other);
BigInteger& operator += (const BigInteger &other);
BigInteger& operator -= (const BigInteger &other);
BigInteger& operator *= (const BigInteger &other);
BigInteger& operator /= (const BigInteger &other);

BigInteger operator + (const BigInteger &other) const;
BigInteger operator - (const BigInteger &other) const;
BigInteger operator * (const BigInteger &other) const;
BigInteger operator / (const BigInteger &other) const;

BigInteger& divide(const BigInteger &D, BigInteger &R);

friend std::ostream& operator << (std::ostream& os, const BigInteger& other);
};


Each character in the string, represents ONE digit.


I implemented ALL operators except the divide function and the division operator.


That's where I'm stuck! I was writing all my algorithms based off of Wikipedia explanations and came across the division algorithm that I like:


http://ift.tt/1KmVZKv


I like this one because it gives me the quotient and remainder and that will make implementing modulo easier.


However, I don't have a shift operator and I'm not sure how to set the least significant bit of R to the bit in the numerator from my string. Any ideas how I can implement my divide function?


I tried:



BigInteger& BigInteger::divide(const BigInteger &D, BigInteger &R)
{
if (D.isNeutral()) //if D == 0.
{
throw std::overflow_error("Division By Zero Exception.");
}

R = 0;
BigInteger Q = 0;

for (std::size_t I = 0; I < digits.size(); ++I)
{
R *= 2; //I believe this is the same as shifting left by 1.
R.digits[0] = digits[I];
if (R >= D)
{
R -= D;
Q.digits[I] = '1';
}
}
*this = Q;
return *this;
}


Digits are stored backwards in the string. For example:


value = 1024 digits = 4201


Any ideas what I need to do to get the BitShifting working and to get the division working? The division is more important to me.


Aucun commentaire:

Enregistrer un commentaire