4 ms·

Just make the expressions into polynomials with variables x_1..x_k for the k different numbers, and see if they agree at (degree + 1) distinct points.

falsedan 9y ago
Could you please show the polynomial forms for these, and an example of your technique? 3*(8*(3/3)) = 24 3+((3*8)-3) = 24
- kwillets 9y ago
  I'm guessing two variables here; I didn't look too closely. x=3, y=8 x*(y*(x/x)) = f(x,y) x+((x*y)-x) = g(x,y) These are pretty obviously both xy, but rather than solve it, find the maximum degree, which is 2, and make a few points: (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.
  - 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 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 ago
        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.
    - kwillets 9y ago
      You are correct. Apologies for misremembering. Looking it up shows (d+1)^n points are needed for multivariate.
  - hyperpallium 9y ago
    The Schwartz-Zippel lemma is a related, also based on roots https://cs.stackexchange.com/questions/33113/is-there-an-efficient-algorithm-for-expression-equivalence https://cs.stackexchange.com/questions/33113/is-there-an-eff...
  - falsedan 9y ago
    Thanks, great explanation!
cousin_it 9y ago
Nice! Maybe rational functions rather than polynomials though, because division is allowed. Anyway, equality of rational functions is reducible to equality of polynomials.
- kwillets 9y ago
  True, I ignored division. I believe this is used in symbolic solvers to prove identities; that's the context where I learned it.

falsedan 9y ago

Could you please show the polynomial forms for these, and an example of your technique? 3*(8*(3/3)) = 24 3+((3*8)-3) = 24

kwillets 9y ago
I'm guessing two variables here; I didn't look too closely. x=3, y=8 x*(y*(x/x)) = f(x,y) x+((x*y)-x) = g(x,y) These are pretty obviously both xy, but rather than solve it, find the maximum degree, which is 2, and make a few points: (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.
- 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 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 ago
      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.
  - kwillets 9y ago
    You are correct. Apologies for misremembering. Looking it up shows (d+1)^n points are needed for multivariate.
- hyperpallium 9y ago
  The Schwartz-Zippel lemma is a related, also based on roots https://cs.stackexchange.com/questions/33113/is-there-an-efficient-algorithm-for-expression-equivalence https://cs.stackexchange.com/questions/33113/is-there-an-eff...
- falsedan 9y ago
  Thanks, great explanation!

cousin_it 9y ago

Nice! Maybe rational functions rather than polynomials though, because division is allowed. Anyway, equality of rational functions is reducible to equality of polynomials.

kwillets 9y ago
True, I ignored division. I believe this is used in symbolic solvers to prove identities; that's the context where I learned it.