3
$\begingroup$

This question is a reference request. Does anyone know of a reference that lists the asymptotic bit-complexity of algebraic operations and transcendental functions implemented on a Turing machine that includes the leading coefficients? For example: $x^n$, $x^{1/n}$, $e^x$, $\sin x$, $\cos x$, and $|x|$.

I intend to combine the results by Schonhage (print ref 2) with the results by Brent (web ref 1). I will use Brent for everything that is at least as complicated as multiplication, and Schohage for everything simpler than multiplication.

My goal is to make the argument that "one equation is more difficult/complex than the other" based on this information. There is precedent for this in the paper by Borwein and Borwein (print ref 4). They write, "(1) How much work (by various types of computational or approximation measures) is required to evaluate n digits of a given function or number? (2) How do analytic properties of a function relate to the efficacy with which it can be approximated? (3) To what extent are analytically simple numbers or functions also easy to compute?"

Print references I have skimmed/read:

  1. "Elementary Functions: Algorithms and Implementation" Muller, J. 2nd Ed. Birkauser, Boston, 2006
  2. "Fast Algorithms: A Multitape Turing Machine Implementation" Schonhage, A; Grotefeld, A F W; Vetter, E. Wissenschaftsverlag, Mannheim, 1994
  3. "Pi and the AGM : a study in analytic number theory and computational complexity" orwein, J; Borwein, P. John Wiley & Sons, New York, 1987
  4. "On the Complexity of Familiar Functions and Numbers" Borwein, J; Borwein, P. SIAM Review, v30, n4, 1988

I'm currently in the process of requesting Volume 2 of Knuth's "The Art of Computer Programming" through my university library (Chapter 4 is on arithmetic).

Partial list of websites I've read:

  1. Multiple-precision zero-finding methods and the complexity of elementary function evaluation

  2. Algorithmic Complexity of Multiplication

  3. Did the 2019 discovery of O(N log(N)) multiplication have a practical outcome?

  4. What is a plain English explanation of “Big O” notation?

  5. What is O(…) and how do I calculate it?

  6. Is there a system behind the magic of algorithm analysis?

  7. How to come up with the runtime of algorithms?

  8. How to discuss coefficients in big-O notation

  9. Why are we allowed to ignore coefficients in Big-O notation?

  10. Why do we ignore co-efficients in Big O notation?

  11. Should questions on Big-Oh be on-topic here?

  12. Computational complexity of calculating the nth root of a real number

Improve this question
$\endgroup$
2
  • $\begingroup$ How do you get around the linear speedup theorem? My understanding is that this implies trying to determine the leading coefficient of the running time of $k$-tape turing machines is not useful, as you can make it whatever you want by modifying the alphabet. $\endgroup$
    – Mark Schultz-Wu
    Commented Oct 19, 2020 at 20:41
  • $\begingroup$ @Mark - I'm assuming the machine implementing the algorithm is fixed (i.e. fixed alphabet). This way, as long as I am consistent, I can make an apples-to-apples comparison of complexity (or so I think). I am willing to accept a certain level of subjectivity in my comparisons, as long as the bias is consistent across all calculations. Hence my hope that there is a single author/reference listing complexities. $\endgroup$
    – Eric Inclan
    Commented Oct 19, 2020 at 23:14

0

Reset to default

You must log in to answer this question.