Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
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. –  TMM Dec 31 '12 at 14:56
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?? –  Peter Smith Dec 31 '12 at 20:27
@PeterSmith: I am not sure. But for example, is $f(x)=\sqrt{x}, x \in \mathbb{N}$ recursive and therefore directly evaluable? –  Tim Dec 31 '12 at 20:32
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. –  Peter Smith Dec 31 '12 at 20:35
Thanks, @PeterSmith! It can be both cases in your comment. –  Tim Dec 31 '12 at 21:17

2 Answers 2

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".

share|improve this answer
Thanks, +1! What do you think direct evaluation means? –  Tim Dec 31 '12 at 14:50
As far as I know, function evaluation can be difficult in complexity theory. –  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.


share|improve this answer
Regards! and thanks! +1 –  Tim Dec 31 '12 at 14:55
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. –  TMM Dec 31 '12 at 14:58
@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 –  Amzoti Dec 31 '12 at 15:00
Nice, Amzoti! ++++ Hope the day went well for you!! –  amWhy May 10 '13 at 1:16
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. –  amWhy May 10 '13 at 2:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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