Evaluating a Polynomial


I got this problem from Rustan Leino, who was told it by Prakash Panangaden.

I solved it and wrote up my solution.


There's a polynomial and you have access to a function that evaluates that polynomial at a given number. You don't know the degree of the polynomial, nor do you know any of the coefficients of its terms. However, you're told that all coefficients are non-negative integers. How many times do you need to call the evaluation function to identify the polynomial (that is, to figure out the values of its coefficients)?

Solution     Reveal