Intergation algorithm

[rick cameron]

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

[Ralf Fritzsch]

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.

[rick cameron]

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

[Patrick]

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.

[rick cameron]

Thank-you - that's the one!

[Patrick]

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.

[hugh]

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

[David Smith]

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

[hugh]

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.