Ask Your Question

How do I find if/where a specific algorithm has been implemented

asked 2010-08-18 20:49:49 -0500

jsrn gravatar image


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, it has mostly been irrelevant posts, while a search on google like "" 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.

edit retag flag offensive close merge delete

5 answers

Sort by ยป oldest newest most voted

answered 2010-08-18 22:09:48 -0500

mvngu gravatar image

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, search_doc, or search_src 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.

edit flag offensive delete link more

answered 2010-08-19 02:11:09 -0500

schilly gravatar image

Apart 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']
edit flag offensive delete link more

answered 2010-08-18 22:14:40 -0500

Nathann gravatar image

Wouldn'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.


edit flag offensive delete link more

answered 2010-08-19 03:20:07 -0500

jsrn gravatar image

Thanks, 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.

edit flag offensive delete link more

answered 2010-08-18 22:17:11 -0500

Mike Hansen gravatar image

Unfortunately, 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 state that it uses either the Zassenhaus method or van Hoeij's method. PARI's documentation 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 which could be used to add this.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2010-08-18 20:49:49 -0500

Seen: 516 times

Last updated: Aug 18 '10