Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

To give a quick answer to the question in title, you can use the magic function %time or %timeit:

sage: R.<x> = GF(17)[]
sage: p = R.random_element(50)
sage: q = R.random_element(50)
sage: %timeit gcd(p,q)
100000 loops, best of 3: 12.2 ┬Ás per loop

The actual computation in my case (univariate polynomial over prime finite field) is done by Flint. I explain below how to get this information.

First, you can use gcd?? which shows you the source code. You'll find

    return a.gcd(b, **kwargs)

which tells you that the actual computation is p.gcd(q). Then using p.gcd??, you'll see that this method, written in the file $SAGE/src/sage/rings/polynomial/polynomial_template.pxi, use the function celement_gcd. If you open this file polynomial_template.pxi, the docstring tells us that this celement_gcd is implemented in some linkage file. Since in my case, the polynomial has type

sage: type(p)
<type 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>

one can open the file $SAGE/src/sage/rings/polynomial/polynomial_zmod_flint.pyx where the linkage file is included:

include "sage/libs/flint/nmod_poly_linkage.pxi"

The linkage file is thus $SAGE/src/sage/libs/flint/nmod_poly_linkage.pxi. In this file one sees that celement_gcd uses nmod_poly_gcd from Flint library. So at the end, this computation is performed by Flint.