2 ms·
Pick 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.
by im3w1l 9y ago
Pick 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.