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

 2019-12-04, 19:48 #1 yae9911     "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 on-line 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.
2019-12-04, 20:32   #2
uau

Jan 2017

10101112 Posts

Quote:
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
But 1/6 does not equal 0.125?

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 non-rational constants...)

2019-12-04, 20:44   #3
bsquared

"Ben"
Feb 2007

3,371 Posts

Quote:
 Originally Posted by uau 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 But 1/6 does not equal 0.125?
I was struggling with the same thing. I'm hoping it is a typo in the provided example.

2019-12-04, 21:05   #4
SmartMersenne

Sep 2017

2×72 Posts

Quote:
 Originally Posted by bsquared I was struggling with the same thing. I'm hoping it is a typo in the provided example.
They started to update the site once a month. So, good luck...

 2019-12-04, 21:24 #5 yae9911     "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.
 2019-12-05, 21:29 #6 what   Dec 2019 Kansas 24 Posts So whats the proper way to calculate the error then?
 2019-12-06, 03:22 #7 LaurV Romulan Interpreter     Jun 2011 Thailand 243B16 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 2019-12-06 at 03:23
 2019-12-06, 05:45 #8 yae9911     "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.
 2019-12-06, 06:44 #9 LaurV Romulan Interpreter     Jun 2011 Thailand 243B16 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 2019-12-06 at 06:46
2019-12-06, 07:17   #10
axn

Jun 2003

113738 Posts

Quote:
 Originally Posted by LaurV 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.
You have to sum all the error squares (which is the integral) and take the average to get the mean, by dividing it by the length of the interval (1 - -1 = 2).

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

 2019-12-06, 10:14 #11 LaurV Romulan Interpreter     Jun 2011 Thailand 927510 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...

 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 11:19.

Sat Mar 6 11:19:33 UTC 2021 up 93 days, 7:30, 0 users, load averages: 0.85, 1.33, 1.42