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!

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