C++ (x86_64-specific) - 220000
(easily portable to x86-32, porting to other architectures implies a significant speed loss)
Here's my own micro-implementation of long arithmetic.
The calculation itself takes 10 seconds, and while the output is in easily printable form (see the operator<<
overload), it takes some more time to print it.
#include <vector>
#include <iostream>
#include <stdint.h>
#include <ctime>
typedef uint64_t digit;
typedef std::vector<digit> number;
std::ostream &operator<<(std::ostream &s, const number &x)
{
std::vector<char> o;
size_t size = x.size() * 21;
o.resize(size);
size_t lud = 0;
for(number::const_reverse_iterator i = x.rbegin(), end = x.rend(); i != end; i++)
{
digit carry = 0;
int j;
for(j = 0; j <= lud || carry; j++)
{
digit r = o[j] * (1LL << 32) + carry;
o[j] = r % 10;
carry = r / 10;
}
lud = j;
carry = 0;
for(j = 0; j <= lud || carry; j++)
{
digit r = o[j] * (1LL << 32) + carry;
o[j] = r % 10;
carry = r / 10;
}
lud = j;
carry = *i;
for(j = 0; carry; j++)
{
digit r = o[j] + (carry % 10);
carry /= 10;
carry += r / 10;
o[j] = r % 10;
}
if(j > lud)
lud = j;
}
for(int j = lud; j--;)
s.put(o[j] + '0');
return s;
}
inline digit dmul(digit x, digit y, digit &carry)
{
asm("mulq %2" : "+a"(x), "=d"(carry) : "r"(y));
return x;
}
inline digit dadd(digit x, digit y, digit &carry)
{
asm("movq $0, %1; addq %2, %0; adcq %1, %1" : "+r"(x), "=r"(carry), "+r"(y));
return x;
}
void multiply(number &x, digit y)
{
x.resize(x.size() + 21);
digit carry = 0;
for(number::iterator i = x.begin(), end = x.end(); i != end; i++)
{
digit nc, res = dmul(*i, y, nc);
*i = dadd(res, carry, carry);
carry += nc;
}
size_t sz = x.size();
for(number::const_reverse_iterator i = x.rbegin(), end = x.rend(); i != end; i++)
{
if(*i)
break;
sz--;
}
x.resize(sz);
}
int main()
{
const int r = 220000;
clock_t start = clock();
number n;
n.push_back(1);
for(digit a = 2; a <= r; a++)
multiply(n, a);
std::cout << "Took: " << (clock() - start)/((double)CLOCKS_PER_SEC) << std::endl;
std::cout << n << std::endl;
}