Timeline for Process quicker than Fourier for squares of polynomials
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 25, 2019 at 7:06 | history | became hot network question | |||
| Aug 25, 2019 at 7:01 | vote | accept | WiccanKarnak | ||
| Aug 25, 2019 at 6:59 | answer | added | Gerhard Paseman | timeline score: 5 | |
| Aug 25, 2019 at 6:39 | history | edited | WiccanKarnak | CC BY-SA 4.0 |
Made the question even more concise
|
| Aug 25, 2019 at 6:37 | comment | added | WiccanKarnak | @The_Sympathizer yes, adding that would help a lot, as I mentioned in the question | |
| Aug 25, 2019 at 6:36 | comment | added | WiccanKarnak | @GerhardPaseman can you please post it as an answer? It's exactly what I am looking for, thanks so much. | |
| Aug 25, 2019 at 0:24 | comment | added | Gerry Myerson | @The, could be, or it could be that OP was unaware of how close FFT is to best possible. I was just trying to figure out which. | |
| Aug 25, 2019 at 0:10 | comment | added | The_Sympathizer | @Gerry Myerson: I suspect sie's wondering if that $O(n \log n)$ is provably optimal, or there is something between $O(n)$ and $O(n \log n)$ (e.g. $O(n \log \log n)$ or similar). That is, is there a proven optimal bound, and if so, what is it? | |
| Aug 24, 2019 at 23:59 | comment | added | Gerry Myerson | How much faster than $O(n\log n)$ are you hoping for? Just entering the data is already $O(n)$. | |
| Aug 24, 2019 at 23:17 | answer | added | kodlu | timeline score: 5 | |
| Aug 24, 2019 at 23:07 | comment | added | Gerhard Paseman | 4AB = (A+B)^2 - (A-B)^2. Gerhard "Don't Use This On Matrices" Paseman, 2019.08.24. | |
| Aug 24, 2019 at 23:04 | comment | added | kodlu | Is your question regarding finite fields or the complex field? | |
| Aug 24, 2019 at 22:54 | comment | added | Joseph O'Rourke | There is work on "Computing squares in GF($2n$)." King, Brian. | |
| Aug 24, 2019 at 22:41 | comment | added | WiccanKarnak | @GerhardPaseman can you prove so? (or if you already did that above, can you write it with big O notations/ give some upper limit that can't be crossed?) | |
| Aug 24, 2019 at 22:38 | comment | added | Gerhard Paseman | (Assuming a commutative multiplication and cheap addition and subtraction) since arbitrary multiplication can be formed as a difference of squares, there should not be anything much faster (asympototically) than a general algorithm. If you have a specific domain or certain fixed parameters, there may be tweaks to the code that can help. Gerhard "What Size Is Your Problem?" Paseman, 2019.08.24. | |
| Aug 24, 2019 at 21:45 | review | First posts | |||
| Aug 24, 2019 at 22:37 | |||||
| Aug 24, 2019 at 21:40 | history | asked | WiccanKarnak | CC BY-SA 4.0 |