Exercise - LebInt

Joe

I am going to be away for 4 days, so I thought I would leave you with a third exercise. I'll check out the answers on Monday.

So here goes:

As you know, int has serious limitations when working with very large numbers. Depending on your CPU, your OS and your compiler, it usually goes up to:

2^32-1 = 4294967295 (It can vary)

These issues appeared to us when trying to retrieve the 100th element of the Fibonacci sequence. We want to create a data structure capable of handling bigger numbers. And we'll be using C++.

Note that C++ already has a class called BigInt that does the job really well. If you ever work on a side project, this is the one you should be using.

LebInt

- Constructing a number from a string.
- Overloading + - * / % ^ ++ --
- Overloading <<
- Adding math functions like || (abs)
- < > <= >= == !=

Bonus: Use this type to determine exactly the 1000th number of Fibonacci Sequence. If needed you can use arithma's C++ code to test it.

Final recommendations:
- Try, as much as possible, to deliver compilable code. That means showing your includes, namespaces, macros, main functions, ... People should be able to copy/paste your code to try it on their machines.

- Mention the compiler you're using. Try to mention the version if possible.

- This exercise require more lines of code than the others. Try to comment as much as possible, and use clear variable names.

Have fun :)

xterm

That is a beautiful exercise.

arithma

This is the signature of the methods I'll be initially working on:

struct BigInt{
	BigInt & operator +=(BigInt const & other);
	BigInt & operator -=(BigInt const & other);
	BigInt & operator++();
	BigInt & operator--();
	BigInt & operator++(int);
	BigInt & operator--(int);
	BigInt & operator *=(BigInt const & other);
	BigInt & operator /=(BigInt const & other);
	bool operator %=(BigInt const & other);

	bool operator <(BigInt const & other);
	bool operator >(BigInt const & other);
	bool operator !=(BigInt const & other);
	bool operator ==(BigInt const & other);
	bool operator >=(BigInt const & other);
	bool operator <=(BigInt const & other);
};

arithma

Anyone working this exercise? It's turning out to be an interesting one. Will share some results soon.

Padre

i already done smth like that for a PIC on assembly, not as elaborate tho. (+ , - , * and / for 6 bytes) dont think i'll work on it.

arithma

test.cpp

#include "BigInt.h"
#include <iostream>
using namespace std;

typedef unsigned int uint;
BigInt fib(uint i){
	BigInt a(0);
	BigInt b(1);
	for(uint j = 1; j < i; j++){
		BigInt temp(a);
		a = b;
		b += temp;
	}

	return b;
}

void main(){
	vector<uint> v;
	v.push_back(0x0);
	v.push_back(0xf);

	BigInt s(v);
	s /= 100;
	BigInt f = fib(1000);
	vector<uint> digits;
	while(BigInt(0) < f){
		BigInt d(f);
		digits.push_back(d %= 10);
		f /= 10;
	}

	for(uint i = digits.size(); i > 0; i--)
		cout << digits[i-1];
	cout << endl;
}

BigInt.h

#include <vector>

struct BigInt{
	typedef unsigned int uint;
	static uint const UINT_BITS = sizeof(uint) * CHAR_BIT;
	static uint const HALF_LO = UINT_MAX >> (UINT_BITS/2);
	static uint const HALF_HI = UINT_MAX << (UINT_BITS/2);
	BigInt ();
	BigInt (uint);
	BigInt (std::vector<uint>);
	operator uint() const;

	BigInt & operator +=(BigInt const & other);
	BigInt & operator -=(BigInt const & other);
	BigInt & operator ++();
	BigInt & operator --();
	BigInt & operator ++(int);
	BigInt & operator --(int);
	BigInt & operator *=(BigInt const & other);
	BigInt & operator /=(BigInt const & other);
	BigInt & operator <<=(uint bits);
	BigInt & operator >>=(uint bits);
	BigInt & operator %=(BigInt const & other);

	BigInt & complement();

	bool operator <(BigInt const & other) const;
	bool operator >(BigInt const & other) const;
	bool operator !=(BigInt const & other) const;
	bool operator ==(BigInt const & other) const;
	bool operator >=(BigInt const & other) const;
	bool operator <=(BigInt const & other) const;

private:
	std::vector<uint> words;
	BigInt & multiplyHalf(uint half, uint dbl_offset = 0);
	BigInt & addWord(uint word, uint offset = 0);
	BigInt & addHalf(uint half, uint dbl_offset = 0);
	BigInt & addWordDblOff(uint word, uint dbl_off = 0);
	uint getHalf(uint dbl_off = 0) const;
	BigInt & clean();
};

BigInt.cpp

#include "BigInt.h"
#include <assert.h>
#include <climits>
using namespace std;

BigInt::BigInt() : words(1) {}

BigInt::BigInt(uint u) : words(1, u) {}

BigInt::BigInt(vector<uint> v) : words(v){
	clean();
}

BigInt::operator uint() const{
	return words[0];
}

BigInt & BigInt::operator +=(BigInt const & _src){
	BigInt other(_src);

	uint maxsize = max(words.size(), other.words.size());
	words.resize(maxsize);
	other.words.resize(maxsize);
	bool carry = false;
	for(uint i = 0; i < maxsize; i++){
		uint a = words[i];
		uint b = other.words[i];

		if(carry){
			if(a != UINT_MAX)
				a++;
			else if(b != UINT_MAX)
				b++;
			else{
				words[i] = a;
				carry = true;
				continue;
			}
		}

		carry = UINT_MAX - a < b;
		words[i] = a + b;
	}
	if(carry)
		words.push_back(0x1);

	return *this;
}

BigInt & BigInt::operator *=(BigInt const & _src){
	uint dblsize = _src.words.size() * 2;
	BigInt orig(*this);
	words.clear();
	words.push_back(0);
	for(uint i = 0; i < dblsize; i++){
		BigInt cpy(orig);
		uint half = _src.getHalf(i);
		cpy.multiplyHalf(half, i);
		(*this) += cpy;
	}
	return *this;
}

BigInt & BigInt::multiplyHalf(uint half, uint offset){
	uint dblsize = words.size()*2;
	uint maxdbloff = offset + dblsize;
	BigInt orig(*this);
	words.clear();
	words.resize(maxdbloff/2+1);
	for(uint i = 0; i < dblsize; i++){
		uint other = orig.getHalf(i);
		addWordDblOff(other * half, offset + i);
	}
	if(words[words.size()-1]==0)
		words.pop_back();
	return *this;
}

BigInt & BigInt::addWord(uint word, uint index){
	bool carry = UINT_MAX - word < words[index];
	words[index] += word;
	index++;
	if(carry){
		if(index<words.size())
			addWord(1, index);
		else
			words.push_back(1);
	}
	return *this;
}

BigInt & BigInt::addHalf(uint half, uint offset){
	half &= HALF_LO;
	if(offset%2 == 0)
		addWord(half, offset / 2);
	else
		addWord(half << (UINT_BITS/2), offset / 2);
	return *this;
}

BigInt & BigInt::addWordDblOff(uint word, uint offset){
	addHalf(word & HALF_LO, offset);
	addHalf((word & HALF_HI) >> (UINT_BITS/2), offset + 1);
	return *this;
}

BigInt::uint BigInt::getHalf(uint offset) const{
	uint word = words[offset/2];
	if(offset%2 == 0)
		return word & HALF_LO;
	else
		return (word & HALF_HI) >> (UINT_BITS/2);
}

BigInt & BigInt::complement(){
	uint size = words.size();
	for(uint i = 0; i < size; i++)
		words[i] = ~words[i];

	return *this;
}

bool BigInt::operator <(BigInt const & other) const{
	if(words.size() < other.words.size())
		return true;
	else if(words.size() > other.words.size())
		return false;

	BigInt cpy(other);
	uint size = words.size();
	for(uint i = size; i > 0; i--){
		if(words[i-1] < other.words[i-1])
			return true;
		else if(words[i-1] > other.words[i-1])
			return false;
	}
	return false;
}

BigInt & BigInt::operator -=(BigInt const & other){
	BigInt cpy(other);
	uint size = std::max(words.size(), other.words.size());
	cpy.words.resize(size);
	cpy.complement().addWord(1, 0);

	*this += cpy;
	words.resize(size);
	clean();
	return (*this);
}

BigInt & BigInt::operator <<=(uint bits){
	vector<uint> result(bits/UINT_BITS, 0);

	uint remain = bits % UINT_BITS;
	uint prev = 0;
	uint up_mask = ~(UINT_MAX >> remain);
	uint shift_down = UINT_BITS - remain;
	words.push_back(0);
	for(uint i = 0; i < words.size(); i++){
		uint curr = (words[i] & up_mask) >> shift_down;
		words[i] <<= remain;
		words[i] |= prev;
		prev = curr;
	}

	result.insert(result.end(), words.begin(), words.end());
	words = result;
	clean();
	return *this;
}

BigInt & BigInt::operator >>=(uint bits){
	vector<uint> result(words.begin() + bits/UINT_BITS, words.end());
	uint prev = 0;
	uint remain = bits % UINT_BITS;
	uint dn_mask = ~(UINT_MAX << remain);
	uint shift_up = UINT_BITS - remain;
	for(uint i = result.size(); i > 0; i--){
		uint curr = (result[i-1] & dn_mask) << shift_up;
		result[i-1] >>= remain;
		result[i-1] |= prev;
		prev = curr;
	}
	words = result;
	clean();
	return *this;
}

BigInt & BigInt::operator /=(BigInt const & other){
	uint minsize = std::min(this->words.size(), other.words.size());

	uint i = 0;
	while(i < minsize && this->words[i]==0 && other.words[i] == 0)
		i++;
	BigInt n;
	BigInt d;
	n.words = vector<uint>(this->words.begin()+i, this->words.end());
	d.words = vector<uint>(other.words.begin()+i, other.words.end());

	BigInt accum;

	while(d < n){
		uint n_last = *(n.words.end()-1);
		uint d_last = *(d.words.end()-1);

		uint bits = (n.words.size() - d.words.size()) * UINT_BITS;
		if(d.words.size()>1){
			if(d_last == UINT_MAX){
				d_last = 1;
				bits -= UINT_BITS;
			}
			else
				d_last++;
		}
		while(n_last / d_last == 0){
			d_last >>= 1;
			bits--;
		}
		uint div_small = BigInt(n_last / d_last);
		BigInt div = BigInt(div_small);
		div <<= bits;
		BigInt mult = d;
		mult *= div;
		while(n < mult){
			div >>= 1;
			mult = d;
			mult *= div;
		}
		accum += div;

		n -= mult;
	}

	words = accum.words;
	return *this;
}

BigInt & BigInt::operator %=(BigInt const & other){
	BigInt orig(*this);
	orig /= other;
	orig *= other;
	return (*this) -= orig;
}

BigInt & BigInt::clean(){
	vector<uint>::iterator itr = words.end();
	while(itr != words.begin() && *(itr-1) == 0)
		itr--;
	words.erase(itr, words.end());
	if(words.size()==0)
		words.push_back(0);
	return *this;
}

arithma

The above post contains the files I have been working on. I tried to make sure I do not break any C++ conformance. I ended up using the unsigned int data type, and the data given by the compiler about the data types (UINT_MAX, CHAR_BITS). I haven't tested it yet, but the code should compile theoretically on 64-bit processors, 32-bit processors and any processor that supports unsigned integer processing that have an even number of bits in that data type.
Not all the functions have been implemented yet, though the remaining ones can be easily implemented in terms of the other functions (in comparisons, only less than has been implemented.. binary non-assignment operators are not defined yet, and the increment operators have been discarded so far).

The test takes considerable time (in seconds) to compute the 1000th Fibonacci. The division and remainder operations are the most costly, and the cause for the delay in the computation is because of the conversion to decimal rather than computing the sequence number itself.

An important note about uint: In C++, unsigned overflow have standard specified behavior, which is the usual bit wrapping on overflow mode. The signed data type has no specific behavior and is left up to the compiler implementation (some people consider this good for saturating shader computations rather than wrapping them around, for example; think saturated camera picture rather than a modulating one).

saeidw

arithma, this is a very nice implementation but I'm curious why you used the "struct" keyword instead of "class" when defining BigInt. From what I can tell this is just a style thing and has no effect on the program. Am I missing something here?

arithma

@saeidw: Well I thought I didn't want to class -> public -> private. Better I struct : interface, private. I was intending not to have any private elements and make it more like an interface, but then I took shortcuts.
[edit]In short, yes, it's just a style thing.[/edit]

jsaade

http://www.codeproject.com/KB/cpp/largenumber.aspx

arithma

@ZeRaW: This class uses characters to represent digits. It's a very naive method of implementation.
Apparently, even this https://mattmccutchen.net/bigint/index.html implementation is not that performant in comparison to the one I contributed. I will contribute my implementation into Matt's. I guess GMP is the industrially sane choice if anything serious is needed anyway.

Apparently I discovered something Donald Knuth described in his Art book independently. Kudos for me.

jsaade

arithma wrote@ZeRaW: This class uses characters to represent digits. It's a very naive method of implementation.
Apparently, even this https://mattmccutchen.net/bigint/index.html implementation is not that performant in comparison to the one I contributed. I will contribute my implementation into Matt's. I guess GMP is the industrially sane choice if anything serious is needed anyway.

Apparently I discovered something Donald Knuth described in his Art book independently. Kudos for me.

Yes but the class Largenumber @http://www.codeproject.com/KB/cpp/largenumber.aspx is made to handle large numbers which are constructed from strings. I would assume the author was using characters to store individual values which your implementation does not handle as it is limited to uint/size of uints.

In the class you implemented (as I understand) you made an interface to handle a vector of uints.

the purpose of the exercise here was to handle something like:

BigInt s("12938999887637383977742121");
s *= 1000;
cout<<s;

And in addition what about signed values?

arithma

The thing is: solving the division and multiplication problem with efficiency is far more interesting to me than getting the signed integers correctly. The string initialization is child's play especially that the class can start with a integers to begin with (set to digit, multiply by ten, take next digit...)

The following code works well:

#include "BigInt.h"
#include <iostream>
using namespace std;

typedef unsigned int uint;
BigInt fib(uint i){
	BigInt a(0);
	BigInt b(1);
	for(uint j = 1; j < i; j++){
		BigInt temp(a);
		a = b;
		b += temp;
	}

	return b;
}

int main(){
	vector<uint> v;
	v.push_back(0x0);
	v.push_back(0xf);

	BigInt s(v);
	s /= 100;
	BigInt f = fib(1000);
	vector<uint> digits;
	while(BigInt(0) < f){
		BigInt d(f);
		digits.push_back(d %= 10);
		f /= 10;
	}

	for(uint i = digits.size(); i > 0; i--)
		cout << digits[i-1];
	cout << endl;
	
	return 0;
}

and returns:

43466557686937456435688527675040625802564660517371780402481729089536555417949051
89040387984007925516929592259308032263477520968962323987332247116164299644090653
3187938298969649928516003704476137795166849228875

Which is correct according to http://www.wolframalpha.com/input/?i=1000th+fibonacci

Anyway, the conversion from a vector of uint to digits is a little time consuming so you may have to endure a little lag while running the program. There's of course no indication of progress (I didn't think of placing a progress bar on a division operation =))

@ZeRaW: Where's your implementation!

Anyone is more than welcome to base a signed big integer implementation with string constructor support on this unsigned arbitrary precision numerical lib.

jsaade

I do not have time to implement I barely finish my work. I just "nazzir" according to what I know.