I have a function that evaluates polynomials with integer coefficients. To evaluate at , for example, you do this:
scala> evalPoly(8, List(6, 5, 0, 2)) res0: (Int, Int) = (8, 1070)
For some reason it echoes the input back out to you. Here’s the code you might write:
This should not be surprising.
But I also have a function that un-evaluates polynomials. To un-evaluate , you do this:
scala> unevalPoly(8, 1070) res1: (Int, List[Int]) = (8, List(6, 5, 0, 2))
and it echoes your input and gives you back the coefficients of the polynomial.
Wait, what? I thought you needed points to determine an -degree polynomial.
Here I’ve seemingly done it with just one point. To spoil the surprise a little,
always work. But how does it work even some of the time? How would you go about coding this up?
Having noticed that the input to
unevalPoly is the output of
evalPoly, and vice versa,
one tack we can try is to write
evalPoly backwards. First let me rewrite it slightly:
I’ve just replaced
x * eval(t) + h with a call to this function:
eval as a data flow diagram.
I’ve threaded through
x as a “context” variable because it isn’t an input to
eval per se.
Following the arrows backwards from the outputs to the inputs we can write the following code:
Now this should work as long as we can write
unplustimes, which is possible only when
destroy information. So given
m = n * q + r, when can we recover
r happens to be less than
n, this is just like doing long division —
r are the quotient
and remainder when dividing
This works because for a given positive integer , any integer can be written uniquely as , where and are nonnegative integers and . Since this formulation is unique, it’s easy to reverse the process and recover and .
So what does that mean for
unevalPoly? It will only work if
xis a positive integer, and
- all of the coefficients are nonnegative integers less than
Let’s try it out. This works:
scala> evalPoly(8, List(1, 3)) res0: (Int, Int) = (8, 25) scala> unevalPoly(8, 25) res1: (Int, List[Int]) = (8, List(1, 3))
But this doesn’t, as expected:
scala> evalPoly(2, List(1, 4, 2)) res2: (Int, Int) = (2, 17) scala> unevalPoly(2, 17) res3: (Int, List[Int]) = (2, List(1, 0, 0, 0, 1))
And neither does this:
scala> evalPoly(5, List(1, -2, 1)) res4: (Int, Int) = (5, 16) scala> unevalPoly(5, 16) res5: (Int, List[Int]) = (5, List(1, 3))
This all came to me through a puzzle I heard: Your friend has a secret polynomial, which you know has nonnegative integer coefficients. She challenges you to determine the coefficients of the polynomial, offering to evaluate the polynomial for you on any two numbers you choose.
From the above, you know need to evaluate the polynomial at a number that is larger than all of the coefficients. So all that’s left to the solution is finding some number that satisfies that description.
What’s really going on
You might have noticed that all
unevalPoly(n, m) is doing is converting
m to its representation in base
Here it is converting 42 to base 2:
scala> unevalPoly(2, 42) res6: (Int, List[Int]) = (2,List(0, 1, 0, 1, 0, 1))
And oh, look:
scala> unevalPoly(10, 12345) res7: (Int, List[Int]) = (10, List(5, 4, 3, 2, 1))
This all makes sense now. The polynomial
is what you mean when you write , which is the unique representation of that number in base provided that all of the coefficients are less than . Recovering the coefficients of is the same as writing in base .
So backwards programming is good for something! If this interests you, you should read my last post on backwards sorting algorithms.
blog comments powered by Disqus