Потестируйте скорость работы класса больших чисел

static const long long BASE = 1000000000;
static const int BASE_DIGITS = 9;
 
enum sign { positive = 1, negative = -1 };
 
struct BigInt {
 
    std::vector<int> a;
    int sign;
 
    // constructors
    BigInt() : sign(positive) { } // default constructor
}

>TestBigInt.exe -factorial 100000
--- factorial test ---
Calculating 100000!
 big integer :  2824 ... 0
 number of decimal digits = 456574
 number of segments       = 50731
 
time : 10.961 sec.

// длинное умножается на целое
BigI* mul(int x) {
    long64 l,l0;
    int i;
 
    // умножаем i-й разряд на n и складываем с i-м разрядом переноса
    l0=0;
    for(i=0;i<n;++i)
    {
        l=(long64)x*m[i]+l0;
    m[i]=(big32)(l%base); // здесь тормоза
    l0=l/base;
    }
    if (l0>0)
        m[n++]=l0;
    return this;
    }

>TestBigInt.exe -mul M33
--- multiplication test ---
Generating the Mersenn prime M33 = (2 ^ 859433) - 1
 
 Ok.
 big integer :  12 ... 500142591
 number of decimal digits = 258716
 number of segments       = 28747
 
 time : 3.151 sec.
 
Multiplying M33 * M33
 big integer :  167 ... 332193281
 number of decimal digits = 517431
 number of segments       = 57493
 
 time : 7.725 sec.

    // всё Ок. Но медленно.  :(
    // naive multiplication. 
    BigInt operator * (const BigInt& x) const {
 
        BigInt res; 
        res.a.resize(a.size()*x.a.size() + 1); // вот тут память отъедает немеряно.
 
        for (long long i = 0; i < a.size(); ++i) {
            long long carry = 0;
            for (long long j = 0; j < x.a.size(); ++j) {
                long long v = (long long)a[i] * x.a[j] + res.a[i + j] + carry;
                carry = v / BASE;
                res.a[i + j] = v % BASE;
            }
            if (carry) res.a[i + x.a.size()] += carry;
        }
        res.trim();
        return res;
    }

>TestBigInt.exe
Usage:
TestBigInt.exe -factorial
TestBigInt.exe -factorial 100000
 
TestBigInt.exe -mul
TestBigInt.exe -mul M23
 
TestBigInt.exe -power
TestBigInt.exe -power M23
 
TestBigInt.exe -sqrt
TestBigInt.exe -sqrt M23
 
TestBigInt.exe -miller_rabin
TestBigInt.exe -miller_rabin M23
 
TestBigInt.exe -lucas_lehmer
TestBigInt.exe -lucas_lehmer M23
 
TestBigInt.exe -fermat
TestBigInt.exe -fermat M23
 
TestBigInt.exe -string
TestBigInt.exe -string M23
 
TestBigInt.exe -candidate 2 12345 -1
 
 where M1 ... M48 are Mersenn number short names.

// префиксный инкремент
const big_integer big_integer::operator++() 
{
    return (*this += 1);
}

const BigInt operator++() 
{
    if (a[0] < BASE_MINUS_1)
       {   a[0]++; 
             return;
        }
      *this += 1
}