Suppose the fastest known method to multiply two decimal numbers is an exponential time algorithm. Would it still be beneficial to mathematics having formulas like the following for positive integers?
$$\sum_{i=1}^n i = \frac {n(n + 1)}{2}$$
Asked
Active
Viewed 35 times
0
-
It is always benefical to have such formulas because they are valid for all input and the time/complexity of numerical computation is of subordinated importance. – gammatester Oct 15 '17 at 17:40
-
Even in the applied world, exponential time (in terms of digits) is actually often ok for numerical problems. For a lot of problems a reasonable goal is to get $O(\log(n))$ or even just $O(1)$ digits in $\operatorname{poly}(n)$ time. See e.g. the CS concept of an approximation scheme: https://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme, or look at the bounds given by any sampling-based algorithm like MCMC – Dap Oct 15 '17 at 18:07