ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 03 Mar 2017 02:18:54 -0600How to find compution time require for gcd of two polynomial over prime fieldhttp://ask.sagemath.org/question/36801/how-to-find-compution-time-require-for-gcd-of-two-polynomial-over-prime-field/ gcd(polynomial1,polynomial2)
what are the operation involved in computation of above operation in SAGE mathFri, 03 Mar 2017 00:05:15 -0600http://ask.sagemath.org/question/36801/how-to-find-compution-time-require-for-gcd-of-two-polynomial-over-prime-field/Answer by B r u n o for <p>gcd(polynomial1,polynomial2)
what are the operation involved in computation of above operation in SAGE math</p>
http://ask.sagemath.org/question/36801/how-to-find-compution-time-require-for-gcd-of-two-polynomial-over-prime-field/?answer=36803#post-id-36803To 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
try:
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.
Fri, 03 Mar 2017 02:18:54 -0600http://ask.sagemath.org/question/36801/how-to-find-compution-time-require-for-gcd-of-two-polynomial-over-prime-field/?answer=36803#post-id-36803