11 ms·
But your last sentence is only true among single-variable polynomials, isn't it? For example, f(x,y)=xy and g(x,y)=x^2 agree on infinitely many points.
by jackameister 9y ago
But your last sentence is only true among single-variable polynomials, isn't it? For example, f(x,y)=xy and g(x,y)=x^2 agree on infinitely many points.
- im3w1l 9y agoPick one value for x, now you have a single variable polynomial. Verify that it is equal with above mentioned technique. Pick another value for x, do the same. Pick a third... I didn't prove this works, but I think it should. It is however exponential in the number of variables which may be seen as a downside. Edit: This can be proven by induction. Let V = (y, z, ...). Then the polynomial can be expressed as p = (x-x2)(x-x3)f(V) + (x-x1)(x-3)g(V) + (x-x1)(x-x2)h(V), where x1, x2, x3 are the values we test for x. By inductive hypothesis we can prove each of f, g and h to be zero by testing. But if those are all zero then p is zero.
- cousin_it 9y agoIt seems to me that expanding everything to sum-of-products form and checking for equality directly would be simpler than your algorithm and would run about as fast.
- kwillets 9y agoYou are correct. Apologies for misremembering. Looking it up shows (d+1)^n points are needed for multivariate.