> In this case the algorithm’s claim is that you can multiply arbitrarily large numbers faster than n log n where n is the size of the numbers being multiplied. But that result holds only if you don’t include the cost to multiple arbitrarily large complex numbers in that n, which are assumed to be able to multiply in constant time.

Well that's certainly not the claim. Think about it, that would mean the whole thing is trivially O(1), so why would they be bothering with the rest?

You've missed part in the analysis, or I believe added an assumption they're not making (the constant-time-multiply one, specifically).

This all _is_ almost certainly impractical, but it's for the usual reason of it only being faster for numbers nobody could ever care about. It's theoretically _quite_ interesting though, because hey...what _is_ the fastest you can actually multiply numbers if it's not O(n lg n) as many ~assumed.

The complex FFT is a generalization of the n-bit integer multiplication algorithm, not the other way around. No complex-number operations are required for the integer case.