#include <iostream>
#include <vector>
#include <string>

#include <stdio.h>      /* printf */
#include <time.h>       /* clock_t, clock, CLOCKS_PER_SEC */

using namespace std;

//=======================================================================
class BigInt
{
public:
    BigInt() { };

    void print();
    void fromString(const std::string& str);
    void add(BigInt& num);

    size_t getLength() const
    {
        return number.size();
    }

    enum Sign { negative = -1, zero = 0, positive = 1 };
private:
    Sign sign;
    vector<char> number;
};
//=======================================================================
void BigInt::print()
{
    cout<<endl<<"num size="<<number.size()<<endl<<"num=";
    for (int i=number.size()-1; i>=0; i--)
    {
        cout<< (char)(number[i]+'0');
    }
    cout<<endl;
}
//=======================================================================
void BigInt::fromString(const std::string& str)
{
    int str_size= str.size();
    number.reserve(str_size+1);

    for (int i = str_size-1; i>=0; i--)
    {
        number.push_back(str[i]-'0');
    }
}
//=======================================================================
void BigInt::add(BigInt& summand)
{
    vector<char> rez;
    vector<char> *summand1;
    if(number.size() > summand.number.size())
    {
        rez=number;
        summand1=&summand.number;
    }
    else
    {
        rez=summand.number;
        summand1=&number;
    }

    for(size_t i=0, imax=summand1->size()-1; i<=imax; i++)
    {
        rez[i]+=summand1->at(i);

        if(rez[i]>9) //carry?
        {
            rez[i]-=10;

            if(i==imax)
            {
                rez.push_back(1);
            }
            else
            {
                rez[i+1]++;
            }
        }
    }

    number=rez;
}
//=======================================================================
int main()
{
    BigInt n1,n2;
    string num1,num2;

    clock_t t;

    t = clock();

    const size_t NUMBER_OF_DIGITS=10000000;

    num1.reserve(NUMBER_OF_DIGITS*10);
    num2.reserve(NUMBER_OF_DIGITS*10);
    for(size_t i=0; i<NUMBER_OF_DIGITS; i++)
    {
        //num1+="9999999999";
        num1+="1234567123";
        num2+="7654321765";
    }
    t = clock() - t;
    printf ("==================\nConstruct 2 strings \nExec time : %f seconds.\n==================\n",((float)t)/CLOCKS_PER_SEC);

    t = clock();
    n1.fromString(num1);
    n2.fromString(num2);
    t = clock() - t;
    printf ("Construct 2 numbers \nExec time : %f seconds.\n==================\n",((float)t)/CLOCKS_PER_SEC);

    if(n1.getLength()>1000)
    {
        cout<<"n1.size="<<n1.getLength()<<endl;
        cout<<"n2.size="<<n2.getLength()<<endl;
    }
    else
    {
        n1.print();
        n2.print();
    }

    t = clock();
    n1.add(n2);
    t = clock() - t;
    printf ("CPU: A = add(B,C)\nExec time : %f seconds.\n==================\n",((float)t)/CLOCKS_PER_SEC);

    if(n1.getLength()<=1000) n1.print();

    cout<<"add.size="<<n1.getLength()<<endl;

    return 0;
}

#include <iostream>
#include <stdio.h>
#include "gmp.h"
#include <string>
#include <stdio.h>      /* printf */
#include <time.h>       /* clock_t, clock, CLOCKS_PER_SEC */


using namespace std;

int main ()
{
    string num1,num2;

    clock_t t;

    t = clock();

    const size_t NUMBER_OF_DIGITS=1000000;

    num1.reserve(NUMBER_OF_DIGITS*10);
    num2.reserve(NUMBER_OF_DIGITS*10);
    for(size_t i=0; i<NUMBER_OF_DIGITS; i++)
    {
        //num1+="9999999999";
        num1+="1234567123";
        num2+="7654321765";
    }
    t = clock() - t;
    printf ("==================\nConstruct 2 strings \nExec time : %f seconds.\n==================\n",((float)t)/CLOCKS_PER_SEC);
    cout<<"str1 size="<<num1.size()<<endl;
    cout<<"str2 size="<<num2.size()<<endl;


    mpz_t n1, n2, sum;
    mpz_init2 (n1,40*NUMBER_OF_DIGITS);
    mpz_init2 (n2,40*NUMBER_OF_DIGITS);
    mpz_init2 (sum,40*NUMBER_OF_DIGITS);

    t = clock();
    mpz_set_str(n1,num1.c_str(),10);
    mpz_set_str(n2,num2.c_str(),10);
    t = clock() - t;
    printf ("Construct 2 numbers \nExec time : %f seconds.\n==================\n",((float)t)/CLOCKS_PER_SEC);

    t = clock();
    mpz_add(sum,n1,n2);
    t = clock() - t;
    printf ("CPU: A = add(B,C)\nExec time : %f seconds.\n==================\n",((float)t)/CLOCKS_PER_SEC);
    //cout<<"Sum is "; mpz_out_str (stdout, 10, sum); cout<<endl;

    mpz_clear (n1);
    mpz_clear (n2);
    mpz_clear (sum);

    return 0;
}

#include <iostream>
#include <vector>
#include <string>
#include <cstring>

#include <stdio.h>      /* printf */
#include <time.h>       /* clock_t, clock, CLOCKS_PER_SEC */

#include "vectorclass.h" // http://www.agner.org/optimize/vectorclass.zip

using namespace std;

//=======================================================================
class BigInt
{
public:
    BigInt() { };

    void print();
    void fromString(const std::string& str);
    void add(BigInt& num);
    void parallel_add(BigInt& s);

    size_t getLength() const
    {
        return number.size();
    }

    enum Sign { negative = -1, zero = 0, positive = 1 };
private:
    Sign sign;
    vector<char> number;
};
//=======================================================================
void BigInt::print()
{
    cout<<endl<<"num size="<<number.size()<<endl<<"num=";
    for (int i=number.size()-1; i>=0; i--)
    {
        cout<< (char)(number[i]+'0');
    }
    cout<<endl;
}
//=======================================================================
void BigInt::fromString(const std::string& str)
{
    int str_size= str.size();
    if(str_size&15)
    {
        str_size = (str_size&0xfffffff0) + 16;
    }

    number.reserve(str_size+16);
    for (int i = str.size()-1; i>=0; i--)
    {
        number.push_back(str[i]-'0');
    }
}
//=======================================================================
void BigInt::add(BigInt& summand)
{
        //
}
//=======================================================================
void print_vector(vector<char> &v)
{
    for(size_t i=0,imax=v.size();i<imax;i++)
    {
        cout<<(char)(v[i]+'0')<<",";
    }
    cout<<endl;
}
//=======================================================================
char get_our_operator(char x, char y) //см. 3.3 табл.  x y | x &#8855; y
{
    if(y==0) //y==N?
    {
        return 0;
    }
    else if(y==1) //y==C?
    {
        return 1;
    }
    else // y == M
    {
        return x;
    }
}
//=======================================================================
//#define debug_output
void BigInt::parallel_add(BigInt& s)
{
    size_t summand_size=s.number.size();
    if(number.size() < summand_size)
    {
        number.reserve(summand_size+1);
        number.resize(summand_size);
    }

    vector<char> carry;
    vector<char> summand=s.number;

    carry.reserve(number.size()+1);
    carry.resize(number.size()+1);
    summand.reserve(number.size());
    summand.resize(number.size());

    #ifdef debug_output
    cout<<endl<<"== Add =="<<endl;
    print_vector(number);
    print_vector(summand);
    #endif

    //заполняем <c>
    for(size_t i=0,imax=number.size();i<imax;i++)
    {
        char sum=number[i]+summand[i];
        if(sum > 9)
        {
            carry[i]=1; // C
        }
        else if(sum == 9)
        {
            carry[i]=2; // M
        }
        else
        {
            carry[i]=0; // N
        }
    }
    #ifdef debug_output
    print_vector(carry);
    #endif

    // заполняем <prefix scan>, сразу оставляем 0( нет переноса - N или M ) или 1 ( есть перенос - С )
    char total = carry[0];
    carry[0] = total & 1;
    for(size_t i=1,imax=number.size();i<imax;i++)
    {
        total=get_our_operator(total,carry[i]);
        carry[i]= total & 1;
    }
    #ifdef debug_output
    print_vector(carry);
    #endif

    // из <prefix scan> получаем <carries>
    memmove(carry.data()+1,carry.data(),carry.size()-1);
    carry[0]=0;
    #ifdef debug_output
    print_vector(carry);
    #endif

    //сложение
    for(size_t i=0,imax=number.size();i<imax;i++)
    {
        number[i]=(number[i] + summand[i] + carry[i]) % 10;
    }
    if(carry.back()==1)
    {
        number.push_back(1);
    }
    #ifdef debug_output
    print_vector(number);
    #endif
}
//=======================================================================
int main()
{
    BigInt n1,n2;
    string num1,num2;

    clock_t t;

    t = clock();

    const size_t NUMBER_OF_DIGITS=10;

    num1.reserve(NUMBER_OF_DIGITS*10);
    num2.reserve(NUMBER_OF_DIGITS*10);
    for(size_t i=0; i<NUMBER_OF_DIGITS; i++)
    {
        num1+="1234567123";
        num2+="7654321765";
        //num2+="909999999";
    }
    //num1="1";

    t = clock() - t;
    printf ("==================\nConstruct 2 strings \nExec time : %f seconds.\n==================\n",((float)t)/CLOCKS_PER_SEC);

    t = clock();
    n1.fromString(num1);
    n2.fromString(num2);
    t = clock() - t;
    printf ("Construct 2 numbers \nExec time : %f seconds.\n==================\n",((float)t)/CLOCKS_PER_SEC);

    if(n1.getLength()>1000)
    {
        cout<<"n1.size="<<n1.getLength()<<endl;
        cout<<"n2.size="<<n2.getLength()<<endl;
    }
    else
    {
        n1.print();
        n2.print();
    }

    t = clock();
    //n1.add(n2);
    n1.parallel_add(n2);
    t = clock() - t;
    printf ("CPU: A = parallel_add(B,C)\nExec time : %f seconds.\n==================\n",((float)t)/CLOCKS_PER_SEC);

    if(n1.getLength()<=1000) n1.print();

    cout<<"add.size="<<n1.getLength()<<endl;

    return 0;
}