[1] Its time complexity is O(n log n * log log n). The double logarithm is already slowly growing; log log 2^(10^15) ~= 34 for the reference. At this stage the constant is much more important than the time complexity itself. y-cruncher, a record-setting pi computation software, actually has a set of proprietary algorithms [2] optimized for modern hardwares.
[2] http://www.numberworld.org/y-cruncher/internals/multiplicati...
But that was to be cool, not for any practical problem.
They needed 156 TiB of storage to hold that singular number, and that happened to be all-solid state storage ( because the majority of the time was spent on I/O, believe it or not!! )
That is to say: a faster CPU wouldn't really make the computation much faster. You need faster storage when you're dealing with numbers that big.
Double-precision floats are what people need most of the time. Crypto-guys need 2048+ or 4096+ byte numbers or something around those sizes for cryptography purposes. I'm not sure if large numbers are really used anywhere else.
Edit: oh wait, 2^(9^12) is the number of bits. So we are actually talking about numbers of the size 2^(2^(9^12)).
“Too big to be practical” is a serious understatement here.
> Let `n0 := 2^(d^12) >= 2^4096`, and suppose that we wish to multiply integers with n bits. For `n >= n0` we will describe a recursive algorithm that reduces the problem to a collection of multiplication problems of size roughly n^(1/d). We will show that this algorithm achieves `M(n) = O(n log n)`, provided that `d >= 1729`. (p. 33)
2^(1729^12) ~= 10^(2.15 * 10^38). The authors do note the possibility of much lower cutoff:
> In this section we outline a number of such modifications that together reduce the constant to `K = 8 + epsilon`, so that the modified algorithm achieves `M(n) = O(n log n)` for any `d >= 9` (rather than `d >= 1729`). (p. 39)
Here 2^(9^12) has about 85 billion decimal digits. Much smaller, but still too big to be practical.