Slashdot Mirror
HP Patents Bignum Implementation From 1912
I Don't Believe in Imaginary Property writes "The authors of GMP (the GNU Multiple Precision Arithmetic Library) were invited to join Peer-to-Patent to review HP's recent patent on a very old technique for implementing bignums because their software might infringe. Basically, HP's patent claims choosing an exponent based on processor word size. If you choose a 4-bit word size and a binary number, you end up working in hexadecimal. Or for a computer with a 16-bit word and a base-10 number, you use base 10,000 so that each digit of the base-10,000 number would fit into a single 16-bit word. The obvious problem with that is that there's plenty of prior art here. Someone who spent a few minutes Googling found that Knuth describing the idea in TAOCP Vol. 2 and other citations go back to 1912 (which implemented the same algorithm using strips of cardboard and a calculating machine). None of this can be found in the 'references cited' section. Even though the patent examiner did add a couple of references, they appear to have cited some old patents. The patent issued a few months ago was filed back in October of 2004, and collected dust at the USPTO for some 834 days."
In the example section they give, they are dividing up the "bigdecimal" in decimal, rather than binary components. The number of decimal digits depends on the word size. For example, an 8 bit word has 0-255 as possible storage, but in decimal, you could store 0-99, but not 0-999. So you would store the number 102,345 as 10, 23, and 45 in 3 separate words if you had an 8 bit word. They claim that this is more efficient than binary for rendering back to decimal, though I can't see how this is more efficient than straight binary storage.
Rhymes that keep their secrets will unfold behind the clouds.There upon the rainbow is the answer to a neverending story
"A few minutes googling"
Less than 10 years ago it would have taken multiple trips to (several) libraries by a very persistant person to find this information. (The kind of person who would read an obscure mailing list about patent abuse).
Most likely a cursory review by a bored patent clerk (as he is working on the next E=MC^2) would have turned up nothing, and the patent would have passed.
Now any Slashdotter with a minute to spare can find the same information.
Its interesting to see how we are getting to grips with information overload.
PostgreSQL starting storing NUMERIC columns in base 10000 six or seven years ago. A nice trick, but not exactly rocket science. If you have a high school level education in computer science, you should know how to do stuff like this. Maybe that is what the patent examiners need.
I'm thinking this would be very useful in the patent approval process, not just after the fact. Suppose it worked like this: The second you file a patent, it would be published. Before it could be approved, it would have to be public for some length of time, during which anyone could present prior art or arguments for "obviousness".
That's brilliant. Why, change "the second" to "within 18 months after" and you just described the USPTO. All patent applications are published and public for some length of time before approval, during which anyone can present prior art or arguments for "obviousness".
You knew that, right? I mean, you're not just griping about something without actually researching it, right?
I used to have a VAX assembly program called "er1e9", which computed e using base 1,000,000,000 numbers (which fit into 32-bit integers). I wrote that in the late 80's, and still have it around somewhere. Multiplying and dividing using the VAX instructions was fairly trivial with that format up to arbitrary lengths. It's a pretty obvious optimization, or at least it was for a college kid.
Do you have ESP?