The Museum of HP Calculators

HP Forum Archive 13

[ Return to Index | Top of Index ]

Intergation algorithm
Message #1 Posted by rick cameron on 2 July 2003, 11:54 p.m.

Hi, all

Several years ago I managed to get a copy of an article that described the algorithm used by HP calculators to do numerical integration. I seem to have lost the article.

Does anyone have an explanation of the algorithm?

Thanks

- rick

      
Re: Intergation algorithm
Message #2 Posted by Patrick on 3 July 2003, 1:09 a.m.,
in response to message #1 by rick cameron

The article of which you speak is very likely this one written by William H. Kahan, the numerical analyst who consulted with HP on many of their calculator algorithms.

            
Re: Integration algorithm
Message #3 Posted by rick cameron on 3 July 2003, 1:17 a.m.,
in response to message #2 by Patrick

Thank-you - that's the one!

                  
Re: Integration algorithm
Message #4 Posted by Patrick on 3 July 2003, 4:42 a.m.,
in response to message #3 by rick cameron

As a calculator fan(atic) and ex-mathematician, I would be interested to know what you had in mind for the algorithm? Do you plan on re-implementing it somewhere, or is it just curiousity?

Personally, I would like to get a flowchart or pseudocode for the solve algorithm. I've read Kahan's article on the matter (you can find it in the same place as the integration article) but there is still lots of holes to be filled in.

                        
Re: Integration algorithm
Message #5 Posted by hugh on 3 July 2003, 2:20 p.m.,
in response to message #4 by Patrick

hi there,

recently ive been reviewing a bunch of quadrature algorithms. tooling up for version3 of my palm calculator. my search is along the lines of; what is the best numerical quadrature algorithm given a pocket device with a bit more poke than a normal calculator (poke=50-500Mhz).

candidates: simpsons rule, newton-cotes etc., romberg (open and closed), gauss and spectral techniques like clenshaw-curtis and other FFT accelerated forms.

BTW, does anyone have any code or doc for gauss-kronrod? i know what it is but i dont have enough details to write it (gauss-kronrod is adaptive gauss apparently now used by casio).

my test suite (so far)is: sqrt(x), cos(log(x)), exp(-x)/x, sqrt(fabs(x-1)), exp(-x*x), cos(1/x), sin (x)/x.

the most promising so far is a modified romberg in the way suggested by kahan. i've come up with something that i think might well be very similar to the method used on the 15c. ok, you wont get the same answers, but algorithmically.

as a taunt i implemented it on the 9g, like this:

INPUT A,B,E H=2;D=0;M=0;J=1;B=B-A FOR (K=0;K<9;++K) { L=D;F=H/2-1;C=0 FOR (I=0;I<J;++I) { D=1-FF;X=((F+DF/2)*B+B)/2+A GOSUB PROG 9;C=C+DY;F=F+H;} F=4;D=M;M=(M+HC)/2 FOR (I=0;I<=K;++I) { C=N[I];N[I]=(F*M[I]-D)/(F-1);D=C;F=4F } D=M[I] IF (ABS(D-L) < 16E*ABS(D)) THEN { GOTO 1; } J=2J;H=H/2 } Lbl 1: S=3DB/4;PRINT S END

if you find this too worrying you can read it clearer here, http://www.voidware.com/rombint.htm

                              
Re: Integration algorithm
Message #6 Posted by David Smith on 3 July 2003, 2:46 p.m.,
in response to message #5 by hugh

For some unknown reason, I have always liked Gaussian Quadrature... a hangover from my IBM 1130 days...

                                    
Re: Integration algorithm
Message #7 Posted by hugh on 3 July 2003, 2:51 p.m.,
in response to message #6 by David Smith

i did some work on the basic gauss-legendre so that the method calculated the weights and sample points as it went along. thus avoiding storage.

the idea was to see if this would work on real calculators. the trouble was that you have to loop over `n' samples for each coefficient, so you got n^2/2 performance. it flew on a pc, but as you can imagine, after only small n, poor old calculator was too slow.

      
Re: Intergation algorithm
Message #8 Posted by Ralf Fritzsch on 3 July 2003, 1:09 a.m.,
in response to message #1 by rick cameron

Googling with the title of the article, "Handheld Calculator Evaluates Integrals", reveals a link at one of the original author's Pages (http://www.cs.berkeley.edu/~wkahan/Math128/), namely

http://www.cs.berkeley.edu/~wkahan/Math128/INTGTkey.pdf

Hope that helps, Ralf.

            
Re: Integration algorithm
Message #9 Posted by rick cameron on 3 July 2003, 1:19 a.m.,
in response to message #8 by Ralf Fritzsch

Funny - Google won't find it for me. Thanks for the pointer!


[ Return to Index | Top of Index ]

Go back to the main exhibit hall