+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: HP Prime (/forum-5.html)
+--- Thread: A recursive GCD in CAS (/thread-765.html)
A recursive GCD in CAS - massimo - 02-25-2014 03:19 AM
CAS is a sort of functional language like LISP or F#. Functional languages often uses recursion in place of loops. Combining recursive and piecewise functions give us all the necessary tools to write powerful "CAS programs" without using HP-PPL.
To test these concepts I wrote a GCD function:
\[
mgcdr(z,w):=z-w*IP(z/w)
\]
\[
mgcdi(z,w) :=
\begin{cases}
{w \ \mbox{if} \ mgcdr(z,w)=0}
\\
{mgcdi(w,mgcdr(z,w)) \ \mbox{if} \ mgcdr(z,w) \neq 0}
\end{cases}
\]
\[
mgcd(a,b):=mgcdi(MAX(|a|,|b|),MIN(|a|,|b|))
\]
Or in HP Prime syntax:
Code:
mgcdr(z,w):=z-w*IP((z/w))
mgcdi(z,w):=PIECEWISE((mgcdr(z,w)) = 0,w,(mgcdr(z,w))≠0,mgcdi(w,mgcdr(z,w)))
mgcd(a,b):=mgcdi(MAX(ABS(a),ABS(b)),MIN(ABS(a),ABS(b)))Note that combining functions is often convenient.
Sure it is less efficient than an HP-PPL equivalent program:
Code:
EXPORT MCD(n,d)
BEGIN
LOCAL z,w,t;
z:=MAX(ABS(n),ABS(d));
w:=MIN(ABS(n),ABS(d));
WHILE w≠0 DO
t:=z;
z:=w;
w:=t-w*IP(t/w);
END;
RETURN z;
END;but I find this approach very interesting (especially when you need to manage lists).
RE: A recursive GCD in CAS - Mic - 02-25-2014 07:42 PM
Very interesting.