Evaluation of the Heuristic Polynomial GCD

The Heuristic Polynomial GCD procedure (GCDHEU) is used by the Maple computer algebra system, but no other. Because Maple has an especially efficient kernel that provides fast integer arithmetic, but a relatively slower interpreter for non-kernel code, the GCDHEU routine is especially effective in that it moves much of the computation into "bignum" arithmetic and hence executes primarily in the kernel. We speculated that in other computer algebra systems an implementation GCDHEU would not be advantageous. In particular, if all the system code is compiled to run at "full speed" in a (presumably more bulky) kernel that is entirely written in C or compiled Lisp, then there would seem to be no point in recasting the polynomial gcd problem into a bignum GCD problem. Manipulating polynomials that are vectors of coefficients would seem to be equivalent computationally to manipulating vectors of big digits. Yet our evidence suggests that one can take advantage of the GCDHEU in a Lisp system as..