A Different Type of Polynomial Interpolation

Write $f(x)$ in the form

$f(x) = \sum_{i=0}^{n} a_{i}x^{i}$

First, ask for $f(1)$ . Say that $f(1) = k$ . It follows that the sum of these coefficients $a_{i}$ must be equal to $k$ , and since they are all non-negative, no one of these coefficients will exceed $k$ . Hence, $a_{i} \leq k$ for all $i = 0, 1, \ldots, n$

Now, let $z$ be the smallest positive integer such that $10^{z}>k$ , and ask for $f(10^{z})$ Then the coefficients of $f(x)$ are exactly what you get by dividing $f(10^{z})$ up into strings of length $z$ starting from the right. This is enough then to determine $f(x)$ exactly.

---

As an explicit example, consider $f(x) = 17x^{6}+3x^{4}+47x^{3}+11x^{2}+x+9$ . We have that $f(1) = 88$ . We then know that none of the coefficients exceed $100$ , and so each coefficient contains at most two digits. Then, we ask for $f(100) = 17000347110109$ . Splitting this up into blocks of two from the right gets us the following:

$09, 01, 11, 47, 03, 00, 17$

And so the coefficients of $f(x)$ are then

$a_{0} = 9, a_{1} = 1, a_{2} = 11, a_{3} = 47, a_{4} = 3, a_{5} = 0, a_{6} = 17$

And we then reconstruct $f(x) = 17x^{6}+3x^{4}+47x^{3}+11x^{2}+x+9$

---

For a more in-depth explanation as to why this works, it comes down to when we said that $f(x)$ contained non-negative integer coefficients. This is what allowed us to say that if $f(1) = k$ , then $a_{i} \leq k$ for each $a_{i}$ .

Going through the rest of the process a bit more carefully, note that if $z$ is the least positive integer such that $10^{z} > k$ , then $k$ contains $z$ digits in its decimal representation. Since $a_{i} < k$ , it follows that each $a_{i}$ has at most $z$ digits in their respective decimal representations.

The other important thing is that when we asked for $f(10^{z})$ , we got that

$f(10^{z}) = \sum_{i=0}^{n} a_{i}10^{zi} = a_{0} + \sum_{i=1}^{n} a_{i}10^{zi} = a_{0} + 10^{z}\left[ \sum_{i=1}^{n} a_{i}10^{z(i-1)}\right]$

Now, the sum in the rightmost equality will evaluate to an integer, and so after multiplying by $10^{z}$ , we get that there are at least $z$ trailing zeroes at the end of the sum. Now, $a_{0} \leq 10^{z}$ , and thus the last $z$ digits of $f(10^{z})$ must be exactly $a_{0}$ . We then continue this process to get the remaining coefficients.