5 ms·
* ... multiplying a 1000x1000 matrix is no different in process but is much more time consuming; should the latter be patentable?* A naive algorithm for multip
by Daniel_Newby 15y ago
* ... multiplying a 1000x1000 matrix is no different in process but is much more time consuming; should the latter be patentable?*
A naive algorithm for multiplying square matrices runs in O(N^4). A slightly less naive algorithm runs in O(N^3). There is an especially clever algorithm that runs in O(N^2.807).
If somebody discovers a practical algorithm that runs in O(N^2.1), should it be patentable? I say yes. No amount of grinding away with pencil and paper is equivalent to a clever divide and conquer algorithm.
- kwantam 15y agoI'm not a lawyer, but I'm pretty sure Gottschalk v. Benson makes it clear that the algorithm itself is not patentable. http://en.wikipedia.org/wiki/Gottschalk_v._Benson http://en.wikipedia.org/wiki/Gottschalk_v._Benson EDIT: It occurs to me upon reflecting on my reply that you're making a statement unqualified by present legal precedent. In that case, I respectfully disagree. Patenting fundamental mathematical truths seems like a very bad idea to me, and I'm glad that nominally such things are not allowed (though of course practically it goes on all the time). Perhaps another way to say this: the problem most people have with software patents is that it's more or less patenting little pieces of math. I think it's more or less well known how most "practitioners of the art" feel about this.
- Daniel_Newby 15y agoSorry. By "patentable" I meant when embodied by a clearly-defined machine. And anyway, why not patent algorithms in the abstract? There are an infinity of "fundamental mathematical truths", but only a few are spectacularly useful. If a given algorithm truly is obvious and trivial, then you can evade the patent by spending 30 seconds to find another obvious and trivial algorithm. (I note that most of the people complaining about the trivial obviousness of all software patents are not cranking out 50 algorithms a day like RSA or the fast Fourier transform. When they talk about software being obvious, they're talking about other people's software.)
- schrototo 15y agoSo Carl Friedrich Gauss could have patented his FFT algorithm, since it would take 160 years for the next guys to come up with it on their own?
- 6ren 15y agoIt's possible for an algorithm to be obvious and trivial, and also the only way to do it.
- Natsu 15y ago> And anyway, why not patent algorithms in the abstract? Because the costs outweigh the benefits, unless you're a patent lawyer. Software patents already create huge legal risks to businesses that did nothing wrong except come up with a simple idea that someone patented first, they're ridiculously expensive to enforce, and most of the money ends up driving more lawsuits rather than more research.
- argv_empty 15y agoNo amount of grinding away with pencil and paper is equivalent to a clever divide and conquer algorithm. Unless that grinding is to reproduce the algorithm's steps. Which is a rather important issue in this case (that and people object to the idea of having patent law restrict use of an organized thought process).
- xyzzyz 15y agoA bit offtopic -- what O(n^4) naive algorithm have you in mind? I cannot really think of any -- just implementing the definition gives you O(n^3).
- Daniel_Newby 15y agoOops. Thanks for the correction.