# class assignment, help!

• 10-04-2007
TriKri
class assignment, help!
Hi! I am constructing a bigint class which contains a vector with all the digits in it. Now I want some operations for the class. if a, b and c is of this class, I want to be able to write a = b + c without having to copy the result of the + operation, the sum, into a. If a, b and c would have been ordinary ints, would the result of the operation have been calculated first and then copied into a or would it be written directly to a? I suppose it's not possible to changes the adress of a to match the adress of the result, since a has a probably has a constant adress, but can you change everything in a (exluding the actual vector data, the digits, which really not is a part of the object) so that the vector's internal pointer points to the adress as the + results vector's pointer? What is the best way to solve this? What is possible?

I would like the = operator to work quickly and hence not copying everything (including the digits) straight of.

I would also like it if there where some operation or function which did copy another bigint so that everything (including the digits) where duplicated, for example if I write a = b, then b should be duplicated into a, else, if there isn't any way to separate duplicating = from assigning = then a function duplicate or something could be created so you can write a.setto(b) or b.duplicate(a) or similar.

Every suggestion is welcome, I supose this could be solved i a thousand ways, but I have no clue how to fix this. If it seems like there's no good solution then I'm probably gonna have to work with pointers to bigints instead of bigints directly, it will probably not slow it down very much but it's lengthy.

Thanks.
• 10-04-2007
MacGyver
What's there to fix? The solution is practically given to you. Work it out so that you can see how everything will generally work before you start, and then go. When you get stuck, then let us know. ;)

Edit: Hint: You should be writing your own operator+, but I'm sure you know that. You have to do the addition somewhere, and that's where you do it.
• 10-04-2007
matsp
Quote:

Originally Posted by TriKri
Hi! I am constructing a bigint class which contains a vector with all the digits in it. Now I want some operations for the class. if a, b and c is of this class, I want to be able to write a = b + c without having to copy the result of the + operation, the sum, into a. If a, b and c would have been ordinary ints, would the result of the operation have been calculated first and then copied into a or would it be written directly to a?

This would, first of all, be dependant on the level you look at it from. At an assembler level, it would depend on the processor architecture, e.g. the commonly used x86 processor would do something like:
Code:

mov eax, dword b
mov dword a, eax

whilst a 29K processor would do:
Code:

Note that since the 29k processor has MANY registers, it can hold lots of data in registers, so there are less need to load or store the data to/from memory.

However, in some respect, the calculation always involves making a copy of the data.
Quote:

I suppose it's not possible to changes the adress of a to match the adress of the result, since a has a probably has a constant adress, but can you change everything in a (exluding the actual vector data, the digits, which really not is a part of the object) so that the vector's internal pointer points to the adress as the + results vector's pointer? What is the best way to solve this? What is possible?

I would like the = operator to work quickly and hence not copying everything (including the digits) straight of.

I would also like it if there where some operation or function which did copy another bigint so that everything (including the digits) where duplicated, for example if I write a = b, then b should be duplicated into a, else, if there isn't any way to separate duplicating = from assigning = then a function duplicate or something could be created so you can write a.setto(b) or b.duplicate(a) or similar.

Every suggestion is welcome, I supose this could be solved i a thousand ways, but I have no clue how to fix this. If it seems like there's no good solution then I'm probably gonna have to work with pointers to bigints instead of bigints directly, it will probably not slow it down very much but it's lengthy.

Thanks.
I don't think it's possible to do what you want to do - but let others comment before that's your final conclusion.

I believe, you always, need a temporary object if you add two numbers together...

--
Mats
• 10-05-2007
TriKri
What I would like to do is that I would like to be able to write following line:

a = (b + c) * (d + e);

And the line should be interpretted as follows:
1. First b + c is calculated and the new bignum (the sum) with digits is stored temporarily somewhere. The same with d + e.
2. Now the product of the sums is calculated and I would love it if it was stored directly into a, but I supose that's impossible. When the product is calculated, both sums which where only temporary is removed and the memory places they refered to for holding the digits are freed.
3. Now the variable a is syncroniced with the product so that it has the same info about length of the number and where the digits are stored in the memory, etc. Now the product can be removed as well, but the memory which holds the digits for the product (and a) can't be freed, since a is now refering to it as well.

So in order to prevent memory leeks, the temporary bigints which is not assigned to any variable has to be destroyed directly after they have been used so that we don't loose conection with them, and the memory which holds the digits has to be freed. On the other hand, if the bigint is assigned to another variable, we have to destroy the temporary variable, but not free the memory it refers to since it's now refered to by another bigint. Hm, thats tricky.

Someone has any idea of how this can be simplest implemented?
• 10-05-2007
anon
You might be able to do it with some sort of reference counting.

a = b + c;

1) in operator+ a temporary object is declared which allocates a buffer, one object referencing it.
2) do the arithmetic
3) in operator= pointer to buffer is passed to a, two objects referencing it.
4) temporary goes out of scope. Since more than one object is referencing the array, it will not delete it in its destructor.

May-be wrap the array in a reference-counted smart pointer.

Edit:
No, that wouldn't work.
Code:

a = b; //a and b referencing same buffer
b = c + d; //oops

You'll also need copy on write or something.

How big numbers are we talking about?

There is always the possibility of void add(BigInt& result, const BigInt& left, const BigInt& right)...
• 10-05-2007
TriKri
Well, arbitrary big numbers. Hehe ^^ That is, no limitation in the number of digits more than the size of the variable in the vector storing the number of elements.

Maybe your idea with a reference counter isn't that bad, then I need to have two types, one which refers to the the place in the memory where the number is, and the other type, the "number", holds all the digits and count the references to it. When references goes down to 0 it's destroyed. Assigning operator = should check whether the left operand has a reference or not, if that's the case then it should be derefered.

Alternatively, the bigint could have a flag which told if it is a temporary number or not; arithmetic operators +, *, etc. should destroy the number and free the digits if it is temporary, else the number and the digits should be left untouched. Assigning operator = should copy the pointer to the digits to the new number and destroy the old if the old is temporary, else it should copy the digits to a new place in memory and refere to it, and the other number should be left untouched.

Hm, looks like I have made progress with this problem; both methods have advantages and dissadvantages, the first method is more lengthy but on the other hand a long sequence of digits doesn't have to be copied but can be refered to multiple times. Since I want everything to run in least amortized time, I'll probably use the first method since it supports faster (constant time) assigning between numbers.

Thanks for the tip! It was a helpful post.
• 10-06-2007
matsp
Remember: Premature optimization is often a cause for bugs (paraphrazing the original phrase).

If you START by doing the math using the most basic method that is reasonably, then look at what you are spendig time on (e.g. is copying the temporary result a big part of your whole time?), and "fix" the places where you find you spend time. It's no point spending several days of a montsh project to optimize something that isn't important in the big picture. If it's real trivial to make it quick, sure, do that. But if it's not, then ignore it.

If you return a copy of your sum, then that's going to work "automatically" using your normal copy constructor or copy-assignment method. The compiler will optimize some of it away.

--
Mats
• 10-06-2007
anon
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&#37; 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. :)