A recursive GCD in CAS
02-25-2014, 03:19 AM
Post: #1
 massimo Junior Member Posts: 21 Joined: Feb 2014
A recursive GCD in CAS
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).

Massimo
from 34c to prime
02-25-2014, 07:42 PM (This post was last modified: 02-25-2014 07:44 PM by Mic.)
Post: #2
 Mic Member Posts: 131 Joined: Dec 2013
RE: A recursive GCD in CAS
Very interesting.