Suppose you have two 2n-bit numbers, u and v. Let u0 be the lower n-bit word of u and u1 the upper. So

u=2^n u1 + u0 v=2^n v1 + v0now you can calculate the product uv using only three (not four!) multiplications of n-bit length:

u v = (2^2n + 2^n) u1 v1 + 2^n (u1 - u0) (v0 - v1) + (2^n + 1) u0 v0This can of course be done recursively, so you have an O(n^log2(3)) algorithm (since the multiplication takes time, addition and subtraction don't).

So when using Fourier transforms to multiply arbitrary-precision numbers, when memory runs out you can recurse this until the words fit in the memory. But eventually of course things get slow (compared to the O(n log n) of the Fourier transform) when you multiply very very big numbers (well they will anyway with numbers big enough).

Back to number theoretic transforms.