Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
@hotpaw2: The number of decimal digits (~mantissa) has nothing to do with the exponent. Doubles can't even represent 10000000000000001.0, which has zero "decimal places".
I never claimed otherwise. What I just told you was the problem I'm trying to solve has nothing to do with rounding. It's a different problem. I don't care to avoid rounding, but I do care to avoid this problem.
The problem I'm trying to solve has nothing to do with rounding though. That's a different issue I'm not trying to solve. The original examples I had were exactly like what you just said, and they worked just fine with direct convolution but got destroyed by FFT.
@OlliNiemitalo: Well the easy way to explain it is that I want the relative error to be low compared to direct $O(n^2)$ convolution. (Any reasonable definition of "low" would work here... the relative error I'm getting with FFT is like $10^{14}$ which isn't low by any definition.)
+1 because it's brilliant and it had never occurred to me that Karatsuba was a convolution algorithm, but it would be nice if you could explain why it should solve this problem. I can easily see it for the 2x2 case, but in the general recursive setting I don't see why it should fix this issue. It would seem plausible to me that it might not even be fixable in general, but I don't know.
Er, this is using the same arithmetic types and operation units isn't it? Clearly it's more accurate. I think the type of noise you're talking about is not the same as the kind I'm talking about. The roots of unity have a magnitude of 1 which means they simply can't represent very small values. This seems not totally related to the question of how noise propagates through the system.
