|
|
#include <iostream>
|
|
|
#include <iomanip>
|
|
|
#include <cstring>
|
|
|
#include "number.h"
|
|
|
|
|
|
Number::Number(int a)
|
|
|
{
|
|
|
#ifdef _DEBUG_CONSTRUCTOR
|
|
|
std::cout << "(Number constructor " << a << " -> ";
|
|
|
#endif
|
|
|
// Находим размер необходимой памяти под это число
|
|
|
int temp = a;
|
|
|
capacity = 0;
|
|
|
while (temp != 0) {
|
|
|
temp /= base;
|
|
|
capacity += 1;
|
|
|
}
|
|
|
|
|
|
// Отдельно обрабатываем случай, когда число равно 0
|
|
|
if (capacity == 0)
|
|
|
capacity = 1;
|
|
|
|
|
|
// Выделяем память и записывем число a в массив data
|
|
|
// Например, число 12345678 представится в виде массива [78, 56, 34, 12]
|
|
|
|
|
|
data = new char[capacity];
|
|
|
|
|
|
for (int i = 0; i < capacity; ++i) {
|
|
|
data[i] = a % base;
|
|
|
a /= base;
|
|
|
}
|
|
|
|
|
|
// В данном случае размер будет равен вместимости
|
|
|
size = capacity;
|
|
|
#ifdef _DEBUG_CONSTRUCTOR
|
|
|
std::cout << *this << ")" << std::endl;
|
|
|
#endif
|
|
|
}
|
|
|
|
|
|
// Конструктор по умолчанию
|
|
|
Number::Number():Number(0){}
|
|
|
|
|
|
// Конструктор копирования
|
|
|
Number::Number(const Number & n)
|
|
|
{
|
|
|
size = n.size;
|
|
|
capacity = n.capacity;
|
|
|
data = new char[capacity];
|
|
|
for (int i = 0; i < size; i++) {
|
|
|
data[i] = n.data[i];
|
|
|
}
|
|
|
}
|
|
|
|
|
|
Number::Number(const char *str)
|
|
|
{
|
|
|
int len = std::strlen(str);
|
|
|
size = (len + len % 2) / 2;
|
|
|
capacity = size;
|
|
|
data = new char[capacity];
|
|
|
char buf[2];
|
|
|
for (int i = 0; i < size; i++) {
|
|
|
buf[1] = str[len - 2 * i - 1];
|
|
|
if (len - 2 * i - 1 > 0) {
|
|
|
buf[0] = str[len - 2 * i - 2];
|
|
|
} else {
|
|
|
buf[0] = '0';
|
|
|
}
|
|
|
data[i] = std::stoi(buf);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
Number::~Number()
|
|
|
{
|
|
|
delete[]data;
|
|
|
}
|
|
|
|
|
|
Number & Number::operator=(const Number & right)
|
|
|
{
|
|
|
capacity = right.capacity;
|
|
|
size = right.size;
|
|
|
data = new char[capacity];
|
|
|
for (int i = 0; i < size; i++) {
|
|
|
data[i] = right.data[i];
|
|
|
}
|
|
|
return *this;
|
|
|
}
|
|
|
|
|
|
Number Number::operator+(Number a)
|
|
|
{
|
|
|
#ifdef _DEBUG_ADD
|
|
|
std::cout << "arg1=" << a << "capacity=" << a.
|
|
|
capacity << ",size=" << a.size << std::endl;
|
|
|
std::cout << "arg2=" << *this << "capacity=" << this->
|
|
|
capacity << ",size=" << this->size << std::endl;
|
|
|
|
|
|
#endif
|
|
|
Number result;
|
|
|
Number temp;
|
|
|
int i;
|
|
|
int carry = 0;
|
|
|
if (size < a.size) {
|
|
|
temp = *this;
|
|
|
*this = a;
|
|
|
a = temp;
|
|
|
}
|
|
|
result.capacity = size + 1;
|
|
|
//result.data = new char[capacity];
|
|
|
result.data = (char *) calloc(result.capacity, sizeof(char));
|
|
|
for (i = 0; i < a.size; ++i) {
|
|
|
result.data[i] = (data[i] + a.data[i] + carry) % base;
|
|
|
carry = (data[i] + a.data[i] + carry) / base;
|
|
|
}
|
|
|
for (; i < size; ++i) {
|
|
|
result.data[i] = (data[i] + carry) % base;
|
|
|
carry = (data[i] + carry) / base;
|
|
|
}
|
|
|
if (carry) {
|
|
|
#ifdef _DEBUG_ADD
|
|
|
std::cout << "applied carry" << std::endl;
|
|
|
#endif
|
|
|
result.data[i] = carry;
|
|
|
result.size = size + 1;
|
|
|
} else {
|
|
|
result.size = size;
|
|
|
}
|
|
|
#ifdef _DEBUG_ADD
|
|
|
std::cout << result << " capacity=" << result.
|
|
|
capacity << ",size=" << result.size << std::endl;
|
|
|
#endif
|
|
|
return result;
|
|
|
}
|
|
|
|
|
|
void Number::operator+=(const Number & a)
|
|
|
{
|
|
|
*this = *this + a;
|
|
|
}
|
|
|
|
|
|
bool Number::isEven() const
|
|
|
{
|
|
|
if (data[0] % 2) {
|
|
|
return false;
|
|
|
}
|
|
|
return true;
|
|
|
}
|
|
|
|
|
|
Number Number::operator*(const Number & right) const
|
|
|
{
|
|
|
#ifdef _DEBUG_MUL
|
|
|
std::
|
|
|
cout << "arg1=" << *this << "(capacity=" << capacity << ",size=" <<
|
|
|
size << ")" << " " << "arg2=" << right << "(capacity=" << right.
|
|
|
capacity << ",size=" << right.size << ")" << std::endl;
|
|
|
#endif
|
|
|
if (*this == Number("0") || right == Number("0"))
|
|
|
return Number("0");
|
|
|
int i, j;
|
|
|
int temp;
|
|
|
Number result;
|
|
|
|
|
|
result.capacity = capacity + right.capacity;
|
|
|
int *carry = (int *) std::calloc(result.capacity, sizeof(int));
|
|
|
|
|
|
result.data = (char *) calloc(result.capacity, sizeof(char));
|
|
|
#ifdef _DEBUG_MUL
|
|
|
std::cout << "carry:[" << carry[0];
|
|
|
for (int k = 1; k < result.capacity; ++k) {
|
|
|
std::cout << "," << carry[k];
|
|
|
}
|
|
|
std::cout << "]" << std::endl;
|
|
|
#endif
|
|
|
for (i = 0; i < size; ++i) {
|
|
|
for (j = 0; j < right.size; ++j) {
|
|
|
#ifdef _DEBUG_MUL
|
|
|
std::cout << i + j << ":" << static_cast <
|
|
|
int >(result.data[i + j]) << " + " << static_cast <
|
|
|
int >(data[i]) << " * " << static_cast <
|
|
|
int >(right.data[j]) << " + " << carry[i + j] << std::endl;
|
|
|
#endif
|
|
|
temp =
|
|
|
(result.data[i + j] + data[i] * right.data[j] +
|
|
|
carry[i + j]);
|
|
|
result.data[i + j] = temp % base;
|
|
|
carry[i + j + 1] += temp / base;
|
|
|
carry[i + j] = 0;
|
|
|
|
|
|
}
|
|
|
}
|
|
|
#ifdef _DEBUG_MUL
|
|
|
std::cout << "result before applying carry:" << result << std::endl;
|
|
|
std::cout << "carry:[" << carry[0];
|
|
|
for (int k = 1; k < result.capacity; ++k) {
|
|
|
std::cout << "," << carry[k];
|
|
|
}
|
|
|
std::cout << "]" << std::endl;
|
|
|
#endif
|
|
|
if (carry[i + j - 1]) {
|
|
|
result.data[i + j - 1] = carry[i + j - 1];
|
|
|
result.size = i + j;
|
|
|
} else {
|
|
|
result.size = i + j - 1;
|
|
|
}
|
|
|
|
|
|
#ifdef _DEBUG_MUL
|
|
|
std::cout << "before correcting capacity, result=" << result << std::
|
|
|
endl;
|
|
|
#endif
|
|
|
// correcting capacity
|
|
|
/*char* temp_data = (char *)calloc(result.size, sizeof(char));
|
|
|
for (i = 0; i < result.size; ++i) {
|
|
|
temp_data[i] = result.data[i];
|
|
|
}
|
|
|
|
|
|
free(result.data);
|
|
|
result.capacity = result.size;
|
|
|
result.data = (char*)calloc(result.size,sizeof(char));
|
|
|
for (i = 0; i < result.size; ++i) {
|
|
|
result.data[i] = temp_data[i];
|
|
|
}
|
|
|
|
|
|
free(temp_data); */
|
|
|
free(carry);
|
|
|
#ifdef _DEBUG_MUL
|
|
|
std::cout << "return value=" << result << "(capacity=" << result.
|
|
|
capacity << ",size=" << result.
|
|
|
size << ")" << std::endl << "======" << std::endl;
|
|
|
#endif
|
|
|
return result;
|
|
|
}
|
|
|
|
|
|
void Number::operator*=(const Number & a)
|
|
|
{
|
|
|
*this = *this * a;
|
|
|
}
|
|
|
|
|
|
bool Number::operator==(const Number & a) const
|
|
|
{
|
|
|
if (size != a.size) {
|
|
|
return false;
|
|
|
}
|
|
|
for (int i = 0; i < size; ++i) {
|
|
|
if (data[i] != a.data[i]) {
|
|
|
return false;
|
|
|
}
|
|
|
}
|
|
|
return true;
|
|
|
}
|
|
|
|
|
|
bool Number::operator!=(const Number & a) const
|
|
|
{
|
|
|
return not(*this == a);
|
|
|
}
|
|
|
|
|
|
bool Number::operator>(const Number & a) const
|
|
|
{
|
|
|
#ifdef _DEBUG_COMP
|
|
|
std::
|
|
|
cout << "comp " << *this << "(size=" << size << ") and " << a <<
|
|
|
"(size=" << a.size << ")" << std::endl;
|
|
|
#endif
|
|
|
if (size > a.size) {
|
|
|
#ifdef _DEBUG_COMP
|
|
|
std::cout << "size > a.size => true" << std::endl;
|
|
|
#endif
|
|
|
return true;
|
|
|
}
|
|
|
if (size < a.size) {
|
|
|
#ifdef _DEBUG_COMP
|
|
|
std::cout << "size < a.size => false" << std::endl;
|
|
|
#endif
|
|
|
return false;
|
|
|
}
|
|
|
for (int i = size - 1; i >= 0; --i) {
|
|
|
if (data[i] > a.data[i]) {
|
|
|
return true;
|
|
|
#ifdef _DEBUG_COMP
|
|
|
std::cout << static_cast <
|
|
|
int >(data[i]) << ">" << static_cast <
|
|
|
int >(a.data[i]) << std::endl;
|
|
|
#endif
|
|
|
}
|
|
|
if (data[i] < a.data[i]) {
|
|
|
#ifdef _DEBUG_COMP
|
|
|
std::cout << static_cast <
|
|
|
int >(data[i]) << "<" << static_cast <
|
|
|
int >(a.data[i]) << std::endl;
|
|
|
#endif
|
|
|
return false;
|
|
|
}
|
|
|
|
|
|
}
|
|
|
#ifdef _DEBUG_COMP
|
|
|
std::cout << "using final false" << std::endl;
|
|
|
#endif
|
|
|
return false;
|
|
|
}
|
|
|
|
|
|
bool Number::operator<(const Number & a) const
|
|
|
{
|
|
|
return not(*this > a) and(*this != a);
|
|
|
}
|
|
|
|
|
|
void Number::div2()
|
|
|
{
|
|
|
#ifdef _DEBUG_DIV2
|
|
|
std::cout << "n = " << *this << std::endl;
|
|
|
#endif
|
|
|
int carry = 0;
|
|
|
int temp;
|
|
|
for (int i = size - 1; i >= 0; --i) {
|
|
|
temp = data[i] + carry * base;
|
|
|
data[i] = temp / 2;
|
|
|
carry = temp % 2;
|
|
|
}
|
|
|
if (data[size - 1] == 0) {
|
|
|
--size;
|
|
|
}
|
|
|
#ifdef _DEBUG_DIV2
|
|
|
std::cout << "unstripped result " << *this << std::endl;
|
|
|
#endif
|
|
|
}
|
|
|
|
|
|
|
|
|
std::ostream & operator<<(std::ostream & stream, const Number & right)
|
|
|
{
|
|
|
#ifdef _DEBUG_COUT
|
|
|
stream << "[";
|
|
|
for (std::size_t i = 0; i < right.size; ++i) {
|
|
|
stream << static_cast <
|
|
|
int >(right.data[right.size - 2 - i]) << ",";
|
|
|
}
|
|
|
stream << "]";
|
|
|
#else
|
|
|
// Печатаем самый большой разряд
|
|
|
stream << (int) right.data[right.size - 1];
|
|
|
|
|
|
// Печатаем остальные разряды с заполнением нулями до 2-х цифр
|
|
|
// setfill и setw это то же самое, что и в языке C спецификатор %02d
|
|
|
for (std::size_t i = 0; i < right.size - 1; ++i)
|
|
|
stream << std::setfill('0') << std::setw(2) << (int) right.
|
|
|
data[right.size - 2 - i];
|
|
|
#endif
|
|
|
return stream;
|
|
|
}
|