The Museum of HP Calculators

HP Forum Archive 13

 Intergation algorithmMessage #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 algorithmMessage #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 algorithmMessage #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 algorithmMessage #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 algorithmMessage #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

 Re: Integration algorithmMessage #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 algorithmMessage #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 algorithmMessage #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 algorithmMessage #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!

Go back to the main exhibit hall