Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented | Hacker News Reader

Donald Knuth: Mathematical Ideas, or Algorithms, Should Not Be Patented

groklaw.net

75 pointsAnon8436 comments

U.S. patent 1,048,576 1970 January 1. "A method for distributed editing of publications with micropayment incentives", Knuth D. E.

Good find, but a man can change his mind. Also, given the existing patent system, you're practically forced to seek patents to avoid getting trolled.

It's a joke. 2^20 = 1,048,576. And the patent sounds a lot like Knuth's scheme for getting corrections to his books...

And epoch time is a dead giveaway for the issue date.

Especially since New Year's Day is a US government holiday...

Good find?

[Edit: I just picked a computationally relevant number that approximates the patent counter circa the epoch.]

I was just flying by HN on a busy day. Syntax parsing: success. Semantic parsing: error. Looks like I failed the Turing test... I'm a bot. Damn. ;)

Way off. That patent is from 1912.

http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sec...

Right order of magnitude; close enough. ;)

you're practically forced to seek patents to avoid getting trolled

How so? What if you released something in the public domain and made it unpatentable?

I can't speak of litigious trolls, but academics have to churn out papers and patents for their own stature and paychecks. Yes, big edu would troll even The Man himself.

Of course, Knuth is notorious for his "churning out" of books; though none are as rigorous as his early VB6 stuff.

http://www.ibiblio.org/Dave/Dr-Fun/df200002/df20000210.jpg

Crowdsourcing. Micropayments. User-generated content.

TAOCP sounds tragically hip, when described like that.

>Surely nobody could apply mathematics if it were necessary to pay a license fee whenever the theorem of Pythagoras is employed.

I’ve seen this argument why algorithms and mathematics shouldn’t be patentable before. A fact that is always overlooked is that this hypothetical patent would have expired sometime in the 5th century BC. To make this argument one would have to find more recent examples. How about anything created within the last 20 years? In my view, the greatest things aren’t practical to be patentable and the practical ones aren’t anywhere close in magnitude to the Pythagorean Theorem. So, where is the problem? And by the way, comparing algorithms to "words" (in this context) is just silly, with all due respect to Knuth.

The problem with this is that while 20 years isn't a long time pre-Industrial Era, and isn't insurmountably long in the Industrial Era, in the Information Age (let's say 1980 on), 20 years is a crazy long time. Twenty years ago, supercomputers where about as powerful as the desktop I'm sitting at now, a desktop that's by modern standards slow (at work, it's a P4 with like 512 RAM). Twenty years ago, BBSes and IRC were as good as it gets. The Web 1.0 forums and Geocities sites would have been cutting edge, much less something like Reddit or Wikipedia. The cutting-edge stuff people are doing on here with location-based social networking (Loopt) or seamless on-the-Internet file storage (Dropbox) is the sci-fi of 20 years ago. 1,000 bit/s was considered a decent connection speed, whereas now anything under 1,000,000 bit/s (1 Mbps, or 128 KB/s) is considered slow.

In this environment, a 20-year patent lasts a life-time. Amazon's One-Click patent was granted in 1999. That means you have to steer clear of it or license it until 2019. That's 20 years that Amazon will be controlling a crucial feature of e-commerce sites.

MP3's patents will run until at least 2012. By the time MP3 (standardized in 1991) is patent-free, it'll be obselete, at best a legacy format. Heck, every music player (software and hardware) for the last few years has supported either MPEG-4 audio (AAC) or WMA, both of which sound better than MP3 at the same bit-rate. By the time patents on MPEG-4 stuff expire, it'll be at least 2020, and we'll be 1-2 generations further advanced.

My point is that for algorithmic, software, and business-model patents, even if they should be legitimate, a 20-year lifespan in the modern era is insane. Measured against the rate of progress, patents are lasting longer and longer, and by the time the patent is expired, there's no longer money in the previously-covered area.

Exactly, at one point in time the ball point pen was patented, You couldn't make a ball point pen without paying someone.

How is the fruit of my labor any different from the fruit of a ME EE or ChemE's labor? The lot of us practice applied math in different domains.

A patent on a ball-point pen only affects how you make your pen. A company can make a competing, non-ballpoint pen that still writes on the same paper and is still the same color (though it might be more expensive or messier or whatever), so not licensing the patent isn't disastrous. Even with a patent on something like an engine, I can still design my own (likely less efficient) engine, which'll still drive on the same roads and probably even use the same gasoline that works slightly differently.

A patent on something like MP3 or One-Click-Ordering prevents competitors from including a feature. If I want to make an e-commerce site, I have to have multiple clicks to order something or I have to license Amazon's patent. If I want to make any sort of media hardware or software that can encode/decode or import/export or even play the content out there, I need a slew of patents licensed. There's no work-around or alternative method, I simply can't include that feature without licensing.

It's the difference between "licensing this patent lets me build off the work of another company to make my product better" and "licensing this patent is mandatory to compete in this field". In my mind, patents of the first type are fine, while patents of the second type are bad.

I should be able to create something that can (for example) play MP3s without licensing, but do so at the cost of efficiency or power (because I'm using a less effective method).

Protip: for those who have only read about him, his name is pronounced "ca-nuth." The K is not silent. I learned this the embarrassing way.

I really would like to see algorithms black-boxed rather than patented. I should be able to reap the benefits of figuring the same thing out on my own some time later than a competitor did.

You've just explained the difference between a patent and a trade secret. :)

I know Knuth for his The Art of Computer Programming and TeX, and he's clearly amazingly smart - I'm curious about what algorithms he has invented, for what applications. e.g. Is there a "Knuth's Algorithm" (like Dijkstra's)?

Wikipedia gives a few...

http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X

http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pr...

http://en.wikipedia.org/wiki/Knuth-Bendix_completion_algorit...

There are probably others as well. KMP is well-known and, I believe, commonly implemented for text search. Algorithm X is implemented in his "dancing links" method, and can be used (among other things) to solve Sudoku puzzles.

I learned of the Fisher-Yates shuffle as the Knuth shuffle, but apparently both names are used for it.

http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

I have used an alternate shuffling approach in the past of my own naive creation, which is to go from 1-N items, each pass selecting a random number to swap the current position with. This would not require counting over missing items (those copied to result) on each loop. What is the flaw in this approach I wonder?

I've used that method too. The flaw is that it is biased; some permutations will be more likely than others.

Each shuffle will consume N random numbers between 1 and N (inclusive). This gives a total of N^N equally probable N-tuples of random numbers, all corresponding to exactly one output permutation.

But there are only N! possible permutations, so some of the N^N N-tuples must share the same output permutation. Since N! does not usually divide N^N evenly, some permutations must be more probable than others.

Ah....clever. thx.

Thanks, how silly of me: the text search algorithms are some of my favourites. :-(

The only one with his name on it that comes to mind is KMP, the Knuth-Morris-Pratt algorithm for text searching, which is actually a fairly big deal in that community. But most of the typesetting algorithms in TeX were totally novel at the time; ditto Metafont. Wikipedia lists several others, including his popularization of the "Dancing Links" exact cover algorithm and his cunning test of recursion in Algol 60 compilers (which was very new at the time).

As a community that does a lot of work dealing with algorithms, I'm curious as to how others feel about this. I think it is important to protect trade secrets (and algorithms would certainly fall under "trade secrets" for some products), but I also believe that hindering anything mathematical or scientific is, for lack of a better phrase, negative.

If your company depends heavily on a huge body of code, are you in favor or against software patents?

Once you patent something it ceases to be a trade secret. This is an important feature of the patent system; to ensure that what would otherwise stay as trade secrets (eventually) become available to the public.

My company depends heavily on a huge body of code, but copyright protects us more than enough. The ideas are cheap, the code to implement it is hard. I think it is fair game if somebody came along and implemented the same ideas we do. Patents stifle this kind of healthy competition.

Thanks for the response.

I'll now pose a different question. Do people in this community keep their ideas out of the patent records, or do they patent? I come from a finance background and have recently returned to school to pursue an MSFE. In the financial world, new strategies, often implemented through algorithms, are the lifeblood of a lot of quantitative firms. Do people think it is better to not publish a patent if your business depends heavily an a very unique idea?

If you sat down everyone in the industry who had the same amount of education and professional experience, how many of them would have come up with a similar system? Sure there is more than one way to skin a cat, but after years of cat skinning school and years of professional cat skinning everybody comes to do it in close(maybe not identical) to the same way. I would step back and try to consider how unique the idea really is, and how easy it would be for someone with a similar background to figure it out just by looking at inputs and outputs.

Testing obviousness with the benefit of hindsight isn't always fair. :-)

One test for non-obviousness is if the problem has been known for a long time, but no one has solved it; or (even better), the standard approaches that are taught for it lead away from your solution.

Trading Technologies has in the past been aggressive about defending patents on their trading software.

On the other side of the aisle, many approaches are under trade secret protection.

I think operationally patents don't do what we would like, and that is to give a small innovator some room to profit from an invention. In real life, it is large companies that produce, acquire, and use them in a defensive fashion.

Our product relies on novel algorithms. That's our "secret sauce," if you will. We publish the algorithms we develop on peer reviewed conferences and journals. There have been improvements made to our work by others and we encourage that. What prevents our competitors from copying our work and reaping the rewards? So patents seems to be a necessary evil from our perspective. It's not the patents that we shall fault it's the patent holders.

The interesting bit is if you read his letter with the attached question and answer session, he talks about how trivial items that could be discovered by a student on their own shouldn't be patented. It's a great point because it seems there is a mutually exclusive situation here: either teachers (starting from grade school) are inhibiting students from becoming creative with math and making proofs, in which case they are told to just learn existing material (that is presumably patented and in the course work) so as not to deviate from the other children. Or they are offered the other option in a software patent free world of ideas where they can think for themselves.

Lockhart's Lament: http://news.ycombinator.com/item?id=130499

How do you get a patent, if you have developed mathematical ideas to solve a practical problem?

I guess the answer is to patent that specific application of the mathematics - like Pagerank. This narrows the patent, so it doesn't impede progress in general; and it doesn't harm you, since that's the only area that you're working in anyway. From a business point of view, it would suck if someone was absurdly successful by applying your mathematical ideas exactly in an unrelated field... but would be kinda cool for you as a knowledge-creator. As an inventor, you're doing both.

Reply on news.ycombinator.com