What functions can computers evaluate directly?

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!

-
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

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

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

Regards

-
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
show 1 more comment