ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 19 Aug 2010 03:20:07 -0500How do I find if/where a specific algorithm has been implementedhttps://ask.sagemath.org/question/7580/how-do-i-find-ifwhere-a-specific-algorithm-has-been-implemented/Hi
Since beginning using Sage, I have often been in the position that I need to find a specific algorithm for solving some problem. I might or might not already know that Sage has _some_ algorithm for doing it, but I want this one (for some reason). Is there an index or an easy way to search for this? The times I have tried using the search bar of sagemath.org, it has mostly been irrelevant posts, while a search on google like "<algorithm-name> site:sagemath.org" can give a bit as it also searches through the comments of the source code; but this is not very user-friendly, and it can take some time from finding some comment in a file, to know how to actually invoke specifically that code.
An example of this is the Berlekamp-Zassenhaus algorithm for factorising polynomials over integers.Wed, 18 Aug 2010 20:49:49 -0500https://ask.sagemath.org/question/7580/how-do-i-find-ifwhere-a-specific-algorithm-has-been-implemented/Answer by mvngu for <p>Hi</p>
<p>Since beginning using Sage, I have often been in the position that I need to find a specific algorithm for solving some problem. I might or might not already know that Sage has _some_ algorithm for doing it, but I want this one (for some reason). Is there an index or an easy way to search for this? The times I have tried using the search bar of <a href="http://sagemath.org">sagemath.org</a>, it has mostly been irrelevant posts, while a search on google like "<algorithm-name> site:sagemath.org" can give a bit as it also searches through the comments of the source code; but this is not very user-friendly, and it can take some time from finding some comment in a file, to know how to actually invoke specifically that code.</algorithm-name></p>
<p>An example of this is the Berlekamp-Zassenhaus algorithm for factorising polynomials over integers.</p>
https://ask.sagemath.org/question/7580/how-do-i-find-ifwhere-a-specific-algorithm-has-been-implemented/?answer=11400#post-id-11400> Is there an index
There is no such index of algorithms implemented in Sage.
> or an easy way to search for this?
> An example of this is the Berlekamp-Zassenhaus algorithm for factorising
> polynomials over integers.
You could use the search functions [search\_def][1], [search\_doc][2], or [search\_src][3] to search through the Sage source tree. When someone implements an algorithm or interfaces to an algorithm from a Sage package, the name of the algorithm should be mentioned in the docstring of the relevant module, class, method, or function. For the Berlekamp-Zassenhaus algorithm, I got this
sage: search_src("Berlekamp-Zassenhau")
rings/polynomial/polynomial_element.pyx:2656: ## NTL uses the Berlekamp-Zassenhaus method with van Hoeij's improvements.
That should tell you where to start looking, specifically in the file sage/rings/polynomial/polynomial_element.pyx around line 2656.
[1]: http://www.sagemath.org/doc/reference/sage/misc/sagedoc.html#sage.misc.sagedoc.search_def
[2]: http://www.sagemath.org/doc/reference/sage/misc/sagedoc.html#sage.misc.sagedoc.search_doc
[3]: http://www.sagemath.org/doc/reference/sage/misc/sagedoc.html#sage.misc.sagedoc.search_srcWed, 18 Aug 2010 22:09:48 -0500https://ask.sagemath.org/question/7580/how-do-i-find-ifwhere-a-specific-algorithm-has-been-implemented/?answer=11400#post-id-11400Answer by Nathann for <p>Hi</p>
<p>Since beginning using Sage, I have often been in the position that I need to find a specific algorithm for solving some problem. I might or might not already know that Sage has _some_ algorithm for doing it, but I want this one (for some reason). Is there an index or an easy way to search for this? The times I have tried using the search bar of <a href="http://sagemath.org">sagemath.org</a>, it has mostly been irrelevant posts, while a search on google like "<algorithm-name> site:sagemath.org" can give a bit as it also searches through the comments of the source code; but this is not very user-friendly, and it can take some time from finding some comment in a file, to know how to actually invoke specifically that code.</algorithm-name></p>
<p>An example of this is the Berlekamp-Zassenhaus algorithm for factorising polynomials over integers.</p>
https://ask.sagemath.org/question/7580/how-do-i-find-ifwhere-a-specific-algorithm-has-been-implemented/?answer=11401#post-id-11401Wouldn't the search_* commands be what you need ? An example :
sage: search_src("Berlekamp-Zassenhaus")
rings/polynomial/polynomial_element.pyx:2656: ## NTL uses the Berlekamp-Zassenhaus method with van Hoeij's improvements.
I have to admit this is not very user-friendly either, sometimes... But it can be helpful ! seach\_doc searches through the doc, search\_def through the methods' names, and search\_src through the sources.
Nathann
Wed, 18 Aug 2010 22:14:40 -0500https://ask.sagemath.org/question/7580/how-do-i-find-ifwhere-a-specific-algorithm-has-been-implemented/?answer=11401#post-id-11401Answer by schilly for <p>Hi</p>
<p>Since beginning using Sage, I have often been in the position that I need to find a specific algorithm for solving some problem. I might or might not already know that Sage has _some_ algorithm for doing it, but I want this one (for some reason). Is there an index or an easy way to search for this? The times I have tried using the search bar of <a href="http://sagemath.org">sagemath.org</a>, it has mostly been irrelevant posts, while a search on google like "<algorithm-name> site:sagemath.org" can give a bit as it also searches through the comments of the source code; but this is not very user-friendly, and it can take some time from finding some comment in a file, to know how to actually invoke specifically that code.</algorithm-name></p>
<p>An example of this is the Berlekamp-Zassenhaus algorithm for factorising polynomials over integers.</p>
https://ask.sagemath.org/question/7580/how-do-i-find-ifwhere-a-specific-algorithm-has-been-implemented/?answer=11409#post-id-11409Apart from search_src, ff you want to know which part of Sage is responsible for a certain calculate, you can use the cite function:
sage: from sage.misc import citation
sage: citation.get_systems("factor(1-x^2)")
['PARI', 'ginac', 'GMP']Thu, 19 Aug 2010 02:11:09 -0500https://ask.sagemath.org/question/7580/how-do-i-find-ifwhere-a-specific-algorithm-has-been-implemented/?answer=11409#post-id-11409Answer by jsrn for <p>Hi</p>
<p>Since beginning using Sage, I have often been in the position that I need to find a specific algorithm for solving some problem. I might or might not already know that Sage has _some_ algorithm for doing it, but I want this one (for some reason). Is there an index or an easy way to search for this? The times I have tried using the search bar of <a href="http://sagemath.org">sagemath.org</a>, it has mostly been irrelevant posts, while a search on google like "<algorithm-name> site:sagemath.org" can give a bit as it also searches through the comments of the source code; but this is not very user-friendly, and it can take some time from finding some comment in a file, to know how to actually invoke specifically that code.</algorithm-name></p>
<p>An example of this is the Berlekamp-Zassenhaus algorithm for factorising polynomials over integers.</p>
https://ask.sagemath.org/question/7580/how-do-i-find-ifwhere-a-specific-algorithm-has-been-implemented/?answer=11411#post-id-11411Thanks, these are all good answers (I don't have any points, so I can't give thumbs up, I'm afraid); I will try to work those into my routines. Did I simply miss them in the documentation somewhere?
I agree Mike, that the syncing is the hardest part. How lucky we are that Sage is open source, so such documentation is less essential ;-)
I guess that if such a table from algorithm names to Sage functions had been made and was complete, most Sage developers would be aware of having to update that along with some given patch that would implement or change the use of a named algorithm. Because of the review system (it could be explicitly added to the documented review procedure), a reviewer would often catch it if the patch developer forgot. One could also implement a best-effort tool to check if the patch might cause changes to the table: the tool could see if the patch changes stuff in a function that is mapped to or a direct dependency hereof and tell the developer to examine these cases. We still have the problem, of course, whenever one of the external libraries changes or implement new algorithms.Thu, 19 Aug 2010 03:20:07 -0500https://ask.sagemath.org/question/7580/how-do-i-find-ifwhere-a-specific-algorithm-has-been-implemented/?answer=11411#post-id-11411Answer by Nathann for <p>Hi</p>
<p>Since beginning using Sage, I have often been in the position that I need to find a specific algorithm for solving some problem. I might or might not already know that Sage has _some_ algorithm for doing it, but I want this one (for some reason). Is there an index or an easy way to search for this? The times I have tried using the search bar of <a href="http://sagemath.org">sagemath.org</a>, it has mostly been irrelevant posts, while a search on google like "<algorithm-name> site:sagemath.org" can give a bit as it also searches through the comments of the source code; but this is not very user-friendly, and it can take some time from finding some comment in a file, to know how to actually invoke specifically that code.</algorithm-name></p>
<p>An example of this is the Berlekamp-Zassenhaus algorithm for factorising polynomials over integers.</p>
https://ask.sagemath.org/question/7580/how-do-i-find-ifwhere-a-specific-algorithm-has-been-implemented/?answer=11402#post-id-11402Wouldn't the search_* commands be what you need ? An example :
sage: search_src("Berlekamp-Zassenhaus")
rings/polynomial/polynomial_element.pyx:2656: ## NTL uses the Berlekamp-Zassenhaus method with van Hoeij's improvements.
I have to admit this is not very user-friendly either, sometimes... But it can be helpful ! seach\_doc searches through the doc, search\_def through the methods' names, and search\_src through the sources.
Nathann
Wed, 18 Aug 2010 22:14:56 -0500https://ask.sagemath.org/question/7580/how-do-i-find-ifwhere-a-specific-algorithm-has-been-implemented/?answer=11402#post-id-11402Answer by Mike Hansen for <p>Hi</p>
<p>Since beginning using Sage, I have often been in the position that I need to find a specific algorithm for solving some problem. I might or might not already know that Sage has _some_ algorithm for doing it, but I want this one (for some reason). Is there an index or an easy way to search for this? The times I have tried using the search bar of <a href="http://sagemath.org">sagemath.org</a>, it has mostly been irrelevant posts, while a search on google like "<algorithm-name> site:sagemath.org" can give a bit as it also searches through the comments of the source code; but this is not very user-friendly, and it can take some time from finding some comment in a file, to know how to actually invoke specifically that code.</algorithm-name></p>
<p>An example of this is the Berlekamp-Zassenhaus algorithm for factorising polynomials over integers.</p>
https://ask.sagemath.org/question/7580/how-do-i-find-ifwhere-a-specific-algorithm-has-been-implemented/?answer=11403#post-id-11403Unfortunately, there isn't really a guaranteed method to figure out what algorithm is being used. By far, the most reliable way to figure it out is by looking through the source code. If you know a particular Sage function, then you can do introspection on that. If you're lucky, then the choice of algorithm or reference will be mentioned in the docstring or the source code for that function. If you don't know exactly where an algorithm might be implemented, then you may have to do a global search on the code base. Since Sage contains other components, you may also have to delve further down to see what they do.
I don't know a good solution for this type of problem. If anyone does, I'd be more than interested in hearing it. The hardest problem is making sure that that documentation actually stays in sync with the code.
As for your example, if we look at the documentation for the factor command on a univariate polynomial over the integers:
sage: R.<x> = ZZ[]
sage: f = (x+1)^2
sage: f.factor?
we see that a choice is made between either NTL or PARI for factoring. The [NTL implementation notes][1] state that it uses either the Zassenhaus method or van Hoeij's method. PARI's [documentation][2] also states that it uses van Hoeij's method.
For multivariate factoring, Sage does not currently support it over the integers. However, there is code at [#2179][3] which could be used to add this.
[1]: http://www.shoup.net/ntl/doc/ZZXFactoring.txt
[2]: http://pari.math.u-bordeaux.fr/dochtml/html.stable/Arithmetic_functions.html#factor
[3]: http://trac.sagemath.org/sage_trac/ticket/2179
Wed, 18 Aug 2010 22:17:11 -0500https://ask.sagemath.org/question/7580/how-do-i-find-ifwhere-a-specific-algorithm-has-been-implemented/?answer=11403#post-id-11403Answer by schilly for <p>Hi</p>
<p>Since beginning using Sage, I have often been in the position that I need to find a specific algorithm for solving some problem. I might or might not already know that Sage has _some_ algorithm for doing it, but I want this one (for some reason). Is there an index or an easy way to search for this? The times I have tried using the search bar of <a href="http://sagemath.org">sagemath.org</a>, it has mostly been irrelevant posts, while a search on google like "<algorithm-name> site:sagemath.org" can give a bit as it also searches through the comments of the source code; but this is not very user-friendly, and it can take some time from finding some comment in a file, to know how to actually invoke specifically that code.</algorithm-name></p>
<p>An example of this is the Berlekamp-Zassenhaus algorithm for factorising polynomials over integers.</p>
https://ask.sagemath.org/question/7580/how-do-i-find-ifwhere-a-specific-algorithm-has-been-implemented/?answer=11399#post-id-11399Apart from search_src, ff you want to know which part of Sage is responsible for a certain calculate, you can use the cite function:
sage: from sage.misc import citation
sage: citation.get_systems("factor(1-x^2)")
['PARI', 'ginac', 'GMP']Thu, 19 Aug 2010 02:10:44 -0500https://ask.sagemath.org/question/7580/how-do-i-find-ifwhere-a-specific-algorithm-has-been-implemented/?answer=11399#post-id-11399