Ok. Originally I was trying to write a program that would calculate pi to infinite decimal places. The calculus baesd algorithm I made for this is flawless, except that C++ can only handle 16 digits! So I did some looking around, for libraries and what not, to find something that supports a datatype of many more digits. Apperantly they don't exist (or they're not free anyway). So I've started writing my own program for handling numbers more precise than 16 digits.

It uses binary based logic to create files containing numbers, and a custom datatype that can contain a variable number of digits. So far I've completed the logic for addition and multiplication of these numbers. The problem is, it's way less efficient and much slower than using regular operations. I benchmarked it at 2.134 seconds to calculate 440000 * 3500. This calculation is instantaneos when c++ does all the math. I know there's probably some holes in the logic, since I'm a bit of a pothead, but here's the code:

#include<iostream>
#include<iomanip>
#include<fstream>
#include<cmath>
#include<ctime>
using namespace std;

const int MAX = 2056;

struct Num
{
	int  _MSBIndex;
	bool _Sign;
	bool _bd[MAX];
};

Num AddNum(Num&, Num&);
Num MultNum(Num&, Num&);
void Neg(Num&);
bool Equal(Num&, Num&);
void ShowNum(Num&);
void SaveNum(Num&, char[]);
void LoadNum(Num&, char[]);
void MakeNum(Num&, double);
void SolveMSB(Num&, int);

//Debug Funcs
void DoEfficiencyDebug();

int main()
{
	Num nNumber;
	Num nNumber2;
	
	//MakeNum(nNumber, 1);
	//SaveNum(nNumber, "One.bin");
	MakeNum(nNumber2, 440000); //303milli--|
	MakeNum(nNumber, 3500);	  //303milli--|
	ShowNum (nNumber);
	ShowNum (nNumber2);
	ShowNum(MultNum(nNumber, nNumber2));
	DoEfficiencyDebug();
	cin.get();
	return 0;
}

void DoEfficiencyDebug()
{
	cout << "\n\nClock ticks for calculation: " << clock();
	cout << "\n@ " << CLOCKS_PER_SEC << " For Duration: " << clock() / (CLOCKS_PER_SEC / 1000) << " milliseconds";
	return;
}

bool Equal(Num &nNumber, Num &nNumber2)
{
	bool bEqual = true;
	if (nNumber._MSBIndex != nNumber2._MSBIndex)
		bEqual = false;
	else
	{
		for (int i = 0; i < nNumber._MSBIndex; i++)
		{
			if (nNumber._bd[i] != nNumber2._bd[i])
			{
				bEqual = false;
				break;
			}
		}
	}

	return bEqual;
}
void SolveMSB(Num &nNumber, int iStartApprox)
{
	for (int i = iStartApprox; i >= 0; i--)
		if (nNumber._bd[i] == true)
		{
			nNumber._MSBIndex = i;
			break;
		}
	return;
}

void Neg(Num &nNumber)
{
	nNumber._Sign = (nNumber._Sign == true) ? false : true;
	return;
}

Num MultNum(Num &nNumber, Num &nNumber2)
{
	Num nReturn = {0};
	Num nCount = {0};
	Num nOne = {0};
	LoadNum(nOne, "One.bin");
	
	while (!Equal(nCount, nNumber2)) 
	{
		nCount = AddNum(nCount, nOne); 
		nReturn = AddNum(nReturn, nNumber);
	}
	SolveMSB(nReturn, (nNumber._MSBIndex + nNumber2._MSBIndex)); 
	//SolveMSB(nReturn, MAX); //DEBUG ONLY
	
	return nReturn;
}

Num AddNum(Num &nNumber, Num &nNumber2)
{
	Num nReturn = {0};
	int iMSB = 0;
	bool bCarry = false;
	

	if (nNumber._MSBIndex >= nNumber2._MSBIndex)
		iMSB = nNumber._MSBIndex;
	else
		iMSB = nNumber2._MSBIndex;

	//the actual addition logic
	for (int i = 0; i <= iMSB + 1; i++)
	{
		if (nNumber._bd[i] == true && nNumber2._bd[i] == true && bCarry == false)
		{
			nReturn._bd[i] = false;
			bCarry = true;
		}
		else if (nNumber._bd[i] == true && nNumber2._bd[i] == true && bCarry == true)
		{
			nReturn._bd[i] = true;
			bCarry = true;
		}
		else if ((nNumber._bd[i] != nNumber2._bd[i]) && bCarry == true)
		{
			nReturn._bd[i] = false;
			bCarry = true;
		}
		else if ((nNumber._bd[i] != nNumber2._bd[i]) && bCarry == false)
		{
			nReturn._bd[i] = true;
			bCarry = false;
		}
		if (nNumber._bd[i] == false && nNumber2._bd[i] == false && bCarry == true)
		{
			nReturn._bd[i] = true;
			bCarry = false;
		}
	}
	
	SolveMSB(nReturn, iMSB + 1);
	//SolveMSB(nReturn, MAX); //DEBUG ONLY
	return nReturn;
}

void SaveNum(Num &nNumber, char szFilename[])
{
	ofstream outFile;
	outFile.open(szFilename, ios::out | ios::binary);
	outFile.write(reinterpret_cast<char*>(&nNumber), sizeof(Num));
	outFile.close();
	return;
}

void LoadNum(Num &nNumber, char szFilename[])
{
	ifstream outFile;
	outFile.open(szFilename, ios::in | ios::binary);
	outFile.read(reinterpret_cast<char*>(&nNumber), sizeof(Num));
	outFile.close();
	return;
}

void MakeNum(Num &nNumber, double dEntry)
{
	bool bMSB = false;
	bool bMSBset = false;
	dEntry+= 1;
	for (int i = MAX; i >= 0; i--)
	{
		if ((dEntry - (pow(2, i))) > 0)
		{
			bMSB = true;
			dEntry -= (pow(2, i));
			nNumber._bd[i] = true;
		}
		else 
			nNumber._bd[i] =false;
		if (bMSB == true && bMSBset == false)
		{
			nNumber._MSBIndex = i;
			bMSBset = true;
		}
		if (dEntry == 0)
			break;
	}
	return;
}

void ShowNum(Num &nNumber)
{
	double dAdder = 0;
	bool bShowFlag = false;
	int iFour = 0;
	int iZeros = 0;
	cout << "Most Significant Bit Index: " << nNumber._MSBIndex << endl;
	cout << "Binary Form: ";
	//Binary display algorithm, displays in 4's
	iZeros = nNumber._MSBIndex + 1;
	for (int ii = 0; ii <= nNumber._MSBIndex; ii++)
	{
		if ((iZeros - 4) >= 0)
			iZeros -= 4;
		else
			break;
	}
	iZeros = 4 - iZeros;
	if (iZeros >= 4)
		iZeros -= 4;
	for (int i = nNumber._MSBIndex + iZeros; i >= 0; i--)
	{
		if (iFour >= 4)
		{
			cout << " ";
			iFour = 0;
		}
		iFour++;
		cout << nNumber._bd[i];
		if (nNumber._bd[i] == true)
		{
			dAdder += pow(2, i) ;
		}
	}
	cout << "\nDecimal Form: ";
	cout << setprecision(15) << dAdder << endl;
	cout << endl;
	return;
}

wow...it's longer than i remembered. sorry. any help increasing the efficiency of this code would be immensly appreciated!

Ok. Originally I was trying to write a program that would calculate pi to infinite decimal places. The calculus baesd algorithm I made for this is flawless, except that C++ can only handle 16 digits! So I did some looking around, for libraries and what not, to find something that supports a datatype of many more digits. Apperantly they don't exist (or they're not free anyway). So I've started writing my own program for handling numbers more precise than 16 digits.

There are datatypes out there that support more than 16 digits and some of them are free. I've never actually used any of them. Check out some of the links on this wikipedia page.

http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic

I didn't look at your code. I feel pretty confident that you don't need to write your own code for this arbitrary precision datatype if you don't want to. If you still want to write your own after you check out the links, post again and I'll look at your code.

thanks for the link! But I think I'm still going to try to get this to work. Problems like this intrigue me too much to ignore :D. Anyone with any tips related to the actual code would be appreciated.

Well I don't know how many suggestions I can make regarding how to improve the efficiency since I really don't understand how this entire program is supposed to work, but here goes.

#include<iostream>
#include<iomanip>
#include<fstream>
#include<cmath>
#include<ctime>
using namespace std;

const int MAX = 2056;

struct Num
{
	int  _MSBIndex;
	bool _Sign;
	bool _bd[MAX];
};

Num AddNum(Num&, Num&);
Num MultNum(Num&, Num&);
void Neg(Num&);
bool Equal(Num&, Num&);
void ShowNum(Num&);
void SaveNum(Num&, char[]);
void LoadNum(Num&, char[]);
void MakeNum(Num&, double);
void SolveMSB(Num&, int);

//Debug Funcs
void DoEfficiencyDebug();

int main()
{
	Num nNumber;
	Num nNumber2;
	
	//MakeNum(nNumber, 1);
	//SaveNum(nNumber, "One.bin");
	MakeNum(nNumber2, 440000); //303milli--|
	MakeNum(nNumber, 3500);	  //303milli--|
	ShowNum (nNumber);
	ShowNum (nNumber2);
	ShowNum(MultNum(nNumber, nNumber2));
	DoEfficiencyDebug();
	cin.get();
	return 0;
}

void DoEfficiencyDebug()
{
	cout << "\n\nClock ticks for calculation: " << clock();
	cout << "\n@ " << CLOCKS_PER_SEC << " For Duration: " << clock() / (CLOCKS_PER_SEC / 1000) << " milliseconds";
	return;
}

bool Equal(Num &nNumber, Num &nNumber2)
{
	bool bEqual = true;
	if (nNumber._MSBIndex != nNumber2._MSBIndex)
		bEqual = false;
	else
	{
		for (int i = 0; i < nNumber._MSBIndex; i++)
		{
			if (nNumber._bd[i] != nNumber2._bd[i])
			{
				bEqual = false;
				break;
			}
		}
	}

	return bEqual;
}
void SolveMSB(Num &nNumber, int iStartApprox)
{
	for (int i = iStartApprox; i >= 0; i--)
		if (nNumber._bd[i] == true)
		{
			nNumber._MSBIndex = i;
			break;
		}
	return;
}

void Neg(Num &nNumber)
{
	nNumber._Sign = (nNumber._Sign == true) ? false : true;
	return;
}

Num MultNum(Num &nNumber, Num &nNumber2)
{
	Num nReturn = {0};
	Num nCount = {0};
	Num nOne = {0};
	LoadNum(nOne, "One.bin");
	
	while (!Equal(nCount, nNumber2)) 
	{
		nCount = AddNum(nCount, nOne); 
		nReturn = AddNum(nReturn, nNumber);
	}
	SolveMSB(nReturn, (nNumber._MSBIndex + nNumber2._MSBIndex)); 
	//SolveMSB(nReturn, MAX); //DEBUG ONLY
	
	return nReturn;
}

Num AddNum(Num &nNumber, Num &nNumber2)
{
	Num nReturn = {0};
	int iMSB = 0;
	bool bCarry = false;
	

	if (nNumber._MSBIndex >= nNumber2._MSBIndex)
		iMSB = nNumber._MSBIndex;
	else
		iMSB = nNumber2._MSBIndex;

	//the actual addition logic
	for (int i = 0; i <= iMSB + 1; i++)
	{
		if (nNumber._bd[i] == true && nNumber2._bd[i] == true && bCarry == false)
		{
			nReturn._bd[i] = false;
			bCarry = true;
		}
		else if (nNumber._bd[i] == true && nNumber2._bd[i] == true && bCarry == true)
		{
			nReturn._bd[i] = true;
			bCarry = true;
		}
		else if ((nNumber._bd[i] != nNumber2._bd[i]) && bCarry == true)
		{
			nReturn._bd[i] = false;
			bCarry = true;
		}
		else if ((nNumber._bd[i] != nNumber2._bd[i]) && bCarry == false)
		{
			nReturn._bd[i] = true;
			bCarry = false;
		}
		if (nNumber._bd[i] == false && nNumber2._bd[i] == false && bCarry == true)
		{
			nReturn._bd[i] = true;
			bCarry = false;
		}
	}
	
	SolveMSB(nReturn, iMSB + 1);
	//SolveMSB(nReturn, MAX); //DEBUG ONLY
	return nReturn;
}

void SaveNum(Num &nNumber, char szFilename[])
{
	ofstream outFile;
	outFile.open(szFilename, ios::out | ios::binary);
	outFile.write(reinterpret_cast<char*>(&nNumber), sizeof(Num));
	outFile.close();
	return;
}

void LoadNum(Num &nNumber, char szFilename[])
{
	ifstream outFile;
	outFile.open(szFilename, ios::in | ios::binary);
	outFile.read(reinterpret_cast<char*>(&nNumber), sizeof(Num));
	outFile.close();
	return;
}

void MakeNum(Num &nNumber, double dEntry)
{
	bool bMSB = false;
	bool bMSBset = false;
	dEntry+= 1;
	for (int i = MAX; i >= 0; i--)
	{
		if ((dEntry - (pow(2, i))) > 0)
		{
			bMSB = true;
			dEntry -= (pow(2, i));
			nNumber._bd[i] = true;
		}
		else 
			nNumber._bd[i] =false;
		if (bMSB == true && bMSBset == false)
		{
			nNumber._MSBIndex = i;
			bMSBset = true;
		}
		if (dEntry == 0)
			break;
	}
	return;
}

void ShowNum(Num &nNumber)
{
	double dAdder = 0;
	bool bShowFlag = false;
	int iFour = 0;
	int iZeros = 0;
	cout << "Most Significant Bit Index: " << nNumber._MSBIndex << endl;
	cout << "Binary Form: ";
	//Binary display algorithm, displays in 4's
	iZeros = nNumber._MSBIndex + 1;
	for (int ii = 0; ii <= nNumber._MSBIndex; ii++)
	{
		if ((iZeros - 4) >= 0)
			iZeros -= 4;
		else
			break;
	}
	iZeros = 4 - iZeros;
	if (iZeros >= 4)
		iZeros -= 4;
	for (int i = nNumber._MSBIndex + iZeros; i >= 0; i--)
	{
		if (iFour >= 4)
		{
			cout << " ";
			iFour = 0;
		}
		iFour++;
		cout << nNumber._bd[i];
		if (nNumber._bd[i] == true)
		{
			dAdder += pow(2, i) ;
		}
	}
	cout << "\nDecimal Form: ";
	cout << setprecision(15) << dAdder << endl;
	cout << endl;
	return;
}

I don't know what is stored in "One.bin" in line 95. I don't see any calls to saveNum at all, so I don't know what its purpose is. I would, if at all possible, not use ofstream or ifstream at all. It slows things down tremendously and it's not at all clear to me why they are needed and how they are used. I don't understand how MultNum works.

MAX is defined as 2056 in line 8, but in line 180 you are raising 2 to the 2056 power, which might be beyond even long double's range. You're then subtracting that from a double. The computer might be able to typecast these both into long doubles and figure it out with overflowing, but I don't know whether every computer has a long double type (one of the options from the "pow" function) that can handle 2 to the 2056 power without blowing up. I'm confessing ignorance here, but it's definitely something to consider.

I also don't know if it's wise to have a 2056 element boolean array and do all of your calculations bit by bit using bools. You might want to have an integer array. C++ still wouldn't be able to straight out multiply two numbers which are each over 1000 bits long, but you could have it at least do some. You could have about 64 integers rather than 2056 bools and save yourself quite a few mathematical operations. I don't see any need to program a bit by bit multiplication or addition. Break the huge number into about 64 chunks/integers and do the work chunk by chunk. You may have to double that to 128 and have them be small enough that integer multiplication won't overflow, but it's better than doing it bit by bit.

Anyway, that's my two cents. I can't comment further since, like I said, I'm not sure how all of these functions work (and what exactly some of them do). Hope this helps.

Thanks for trying to understand my code! Haha
Alot of the concerns you have with functions, such as MakeNum, SaveNum, and LoadNum are not what is causing the inefficiency. MakeNum is only for testing purposes, until I have discrete logic for all number operations - it basically translates a double into a binary form number. SaveNum does a binary save of a number to a file - which as far as I know is one of the fastest methods of dumping a arbitrary data structure. LoadNum loads the number from the binary file.

Also, in MakeNum the MAXIMUM it will raise 2 to the power of is 2056, but that is likely never to happen because it breaks when it's done converting up to the highest power of the number. One.bin is simply the number 1 - but it's loaded from a file because the datatype is so complex that it's just faster to load then to hardcode. This only happens once during the execution so it shouldn't be the cause of the inefficiency either.

C++ still wouldn't be able to straight out multiply two numbers which are each over 1000 bits long

But that's not true! This program is capable of doing that, only it's so inefficient that it would take quite a long time. Since I've started this program, I've improved the efficiency over 700%, and I'm sure I can do much better. I'm pretty sure it's MultNum that needs the tightening up - since it works by adding Number1's Number2 amount of times. I'm sure there's a more complex binary pattern I could implement to do the multiplication in many less iterations. But seriously, thanks for you help!

By "straight out multiply", I meant "multiply without having to tell the computer how" (i.e. keep track of carry bits, etc., like you're doing). C++, if you program it right and give it new types, can multiply numbers with millions of bits. Anyway, it's an interesting project. I think I'll play around with it. Thanks.

This article has been dead for over six months. Start a new discussion instead.