alt Hacker NewsIf you're going to preprocess the polynomial, maybe you want to evaluate it at many different points. But then why not use the FFT?
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.