[C++] Huge numbers

alienchild · May 1, 2009

Does aNY1 have C++ code they wrote themself that can add 2 integers of ANY size together ? and show the answer in HEX?

onemorejosh · May 1, 2009

Yeah you're looking for a BigInt or BigInteger library

I wrote one a while back

Here's some pieces of it that'll do what you want.

Code:

#define BIGINT_E_OUTOFMEMORY -1
#define BIGINT_DATATYPE unsigned __int32
#define BIGINT_DATATYPE_MAX 0xFFFFFFFF
#define BIGINT_BYTES 4
#define BIGINT_BITS 32
#define BIGINT_ALLOCATE_BY 256

class BigInt
{
protected:
	BIGINT_DATATYPE *data;
	__int32 dataused, dataallocated;
public:
	void SetDataSize(const BIGINT_DATATYPE size)
	{
		int a = (size+BIGINT_ALLOCATE_BY-1)/BIGINT_ALLOCATE_BY;
		if (a<1)
			a=1;
		a*=BIGINT_ALLOCATE_BY*BIGINT_BYTES;
		if (this->data && this->dataallocated==a/BIGINT_BYTES)
			return;
		BIGINT_DATATYPE *newdata = (BIGINT_DATATYPE *)malloc(a);
		if (!newdata)
			throw BIGINT_E_OUTOFMEMORY;
		Zero(newdata, a/BIGINT_BYTES);
		if (this->data)
		{
			CopyMemory(newdata, this->data, this->dataallocated*BIGINT_BYTES>a?a:this->dataallocated*BIGINT_BYTES);
			free(this->data);
		}
		this->data=newdata;
		this->dataallocated=a/BIGINT_BYTES;
	}
	void Shrink()
	{
		while (this->dataused && !this->data[this->dataused-1])
			--this->dataused;
	}
	static void Zero(void *p, int num)
	{
		if (!num)
			return;
		__asm
		{
			cld
			mov ecx,num
			xor eax,eax
			mov edi,p
			rep stosd
		}
	}
	void ZeroUsed()
	{
		int x=this->dataused;
		if (!x)
			return;
		void *p=this->data;
		__asm
		{
			cld
			mov ecx,x
			xor eax,eax
			mov edi,p
			rep stosd
		}
		this->dataused=0;
	}
	void ZeroAllocated()
	{
		int x=this->dataallocated;
		if (!x)
			return;
		void *p=this->data;
		__asm
		{
			cld
			mov ecx,x
			xor eax,eax
			mov edi,p
			rep stosd
		}
		this->dataused=0;
	}
	void Swap(BigInt &value)
	{
		int da, du;
		BIGINT_DATATYPE *p;

		da=value.dataallocated;
		du=value.dataused;
		p=value.data;

		value.dataallocated=this->dataallocated;
		value.dataused=this->dataused;
		value.data=this->data;

		this->dataallocated=da;
		this->dataused=du;
		this->data=p;
	}
	int BitCount()
	{
		Shrink();
		if (!this->dataused)
			return 0;
		int count=BIGINT_BITS;
		BIGINT_DATATYPE a = this->data[this->dataused-1];
		for (int x=0; x<BIGINT_BITS; ++x)
			if (a & 0x80000000)
				return ((this->dataused-1)*BIGINT_BITS)+count;
			else
			{
				--count;
				a<<=1;
			}
		return ((this->dataused-1)*BIGINT_BITS)+count;
	}
	~BigInt()
	{
		if (data)
			free(data);
	}
	BigInt()
	{
		data=0;
		dataallocated=0;
		dataused=0;
		SetDataSize(BIGINT_ALLOCATE_BY);
	}
	BigInt(const BigInt &value)
	{
		data=0;
		dataallocated=0;
		dataused=value.dataused;
		SetDataSize(value.dataallocated);
		if (value.dataused)
			CopyMemory(data, value.data, value.dataused*BIGINT_BYTES);
	}
	BigInt(const __int32 value)
	{
		data=0;
		dataallocated=0;
		if (value)
			dataused=1;
		else
			dataused=0;
		SetDataSize(BIGINT_ALLOCATE_BY);
		data[0]=value;
	}
	BigInt(const unsigned __int32 value)
	{
		data=0;
		dataallocated=0;
		if (value)
			dataused=1;
		else
			dataused=0;
		SetDataSize(BIGINT_ALLOCATE_BY);
		data[0]=value;
	}
	BigInt(const std::string s)
	{
		data=0;
		dataallocated=0;
		dataused=0;
		SetDataSize(BIGINT_ALLOCATE_BY);
		for (unsigned __int32 x=0; x<s.length(); ++x)
		{
			if (s[x]>='0' && s[x]<='9')
			{
				*this<<=4;
				*this+=((int)s[x]-'0');
			}
			if (s[x]>='a' && s[x]<='f')
			{
				*this<<=4;
				*this+=((int)s[x]-'a'+10);
			}
			if (s[x]>='A' && s[x]<='F')
			{
				*this<<=4;
				*this+=((int)s[x]-'A'+10);
			}
		}
	}
	BigInt & operator += (const BIGINT_DATATYPE value)
	{
		++this->dataused;
		if (this->dataused>this->dataallocated)
			this->SetDataSize(this->dataused);
		void *p=this->data;
		__asm
		{
			mov eax,p
			mov ebx,value
			add [eax], ebx
			jnc adddone
addloop:
			add eax, 4
			add [eax], 1
			jc addloop
adddone:
		}
		if (!this->data[this->dataused-1])
			--this->dataused;
		return *this;
	}
	BigInt &operator += (const BigInt &value)
	{
		BIGINT_DATATYPE x=value.dataused;
		this->dataused=x+1;
		if (this->dataused>this->dataallocated)
			this->SetDataSize(this->dataused);
		void *p1=this->data;
		void *p2=value.data;
		__asm
		{
			mov eax,p1
			mov ebx,p2
			mov ecx,x
			inc ecx
			clc
addloop:
			mov edx, [ebx]
			adc [eax], edx
			inc ebx
			inc eax
			inc ebx
			inc eax
			inc ebx
			inc eax
			inc ebx
			inc eax
			dec ecx
			jnz addloop
			jnc addshiftdone
addshiftloop:
			add [eax], 1
			inc eax
			inc eax
			inc eax
			inc eax
			jc addshiftloop
addshiftdone:
		}
		if (!this->data[x])
			--this->dataused;
		return *this;
	}
	BigInt & operator = (const __int32 value)
	{
		if (this->dataused>1)
			ZeroUsed();
		if (value)
			this->dataused=1;
		else
			this->dataused=0;		
		this->data[0]=value;
		return *this;
	}
	BigInt & operator = (const unsigned __int32 value)
	{
		if (this->dataused>1)
			ZeroUsed();
		if (value)
			this->dataused=1;
		else
			this->dataused=0;
		this->data[0]=value;
		return *this;
	}
	BigInt & operator = (const BigInt &value)
	{
		this->Swap(BigInt(value));
		return *this;
	}
	friend BigInt operator + (const BigInt &a, const BigInt &b)
	{
		return BigInt(a)+=b;
	}
friend bool operator == (const BigInt &a, const int value)
	{
		int ad=a.dataused;
		if (ad)
			while (ad && !a.data[ad-1])
				--ad;
		if (ad>1)
			return false;
		if (!ad && !value)
			return true;
		return a.data[0]==value;
	}
	friend bool operator == (const BigInt &a, const BigInt &b)
	{
		int ad=a.dataused;
		int bd=b.dataused;
		if (ad)
			while (ad && !a.data[ad-1])
				--ad;
		if (bd)
			while (bd && !b.data[bd-1])
				--bd;
		if (ad!=bd)
			return false;
		for (int x=0; x<ad; ++x)
			if (a.data[x]!=b.data[x])
				return false;
		return true;
	}
	friend bool operator != (const BigInt &a, const BigInt &b)
	{
		return !(a==b);
	}
	friend bool operator != (const BigInt &a, const int b)
	{
		return !(a==b);
	}
friend bool operator > (const BigInt &a, const BigInt &b)
	{
		int ad=a.dataused;
		int bd=b.dataused;
		if (ad)
			while (ad && !a.data[ad-1])
				--ad;
		if (bd)
			while (bd && !b.data[bd-1])
				--bd;
		if (ad!=bd)
			return ad>bd;
		for (int x=ad-1; x>=0; --x)
			if (a.data[x]!=b.data[x])
				return a.data[x]>b.data[x];
		return false;
	}
	friend bool operator < (const BigInt &a, const BigInt &b)
	{
		int ad=a.dataused;
		int bd=b.dataused;
		if (ad)
			while (ad && !a.data[ad-1])
				--ad;
		if (bd)
			while (bd && !b.data[bd-1])
				--bd;
		if (ad!=bd)
			return ad<bd;
		for (int x=ad-1; x>=0; --x)
			if (a.data[x]!=b.data[x])
				return a.data[x]<b.data[x];
		return false;
	}
	friend bool operator >= (const BigInt &a, const BigInt &b)
	{
		int ad=a.dataused;
		int bd=b.dataused;
		if (ad)
			while (ad && !a.data[ad-1])
				--ad;
		if (bd)
			while (bd && !b.data[bd-1])
				--bd;
		if (ad!=bd)
			return ad>bd;
		for (int x=ad-1; x>=0; --x)
			if (a.data[x]!=b.data[x])
				return a.data[x]>b.data[x];
		return true;
	}
	friend bool operator <= (const BigInt &a, const BigInt &b)
	{
		int ad=a.dataused;
		int bd=b.dataused;
		if (ad)
			while (ad && !a.data[ad-1])
				--ad;
		if (bd)
			while (bd && !b.data[bd-1])
				--bd;
		if (ad!=bd)
			return ad<bd;
		for (int x=ad-1; x>=0; --x)
			if (a.data[x]!=b.data[x])
				return a.data[x]<b.data[x];
		return true;
	}
	std::string ToHex()
	{
		if (!this->dataused)
			return std::string("0");
		std::string str;
		bool foundfirst=0;
		for (int x = this->dataused-1; x>=0; --x)
		{
			int v;
			for (int y=1; y<=BIGINT_BITS/4; ++y)
			{
				v = (this->data[x] & (0xF << (BIGINT_BITS-y*4))) >> (BIGINT_BITS-y*4);
				if (foundfirst || v)
				{
					foundfirst=true;
					if (v<10)
						str+=((char)'0'+v);
					else
						str+=((char)'A'+v-10);
				}
			}
		}
		return str;
	}
	BigInt & operator ++ ()
	{
		for (int x=0; x<this->dataused; ++x)
			if (++this->data[x])
				return *this;
		++this->dataused;
		if (this->dataused>this->dataallocated)
			this->SetDataSize(this->dataused);
		this->data[this->dataused-1]=1;
		return *this;
	}
};

...I snipped a lot out but I think I gave you enough to create big integers, compare them to each other, add them, and print a result

Anyway

To use it in your program you could just do something like

Code:

int _tmain(int argc, _TCHAR* argv[])
{

	BigInt a = 12472910;
	BigInt b("123ABCDE098");
	BigInt c=a+b;

	std::cout << a.ToHex() << " + " << b.ToHex() << " = " << c.ToHex() << "\n";
	
	_getch();

	return 0;
}

...which would give this output:

BE524E + 123ABCDE098 = 123AC8C32E6

...This is written for 32 bit systems. There's a 64 bit version too

alienchild · May 1, 2009

WOW how big a number can it hold

onemorejosh · May 1, 2009

erm...

a lil over 16 billion binary digits, or 4 billion hex digits... or about 6 billion regular number digits

decent keys for encryption use 1024 binary digits

stupidly paranoid keys might be 4096 digits... but i think you'll be jusssst fine with your 16 billion

I didn't give you the X to the power of Y modulus N routines ... let alone miller rabin or even..um... multiplication

So you won't be doin much encrypting with that

but you only asked to add lol

Hope it works for ya.

PS: Positive numbers only.

[C++] Huge numbers

alienchild

Initiate Mage

onemorejosh

Experienced Elementalist

alienchild

Initiate Mage

onemorejosh

Experienced Elementalist

RaGEZONE Sponsor

About RaGEZONE

Forum Statistics

RaGEZONE Partners