From Wikipedia

computers can directly evaluate polynomials

What precisely does direct evaluation mean? As far as I know, function evaluation can be difficult in complexity theory.

I was wondering if polynomials are the only functions that computers can evaluate directly? Thanks and regards!

  • 1
    $\begingroup$ I suppose "direct evaluation" is just a matter of plugging in the value and using addition/multiplication to get the result. For example, "calculating" $\sqrt{2}$ doesn't work like that. $\endgroup$ – TMM Dec 31 '12 at 14:56
  • $\begingroup$ If a function is recursive, so Turing computable, in what sense would its value not be "directly" evaluable by following the steps in the Turing program?? $\endgroup$ – Peter Smith Dec 31 '12 at 20:27
  • $\begingroup$ @PeterSmith: I am not sure. But for example, is $f(x)=\sqrt{x}, x \in \mathbb{N}$ recursive and therefore directly evaluable? $\endgroup$ – Tim Dec 31 '12 at 20:32
  • 1
    $\begingroup$ Which function? The partial sqrt function from $\mathbb{N}$ to $\mathbb{N}$ is recursive; the totalsqrt function from $\mathbb{R}^+$ to $\mathbb{R}^+$ isn't. $\endgroup$ – Peter Smith Dec 31 '12 at 20:35
  • $\begingroup$ Thanks, @PeterSmith! It can be both cases in your comment. $\endgroup$ – Tim Dec 31 '12 at 21:17

I can think of many functions that are not polynomials which a computer should be able to evaluate directly by any obvious definition of "evaluate directly", such as:

  • $y=|x|$
  • $y=2^x$
  • $y$ is the smallest prime factor of the integer $x$

I am not sure that they have a precise definition of "evaluate directly", but as a first stab, I would suggest something along the lines of "can calculate (by sensible algorithm) the precise value of the function, given the precise value of the argument".

  • $\begingroup$ Thanks, +1! What do you think direct evaluation means? $\endgroup$ – Tim Dec 31 '12 at 14:50
  • $\begingroup$ As far as I know, function evaluation can be difficult in complexity theory. $\endgroup$ – Tim Dec 31 '12 at 14:53

I am guessing that they were referring to such things as Evaluation of Polynomials By Computer by Knuth.

If you look at what this means today, you would look to a vast array of functions that can be approximated using various means of computing.

For example, look at the Mathematica list of functions to be inclusive of what is possible.


  • $\begingroup$ Regards! and thanks! +1 $\endgroup$ – Tim Dec 31 '12 at 14:55
  • $\begingroup$ I don't think all Mathematica functions can be counted as "direct evaluations". You can only get approximations for most of them, while polynomials can be evaluated exactly with no effort. $\endgroup$ – TMM Dec 31 '12 at 14:58
  • $\begingroup$ @TMM, point taken! Even with closed form solutions to functions, the computer has to do an approximation (while not getting into a discussion about CAS approaches). Regards $\endgroup$ – Amzoti Dec 31 '12 at 15:00
  • $\begingroup$ Nice, Amzoti! ++++ Hope the day went well for you!! $\endgroup$ – Namaste May 10 '13 at 1:16
  • $\begingroup$ I'm used to Wisconsin cows grazing in fields! (Maybe by lakes: Wisconsin aka Lakeland, not to be confused with "land'o lakes" which is Minnesota. $\endgroup$ – Namaste May 10 '13 at 2:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.