December 2019 - Page 5

yae9911 · 2020-01-08, 08:23

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?

Dieter · 2020-01-08, 08:36

„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.

axn · 2020-01-08, 09:36

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).

axn · 2020-01-08, 09:37

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.

Dieter · 2020-01-08, 18:03

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.

SmartMersenne · 2020-01-08, 22:02

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!

Dr Sardonicus · 2020-01-08, 22:30

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.

Yusuf · 2020-01-08, 22:52

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"}]

what · 2020-01-11, 06:00

Wow! After 11 days a solution still has not been published, and the names haven't been updated

Dieter · 2020-01-11, 07:43

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

Dieter · 2020-01-12, 03:03

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.

2020-01-11, 06:00	#53
what Dec 2019 Kansas 10000₂ 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

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

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 - xx) + c2) + x / (xx / (d0 / (d1 - xx) + 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 147₈ 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, 22:30	#51
Dr Sardonicus Feb 2017 Nowhere 2×13×167 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/16x^2, MSE = 1/192, and f(x) = 15/128+105/64x^2-105/128x^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 + xx(0.8203125 - xx0.41015625)) + xx/(0.234375 + xx(3.28125 - xx1.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-12, 03:03	#55
Dieter Oct 2017 67₁₆ 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.