My program runs on all numbers, but not when calculating BigInt MAX(INT_MAX). When I try to run this, it gives me a segmentation fault. Here is the BigInt class:
#include <iostream>
#include <limits.h>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class BigInt
{
private:
vector<char> v;
public:
BigInt()
{
v.push_back('0');
}
BigInt(int num)
{
while (num != 0)
{
v.push_back(num % 10);
num /= 10;
}
}
BigInt(string str) //3
{
for (int i = str.length() - 1; i >= 0; i--)
v.push_back(str[i] - '0');
}
BigInt operator+(BigInt b)
{
BigInt result;
int carry = 0;
for (int i = 0; i < max(v.size(), b.v.size()); i++)
{
int sum = carry;
if (i < v.size())
sum += v[i];
if (i < b.v.size())
sum += b.v[i];
result.v.push_back(sum % 10);
carry = sum / 10;
}
if (carry != 0)
result.v.push_back(carry);
return result;
}
BigInt operator++( )
{
*this = *this + BigInt(1);
return *this;
}
BigInt operator++(int)
{
BigInt temp = *this;
*this = *this + BigInt(1);
return temp;
}
BigInt operator*(BigInt b)
{
BigInt result;
result.v.resize(v.size() + b.v.size());
for (int i = 0; i < v.size(); i++)
for (int j = 0; j < b.v.size(); j++)
result.v[i + j] += v[i] * b.v[j];
for (int i = 0; i < result.v.size() - 1; i++)
{
result.v[i + 1] += result.v[i] / 10;
result.v[i] %= 10;
}
while (result.v.back() == 0 && result.v.size() > 1)
result.v.pop_back();
return result;
}
BigInt operator+=(BigInt b)
{
*this = *this + b;
return *this;
}
BigInt half()
{
BigInt result;
int remainder = 0;
for (int i = v.size() - 1; i >= 0; i--)
{
int current = remainder * 10 + v[i];
int digit = current / 2;
if (digit != 0 || !result.v.empty())
result.v.push_back(digit);
remainder = current % 2;
}
if (result.v.empty())
result.v.push_back(0);
return result;
}
bool isOdd()
{
return v[0] % 2 == 1;
}
bool isEven()
{
return !isOdd();
}
bool operator==(BigInt b)
{
if (v.size() != b.v.size())
return false;
for (int i = 0; i < v.size(); i++)
if (v[i] != b.v[i])
return false;
return true;
}
bool operator<(BigInt b)
{
if (v.size() != b.v.size())
return v.size() < b.v.size();
for (int i = v.size() - 1; i >= 0; i--)
if (v[i] != b.v[i])
return v[i] < b.v[i];
return false;
}
friend ostream& operator<<(ostream& os, const BigInt& b){
if (b.v.size() < 9)
{
for (auto it = b.v.rbegin(); it != b.v.rend(); ++it)
{
os << static_cast<int>(*it);
}
}
else
{
os << static_cast<int>(b.v.back()) << ".";
for (size_t i = 1; i <= 7; ++i)
{
os << static_cast<int>(b.v[b.v.size() - i - 1]);
}
os << "e" << b.v.size() - 1;
}
return os;
}
};
and here is the driver code:
struct ThreeNp1
{
BigInt start;
BigInt steps;
BigInt max;
BigInt odd;
BigInt even;
};
void print(ThreeNp1 temp)
{
cout << "start:" << temp.start << endl;
cout << "steps:" << temp.steps << endl;
cout << "max:" << temp.max << endl;
cout << "odds:" << temp.odd << endl;
cout << "evens:" << temp.even << endl;
}
void findThreeNp1(BigInt n, ThreeNp1 &Np1, bool printSteps = false)
{
if (printSteps)
{
cout << "->" << '(' << n << ')';
}
if (Np1.max < n)
Np1.max = n;
if (n == BigInt(1))
{
return;
}
else if (n.isEven())
{
Np1.even++;
Np1.steps++;
findThreeNp1(n.half(), Np1, printSteps);
}
else if (n.isOdd())
{
Np1.odd++;
Np1.steps++;
BigInt tempN(n);
findThreeNp1(tempN * BigInt(3) + BigInt(1), Np1, printSteps);
}
else
{
cout << "How the hell did I get here?\n";
return;
}
}
int main()
{
BigInt MAX(INT_MAX);
cout << "The largest integer is " << MAX << endl;
cout << "Twice the largest integer is " << MAX + MAX << endl;
BigInt start(INT_MAX);
bool printSteps = false;
ThreeNp1 N = {start, 0, 0, 0, 0};
findThreeNp1(start, N, printSteps);
cout << endl;
print(N);
return 0;
}
I have rewritten this code so many times, I've checked for errors in my logic. I've tried everything I can think of. If anyone sees anything wrong or I could improve to get this thing running, please let me know.
