mersenneforum.org December 2019
 Register FAQ Search Today's Posts Mark Forums Read

 2020-01-08, 08:23 #45 yae9911     "Hugo" Jul 2019 Germany 31 Posts Since we are not getting a solution from IBM for the time being, we could at least try to find out together what a record solution could have looked like. That would be a little more fun than complaining about the inability of the puzzle team to update their website. I can only assume that IBM's management stopped supporting the puzzle team because the puzzle solvers are not the company's commercial target group. I can only contribute what I found out together with Hermann Jurksch, with whom I work from time to time. We found a solution that had approximately the record MSE. f(x) = c3 + x * (x / (c0 / (c1 - x*x) + c2) + x / (x*x / (d0 / (d1 - x*x) + d2) + d3 )) c0= 1.3555986881256104 c1= -0.51428204774856567 c2= 2.8334267139434814 c3= 4.7942781820893288E-003 d0= 0.33841833472251892 d1= -0.51365238428115845 d2= 0.70969653129577637 d3= 2.6548692956566811E-002 MSE ~= 1.8215E-7. Unfortunately, this solution required one operation too much, so 16. I have not found a trick how I could change this to get rid of the operation. If I omit the constant term c3 and re-fit the coefficients, the deviation will increase approximately to 2 * (record value), which is not bad, but would not have been awarded the "*". Does anyone of you have an idea how to improve it?
 2020-01-08, 08:36 #46 Dieter   Oct 2017 2×5×11 Posts „I can only assume that IBM's management stopped supporting the puzzle team because the puzzle solvers are not the company's commercial target group.“ But the puzzlemaster reacts quickly to wrong solutions. I have submissed such one at 2.1. and he has responded a few hours later — so I was able to correct my code.
2020-01-08, 09:36   #47
axn

Jun 2003

132·29 Posts

Quote:
 Originally Posted by yae9911 I can only assume that IBM's management stopped supporting the puzzle team because the puzzle solvers are not the company's commercial target group.
A much simpler explanation is that the puzzlemasters screwed up while publishing the solution (maybe they published under a typoed url), and the server doesn't know how to reach it. This is evidenced by the fact that someone actually enabled the solution link (which doesn't show up automatically, AFAICT).

2020-01-08, 09:37   #48
axn

Jun 2003

132516 Posts

Quote:
 Originally Posted by Dieter But the puzzlemaster reacts quickly to wrong solutions. I have submissed such one at 2.1. and he has responded a few hours later — so I was able to correct my code.
Can you inform them that the December solution link is dead ? I am sure they will fix it if they are aware of the issue.

2020-01-08, 18:03   #49
Dieter

Oct 2017

1568 Posts

Quote:
 Originally Posted by axn Can you inform them that the December solution link is dead ? I am sure they will fix it if they are aware of the issue.
Yes, I have.

2020-01-08, 22:02   #50
SmartMersenne

Sep 2017

6316 Posts

Quote:
 Originally Posted by axn Can you inform them that the December solution link is dead ? I am sure they will fix it if they are aware of the issue.
I doubt it. I think they (yes I-B-M) is having difficulties updating their website, and can only do it once a month!

 2020-01-08, 22:30 #51 Dr Sardonicus     Feb 2017 Nowhere 25×139 Posts I didn't try to optimize my answer; I merely sought an answer good enough to beat the bound with 15 operators. It occurred to me to formulate the MSE integral for the approximating function f(x) on [-1,1] separately in [-1,0] where |x| = -x, and [0,1] where |x| = x. This leads to an expression of the MSE as an integral from 0 to 1, with integrand (x - e(x))^2 + o(x)^2, where e(x) = (f(x) + f(-x))/2 is the even part of f(x), and o(x) = (f(x) - f(-x))/2 is the odd part of f(x). Thus, if f is neither even nor odd, taking the even part of f makes the MSE smaller. For example, taking the even part 1/2 of the example (1+x)/2, gives an MSE of 1/12. I was able to optimize polynomial approximations. Doing the formal integration of (x - e(x))^2 with e(x) a even polynomial gives a formula which is a quadratic polynomial in the coefficients. Equating the partial derivatives to 0 gives a system of linear equations which can always be solved. Using Pari-GP to bludgeon out "best" even polynomial approximations to x over [0,1] yielded f(x) = 1/2, MSE = 1/12; f(x) = 3/16 + 15/16*x^2, MSE = 1/192, and f(x) = 15/128+105/64*x^2-105/128*x^4, MSE = 1/768. These polynomials aren't good enough approximating functions to get a formula that beats the bound with 15 operators. However, polynomials aren't the only game in town. Another definition of |x| is the (positive) square root of x^2. This suggests using Newton's method to improve a polynomial approximation with a rational function. We refine f(x) to g(x) = (f(x) + x^2/f(x))/2. Trying this with the constant and quadratic polynomials yields rational functions g(x) with MSE values that exceed the given bound of 0.0001. However, the quartic polynomial gives a g(x) with an MSE of approximately 0.0000867, which is less than 0.0001. And g(x) = (0.05859375 + x*x*(0.8203125 - x*x*0.41015625)) + x*x/(0.234375 + x*x*(3.28125 - x*x*1.640625)) [coefficients are exact terminating decimals] uses precisely 15 operators. Problem solved. However, there are better rational-function approximations. Alas, with rational functions, optimizing the coefficients is much more complicated -- the formal integrals can involve inverse tangents and/or logarithms with the coefficients buried inside. I looked up Pade approximants, but didn't pursue them. I also found a result called "Newman's Theorem" which gave a formula for an approximating rational function to |x| which is quite good for large degrees. I worked out some low-degree cases, and did obtain a much better answer than the one I submitted.
 2020-01-08, 22:52 #52 Yusuf   Jan 2020 18 Posts I used the following Mathematica code to attain a MSE of 2.92237E-6 Code: f[x_, a_, b_, c_, d_, m_, v_, g_] := 1/2*(Abs[x]-((x*x*(x*x*(a*x*x+b)+c)+g)/(x*x*(x*x+v)+m)))^2; NMinimize[{NIntegrate[f[x, a, b, c, d, m, v, g], {x, -1, 1}]}, {a, b, c, d, m, v, g}, Method -> {"RandomSearch"}]
 2020-01-11, 06:00 #53 what   Dec 2019 Kansas 100002 Posts Wow! After 11 days a solution still has not been published, and the names haven't been updated Last fiddled with by what on 2020-01-11 at 06:01
2020-01-11, 07:43   #54
Dieter

Oct 2017

11011102 Posts

Quote:
 Originally Posted by what Wow! After 11 days a solution still has not been published, and the names haven't been updated
I have pointed out this to the puzzlemaster : 8.1.2020

Last fiddled with by Dieter on 2020-01-11 at 07:44

 2020-01-12, 03:03 #55 Dieter   Oct 2017 11011102 Posts He has answered. They have indeed technical problems, but they will update. The December solution is deferred to another month — so it is still possible to get a „*“ for December.

 Similar Threads Thread Thread Starter Forum Replies Last Post Xyzzy Puzzles 6 2019-01-06 23:07 Batalov Puzzles 4 2018-01-04 04:33 Xyzzy Puzzles 11 2017-01-24 12:27 Xyzzy Puzzles 15 2016-01-06 10:23 Xyzzy Puzzles 13 2015-01-02 19:41

All times are UTC. The time now is 10:10.

Tue Apr 13 10:10:58 UTC 2021 up 5 days, 4:51, 1 user, load averages: 1.42, 1.29, 1.33