Timeline for Interpolating for particular coefficients
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 24, 2011 at 1:24 | comment | added | Turbo | When you calculate $F(X)$ you will have to raise $X$ to power $N$ at some point which will make the words $O(N)$ size. (size is number of bits) | |
| May 23, 2011 at 23:40 | comment | added | Igor Rivin | No, the number of bits depends on $m$ (in @Pietro's notation), not on $N.$ | |
| May 23, 2011 at 22:31 | comment | added | Turbo | But still $F(X)X^{−N}$ is $O(n^{1+\epsilon})$ bits isn't it? | |
| May 23, 2011 at 20:28 | comment | added | Pietro Majer | Precisely: if we know that $|a_k|\leq m$ for $0\leq k < N$, then $| a_N - F(X)X ^ {-N} | < 1/2$ for $X=2m+1$ so $a_N$ is the closest integer to $F(X)X ^ {-N}$. | |
| May 23, 2011 at 19:40 | comment | added | Turbo | I think you may be right. But is there some kind of proof that shows one canot do better than $O(n)$. | |
| May 23, 2011 at 18:53 | history | answered | Igor Rivin | CC BY-SA 3.0 |