Eine bigint Klasse, halbwegs von mir...

Mis2com

Hallo,

ich habe eine kleine BigInt-Klasse geschrieben, sie ist nur teilweise von mir, + und * habe ich alleine nicht hinbekommen (schnell) und - ist hier eh noch falsch.
Dennoch habe ich dadurch einiges gelernt...

#ifndef DQL_
#define DQL_

#include <ostream>
#include <string>

// Double Quadruple Long (Doppelt vierfacher Long (256 Bit))

template<int D>
class DQL
{
private:

	unsigned long m_l[D];

	void inEach(unsigned long l);
	int  charToDigit(char c)
	{
		return c - '0';
	}

public:

	typedef unsigned long* iterator;
						int      digits_count() const;
						void     bit(unsigned long);
						iterator begin() {return m_l;}
						iterator end()   {return m_l + D;}
						void     out();
						unsigned long low(unsigned __int64 i64)
						{
							return static_cast<unsigned long>(i64);
						}
						unsigned long high(unsigned __int64 i64)
						{
							return static_cast<unsigned long>(i64 >> 32);
						}
						void     setBit(int n, bool set)
						{
							if(set)
								m_l[n / 32] |=  (1 << (n % 32));
							else
								m_l[n / 32] &= ~(1 << (n % 32));
						}

	                             DQL() {inEach(0);}
	                             DQL(std::string str);
							     DQL(unsigned long l) {(*this) = l;}
	DQL                 operator+   (const DQL& dql);	
	DQL                 operator*   (const DQL& dql);
	DQL                 operator*   (unsigned long ul);
	bool                operator>   (const DQL& dql) const;
	bool                operator==  (const DQL& dql) const;
	DQL                 operator-   (const DQL& dql);
	DQL&                operator=   (const std::string& str);
	DQL&                operator=   (const unsigned long l[D]);
	DQL&                operator=   (unsigned long l);         
	bool                operator<   (const DQL& dql) const
	{
		return dql > *this;
	}
	bool                operator<=  (const DQL& dql) const
	{
		return *this < dql || *this == dql;
	}
	bool                operator>=  (const DQL& dql) const
	{
		return *this > dql || *this == dql;
	}
	DQL&                operator*=  (const DQL& dql)
	{
		*this = *this * dql;
		return *this;
	}
	DQL&                operator+=  (const DQL& dql)
	{
		*this = *this + dql;
		return *this;
	}
	DQL&                operator-=  (const DQL& dql)
	{
		*this = *this - dql;
		return *this;
	}
	DQL&                operator++  ()
	{
		(*this) += 1;
		return *this;
	}
	DQL                 operator++  (int)
	{
		DQL temp(*this);
		++(*this);
		return temp;
	}
	DQL&                operator--  ()
	{
		(*this) -= 1;
		return *this;
	}
	DQL                 operator--  (int)
	{
		DQL temp(*this);
		--(*this);
		return temp;
	}
	unsigned long&      operator[]  (size_t n)
	{
		return m_l[n];
	}
	unsigned long       operator[]  (size_t n) const
	{
		return m_l[n];
	}
};

// ==================================================

template<int D>
inline void DQL<D>::inEach(unsigned long l)
{
	for(size_t n = 0; n < D; ++n)
		m_l[n] = l;
}

// ==================================================

template<int D>
inline DQL<D>& DQL<D>::operator=(unsigned long l)
{
	inEach(0);
	m_l[0] = l;	
	return *this;
}

// ==================================================

template<int D>
inline DQL<D>& DQL<D>::operator=(const unsigned long l[D])
{
	memcpy(&m_l, l, sizeof(unsigned long) * D);
	return *this;
}

// ==================================================

template<int D>
void DQL<D>::bit(unsigned long l)
{
	std::cout << "\r\n\r\n";
	for(int n = 31; n >= 0; --n)
	{
		std::cout << ((l & (1 << n)) >> n);
	}
	std::cout << "\r\n\r\n";
}

// ==================================================

template<int D>
DQL<D>::DQL(std::string str)
{
	(*this) = 0ul;

	std::string::iterator it;
	DQL                   dql;
	int n = 0;
	for(it = str.end() - 1; it >= str.begin(); --it, ++n)
	{
		*this += DQL(charToDigit(*it)) * pow(10, n);
	}
	dql = dql;
}

// ==================================================

template<int D>
DQL<D>& DQL<D>::operator=(const std::string& str)
{
	std::string temp = str;

	return *this;	
}

// ==================================================

template<int D>
DQL<D> DQL<D>::operator+(const DQL& dql)
{
	DQL<D>           temp;
	unsigned long    ulCarry = 0;
	unsigned __int64 temp2;

	for(int n = 0; n < D; ++n)
	{
		temp2        = static_cast<unsigned __int64>(m_l[n]) + dql.m_l[n] + ulCarry;
		ulCarry      = high(temp2);
		temp.m_l[n]  = low(temp2);
	}
	return temp;
}

// ==================================================

template<int D>
DQL<D> DQL<D>::operator-(const DQL& dql)
{
	DQL<D> temp;
	int res;
	int mind = 0;

	for(int arr = 0; arr < D; ++arr)
	{
		for(int n = 0; n < 32; ++n)
		{
			res = ((m_l[arr] & (1 << n)) >> n) - ((dql.m_l[arr] & (1 << n)) >> n);
			if(mind != 0)
			{
				res -= mind;
				mind = 0;
			}
			if(abs(res) == 1)
			{
				temp.m_l[arr] |= (1 << n);
			}
			else
				temp.m_l[arr] &= ~(1 << n);
			if(res < 0)
				mind = 1;
		}
	}
	return temp;
}

// ==================================================

template<int D>
void DQL<D>::out()
{
	for(int arr = 7; arr >= 0; --arr)
	{
		for(int n = 31; n >=0; --n)
		{
			std::cout << ((m_l[arr] & (1 << n)) >> n);
		}
		std::cout << ' ';
	}

	std::cout << "\r\n\r\n";
}

// ==================================================

template<int D>
bool DQL<D>::operator==(const DQL<D>& dql) const
{
	for(int arr = 7; arr >= 0; --arr)
	{
		for(int n = 31; n >= 0; --n)
		{
			if((dql.m_l[arr] & (1 << n)) != (m_l[arr] & (1 << n)))
				return false;
		}
	}
	return true;
}

// ==================================================

template<int D>
bool DQL<D>::operator>(const DQL<D>& dql) const
{
	for(int arr = 7; arr >= 0; --arr)
	{
		for(int n = 31; n >= 0; --n)
		{
			if((m_l[arr] & (1 << n)) > (dql.m_l[arr] & (1 << n)))
				return true;
			else if((m_l[arr] & (1 << n)) < (dql.m_l[arr] & (1 << n)))
				return false;
		}
	}
	return false;
}

// ==================================================

template<int D>
DQL<D> DQL<D>::operator*(const DQL& dql)
{
	DQL<D> temp;
	int p = digits_count();
	int o = dql.digits_count();
	unsigned long carry = 0;

	for (size_t m = 0; m < digits_count() || carry != 0; ++m)
	{
		for(size_t n = m; n < dql.digits_count() || carry != 0; ++n)
		{
			unsigned __int64 t = static_cast<unsigned __int64>(m_l[m]) * dql[n] + temp[n+m] + carry;
			carry       = high(t);
			temp[n + m] = low(t);
		}
	}

	return temp;
}

// ==================================================

template<int D>
DQL<D> DQL<D>::operator*(unsigned long ul)
{
	DQL<D>           temp;
	unsigned long    ulCarry = 0;
	unsigned __int64 temp2;

	for(int n = 0; n < D; ++n)
	{
		temp2        = static_cast<unsigned __int64>(m_l[n]) * ul + ulCarry;
		ulCarry      = high(temp2);
		temp.m_l[n]  = low(temp2);
	}
	return temp;
}

// ==================================================

template<int D>
int DQL<D>::digits_count() const
{
	int digits_count = D;
	while((*this)[digits_count - 1] == 0)
		--digits_count;
	return digits_count;
}

// ==================================================

template<int D>
const std::ostream& operator<<(const std::ostream& str, const DQL<D>& dql)
{
	return str;	
}

// ==================================================

#endif

DQL<8> bla; ist ein 8 Byte datentyp.

ich bin nicht sicher, ob alles richtig ist...

Ich wollte die Klasse nur einmal so zeigen.

MfG MAV

hm, was ist denn dieser Template Parameter? Ich dachte das ist ein 256 bit (also 32 byte) großer Typ.

phlox81

fest schrieb:

hm, was ist denn dieser Template Parameter? Ich dachte das ist ein 256 bit (also 32 byte) großer Typ.

Ist es auch. Aber in dem fall gibt die Zahl die Anzahl der Bytes im Datentyp an.

Devil

Mis2com

Exakt, eigentlich soll es ein 256 Bittyp sein, aber es ist auch möglich auf max_int zu erweitern.
Allerdings konnte ich die Ergebnisse bei hoher Multiplikation nur schwerlich prüfen und da waren die Proben falsch... hm...
Naja, wen es interessiert, ich fand das Schreiben davon sehr interessant.
Aber da ich nur einen Big IEEE Typ brauchen kann und ich hier sowieso nichts mehr selber machen würde (wenn ich selber Artikel zum Lenren dazu finden würde, wäre es ja k.P.), höre ich mit der Klasse auf.

MfG MAV