Re: [PrimeNumbers] Modular Arithmetic Squaring vs. Multiplication
- --- On Thu, 1/26/12, paulunderwooduk <paulunderwood@...> wrote:
> I am guilty of bandying around the term "selfridge" as aIt depends on what you can re-use.
> measure, first given by Oliver Atkin in:
> My question is about FFT. I remember Chris Nash saying that
> general modular reduction in Primeform costs about 3
> multiplications (or squarings?). What is the time ratio
> between a FFT multiplication and a FFT squaring (before
With D standing for "digits" = size of input:
Raw squaring is FFT + Convolution + IFFT ~= (2*log(D) + 1) * D ~= "2"
Raw multiply is 2*FFT + Convolution + IFFT ~= (3*log(D) + 1) * D ~= "3"
So the simple answer is 3/2.
However, a lot of the time when you're doing multiplies, you're multiplying by the same value, and therefore the FFT of it can be cached.
So multiply also costs 2. Your memory footprint is still a little larger, but that's a "cost of memory access" effect which you've not even started to introduce, so there's no point introducing it now. (In the real world, cost of memory access is not O(1), it's O(f(D)) for some f(D) in omega(1).)