5
$\begingroup$

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
    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.2012-12-31
  • 0
    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??2012-12-31
  • 0
    @PeterSmith: I am not sure. But for example, is $f(x)=\sqrt{x}, x \in \mathbb{N}$ recursive and therefore directly evaluable?2012-12-31
  • 1
    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.2012-12-31
  • 0
    Thanks, @PeterSmith! It can be both cases in your comment.2012-12-31

2 Answers 2

4

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

  • 0
    Thanks, +1! What do you think direct evaluation means?2012-12-31
  • 0
    As far as I know, [function evaluation](http://en.wikipedia.org/wiki/Function_problem) can be difficult in complexity theory.2012-12-31
3

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

  • 0
    Regards! and thanks! +12012-12-31
  • 0
    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.2012-12-31
  • 0
    @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). Regards2012-12-31
  • 0
    Nice, Amzoti! ++++ Hope the day went well for you!!2013-05-10
  • 0
    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.2013-05-10
  • 0
    I have been to Minnesota,Iowa and Ohio, but never Wisconsin. Maybe this is where the cheeseheads are, but Cali leads in cheese. Also, you have a very good football team. Your state and the people are probably very nice too!2013-05-10