William Stein wrote: > On 10/28/07, Jaap Spies <[EMAIL PROTECTED]> wrote:
> >> I did change some of them in trac #217, but I think a new trac >> ticket should be created. > > > Are you sure? I just had a look at trac #217, and your changing Py_ssize_t > into int specifically *introduces* bugs into that code. E.g., suppose the > input > were a 1 x 2^33 matrix. Then you did this in your patch: > > - cdef Py_ssize_t m, n, r > + cdef int m, n, r > > Lower down one has: > m = self._nrows > n = self._ncols > > Now, instead if the code working like it used to, there will be an overflow, > and one will get total nonsense. > In your example the permanent is just the product of the entries. You deserve to get total nonsense when you try to calculate the permanent of matrices of that size! In practice you know that m and n are small ints. The permanent is a really hard problem. For example the calculation of a 40 x 40 (0,1)-matrix with the implemented Ryser algorithm will take forever. Let alone a general matrix of that size! This best known Ryser algorithm is of time O(n^2*2^n). The best we can hope is doing better for certain types of (0,1) matrices. Jaap --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
