Re:Recognizing when two arithmetic expressions are essential...
by hyperpallium on Wednesday August 23, 2017 @12:49AM
(#15078590)
The Schwartz-Zippel lemma is a related, also based on roots https://cs.stackexchange.com/questions/33113/is-there-an-eff...
Re:Recognizing when two arithmetic expressions are essential...
by jackameister on Wednesday August 23, 2017 @12:47AM
(#15078587)
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.
Re:Recognizing when two arithmetic expressions are essential...
by im3w1l on Wednesday August 23, 2017 @01:36AM
(#15078784)
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.
Re:Recognizing when two arithmetic expressions are essential...
by cousin_it on Wednesday August 23, 2017 @08:14AM
(#15080805)
It 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.
(1,1) => 1(1(1/1)) = 1 = 1+((1*1)-1) (1,0) => 0 for both (1,2) => 2 etc.
It's an old technique; Alan Perlis taught it to me. If two polynomials of degree d agree on more than d points, then their difference (of degree <= d) has more than d roots, so their difference must be 0.