Comment by throwaway81523
4 hours ago
If you're going to preprocess the polynomial, maybe you want to evaluate it at many different points. But then why not use the FFT?
4 hours ago
If you're going to preprocess the polynomial, maybe you want to evaluate it at many different points. But then why not use the FFT?
FFT multipoint evaluation is great when you know all the evaluation points in advance. However, for many practical applications the input is only streamed to you. E.g. a polynomial hash for a hashmap. Or preprocessing the taylor approximation of exp(x) for a standard library.