Tracing Procedure Execution: printlevel

Here is a Maple procedure which computes the greatest common divisor of two non-negative integers using the Euclidean algorithm. For example, the greatest common divisor of the integers 21 and 15 is 3 because 3 is the largest integer that divides both 21 and 15. By the way, the Euclidean algorithm is one of the oldest known algorithms in Mathematics. It dates back to around 300 BC.

GCD := proc(a,b) local c,d,r;
    c := a;
    d := b;
    while d <> 0 do r := irem(c,d); c := d; d := r od;
    c
end;

The irem function computes the integer remainder of two integers. How does the GCD routine really work? The simplest tool for looking at the execution of a procedure is the printlevel facility. The printlevel variable is a global variable that is initially assigned 1. If you set it to a higher value, a trace of all assignments, and procedure entries and exits is printed. Let's see what happens when we compute GCD(21,15);

> printlevel := 100;
> GCD(21,15);
--> enter GCD, args = 21, 15
                                    c := 21

                                    d := 15

                                     r := 6

                                    c := 15

                                     d := 6

                                     r := 3

                                     c := 6

                                     d := 3

                                     r := 0

                                     c := 3

                                     d := 0

                                       3

<-- exit GCD = 3
                                       3

We see that the input arguments to the GCD procedure are displayed together with the value returned. The execution of each assignment statement is also displayed.

An interesting point about our Maple GCD procedure is that this routine works for integers of any size because Maple uses arbitrary precision integer arithmetic. For example, here is the greatest common divisor between 100! and

> GCD(100!,2^100);
                         158456325028528675187087900672

Our GCD procedure could also have been been written recursively in this way

GCD := proc(a,b)
    if b = 0 then a else GCD(b,irem(a,b)) fi
end;

The recursive version is simpler and easier to understand. Let us see a trace of the recursive version to see how the printlevel facility can show the flow of computation.

> GCD(15,21);
--> enter GCD, args = 15, 21
--> enter GCD, args = 21, 15
--> enter GCD, args = 15, 6
--> enter GCD, args = 6, 3
--> enter GCD, args = 3, 0
                                       3

<-- exit GCD = 3
                                       3

<-- exit GCD = 3
                                       3

<-- exit GCD = 3
                                       3

<-- exit GCD = 3
                                       3

<-- exit GCD = 3
                                       3