Minimax Polynomial Fit - Printable Version +- HP Forums (https://archived.hpcalc.org/museumforum) +-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html) +--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html) +--- Thread: Minimax Polynomial Fit (/thread-79477.html) |
Minimax Polynomial Fit - Valentin Albillo - 10-10-2005 Hi all,
Busy as always, just a quick post to let you know that a new article HP-71B Minimax Polynomial Fit
This is a 12-page article including two programs, namely a 3-liner to compute the
The user can specify the degree of the polynomial or else specify instead a maximum
For example, when asked to automatically produce the minimax polynomial of lowest P(x) = A0 + A1*x + A2*x^2 + ... + A5*x^5with A0 = 3.73459956Once computed, we can use the automatic scan option to check the [1,2] interval at 0.01 steps to confirm that it has absolute maximum error app. 0.00003812 (<0.00005) at x=1.06 >FNE(1, 2, 0.01)
and can evaluate it for any argument, say Ln(Pi), like this: >FIX 5 @ FNF(LN(PI))while the correct value is GAMMA(LN(PI)) -> 0.93480i.e., we sure got 4 correct decimal places, more nearly five. Any and all comments are very welcome.
Best regards from V.
Re: Minimax Polynomial Fit - Gerson W. Barbosa - 10-10-2005 Quote: Hello Valentin,
Thanks for letting us know of your new article. Just one question: Best regards,
Gerson.
Re: Minimax Polynomial Fit - Valentin Albillo - 10-11-2005 Hi, Gerson: Gerson posted:
"Can the user also specify polynomials with odd or even powers only? This would be particularly First of all, thanks for your interest in my article. As for your question, there's no need of a separate option to achieve that effect. You just simply specify an interval where it shows that the function is odd or even, and the minimax error condition itself will guarantee that only odd or even powers are used. For instance, let's say that you want to fit a minimax polynomial of lowest possible degree to y=sin(x) for values of x not exceeding Pi/2 and using just odd powers of x (as sin(-x) = -sin(x), so sin(x) is an odd function). Also, you want a guaranteed maximum error <= 1E-6.
As I've stated, you only need to specify an interval where the 'oddness' of the functions shows, in this case [-Pi/2, Pi/2] will
- 0.00018365 * x7 with guaranteed absolute maximum error less than 1E-6 in [-Pi/2, Pi/2]. As you can see, only odd powers of x were returned, all the remaining coefficients being zero within machine rounding limits so our minimax approximation only requires four non-zero coefficients.
Here's a short table of sin(x) vs. P(x): >FIX 7 @ FOR X=-PI/2 TO PI/2 STEP PI/20 @ DISP X,SIN(X),FNF(X),RES-SIN(X) @ NEXT X and, as you can see, the absolute error never exceeds 0.0000006 < 1E-6, so the results are accurate to six decimal places plus or minus 1 ulp. This exact same approach, but specifying the [-Pi/6, Pi/6] interval instead, yields a 7th-degree, odd-powers-only, minimax polynomial which has a guaranteed absolute maximum error e = 3.2E-11 in that interval, while using only four coefficients. Combined with range reduction, this could form the basis of a simple yet very accurate implementation of trigonometric functions in machines lacking them, as you know. Similar approaches would allow implementing most any specialized function, say Gamma(x), Lambert's W(x), etc.
Best regards from V. Edited: 11 Oct 2005, 5:55 a.m.
Re: Minimax Polynomial Fit - Gerson W. Barbosa - 10-11-2005 Quote: Hi Valentin, Thanks for your detailed and comprehensive reply. However, I still have another question, if you don't mind: is it possible to force the first coefficient to 1 and then recalculate the other coefficients? Just rounding the first coefficient to 1 would cause the accuracy to decrease, as we can see in the table below:
P(x) = x - 0.16664831 * x3 + 0.00830636 * x5 - 0.00018365 * x7
X SIN(X) P(X) ERROR
Of course the new polynomial with recalculated coefficients wouldn't be as accurate as the original one, but would be better than this. Best regards,
Gerson.
Impressive! [Re: Minimax Polynomial Fit] - Karl Schneider - 10-11-2005 Valentin -- Looks like an impressive effort! However, I'll have to delve into my HP-71B manuals in order to try out your work. I saw no mention of this program needing a Math ROM, but I have one with the manual. Now all I need is a HP-71B Surveying Pac manual to go with the ROM...
-- KS
Re: Minimax Polynomial Fit - Valentin Albillo - 10-13-2005 Hi again, Gerson:
Gerson wrote:
Yes, there are two ways of doing it:
To save you the trouble of reading it, basically you transform the problem of finding a 7th-degree minimax polynomial for y=sin(x) in [0, Pi/4], say, for the related problem of finding a 2nd-degree polynomial for y=f(x) in [0, (Pi/4)^2], where f(x) is defined thus: f(x) = sin(sqrt(x))/x^(3/2)-1/xthis way you get a polynomial which directly translates to your desired special-form one for the original y=sin(x) function in the original [0, Pi/4] interval.
You can achieve that with my program by simply selecting [D]efined function, then answering the "f(x)=" prompt like this: f(x) = SIN(SQR(X))/(X*SQR(X))-1/Xand specifying the [0, (Pi/4)^2] interval, as stated. You'll get the results you want.
Note:As f(x) is defined, it would generate an error when evaluated at x=0. You can either specify the interval using a small number (1E-6, say) instead of 0, or else include a user-defined function, like this: Best regards from V.
Edited: 13 Oct 2005, 6:37 a.m.
Re: Impressive! [Re: Minimax Polynomial Fit] - Valentin Albillo - 10-13-2005 Hi, Karl: Karl posted: "I saw no mention of this program needing a Math ROM, but I have one with the manual." Thanks for your continued interest in my humble productions. Yes, I didn't mention that a Math ROM is needed, but of course it is. If you've followed my posts since long, you'll know that when I write "HP-71B" it goes without saying that it includes a Math ROM, because if not, it is *not* the real HP-71B originally designed by its wise creators, but the maimed thingy they were forced to release when it was clear the System ROMs were going to exceed the allotted 64 Kb of ROM space. The original HP-71B did include most functionality now present in the Math ROM, including complex numbers definition and functionality, of which some scraps still remain in a bare-bones HP-71B (try to enter the program line: 10 A=(2,3)+SIN((4,5)) and see it being duly accepted, no syntax complaints), and so for me an HP-71B deserves that name if and only if it includes a Math ROM. Else, you should change its name, perhaps "HP-71BL" for "Light" will do, though "HP-71BM" would be better, or even "HP-71BFU" ... ;-) BTW, don't miss my upcoming S&SCM #11, due today ! :-)
Best regards from V.
Re: Minimax Polynomial Fit - Gerson W. Barbosa - 10-16-2005 Hi Valentin,
Thanks for your step by step explanations, they've really helped me. And thanks for reminding me to read my own reference too :-) Using the procedure you showed me, I found the odd power coefficients for a 13th degree polynomial to approximate ATAN (of course, the coefficient indeces refer to the auxiliary 5th degree polynomial):
8 DEF FNY(Y) @ IF X=0 THEN FNY=-1/3 ELSE FNY=ATAN(SQR(X))/(X*SQR(X))-1/XJust for a comparison, here are the same coefficients calculated by an expensive mathematical software, using the tecnique shown in the reference: a0=-0.3333333328040560 The slight difference observed is due, of course, to different machine precisions. Anyway, the maximum absolute errors are 5E-10 and 7E-11, respectively. A remarkable achievement for both programmer and HP-71B! You program is a joy to use, I wish I only had a real 71B! Best regards, Gerson.
P.S.: Below are my approximations to ATAN and SIN. Maximum errors --------------------------------------------------------------------- Re: Minimax Polynomial Fit - Valentin Albillo - 10-17-2005 Hi, Gerson:
Gerson posted:
Also, it's a real testimony to HP-71B/Math capabilities that this kind of functionality, which usually requires advanced software to accomplish, can be implemented in a mere 50 lines of code, and moreover, providing three different input methods (including mass And it's minimaxing, no less ! :-) Best regards from V.
|