Last active
December 26, 2015 00:39
-
-
Save neetsdkasu/7065838 to your computer and use it in GitHub Desktop.
class managing Big Integer ( test on ideone: http://ideone.com/EGANYD )
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <cstdio> | |
using namespace std; | |
class Carrier; | |
class BigInt; | |
class Decimal; | |
class Carrier { | |
friend class Decimal; | |
protected: | |
struct Four { | |
Four *upper; | |
Four *under; | |
unsigned long value; | |
Four(); | |
}; | |
Four *most; | |
Four *least; | |
unsigned long count; | |
Carrier(); | |
~Carrier(); | |
virtual unsigned long calcFlow(const unsigned long& value) const = 0; | |
virtual unsigned long calcUnit(const unsigned long& value) const = 0; | |
void init(unsigned long value); | |
Four* carry(); | |
Carrier& copy(const Carrier& carrier); | |
Carrier& copy(const Carrier *carrier); | |
Carrier& swap(Carrier& carrier); | |
Carrier& add(const Carrier& value); | |
Carrier& mul(const Carrier& value, Carrier& temp); | |
}; | |
class BigInt : public Carrier | |
{ | |
friend class Decimal; | |
private: | |
static const unsigned long UNIT = 0xFFFF; | |
static const unsigned long SHIFT = 16; | |
unsigned long calcFlow(const unsigned long& value) const; | |
unsigned long calcUnit(const unsigned long& value) const; | |
public: | |
BigInt(); | |
BigInt(unsigned long value); | |
BigInt(const BigInt& value); | |
BigInt(const BigInt *value); | |
BigInt operator ++ (int); | |
BigInt& operator ++ (); | |
BigInt& operator += (const BigInt& value); | |
BigInt& operator *= (const BigInt& value); | |
BigInt& operator = (const BigInt& value); | |
BigInt operator + (const BigInt& value) const; | |
BigInt operator * (const BigInt& value) const; | |
unsigned long digits() const; | |
void print() const; | |
void println() const; | |
}; | |
class Decimal : public Carrier | |
{ | |
private: | |
static const unsigned long UNIT = 10000; | |
unsigned long calcFlow(const unsigned long& value) const; | |
unsigned long calcUnit(const unsigned long& value) const; | |
public: | |
Decimal(); | |
Decimal(unsigned long value); | |
Decimal(const Decimal& value); | |
Decimal(const Decimal *value); | |
Decimal(const BigInt& value); | |
Decimal(const BigInt *value); | |
Decimal operator ++ (int); | |
Decimal& operator ++ (); | |
Decimal& operator += (const Decimal& value); | |
Decimal& operator *= (const Decimal& value); | |
Decimal& operator = (const Decimal& value); | |
Decimal operator + (const Decimal& value) const; | |
Decimal operator * (const Decimal& value) const; | |
unsigned long digits() const; | |
void print() const; | |
void println() const; | |
}; | |
BigInt operator + (const unsigned long& lvalue, const BigInt& rvalue); | |
BigInt operator * (const unsigned long& lvalue, const BigInt& rvalue); | |
Decimal operator + (const unsigned long& lvalue, const Decimal& rvalue); | |
Decimal operator * (const unsigned long& lvalue, const Decimal& rvalue); | |
Carrier::Four::Four() : upper(NULL), under(NULL), value(0) {} | |
Carrier::Carrier() : count(1) { most = least = new Four; } | |
Carrier::~Carrier() { | |
Four *temp; | |
while (most != NULL) { | |
temp = most->under; | |
delete most; | |
most = temp; | |
} | |
//count = 0; | |
//most = least = NULL; | |
} | |
void Carrier::init(unsigned long value) { | |
Four *temp = least; | |
while (value > 0) { | |
if (temp == NULL) { | |
temp = carry(); | |
} | |
temp->value = calcUnit(value); | |
value = calcFlow(value); | |
temp = temp->upper; | |
} | |
} | |
Carrier& Carrier::copy(const Carrier& carrier) { | |
Four *me = least; | |
Four *he = carrier.least; | |
while (he != NULL) { | |
if (me == NULL) { | |
me = carry(); | |
} | |
me->value = he->value; | |
me = me->upper; | |
he = he->upper; | |
} | |
while (me != NULL) { | |
me->value = 0; | |
me = me->upper; | |
} | |
return *this; | |
} | |
Carrier& Carrier::copy(const Carrier *carrier) { if (carrier != NULL) { copy(*carrier); } return *this; } | |
Carrier& Carrier::swap(Carrier& carrier) { | |
Four *temp_most = most; | |
Four *temp_least = least; | |
int temp_count = count; | |
most = carrier.most; | |
least = carrier.least; | |
count = carrier.count; | |
carrier.most = temp_most; | |
carrier.least = temp_least; | |
carrier.count = temp_count; | |
return *this; | |
} | |
Carrier::Four* Carrier::carry() { | |
count++; | |
Four *temp = new Four; | |
temp->under = most; | |
most->upper = temp; | |
most = temp; | |
return most; | |
} | |
Carrier& Carrier::add(const Carrier& value) { | |
unsigned long flow = 0; | |
Four *me = least; | |
Four *he = value.least; | |
while (he != NULL) { | |
if (me == NULL) { | |
me = carry(); | |
} | |
me->value += he->value + flow; | |
flow = calcFlow(me->value); | |
me->value = calcUnit(me->value); | |
me = me->upper; | |
he = he->upper; | |
} | |
while (flow > 0) { | |
if (me == NULL) { | |
me = carry(); | |
} | |
me->value += flow; | |
flow = calcFlow(me->value); | |
me->value = calcUnit(me->value); | |
me = me->upper; | |
} | |
return *this; | |
} | |
Carrier& Carrier::mul(const Carrier& value, Carrier& temp) { | |
swap(temp); | |
Four *me = least; | |
Four *he = value.least; | |
Four *she, *who; | |
unsigned long flow1, flow2, product; | |
while (he != NULL) { | |
if (me == NULL) { | |
me = carry(); | |
} | |
she = temp.least; | |
who = me; | |
flow1 = flow2 = 0; | |
while (she != NULL) { | |
if (who == NULL) { | |
who = carry(); | |
} | |
product = he->value * she->value; | |
flow2 = calcFlow(product); | |
who->value += calcUnit(product); | |
flow2 += calcFlow(who->value); | |
who->value = calcUnit(who->value); | |
who->value += flow1; | |
flow1 = flow2 + calcFlow(who->value); | |
who->value = calcUnit(who->value); | |
who = who->upper; | |
she = she->upper; | |
} | |
while (flow1 > 0) { | |
if (who == NULL) { | |
who = carry(); | |
} | |
who->value += flow1; | |
flow1 = calcFlow(who->value); | |
who->value = calcUnit(who->value); | |
who = who->upper; | |
} | |
me = me->upper; | |
he = he->upper; | |
} | |
return *this; | |
} | |
unsigned long BigInt::calcFlow(const unsigned long& value) const { return value >> SHIFT; } | |
unsigned long BigInt::calcUnit(const unsigned long& value) const { return value & UNIT; } | |
BigInt::BigInt() {} | |
BigInt::BigInt(unsigned long value) { init(value); } | |
BigInt::BigInt(const BigInt& value) { copy(value); } | |
BigInt::BigInt(const BigInt *value) { copy(value); } | |
void BigInt::print() const { Decimal temp(*this); temp.print(); } | |
void BigInt::println() const { Decimal temp(*this); temp.print(); putchar('\n'); } | |
unsigned long BigInt::digits() const { Decimal temp(*this); return temp.digits(); } | |
BigInt& BigInt::operator ++ () { add(BigInt(1)); return *this; } | |
BigInt BigInt::operator ++ (int) { BigInt temp(*this); add(BigInt(1)); return temp; } | |
BigInt& BigInt::operator += (const BigInt& value) { add(value); return *this; } | |
BigInt BigInt::operator + (const BigInt& value) const { BigInt sum(value); sum.add(*this); return sum; } | |
BigInt& BigInt::operator *= (const BigInt& value) { BigInt zero; mul(value, zero); return *this; } | |
BigInt BigInt::operator * (const BigInt& value) const { BigInt product(value), zero; product.mul(*this, zero); return product; } | |
BigInt& BigInt::operator = (const BigInt& value) { copy(value); return *this; } | |
BigInt operator + (const unsigned long& lvalue, const BigInt& rvalue) { return BigInt(lvalue) + rvalue; } | |
BigInt operator * (const unsigned long& lvalue, const BigInt& rvalue) { return BigInt(lvalue) * rvalue; } | |
unsigned long Decimal::calcFlow(const unsigned long& value) const { return value / UNIT; } | |
unsigned long Decimal::calcUnit(const unsigned long& value) const { return value % UNIT; } | |
Decimal::Decimal() {} | |
Decimal::Decimal(unsigned long value) { init(value); } | |
Decimal::Decimal(const Decimal& value) { copy(value); } | |
Decimal::Decimal(const Decimal *value) { copy(*value); } | |
Decimal::Decimal(const BigInt& value) { | |
const Decimal temp(BigInt::UNIT + 1); | |
Four *cur = value.most; | |
while (cur != NULL) { | |
Decimal zero; | |
mul(temp, zero); | |
add(Decimal(cur->value)); | |
cur = cur->under; | |
} | |
} | |
Decimal::Decimal(const BigInt *value) { | |
if (value != NULL) { | |
Decimal temp(*value); | |
swap(temp); | |
} | |
} | |
void Decimal::print() const { | |
Four *temp = most; | |
int f = 0; | |
while (temp != NULL) { | |
if (f == 0) { | |
if (temp->value != 0) { | |
printf("%ld", temp->value); | |
f = 1; | |
} | |
} else { | |
printf("%04ld", temp->value); | |
} | |
temp = temp->under; | |
} | |
if (f == 0) { | |
putchar('0'); | |
} | |
} | |
void Decimal::println() const { print(); putchar('\n'); } | |
unsigned long Decimal::digits() const { | |
unsigned long temp_count = count; | |
Four *temp = most; | |
while (temp->value == 0) { | |
temp_count--; | |
if ((temp = temp->under) == NULL) { | |
return 1; | |
} | |
} | |
temp_count *= 4; | |
unsigned long unit = UNIT / 10; | |
while (temp->value < unit) { | |
temp_count--; | |
unit /= 10; | |
} | |
return temp_count; | |
} | |
Decimal& Decimal::operator ++ () { add(Decimal(1)); return *this; } | |
Decimal Decimal::operator ++ (int) { Decimal temp(*this); add(Decimal(1)); return temp; } | |
Decimal& Decimal::operator += (const Decimal& value) { add(value); return *this; } | |
Decimal Decimal::operator + (const Decimal& value) const { Decimal sum(value); sum.add(*this); return sum; } | |
Decimal& Decimal::operator *= (const Decimal& value) { Decimal zero; mul(value, zero); return *this; } | |
Decimal Decimal::operator * (const Decimal& value) const { Decimal product(value), zero; product.mul(*this, zero); return product; } | |
Decimal& Decimal::operator = (const Decimal& value) { copy(value); return *this; } | |
Decimal operator + (const unsigned long& lvalue, const Decimal& rvalue) { return Decimal(lvalue) + rvalue; } | |
Decimal operator * (const unsigned long& lvalue, const Decimal& rvalue) { return Decimal(lvalue) * rvalue; } | |
int main() { | |
BigInt val1(111111); | |
BigInt val2(val1 + 800800); | |
BigInt val3(val1 * val2); | |
BigInt val4(val1 + val2); | |
val3 *= val1 * val1; | |
val4 += val2 * val2;; | |
val1.println(); | |
cout << "digits: " << val1.digits() << endl; | |
val2.println(); | |
cout << "digits: " << val2.digits() << endl; | |
val3.println(); | |
cout << "digits: " << val3.digits() << endl; | |
val4.println(); | |
cout << "digits: " << val4.digits() << endl; | |
Decimal dec1(111111); | |
Decimal dec2(dec1 + 800800); | |
Decimal dec3(dec1 * dec2); | |
Decimal dec4(dec1 + dec2); | |
dec3 *= dec1 * dec1; | |
dec4 += dec2 * dec2; | |
dec1.println(); | |
cout << "digits: " << dec1.digits() << endl; | |
dec2.println(); | |
cout << "digits: " << dec2.digits() << endl; | |
dec3.println(); | |
cout << "digits: " << dec3.digits() << endl; | |
dec4.println(); | |
cout << "digits: " << dec4.digits() << endl; | |
BigInt val5(val4 * val4 * val4); | |
val5 *= val5 * val5 * val5; | |
val5 *= val5 * val5 * val5; | |
Decimal dec5(val5); | |
dec5.println(); | |
cout << "digits: " << dec5.digits() << endl; | |
BigInt val6; | |
val6 = 9 * val1; | |
val6.println(); | |
Decimal dec6; | |
dec6 = 12345 + dec1; | |
dec6++; | |
++dec6; | |
dec6.println(); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment