21–30 of 61 posts
My impression is that this sort of method isn't used by computer algebra system for this reason.
Sure, the naive method of multiplying polynomials is slow in the degree of the polynomial. But when does one have to deal with two degree 100 polynomials? My impression is that this sort of method isn't used by computer algebra system for this reason.
> In other words, performing the convolution of two signals in time domain is equivalent to multiplying them in the frequency domain.
Great article, as it breaks down a complex idea into much smaller steps that even my math challenged mind can somehow grasp, but did I miss a step? Or is it left as an exercise to the reader to look up? I was already stretching my math ability to that point, but it felt a little bit like - “and then, draw the rest of the F-ing owl” to me. Is it just me?
Great writing otherwise.
Earlier quoted context omitted.
Would you mind just sharing it here...?
Short answer is that FFTs are about as well behaved as anything can possibly be, because they're rotations in C^n. Explicit bound is in https://www.daemonology.net/papers/fft.pdf
Sure, the naive method of multiplying polynomials is slow in the degree of the polynomial. But when does one have to deal with two degree 100 polynomials? My impression is that this sort of method isn't used by computer algebra system for this reason.
Earlier quoted context omitted.
Short answer is that FFTs are about as well behaved as anything can possibly be, because they're rotations in C^n. Explicit bound is in https://www.daemonology.net/papers/fft.pdf
This is why I keep coming back to HN. You read an interesting article, a little proud you understand half of it, read a question that already makes you feel like the stupidest person in the room, then read a clarifying answer by someone who probably got a Knuth reward check for correcting an errata in the art of computer programming.
Sure, the naive method of multiplying polynomials is slow in the degree of the polynomial. But when does one have to deal with two degree 100 polynomials? My impression is that this sort of method isn't used by computer algebra system for this reason.
Earlier quoted context omitted.
This is why I keep coming back to HN. You read an interesting article, a little proud you understand half of it, read a question that already makes you feel like the stupidest person in the room, then read a clarifying answer by someone who probably got a Knuth reward check for correcting an errata in the art of computer programming.
Knuth judged that it wasn't an erratum, since the bound he included was correct and he never claimed it was optimal. :-/
Earlier quoted context omitted.
But if the coefficients are integers, you can use NTT with a big enough modulus and get exact results and a boost (esp. in hardware) in multiplication time.
Is there a way to find groups with easy generators/primitive roots? I imagine you'd want a small root of unity, but also be able to choose a bigger modulus for extra big multiplications. Also, afaik it's discrete-logarithm level of difficulty to even find a generator if you choose a random modulus, though I don't know if it's easier to find a modulus after you choose the generator.
Sure, pick a large prime. Double it and add 1 (and call it n). If it's still prime, then you know the prime factorization of n-1. Pick your generator, and check if it raised to the p is 1, or if squaring it is one. If not, it's a generator of the multiplicative group mod n.