Integer Class

Post date: Nov 27, 2013 3:17:47 AM

سلام

مدتی بود می‌خواستم کلاسی برای اعداد صحیح برزگ بنویسم. فرصت شد نوشتم. در نوشتن به این فکر می‌کردم که اصول اولیه اعداد صیحیح را می‌شود با برنامه نویسی خیلی بهتر گفت تا اصول پئانو در ریاضیات. البته در ریاضیات اعداد حقیقی هم هستند که بدون شک به شکل مشابه نمی‌شود آن‌ها را بازسازی کرد. فقط یک زیر مجموعه شمارش پذیر از اون‌ها را می‌شود شبیه سازی کرد.

کلاس زیر را می‌شود اصلاح کرد و بهترش کرد. این کلاس با رشته‌ها نوشته شده است. این طور بهتر است چون با رشته‌ها راحت تر می‌شود کار کرد تا بیت‌ها. ولی مشکل این جاست که حجم ذخیره سازی عدد بالاتر است که در کامپوترهای امروزی یک مشکل به حساب نمی‌آید. البته قبل از نوشتن ایدۀ من این بود که از کنار هم گذاشتن متغیرهای معمولی استفاده کنیم. ولی نوشتن برنامه با رشته، طبیعی تر به نظر می‌رسد. من برای ضرب و تقسیم همان روشی را به کار برده‌ام که در دورۀ ابتدایی گفته می‌شود. مبنا 10 است ولی می‌شود به راحتی مبنا را عوض کرد.

#include <string>

#include <vector>

#include <map>

#include <iostream>

using namespace std;

inline void print_error(string error)

{

cout<< error;

}

class Unsigned

{

public:

string number;

private:

void AddZeros(unsigned n)

{

if(n == 0)

return;

if(n > 5000) // protecting code

print_error("AddZero");

char* c = new char [n + 1];

for(unsigned i = 0; i < n; i++)

c[i] = '0';

c[n] = 0;

number = string(c) + number;

delete [] c;

}

void RemoveZeros()

{

unsigned len = number.size();

if(len == 0) // protecting code

print_error("RemoveZeros");

const char* c = number.c_str();

unsigned s = 0;

while(c[s] == '0')

{

s++;

if(s >= len - 1) // needed if number == "000"

break;

}

number = string(c + s);

}

unsigned DigNum() const

{

return number.size();

}

void SetDigNum(unsigned len)

{

RemoveZeros();

if(DigNum() < len)

AddZeros(len - DigNum());

}

unsigned Dig(unsigned n) const

{

unsigned dignum = DigNum();

if(n < dignum)

return number[dignum - n - 1] - '0';

else

return 0;

}

void SetDig(unsigned dig, unsigned value)

{

unsigned i = 0;

while(true)

{

unsigned dignum = DigNum();

unsigned n = dig + i + 1;

if(dignum < n)

{

SetDigNum(n);

dignum = DigNum();

}

number[dignum - n] = value % 10 + '0';

if(value < 10)

break;

value /= 10;

i++;

if(i > 50) // protecting code

break;

}

}

void AddDig(unsigned dig, unsigned value)

{

unsigned dignum = DigNum();

unsigned n = dig + 1;

if(dignum < n)

{

SetDigNum(n);

dignum = DigNum();

}

number[dignum - n] += value % 10;

if(number[dignum - n] >= 10 + '0')

{

number[dignum - n] -= 10;

AddDig(dig + 1,1);

}

if(value >= 10)

AddDig(dig + 1,value / 10);

}

void SubDig(unsigned dig, unsigned value)// SubtractDig

{

unsigned dignum = DigNum();

if(Dig(dig) >= value)

SetDig(dig,Dig(dig) - value);

else

{

if(dig + 1 >= dignum)

print_error("SubDig");

else

{

SubDig(dig + 1,1);

SetDig(dig,10 + Dig(dig) - value);

}

}

}

void DivideBy(const Unsigned& U2,string& ret_number,unsigned min_sep) const

{

const Unsigned& U1 = *this;

if(U1 < U2)

{

ret_number += "0";

return;

}

unsigned sep = 1 + min_sep;

string str = U1.number;

char* cstr = (char*) str.c_str();

char reserved_ch = cstr[sep];

cstr[sep] = 0;

Unsigned paraU1 = string(cstr);

while(paraU1 < U2)

{

if(ret_number != "")

ret_number += "0";

cstr[sep] = reserved_ch;

sep++;

reserved_ch = cstr[sep];

cstr[sep] = 0;

paraU1 = string(cstr);

}

//so now U2 <= paraU1

string para_number;

for(unsigned i = 1;; i++)

{

Unsigned I(i);

if(paraU1 < I*U2)

{

para_number = (Unsigned(i - 1)).number;

break;

}

if(i >= 11)

{

print_error("division by zero");

return;

}

}

ret_number += para_number;

Unsigned paraQ = para_number;

if(reserved_ch != 0)

{

const char* c = U1.number.c_str();

Unsigned paraRemainder = paraU1 - paraQ*U2;

if(paraRemainder == Unsigned("0"))

{

Unsigned newU1 = string(c + sep);

newU1.DivideBy(U2,ret_number,0);

}

else

{

Unsigned newU1 = paraRemainder.number + string(c + sep);

newU1.DivideBy(U2,ret_number,paraRemainder.DigNum());

}

}

}

public:

string GetStr()

{

return number;

}

//-----------------------------------

void operator +=(const unsigned& value)

{

AddDig(0,value);

}

Unsigned operator +(const Unsigned& U) const

{

Unsigned ret = *this;

unsigned U_dignum = U.DigNum();

for(unsigned i = 0; i < U_dignum; i++)

ret.AddDig(i,U.Dig(i));

ret.RemoveZeros();

return ret;

}

void operator += (const Unsigned& U)

{

*this = *this + U;

}

Unsigned operator ++()

{

*this += Unsigned("1");

return *this;

}

void operator -= (const Unsigned& U)

{

*this = *this - U;

}

Unsigned operator --()

{

*this -= Unsigned("1");

return *this;

}

Unsigned operator *(const Unsigned& u2) const

{

const Unsigned& u1 = *this;

Unsigned ret;

unsigned dignum1 = u1.DigNum();

unsigned dignum2 = u2.DigNum();

for(unsigned i = 0; i < dignum1; i++)

for(unsigned j = 0; j < dignum2; j++)

ret.AddDig( i + j , u1.Dig(i)*u2.Dig(j) );

return ret;

}

bool operator < (const Unsigned& u2) const

{

const Unsigned& u1 = *this;

unsigned dignum1 = u1.DigNum();

unsigned dignum2 = u2.DigNum();

unsigned max = dignum1 <= dignum2 ? dignum2 : dignum1;

for(unsigned i = 1 ; i <= max; i++)

{

unsigned dig1 = u1.Dig(max - i); // delete

unsigned dig2 = u2.Dig(max - i); // delete

if(dig1 < dig2)

return true;

else if(dig2 < dig1)

return false;

}

return false;

}

bool operator > (const Unsigned& u2) const

{

const Unsigned& u1 = *this;

return u2 < u1;

}

bool operator == (Unsigned u2) const

{

Unsigned u1 = *this;

u1.RemoveZeros();

u2.RemoveZeros();

return u1.number == u2.number;

}

bool operator <= (const Unsigned& u2) const

{

const Unsigned& u1 = *this;

if(u1 < u2)

return true;

if(u1 == u2)

return true;

return false;

}

bool operator >= (const Unsigned& u2) const

{

const Unsigned& u1 = *this;

return u2 <= u1;

}

Unsigned operator - (const Unsigned& u2) const

{

const Unsigned& u1 = *this;

if(u1 <= u2)

return Unsigned("0"); // return zero

Unsigned ret = u1;

unsigned dignum2 = u2.DigNum();

for(unsigned i = 0; i < dignum2; i++)

ret.SubDig(i,u2.Dig(i));

ret.RemoveZeros();

return ret;

}

Unsigned operator / (const Unsigned& U2) const

{

string ret_number;

DivideBy(U2,ret_number,U2.DigNum() - 1);

return Unsigned(ret_number);

}

//-----------------------------------

Unsigned& operator = (const Unsigned& U)

{

number = U.number;

return *this;

}

Unsigned() : number("0")

{

}

Unsigned(string _number) : number(_number)

{

}

Unsigned(unsigned n) : number("0")

{

SetDig(0,n);

}

Unsigned(const Unsigned& U) : number(U.number)

{

}

};

class Integer

{

public:

bool negative;

Unsigned abs;

void Negate()

{

if(abs == Unsigned("0"))

negative = false;

else

{

if(negative == true)

negative = false;

else

negative = true;

}

}

string GetStr()

{

string ret;

if(negative)

ret += "-";

ret += abs.GetStr();

return ret;

}

//-----------------------------------

Integer operator +(const Integer& I2) const

{

const Integer& I1 = *this;

Integer ret;

if(I1.negative)

{

if(I2.negative)

{

ret.abs = I1.abs + I2.abs;

ret.Negate();

}

else

{

if(I1.abs < I2.abs)

ret.abs = I2.abs - I1.abs;

else // if I2.abs <= I1.abs

{

ret.abs = I1.abs - I2.abs;

ret.Negate();

}

}

}

else if(I2.negative)

ret = I2 + I1;

else

ret.abs = I1.abs + I2.abs;

return ret;

}

void operator += (const Integer& I)

{

*this = *this + I;

}

Integer operator ++()

{

*this += Integer("1");

return *this;

}

void operator -= (const Integer& I)

{

*this = *this - I;

}

Integer operator --()

{

*this -= Integer("1");

return *this;

}

Integer operator *(const Integer& I2) const

{

const Integer& I1 = *this;

Integer ret;

ret.abs = I1.abs * I2.abs;

if( (!I1.negative && I2.negative) || (I1.negative && !I2.negative) )

ret.Negate();

return ret;

}

bool operator < (const Integer& I2) const

{

const Integer& I1 = *this;

if(!I1.negative && I2.negative)

return false;

if(I1.negative && !I2.negative)

return true;

if(I1.negative && I2.negative)

return (I2.abs < I1.abs);

return I1.abs < I2.abs;

}

bool operator > (const Integer& I2) const

{

const Integer& I1 = *this;

return I2 < I1;

}

bool operator == (const Integer& I2) const

{

const Integer& I1 = *this;

if(I1.abs == I2.abs && I1.negative == I2.negative)

return true;

return false;

}

bool operator <= (const Integer& I2) const

{

const Integer& I1 = *this;

if(I1 < I2)

return true;

if(I1 == I2)

return true;

return false;

}

bool operator >= (const Integer& I2) const

{

const Integer& I1 = *this;

return I2 <= I1;

}

Integer operator - (Integer I2) const

{

const Integer& I1 = *this;

I2.Negate();

return I1 + I2;

}

Integer operator / (const Integer& I2) const

{

const Integer& I1 = *this;

Integer ret;

ret.abs = I1.abs / I2.abs;

if( (!I1.negative && I2.negative) || (I1.negative && !I2.negative) )

ret.Negate();

return ret;

}

//-----------------------------------

Integer() : abs(), negative(false)

{

}

Integer(string number) : abs(), negative(false)

{

if(number[0] == '-')

{

negative = true;

const char* c = number.c_str();

abs = Unsigned(string(c + 1));

}

else

abs = Unsigned(number);

if(abs == Unsigned(0))

negative = false;

}

Integer(int n): abs(), negative(false)

{

if(0 <= n)

abs = Unsigned(unsigned(n));

else

{

negative = true;

abs = Unsigned(unsigned(-n));

}

if(n == 0)

negative = false;

}

Integer(const Integer& I): abs(I.abs), negative(I.negative)

{

}

};

inline ostream& operator << (ostream&,Integer I)

{

cout<< I.GetStr();

return cout;

}

int main()

{

Integer a("100");

Integer b("-110");

cout<< a - b;

cin.get();

}

Output:

210