/* [wxMaxima batch file version 1] [ DO NOT EDIT BY HAND! ]*/
/* [ Created with wxMaxima version 0.8.1 ] */

/* [wxMaxima: title   start ]
The Euclidean algorithm
   [wxMaxima: title   end   ] */

/* [wxMaxima: comment start ]
(in various versions)  
   [wxMaxima: comment end   ] */

/* [wxMaxima: comment start ]
Reference: J. Ziegenbalg: Algorithmen von Hammurapi bis Gödel,  
  Verlag Harri Deutsch, Frankfurt a.M. 2007, section 3.2.2   
   [wxMaxima: comment end   ] */

/* [wxMaxima: section start ]
The Euclidean algorithm by iterated subtraction
   [wxMaxima: section end   ] */

/* [wxMaxima: input   start ] */
euclid(a, b):=
  block([x : a, y : b], 
    while not(x*y = 0) do
      (if x > y then x : x-y else y : y-x),
    return(x+y) );
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
euclid(136, 60);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: comment start ]
In the next version the subtraction process is made visible by introduction 
of the global variable "verbose".  If the value of verbose is "true" then 
intermediate values are printed, otherwise only the result is returned.  
   [wxMaxima: comment end   ] */

/* [wxMaxima: input   start ] */
verbose : true   /* global control variable */   $
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
euclid_verbose(a, b):=
  block([x : a, y : b], 
    while not(x*y = 0) do
      (if x > y then x : x-y else y : y-x , 
       if verbose then print(x, " ", y) ), 
    return(x+y) );
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
euclid_verbose(136, 60);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: section start ]
The Euclidean algorithm by iterated (integer-) division
   [wxMaxima: section end   ] */

/* [wxMaxima: input   start ] */
quotient(17, 5);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
mod(17, 5);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
is(17 = quotient(17,5)*5+mod(17,5));
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
euclid_division(a, b) :=
  block([x : a, y : b], 
    while not(x*y = 0) do
      (if x > y then x : mod(x, y) else y : mod(y, x) , 
       if verbose then print(x, " ", y) ), 
    return(x+y) );
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
euclid_division(136, 60);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
verbose : false;
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
euclid_division(8765432, 2345678);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: section start ]
The Euclidean Algorithm by recursion 
   [wxMaxima: section end   ] */

/* [wxMaxima: comment start ]
Two recursive versions are given:  
    first version:  "subtraction" form 
    second version: "(integer) division" form 
   [wxMaxima: comment end   ] */

/* [wxMaxima: input   start ] */
euclid_sub_rec(a, b):= 
  (if verbose then print(a, "  ", b),
   if a=0 then b 
      else if b=0 then a 
              else if a>b then euclid_sub_rec(a-b,b) 
                      else euclid_sub_rec(a, b-a) );
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
verbose:false;
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
euclid_sub_rec(136,98);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
euclid_div_rec(a, b):= 
  (if verbose then print(a, "  ", b),
   if a=0 then b 
      else if b=0 then a 
              else if a>b then euclid_div_rec(mod(a,b), b) 
                      else euclid_div_rec(a, mod(b,a)) );
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
verbose:true;
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
euclid_div_rec(136,60);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: section start ]
The Euclidean Algorithm by using Maxima's divide command 
   [wxMaxima: section end   ] */

/* [wxMaxima: input   start ] */
divide(17,5);
/* [wxMaxima: input   end   ] */

/* [wxMaxima: comment start ]
It also works for polynomials: 
   [wxMaxima: comment end   ] */

/* [wxMaxima: input   start ] */
expand((x^3-2*x^2+3*x-4)*(5*x^2-4*x+3));
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
divide(5*x^5-14*x^4+26*x^3-38*x^2+25*x-12, (5*x^2-4*x+3)) ;
/* [wxMaxima: input   end   ] */

/* [wxMaxima: input   start ] */
divide(5*x^5-14*x^4+26*x^3-38*x^2+25*x-12, (x^4-4*x+3)) ;
/* [wxMaxima: input   end   ] */

/* Maxima can't load/batch files which end with a comment! */
"Created with wxMaxima"$