20191204, 19:48  #1 
"Hugo"
Jul 2019
Germany
31 Posts 
December 2019
I'm not here long enough to know whether usually only the same user may open the discussion on the new Ponder This Challenge. The new task is already available online at this link:
Approximation of x in [1,1] using not more than 15 operations of {+,,*,/} This time, this is actually a routine approximation task that can be solved with known methods. I also think I know how to do that. 
20191204, 20:32  #2 
Jan 2017
1010110_{2} Posts 
Did I misunderstand something about the challenge/example? I thought the error would be calculated as half (due to interval length 2) of:
Code:
sage: integral( (abs(x)  (x+1)/2)^2, (x, 1, 1)) 1/3 Also, not completely clear whether the literals in the expression can be integers or rationals/reals (probably no difference between the latter two, unless you have some expression that achieves exactly 0.0001 with optimal nonrational constants...) 
20191204, 20:44  #3 
"Ben"
Feb 2007
6441_{8} Posts 
I was struggling with the same thing. I'm hoping it is a typo in the provided example.

20191204, 21:05  #4 
Sep 2017
134_{8} Posts 

20191204, 21:24  #5 
"Hugo"
Jul 2019
Germany
31 Posts 
I have noticed the same "problem" for the MSE of the example function, but I forgot to mention this concern in my submission to the challenge team. If the team continues this new tradition of never updating the web page, reporting bugs is useless anyway.
The problem itself is famous in approximation theory, and one classical publication about it appeared more than 100 years ago, in 1913. 
20191205, 21:29  #6 
Dec 2019
Kansas
10_{16} Posts 
So whats the proper way to calculate the error then?

20191206, 03:22  #7 
Romulan Interpreter
Jun 2011
Thailand
3^{4}·113 Posts 
Maybe they used pari
Code:
gp > intnum(x=1,0,x)+intnum(x=0,1,x) %1 = 1.0000000000000000000000000000000000000 gp > intnum(x=1,1,abs(x)) %2 = 0.99933543872387558196994670871164968171 gp > Last fiddled with by LaurV on 20191206 at 03:23 
20191206, 05:45  #8 
"Hugo"
Jul 2019
Germany
31 Posts 
The behavior of PARI's intnum is not unexpected, because of the discontinuity of derivative of abs(x) at zero. _num_ means numerical integration and unless the method automatically splits the interval, it will try to approximate the integrand by smooth functions or some other approximation. If you help intnum by splitting the interval, everything works fine:
(intnum(x=1,0,(abs(x)  (x+1)/2)^2) + intnum(x=0,1,(abs(x)  (x+1)/2)^2) ) / 2 gives result 0.166666666666666666666666666666666666666666... PARI can do formal integration for certain integrands intformal((x  (x+1)/2)^2) = 1/12*x^3  1/4*x^2 + 1/4*x intformal((x  (x+1)/2)^2) = 3/4*x^3 + 3/4*x^2 + 1/4*x Just plug in the integration limits and you get the same result  hopefully identical to the one obtained by pencil and paper. Summary: PARI's intnum is perfectly suitable to determine if a solution is meeting the > 0.0001 criterion. 
20191206, 06:44  #9 
Romulan Interpreter
Jun 2011
Thailand
3^{4}×113 Posts 
Yeah, that is what I was doing, if you look careful... the post was a joke (and you do not need abs in expansion,you can directly use x and x, or multiply the intervals with 1 and use two integrals on 0 to 1). However I do not understand this part about final division by 2, that you, uau, and b2 are talking about. Why should you divide the interval? The mean is for ALL the domain, not only for pieces of domain. That is the reason of it, if your interval is longer, your approximation should be for all the interval, not per unit of interval. Otherwise the MSE makes no sense. In this light, their example has a MSE of 0.33333, that's it. They have a typo either in the value or in the function chosen, or used a wrong tool to calculate it. Which is also confirmed by excel (except that the excel shows the "fitness" function of the trendlines, R^2, which is the complementary of MSE, it shows how well the two graphics fit together)
By the way, is this a puzzle, or what? A polynomial approximation is ensured by Weierstrass theorem and for the 4th degree you have exactly 14 operations to write the full polynomial. Put it in excel, make a graphic, add a polynomial trendline of degree 4 or 6, and you are 0.00013 far away, the rest may be just a bit of optimization... Last fiddled with by LaurV on 20191206 at 06:46 
20191206, 07:17  #10  
Jun 2003
12EA_{16} Posts 
Quote:
Here is a simulation to convince you: Code:
myrand()=(random(2^64)2^63)/2.^63; \\ random real number in the range 1..1 sum(n=1, 10^4, r=myrand(); e=abs(r)(r+1)/2; e^2)/10^4 

20191206, 10:14  #11 
Romulan Interpreter
Jun 2011
Thailand
3^{4}×113 Posts 
Well, you are right, and I was a bit stupid, haha... Of course, if you have 61 values, you add them and divide the result by 61. If you have 89, you add them and divide the result by 89. If you have M82589933 values, you add them and divide the result by M82589933. When you integrate, that is how those little rectangles work... Grrr...
However, we solved this puzzle already, after half hour of playing with MS Excel, with a much smaller epsilon than the required one. It is quite simple, if you consider two things, starting from the mentioned theorem, you need to find the largest degree polynomial that you can write down with 15 operations (no powering, you must write x^n as x*x*x... n times, hehe) and then one of the two things that you have to consider is the fact that the function is symmetric in x therefore you can double the degree of the polynomial, and yet use the same amount of operations, and the second one, you will find by yourself... hehe... 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
December 2018  Xyzzy  Puzzles  6  20190106 23:07 
December 2017  Batalov  Puzzles  4  20180104 04:33 
December 2016  Xyzzy  Puzzles  11  20170124 12:27 
December 2015  Xyzzy  Puzzles  15  20160106 10:23 
December 2014  Xyzzy  Puzzles  13  20150102 19:41 