mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2020-01-08, 08:23   #45
yae9911
 
yae9911's Avatar
 
"Hugo"
Jul 2019
Germany

378 Posts
Default

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?
yae9911 is offline   Reply With Quote
Old 2020-01-08, 08:36   #46
Dieter
 
Oct 2017

6216 Posts
Default

„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.
Dieter is offline   Reply With Quote
Old 2020-01-08, 09:36   #47
axn
 
axn's Avatar
 
Jun 2003

2×5×479 Posts
Default

Quote:
Originally Posted by yae9911 View Post
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).
axn is offline   Reply With Quote
Old 2020-01-08, 09:37   #48
axn
 
axn's Avatar
 
Jun 2003

479010 Posts
Default

Quote:
Originally Posted by Dieter View Post
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.
axn is offline   Reply With Quote
Old 2020-01-08, 18:03   #49
Dieter
 
Oct 2017

6216 Posts
Default

Quote:
Originally Posted by axn View Post
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.
Dieter is offline   Reply With Quote
Old 2020-01-08, 22:02   #50
SmartMersenne
 
Sep 2017

2×43 Posts
Default

Quote:
Originally Posted by axn View Post
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!
SmartMersenne is online now   Reply With Quote
Old 2020-01-08, 22:30   #51
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

F2B16 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2020-01-08, 22:52   #52
Yusuf
 
Jan 2020

1 Posts
Default

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"}]
Yusuf is offline   Reply With Quote
Old 2020-01-11, 06:00   #53
what
 
Dec 2019
Kansas

24 Posts
Default

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
what is offline   Reply With Quote
Old 2020-01-11, 07:43   #54
Dieter
 
Oct 2017

2·72 Posts
Default

Quote:
Originally Posted by what View Post
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
Dieter is offline   Reply With Quote
Old 2020-01-12, 03:03   #55
Dieter
 
Oct 2017

11000102 Posts
Default

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.
Dieter is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 07:13.

Wed Dec 2 07:13:22 UTC 2020 up 83 days, 4:24, 1 user, load averages: 1.39, 1.55, 1.52

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.