Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Recognizing when two arithmetic expressions are essentially the same

blog.plover.com

Post reply on HN
Print view View original

31–39 of 39 posts

Re: Recognizing when two arithmetic expressions are essentially the same

#31

Post by falsedan »

kwillets wrote: post #22
falsedan wrote: post #17

Earlier quoted context omitted.

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

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,…

Thanks, great explanation!

Re: Recognizing when two arithmetic expressions are essentially the same

#32

Post by cousin_it »

im3w1l wrote: post #28
jackameister wrote: post #25

Earlier quoted context omitted.

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.

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-x…

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.

Re: Recognizing when two arithmetic expressions are essentially the same

#36

Post by kwillets »

jackameister wrote: post #25
kwillets wrote: post #22

Earlier quoted context omitted.

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,…

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.

You are correct. Apologies for misremembering. Looking it up shows (d+1)^n points are needed for multivariate.

Re: Recognizing when two arithmetic expressions are essentially the same

#37

Post by zmonx »

coolio222 wrote: post #19
zmonx wrote: post #8

Thank you for sharing! A closely related puzzle was previously discussed at: https://news.ycombinator.com/item?id=14400017 The present puzzle can be seen as a natural continuation of this earlier thread, and the declarative programming language Prolog is again well-suited for this puzzle. For example, we can start with a short Prolog program that exhaustively generates all solutions: numbers_tree([N], leaf(N)). numbe…

You defined rewrite rules that reduce an expression down to a 'normalized' form such that two expression are equivalent if they reduce to the same 'normalized' form. These rules are obvious for simple arithmetic expressions. Is it possible to deduce the normalized form and the rewrite rules from a set axioms automatically (e.g. for relational (like SQL) expression with operands like join, project, filter)?

In the terminology (may I say: terms) of term rewriting, you are looking for a so-called completion procedure. This takes a set of axioms and turns it into a convergent term rewriting system (or not, because it may not terminate!).

If the completion procedure succeeds, you end up with rules that always terminate, and which reduce any given term to its normal form. In the literature, search for Knuth-Bendix and Huet completion procedure, if you are interested. For SQL, it may get quite complex, but still doable, potentially with some extensions of the primary method.

There are all kinds of variations on the general scheme. If you are interested in term rewriting, a solid starting point is Term rewriting and all that by Baader and Nipkow.

Re: Recognizing when two arithmetic expressions are essentially the same

#38

Post by jjaredsimpson »

gordaco wrote: post #15
jjaredsimpson wrote: post #9

Earlier quoted context omitted.

That problem is small enough to just brute force. There are only 1612800 calculations to do.

Of course... but for many people, in Project Euler the goal is not just to get a solution, it's to create a beautiful and/or efficient solution. This is why reading the comments and finding other people's solutions after solving a problem is usually as fulfilling as solving it, or even more.

For sure, only commenting that for that particular problem, brute force is viable. For many problems brute force is not viable.

I was grinding PE a couple years ago to pick up Haskell.

Re: Recognizing when two arithmetic expressions are essentially the same

#39

Post by coolio222 »

zmonx wrote: post #37
coolio222 wrote: post #19

Earlier quoted context omitted.

You defined rewrite rules that reduce an expression down to a 'normalized' form such that two expression are equivalent if they reduce to the same 'normalized' form. These rules are obvious for simple arithmetic expressions. Is it possible to deduce the normalized form and the rewrite rules from a set axioms automatically (e.g. for relational (like SQL) expression with operands like join, project, filter)?

In the terminology (may I say: terms ) of term rewriting, you are looking for a so-called completion procedure. This takes a set of axioms and turns it into a convergent term rewriting system (or not, because it may not terminate!). If the completion procedure succeeds, you end up with rules that always terminate, and which reduce any given term to its normal form. In the literature, search for Knuth-Bendix and Huet…

Thank you very much. I checked Wikipedia for Knuth-Bendix and will try to get hold on the book.
Post reply on HN