Implementing High-Precision Arithmetic in C++ with a Custom Big Integer Class
Tech
2
A high-precision integer class enables arithmetic operations on numbers exceedign standard integer limits, icnluding handling negative values.
This class uses a fixed-size array to store digits, with M defining the maximum length of the string representation. It overloads operators for addition, subtraction, multiplication, division, and modulus, along with comparison operators like <=. It also spuports fast exponentiation.
Key functions enclude:
BigInt example;
BigInt::convertToBigInt(1); // Converts integer 1 to BigInt type
example.reset(); // Initializes all digits to zero
example.read(); // Reads input from standard input
example.write(0 or 1) // 1 outputs with newline, 0 without
example.setValue(1) // Sets initial value to 1
example.power(example, 1000) // Computes example^1000
struct BigInt {
static const int MAX_DIGITS = 20087;
int digits[MAX_DIGITS + 10], length;
bool isNegative;
BigInt() { reset(); }
void reset() {
memset(digits, 0, sizeof(digits));
length = 1;
isNegative = false;
}
void read() {
char input[MAX_DIGITS + 10];
scanf("%s", input);
length = strlen(input);
if (input[0] == '-') {
isNegative = true;
for (int i = 1; i < length; ++i)
digits[i] = input[length - i] - '0';
length--;
} else {
for (int i = 1; i <= length; ++i)
digits[i] = input[length - i] - '0';
}
}
void write(bool newline) {
if (isNegative) putchar('-');
for (int i = length; i >= 1; --i)
putchar(digits[i] + '0');
if (newline) puts("");
}
template <typename T> void setValue(T x) {
reset();
while (x != 0) {
digits[length++] = x % 10;
x /= 10;
}
if (length != 1) length--;
}
template <typename T> static BigInt convertToBigInt(T x) {
BigInt result;
if (x < 0) {
x = abs(x);
result.isNegative = true;
}
while (x != 0) {
result.digits[result.length++] = x % 10;
x /= 10;
}
if (result.length != 1) result.length--;
return result;
}
bool operator < (const BigInt &other) const {
if (length != other.length) return length < other.length;
for (int i = length; i >= 1; --i)
if (digits[i] != other.digits[i]) return digits[i] < other.digits[i];
return false;
}
bool operator > (const BigInt &other) const { return other < *this; }
bool operator <= (const BigInt &other) const { return !(other < *this); }
bool operator != (const BigInt &other) const { return other < *this || *this < other; }
bool operator == (const BigInt &other) const { return !(other < *this || *this < other); }
BigInt operator + (const BigInt &B) const {
if (B.isNegative && isNegative) {
BigInt temp1 = *this, temp2 = B;
temp1.isNegative = false; temp2.isNegative = false;
BigInt sum = temp1 + temp2;
sum.isNegative = true;
return sum;
}
if (B.isNegative) {
BigInt temp = B;
temp.isNegative = false;
BigInt sum = *this - temp;
return sum;
}
if (isNegative) {
BigInt temp = *this;
temp.isNegative = false;
BigInt sum = B - temp;
return sum;
}
BigInt sum;
sum.length = max(length, B.length);
for (int i = 1; i <= sum.length; ++i) {
sum.digits[i] += digits[i] + B.digits[i];
if (sum.digits[i] >= 10) {
sum.digits[i] -= 10;
sum.digits[i + 1]++;
}
}
while (sum.digits[sum.length + 1]) sum.length++;
return sum;
}
BigInt operator - (const BigInt &B) const {
if (B.isNegative && isNegative) {
BigInt temp = B;
temp.isNegative = false;
BigInt diff = *this + temp;
return diff;
}
if (B.isNegative) {
BigInt temp = B;
temp.isNegative = false;
BigInt diff = *this + temp;
return diff;
}
if (isNegative) {
BigInt temp1 = *this, temp2 = B;
temp1.isNegative = false; temp2.isNegative = false;
BigInt diff = temp1 + temp2;
diff.isNegative = true;
return diff;
}
if (*this < B) {
putchar('-');
BigInt diff = B - *this;
return diff;
}
BigInt diff;
diff.length = max(length, B.length);
for (int i = 1; i <= diff.length; ++i) {
diff.digits[i] += digits[i] - B.digits[i];
if (diff.digits[i] < 0) {
diff.digits[i] += 10;
diff.digits[i + 1]--;
}
}
while (!diff.digits[diff.length] && diff.length > 1) diff.length--;
return diff;
}
BigInt operator * (const BigInt &B) const {
BigInt product;
if ((B.isNegative xor isNegative)) product.isNegative = true;
if ((B.length == 1 && B.digits[1] == 0) || (length == 1 && digits[1] == 0)) return product;
product.length = B.length + length - 1;
for (int i = 1; i <= length; ++i)
for (int j = 1; j <= B.length; ++j) {
product.digits[i + j - 1] += digits[i] * B.digits[j];
product.digits[i + j] += product.digits[i + j - 1] / 10;
product.digits[i + j - 1] %= 10;
}
while (product.digits[product.length + 1]) product.length++;
return product;
}
BigInt operator / (const BigInt &B) const {
BigInt quotient;
if ((B.isNegative xor isNegative)) quotient.isNegative = true;
if ((B.length == 1 && B.digits[1] == 0) || (length == 1 && digits[1] == 0)) return quotient;
BigInt remainder, temp;
quotient.length = 0;
for (int i = length; i >= 1; --i) {
temp.setValue(10);
remainder = remainder * temp;
temp.setValue(digits[i]);
remainder = remainder + temp;
int digit = -1;
for (int j = 1; j <= 10; ++j) {
temp.setValue(j);
if (temp * B > remainder) {
digit = j - 1;
break;
}
}
quotient.digits[++quotient.length] = digit;
temp.setValue(digit);
remainder = remainder - temp * B;
}
for (int i = 1; i <= length / 2; ++i) swap(quotient.digits[i], quotient.digits[length - i + 1]);
while (!quotient.digits[quotient.length] && quotient.length > 1) quotient.length--;
return quotient;
}
BigInt operator % (const BigInt &B) const {
BigInt remainder;
BigInt quotient = *this / B;
remainder = *this - quotient * B;
return remainder;
}
static BigInt power(const BigInt &base, int exponent) {
if (exponent == 1) return base;
BigInt half = power(base, exponent / 2);
if (exponent & 1) return half * half * base;
else return half * half;
}
void operator = (const BigInt &other) {
for (int i = 1; i <= other.length; ++i)
digits[i] = other.digits[i];
length = other.length;
isNegative = other.isNegative;
}
};
