Well, you probably shouldn't be rolling your own BigInt class if it wasn't for exercise, because good and well-tested big number classes are already available.
If it is for exercise, you probably should first see if you are able to implement it all.
But then, it is not unreasonable to want this class to be as fast as possible (because it is a utility and you won't know where and how it would be used).
I'm not entirely sure that the optimization you described is the best optimization you can do for your class. Most optimizations that would make any noticeable difference are algorithmic optimizations.
Nevertheless, below is my attempt (out of curiosity) to implement what you are describing. I'm not 100% sure that it works the way I hope and I haven't tested it very thoroughly but at least it seems to be giving expected output. (To test if it actually works the way I hope, I guess I should have compared with a simpler implementation and counted how many times the internal representation gets copied in either case. Moreover, it may not be an optimization at all because everything has some small additional overhead that may null out the potential gains of avoiding a few copies.)
Code:
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
template <typename T>
class RefPointer
{
public:
RefPointer(T* p): ptr(p), counter(new int(1)) {}
RefPointer(const RefPointer& rp): ptr(rp.ptr), counter(rp.counter) {++*counter; }
~RefPointer()
{
if (--*counter == 0) {
delete counter;
delete ptr;
}
}
const RefPointer& operator= (const RefPointer& rp)
{
if (this != &rp) {
RefPointer temp(rp);
swap(*this, temp);
}
return *this;
}
T& operator* () {return *ptr; }
const T& operator* () const { return *ptr; }
T* operator-> () {return ptr; }
const T* operator-> () const {return ptr; }
template <typename N>
friend void swap(RefPointer<N>& left, RefPointer<N>& right);
bool has_other_reference() const
{
return *counter > 1;
}
private:
T* ptr;
int* counter;
};
class BigUnsigned
{
public:
BigUnsigned(const std::string& num = std::string("0")):
buffer(new std::string(num))
{
//keep the representation reversed to make addition easier
std::reverse(buffer->begin(), buffer->end());
}
const BigUnsigned& operator += (const BigUnsigned& right);
friend
std::ostream& operator<< (std::ostream& os, const BigUnsigned& us)
{
//reverse output
std::copy(us.buffer->rbegin(), us.buffer->rend(), std::ostream_iterator<char>(os, ""));
return os;
}
private:
RefPointer<std::string> buffer;
};
BigUnsigned operator+ (const BigUnsigned& left, const BigUnsigned& right);
int main(int argc, char* argv[])
{
if (argc < 4) {
std::cout << "Call with three numbers\n";
return 0;
}
BigUnsigned a(argv[1]), b(argv[2]), c(argv[3]);
std::cout << "a = " << a << '\n'
<< "b = " << b << '\n'
<< "c = " << c << '\n';
std::cout << "\nb = a + c\n";
b = a + c;
std::cout << "a = " << a << '\n'
<< "b = " << b << '\n'
<< "c = " << c << '\n';
std::cout << "\na = a + b + c\n";
a = a + b + c;
std::cout << "a = " << a << '\n'
<< "b = " << b << '\n'
<< "c = " << c << '\n';
}
BigUnsigned operator+ (const BigUnsigned& left, const BigUnsigned& right)
{
BigUnsigned temp(left);
return temp += right;
}
const BigUnsigned& BigUnsigned::operator += (const BigUnsigned& right)
{
//if buffer referenced elsewhere, create new buffer and detach
//(hopefully swap(RefPointer&, RefPointer&) achieves this
if (buffer.has_other_reference()) {
RefPointer<std::string> temp(new std::string(*buffer));
swap(buffer, temp);
}
//make sure *this* is as large as right
if (buffer->size() < right.buffer->size()) {
buffer->resize(right.buffer->size(), '0');
}
char carry_over = 0;
for (std::size_t i = 0; i < right.buffer->size(); ++i) {
char sum = (*buffer)[i] + (*right.buffer)[i] + carry_over - '0';
if (sum <= '9') {
carry_over = 0;
}
else {
sum -= 10;
carry_over = 1;
}
(*buffer)[i] = sum;
}
for (std::size_t i = right.buffer->size(); carry_over && i < buffer->size(); ++i) {
char sum = (*buffer)[i] + carry_over;
if (sum <= '9') {
carry_over = 0;
}
else
{
sum -= 10;
}
(*buffer)[i] = sum;
}
if (carry_over) {
*buffer += '1';
}
return *this;
}
template <typename T>
void swap(RefPointer<T>& left, RefPointer<T>& right)
{
T* ptr = left.ptr;
left.ptr = right.ptr;
right.ptr = ptr;
int* counter = left.counter;
left.counter = right.counter;
right.counter = counter;
}
Here I'm expecting the destructor, copy constructor and assignment operator of BigUnsigned to do the right thing as the destructor, copy constructor and assignment operator of RefPointer (reference counting pointer) should work correctly.
Any BigUnsigned method that is going to modify the buffer (here operator +=) first needs to check if it's shared with other BigUnsigned's and if so, allocate new buffer and detach the old one.
-----
I believe, however, that a much more significant optimization would be changing the way how the big number is represented internally. I'm not sure if you are thinking about something similar, but you mention storing digits, so I assume you have a similar idea.
The problem with the internal representation of BigUnsigned is that it is wasting a lot of memory: it is only using values ['0'--'9'] of all the 256 different values a char can hold.
Therefore
- 96% of the memory is not used;
- the internal buffer is much larger than it needs to be - copying would be smaller problem if the representation was more memory-efficient;
- the calculations involve more numerous and more complicated operations than a binary representation would need (probably).
On the other hand, representing BigUnsigned and doing maths in binary (and converting to decimal string for output) might be quite hard for mathematically less-talented (like me) because most people are used to calculating in base 10.
---
Be warned that I'm no expert, so most of what I said might be non-sense. 
Originally Posted by TriKri
