I produced my own class long_number to proceed mathematical operations for higher numbers than long long int (for prime numbers purpose, etc. ). Now I am testing the addition and comparing the speed on the following code:
#include <iostream>
#include <cmath>
#include <vector>
#include <typeinfo>
#include <string>
//#include "long_number.h" the header is below
#include <chrono>
using namespace std;
using namespace ln;
typedef long long int Te;
typedef long_number Se;
int main()
{
// Start measuring time
vector<Te> numbers;
string s = "";
for(int i=1;i<15;i++)
{
s.append(to_string(i));
numbers.push_back(stoll(s));
}
auto begin = std::chrono::high_resolution_clock::now();
Te sum=0;
for(int k=0;k<=5000;k++)
{
sum=0;
for(int j=1;j<=7;j++)
for(int i =0;i<numbers.size();i++)
sum +=numbers[i];
}
cout << "Sum " <<sum <<endl;
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
printf("Time measured: %.6f seconds.\n", elapsed.count() * 1e-9);
vector<Se> numbers2;
string se;
for(int i=1;i<15;i++)
{
se.append(to_string(i));
numbers2.push_back((Se)stoll(se));
}
begin = std::chrono::high_resolution_clock::now();
Se sum2=0;
for(int k=0;k<=5000;k++)
{
sum2=0;
for(int j=1;j<=7;j++)
for(int i =0;i<numbers2.size();i++)
sum2 += numbers2[i];
}
cout << "Sum " <<sum2 <<endl;
end = std::chrono::high_resolution_clock::now();
elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
printf("Time measured: %.6f seconds.\n", elapsed.count() * 1e-9);
return 0;
}
Which compiled with g++ main.cpp -Wall -O3 -std=c++17 -o program prints following result:
Sum 8729267916327544355
Time measured: 0.000474 seconds.
Sum 8729267916327544355
Time measured: 0.677444 seconds.
You can see, that the int addition is about 1000 times faster. My class long_number is following:
#include <iostream>
#include <cmath>
#include <vector>
#include <typeinfo>
#include <string>
using namespace std;
namespace ln
{
//stores long integers in vector, 0th position means 10^0 -> reversed order, using for operation of huge nubers overnight
class long_number
{
private:
public:
vector<unsigned int> numero = {};//every component store one digit of the number
unsigned int size = 0;//size of the numero - how many digit has the number
long_number() {};//default constructor
void zero_check()//checks and remuves zero digits from the left of the number
{
while(numero[numero.size()-1]==0&&numero.size()>=2)
{
numero.pop_back();
size--;
}
size = numero.size();
}
operator unsigned int() const //conversion form long_number to int
{
//cout << "typecast operator unsigned int() used" << endl;
unsigned int num=0;
for(unsigned int i=0;i<size;i++)
num += numero[i]*pow(10.,i);
return num;
}
template<typename numb>
long_number(numb a)//constructor
{
string b = to_string(a);
read(b);
}
long_number(const long_number& a)//copy constructor
{
numero = a.numero;
size = a.numero.size();
}
int ssize() const
{
return (this->numero).size();
}
void set_size(int i)
{
(this->numero).resize(i);
}
void get (ostream& out) const;//historic function to print the long_number
void read(string input); //historic function to declare long_number
vector <unsigned int> get_numero() const //not necessary cauz all is public
{
return numero;
}
void set_numero(int num,int pos)
{
numero[pos]=num;
}
long_number& operator+=(const long_number& b)//defined by the binary operator +
{
long_number a= *this;
*this = (a + b);
return *this;
}
template <typename numb>
long_number& operator=( numb b)// I don't know why is this here
{
string s = to_string(b);
this->read(s);
return *this;
}
~long_number(){}//destructor
//this is here to get acces inside the operators to another operators
//it should work also without this according to
//https://www.learncpp.com/cpp-tutorial/9-2a-overloading-operators-using-normal-functions/
//because all is public but it doesnt
friend long_number operator + ( const long_number&,const long_number&);
};
long_number operator+ (const long_number& a, const long_number& b)//sum of two long_numbers
{
long_number res;
int ten = 10;
int a_size=a.get_numero().size();//size of number a
int b_size=b.get_numero().size();//size of number b
res.set_size(max(a_size,b_size)+1);
int rest = 0; //stores the rest when adding over ten
for(int i=0;i<min(a_size,b_size);i++)//part where both numbers have digits
{
res.set_numero((a.get_numero()[i]+(b.get_numero())[i]+rest)%ten,i);//sum of digits,
rest=((a.get_numero())[i]+(b.get_numero())[i]+rest)/ten;// rest is saving suming over 10
}
if(a_size>b_size)//to find which number is greater
for(int i=min(a_size,b_size);i<a_size;i++)//part where one numbers has no digit -> is less
{
//res.get_numero().push_back((a.get_numero()[i]+rest)%10);//set zero at the higher positions of the smallest number
res.set_numero((a.get_numero()[i]+rest)%ten,i);
rest=((a.get_numero())[i]+rest)/ten;
}
else
for(int i=min(a_size,b_size);i<b_size;i++)
{
//res.get_numero().push_back(((b.get_numero())[i]+rest)%10);
res.set_numero(((b.get_numero())[i]+rest)%ten,i);
rest=((b.get_numero())[i]+rest)/ten;
}
if(rest!=0)//if the result has more digit than the greatest partner
{
//res.get_numero().push_back(rest);
res.set_numero(rest,max(a_size,b_size));
}
if((res.numero[(res.numero).size()-1])==0)//reduces zero digit from left if possible
(res.numero).erase((res.numero).end()-1);
return res;
}
ostream& operator<< (ostream& out, const long_number& num)//output of the number
{
for(int i=(num.numero).size()-1;i>=0;i--)
{
out << (num.numero)[i];
}
return out;
}
void long_number::read(string input)
{
//if(this->numero)
this->numero.erase(this->numero.cbegin(),this->numero.cend());
string s;
if(typeid (input)== typeid (string))
string s = input;
else
;
//string s = to_string(input);
for(int i=input.size()-1;i>=0;i--)
(this->numero).push_back(input[i]-'0');
this->size = (this->numero).size();
}
void long_number::get(ostream& out) const
{
for(int i=(this->numero).size()-1;i>=0;i--)
{
out << (this->numero)[i];
}
//out << endl;
}
}
I know that there are faster algorithms to use for sumation but I used the standard digit-by-digit summation but I haven't expected that the difference will be so large. Is the speed really given by the algorithm? What is the maximum speed to achieve in comparing with standard data types? Are in my code any places which could be better optimased to accelerate the code execution? Or could I use any more flags at the compiler command for higher performance?
I am really grateful for every help which let me move forward!!! Frank
Your long_number operator+ can easily be improved by eliminating multiple copies of the vector in get_numero().
You don't really need to make a copy of your vector to then ask for its size. Just provide a size() method for your class.
Similarly, instead of (a.get_numero())[i] (that, again, makes a copy of the entire vector before indexing into it), implement operator [] to directly access individual digits.
1,000 times longer that addition - it's a lot! however, something like 100 times would be expected - just count how many steps you have in place of a simple add instruction