I could be wrong, but based on the similarities to interval arithmetic everyone has already identified, I'm pretty skeptical. At best, this could be a patent on a more efficient way to build interval arithmetic into a CPU architecture rather than a completely new technique.
As my British friends would say though, I can't be arsed to actually read the patent.
For example, sqrt(2) + sqrt(8) would print 3 sqrt(2) rather than 4.242640687119286~
I wish I knew how it worked, it's probably something simple like suggested in another comment.
It's patent law lingo. The patent covers both the idea (the "system") and subsequent implementations (the "apparatus") that are direct implementations of the idea.
You won't need many bits for the error, and operations can be made reasonably fast as only several lowest bits are affected.
Not directly related to the article, but many [1] irrational numbers (π for example, or sqrt(2)) can be represented in a computer in their entirety, i.e. "accurate to the last digit." Not all digits are stored at once in RAM, of course, but you can obtain an arbitrary digit (given sufficient time). That's precisely how computable numbers are defined (first by Turing in his 1936 paper that first defined the notion of computation, and was called On Computable Numbers, where the "numbers" in the title refer to real numbers, including irrational ones).
[1]: Relative to the irrational numbers that "we know", not to all uncountable ones, of course.
Moreover, these are clearly marked quotes from the press release and the patent. Maybe this technology doesn't merit an article. But if it does, quoting the inventor is exactly what one expect from coverage. Note that it does invite scepticism, starting with "claims" in the headline.
This gratuitous hatred of journalism is seriously getting out of hands.
Not only does this method not reduce floating point error, it reduces the precision that you have for any given number of bits.
Unfortunately I can't find any of the figures referenced in the patent to help me understand the novelty of this patent.
What about for binary repeating decimals like 0.3? Wouldn't it always raise that signal?
unums: https://en.wikipedia.org/wiki/Unum_(number_format)
interval arithmetic: https://en.wikipedia.org/wiki/Interval_arithmetic
That does seem useful but it's a bit akin to saying that you've solved the division-by-zero problem by inventing NaN. Suppose you're writing some critical piece of software and a floating point operation raises the "inaccurate" flag, how do you deal with that? Do you at least have access to the bounds computed by the hardware, so that you may decide to pick a more conservative value if that makes sense?
Besides the link to the "1991 Patriot missile failure" kinds of contradicts the claim that this would solve the issue since Wikipedia says:
>However, the timestamps of the two radar pulses being compared were converted to floating point differently: one correctly, the other introducing an error proportionate to the operation time so far (100 hours) caused by the truncation in a 24-bit fixed-point register.
If the problem comes from truncation in a FP register I'm not sure how this invention would've helped.
You can trap. ...but then again, existing arithmetic traps are not uniformly enabled by default.
EDIT: and for some other methods: https://en.wikipedia.org/wiki/Unum_%28number_format%29, particularly the latest one being the Posit method: http://superfri.org/superfri/article/download/137/232
EDIT2: of course other people can license it, but the other way to bring a new floating point to the scene would be through the same process that happened with IEEE 754. There are plenty of people who wouldn't touch anything patented at all, sometimes even with a patent clause.
> When the calculated result is no longer sufficiently accurate the result is so marked, as are all further calculations made using that value.
Solving it would be a pretty big deal. This doesn't feel like it is, though I admit I haven't worked on a similar problem in a long time. Kinda feels like patent trolling as I imagine that lots of companies have put bounds on detecting floating point errors when they need it. There are certainly lots of papers on it: https://www.google.com/search?q=floating+point+error+bounds
The hard part has been left as an exercise for the examiner.
The whole technique smells a bit fishy to me, but it might be genuine (in any way, the article seems more like marketing since the technical merit is not immediately obvious, and the difference with existing techniques not immediately clear).
To me, it looks like a specific mechanism for encoding the bounds and scale of error into a floating point representation, along with a pipeline for processing operations on operands of this form (presumably efficiently). So to me it looks like a specific variant of IA.
It looks like the purpose is to be implemented as an alternative to conventional floating point libraries and CPU modules. E.g., Intel might license this and add a floating point module based on this + instructions to access it to a future CPU. (Well, even if it's great and all is as advertised, and proves to be generally useful, I'm not sure it would jump right into the CPU. It would probably have to grow more organically first, but that's another discussion.)
I mean, I have no idea if this does all of what it says or if it does, whether that would prove to be generally useful enough to make it out of niche cases.
But it's interesting.
I'm not sure how much it increases computation time, but software for exactly this is freely available, see for instance Arb: https://github.com/fredrik-johansson/arb
For machine precision, I believe ordinary interval arithmetic is the best way to go still. Unfortunately, this not only uses twice as much space; the time overhead can be enormous on current processors due switching rounding modes (there are proposed processor improvements that will alleviate this problem). However, the better interval libraries batch operations to minimize such overhead, and it's even possible to write kernel routines for things like matrix multiplication and FFT that run just as fast as the ordinary floating-point versions (if you sacrifice some tightness of the error bounds).
Regarding the article, using a more compact encoding for intervals is a fairly old idea and I'm not really sure what is novel here.
Thanks for the numbers, how did you get that estimate? Did you consider SIMD?
It seems to be a system where the hardware design itself keeps track of the accuracy losses in floating point calculations, and provides them as part of the value itself.
The title is (predictably) exaggerated, but it's an interesting idea, and could potentially be a significant improvement in particular use cases.
Looking at the claims, it looks like he's patented an augmented floating point unit (hardware) that does bounded arithmetic. The #1 claim is "A processing device [with a] FPU [and a] bounded floating point unit (BFPU)." All the following claims are "The processing device as recited in claim 1" (e.g. CPU+FPU+BFPU) with subsequent changes.
This may seem odd, but it can be the difference between knowing and unknowing infringement. Knowing infringement results in triple damages.
IANAL — just repeating consistent advice I have received
Reading a patent is more likely to make you not infringe upon it than to make you knowingly infringe upon it.
Addition has a maximum accuracy of 1 LSB. Makes sense: the last bit could have been "rounded off" and 1.5+1.5 == 2 (but really 3 should have been returned).
Subtraction has unlimited error bounds (!!!). Well, I guess there's 53-bits of a double-precision float. So subtraction can theoretically create 53-bits of error.
In practice, you need to keep track of the error bounds during the runtime of the program. Its not something that can be computed at compile time. After all, addition of a positive and negative number IS subtraction. (so some subtractions are additions: with accuracy of 1LSB. While some additions are subtractions: with unlimited error bounds)
Is there something more novel to his approach?
Note that it’s a claim on the processing unit implementation (e.g. the FPU), not the method.
Nonetheless, I’d be very surprised if this stands the test of interval arithmetic prior art.
So the inventor gets a patent number for his LinkedIn profile, and USPTO get their fee, and that's the end of it. A win-win for all involved.
Earlier HN discussion of the phenomenon: https://news.ycombinator.com/item?id=16015371
Patents like this have "threat value", which is often happily exploited by "IP monetization" companies, contingent law firms, etc.
This is the kind of stuff that turns into 100x $50k settlement demands.
What he is doing appears so be interval arithmetic: https://en.wikipedia.org/wiki/Interval_arithmetic
Because we don't have infinite computer memory or processing power numbers have to be finite, so no one will ever "solve the floating point error problem" however being able to quantify the error is both extremely useful and extremely complex because you have to try to determine how the error propagates through all of the operations applied over the original input values.
In science this is also done based on the precision of the raw data... roughly through selecting a sensible number of significant figures in final calculation. In other words they omit all of the digits they deem to be potentially outside of the precision provided by the raw data, e.g your inputs a:123.456 and b:789.012 but your result from some multistep calculation is 12.714625243422799, obviously the extra precision is artificial and should be reduced to something slightly less than the input precision (because it will have been rounded).
For floating point math this is about going a step further by calculating the propagation of error from the end of the maximum length significand provided by IEEE 754 (where anything longer causes rounding and thus error), and trying to quantify how that window opens wider and wider as those rounding errors propagate towards more significant digits as more operations are performed. With interval arithmetic this is done by keeping track of the upper and lower bounds of that window (the real number existing somewhere within that window).
This doesn't solve any of the many issues that floating point math has, but it allows whatever is consuming it to potentially assign significance to the output of a calculation more precisely. i.e so that you can say 1369.462628234m is actually 1.4e3m (implying ± 100m) perhaps translating into understanding that your trajectory calculation isn't actually as accurate accurate as the output looks, but instead the target has a variance of up to 100x100 meters.
I expect the patent details a hardware implementation to make this practical at the instruction level rather than a likely very slow software implementation.
In the end, it seemed like any substantial computation ended up having extremely wide bounds, much wider than they deserved. Trying to invert a matrix often resulted in [-Inf .. +Inf] bounds.
Funny. There was a project at Sun Labs in the early 2000s that way far down this road. Without looking at its specifics, I am still surprised that the patent was accepted.
I want this guy to be compensated, but I'd prefer this guy be compensated in a manner that doesn't prevent third parties from fixing their hardware. In general, I think bounties are a good solution to this. Failing that, there are plenty of trade groups and nonprofits and regulatory bodies that could be tasked (and funded) with acquiring and freely redistributing this class of innovation if we wanted to.
Apparently he did up until now, didn't he?
I agree he should get a percentage of the profits other companies make off of his invention, but it's not like he's entitled to any payments just because he liked to tinker around. Inventor's not a real profession.
Then that's their loss. This seems like the ideal scenario for patent protections: small inventor developing a genuinely novel and useful invention that big, rich companies would otherwise shamelessly copy.
https://ploum.net/working-with-patents/
> Note that by « valid », I mean that the Patent Office didn’t found a trivial prior art for this. It doesn’t mean that there is no prior art or that I’m the real inventor or that my invention works.
An example of an insane patent:
https://www.google.com/patents/US6960975
> Space vehicle propelled by the pressure of inflationary vacuum state US 6960975 B1
(via https://www.metabunk.org/do-patents-mean-the-invention-works... )
Apparently, there were design reasons why for electronic calculations a different mathematical formulation was more efficient. The competing manufacturers would discover this fact one by one, and Zuse was worried that someone may question his integriry, thinking he was the source of the leak. But no one did.
Michael Hanack (the materials chemist) used a different strategy: he would not patent anything so his inventions could be used my any market participant, and he would consult for all of them.
On the other hand, everyone is looking forward to the day the aptamer patent runs out. Uptake is limited (and you'd think that CRISPR/CAS9 has the same problem) because of unreasonableness (in case of CRISPR uncertainty) around licensing.
There's a reason Linux and GNU utilities are so massively widely used, and overall they've probably provided billions in economic value. They do that freely, for any human to use, and in fact that's part of their main value proposition. Both were born out of the legal nightmare that was UNIX at the time.
How should he get paid for this? In a very-ideal world, people and corporations that used his idea and had spare capital would voluntarily give him donations. In a better-than-this world, governments (or some other entity) would pay bounties to inventories out of a pool of tax money, based on both perceived usefulness of the invention and how widespread its use came to be.
It depends on whether he would consider the filing's "invention" to be within a reasonable definition of what should be patentable.
If yes, then he's just playing his part in our society's overall machinations for technical progress, and there's nothing really blameworthy about the filing.
If no, then he's being deeply selfish: He's capitalizing on the government's unjustified encroachment on our individual liberties, via the patent system, for his own personal gain.
For people who are writing novel software it can be better to always avoid reading patents, that way they can honestly state they haven't read a specific patent.
Perverse incentives indeed.
The first clause in your sentence is exactly what patents are for; the second clause is...tangential at best.
Obviously 1) is a greater public good than 2), but in reality these are not the only options.
Here's some other realistic situations: 3) With no incentives to make things public, this guy either stops working on this much earlier, doesn't tell anyone, or throws it in the garbage. 4) This guy goes and talks to Intel about his design. They quietly pay him some money or hire him and implement it in secret. Two years from now they launch a processor with this feature and for the indefinite future, until their competitors spend costly time reverse engineering the secret hardware, only Intel processors have this circuit. 5) Same as 4) except Intel says, "Haha, thanks for being a sucker" and doesn't pay anyone.
This is the patent system at its best: incentivizing some guy to work on this invention, then publish his work and describe it in detail. For the next 20 years, he can license it to anyone he wants and profit from his work. After that point everyone can implement it as a public good.
Patents, like any monopoly-granting device, benefit market incumbents much more than encourage new entrants
However, some of the case law around what they'd need to patent the turned unfavorable around the time they were pursuing this and looking to turn it into a business. For your reasons 3) and 5), they've shelved it. This was an individual, not a large company, and without sufficient legal protection to reasonably hold large companies at bay, there simply was not sufficient reason to pursue this effort given how questionable the return would be.
Ideally, that would be how patents are "supposed" to be use: An idea you patent can be used by others in exchange for a royalty fee. In reality, that happens quite a bit, but we also get anti-competitive tech companies who wish to keep advances to themselves, and patent trolls who wait on violations to sue.
> Michael Hanack (the materials chemist) used a different strategy: he would not patent anything so his inventions could be used my any market participant, and he would consult for all of them.
That won't work if the invention is easily copied. Chemistry is tricky and there's probably plenty of money to be made in consulting in it. A lot of industries aren't like that.
In the sciences you'll notice that simultaneous discoveries are nothing unusual, once the groundwork is laid the idea hangs in the air, you do nothing but reach out and catch it. The Zuse example is just another instance.
In the case of mathematics and computing, the invention can be copied easily by development costs are minimal as well. These is no compelling reason why someone should reap disproportionate rewards from a government-supported artificial monopoly. Progress suffers and the economy as well.
Yes there is: because of the effort of invention. The effort required to copy is irrelevant. Also, by arguing against patents, you're basically arguing that Intel and the like should get a huge payday at the expense of this guy's efforts.
Patents only last for 20 years [1], and it's not like progress stops when they're in force. Have some patience.
Offering an alternative to that is why the patent system was created. The idea is you publish and in return get a monopoly for a short period of time. Of course the system is abused (all systems are abused), but the reasons for its creation were actually quite "liberal."
What strikes me as odd is that in my intro course to numerical methods taught how to calculate floating point error bounds when introducing the concept of floating point numbers, including how errors propagated with each flop.
Not sure if you were taught a different method, but I envision this being similar to counting "significant digits" in scientific notation, and it sounds like that's very similar to the approach he took. I wonder if that explains there statements about tracking to the last "digit". They obviously can't do that for irrational number, so maybe they mean the last "significant" digit as far as the underlying floating point implementation is concerned.
So in that case, "[it] allows representation of real numbers accurate to the last digit" doesn't really hold true.
That's how I read it.
So how do you then store this number to the final digit or final -1 digit using this mechanism?
Many people attack companies that use tax loopholes even though the government does "allow" these loopholes. So if one is opposed to something, but it is formally allowed, one should attack both sides: The people doing it and the government.
Your correlation doesn't hold up because tax loopholes are not formally allowed. You call that out in your previous sentence by scare-quoting "allow". The inventor uses a formal system (patents). The company uses an informal system (tax loopholes). In the case of a formal system, you do not attack the inventor because he is just using the proper channel. In the case of an informal system, you do attack the company because the company is unethically taking advantage of a channel that shouldn't be there in the first place.
[0]: The original "Free as in speech" seems to be a much better way to express your sentiment.
https://en.wikipedia.org/wiki/Alice_Corp._v._CLS_Bank_Intern...
The boundaries are fluent (FPGAs).
> Almost all
I love this comment because it brings back memories of school.
In a layman's terms, I think almost all in this case means all but a finite amount
can we say almost all real numbers are irrational?
1 1/1 2/1 3/1 4/1 5/1 ... 2 1/2 2/2 3/2 4/2 5/2 ... 3 ...
so clearly we can count all the rational numbers but how many irrational numbers are there? are there (many) more irrational numbers than there are rational numbers?
http://austinrochford.com/posts/2013-12-31-almost-no-rationa...
So all of the irrationals that we use or could ever use in calculations are countable. The uncountability of the irrationals comes entirely from the uncomputable ones, which we will probably never see.
The reals are deeply weird.
Infinity is funny like that.
The conclusion that there are somehow more irrationals than rationals depends on subtle philosophical points that have no possible proof or disproof and usually get glossed over. Accepting that philosophy also leads to the conclusion that not only do numbers which can in no way ever be represented exist, but there are more of them than numbers which we can explicitly name. Now I ask you, in what sense do they REALLY exist?
If so, here's a simple argument: If you have N rational numbers and I have K irrationals to start with, I can produce roughly N*K additional irrationals. Since we know at least two irrationals (pi and e) we can make at least twice as many irrationals as rationals.
0 <-> 1
1 <-> 3
2 <-> 5
:
I'm curious, how?
As 1/3 - exactly as it's on your screen. All rational numbers can be represented exactly.
Is possible to convert to rationals in calculations?
So if I do:
1/3 + 4 + sum / total it record values properly?
Sure, there are times when space or speed concerns favor inexact representation over correctness, but that's an optimization that ought to be properly evaluated; the fact that lots of languages are designed in a way which makes it the default everyone reaches for contributes to lots of errors.
struct rational {
int numerator;
int denominator;
};Patents were explicitly created to avoid, "incentivize holding back global progress for small amounts of individual enrichment." The other realistic alternative is keeping the invention a trade secret, which is much worse for progress.
> How should he get paid for this? In a very-ideal world, people and corporations that used his idea and had spare capital would voluntarily give him donations.
That sounds exactly like how patents work except with no protections for the inventor. With a patents, the corporations that use the idea do give the inventor donations called license fees, but they can't screw him over and pay him less than he's worth (which they would otherwise do so they can keep the profits for themselves).
Basically, it sounds like you're proposing worse, more awkward systems because you irrationally hate the concept of patents for some reason.
1 - It's not holding back anything. If this invention has any merit, it will be licensed and society at large will benefit from it.
2 - Incentive. If this inventor could not make a guaranteed profit from this idea, I imagine he could have found more interesting ways to spend his time than playing with floating point numeric representations. It's not like he stumbled upon this on the road and then hid it from society. He set out to create things like this as a means of sustaining himself and improving the world at the same time.
3 - The reason markets are useful is because they work phenomenally well at determining value. As we swapped to currency operated markets over barter, nobody ruled a chicken was worth 3 coins, a pig 10, and a cow 25. Instead market forces decided, and tend to do better than any other means of measuring value. Donations, let alone bureaucracy, are extremely poor substitutes in determining the value of anything. Their ideal would be to approach market force level efficiency. This isn't to say markets are flawless, but rather they're a whole let less flawed than any alternative.
Issue with patent system is that it's real implementations are gameable, not with the idea itself.
Most people are not little philosopher kings who work to advance a grand vision of life's unfolding in the universe. Most people just want to do the minimum to get by until they can get their next dose of entertainment. I hate to be such a cynic, but I have eyes.
Social democracy (Europe, USA to a lesser extent) is a hybrid that basically works but you still have to make money in that system.
Whether it's capitalism with a large dose of socialism of socialism or socialism with a large dose of capitalism, neither extreme seems to work as well as approaches that adopt portions of both.
> Most people are not little philosopher kings who work to advance a grand vision of life's unfolding in the universe. Most people just want to do the minimum to get by until they can get their next dose of entertainment. I hate to be such a cynic, but I have eyes.
I think the only people that actually work to advance understanding of the universe do so for selfish reasons, and we all just get to benefit from the byproduct of their self interest. If I had to guess whether Einstein of Newton did what they did because they wanted every human to be better of, or if it was primarily because that's what they enjoyed doing and they were lucky enough to be in circumstances that allowed them to live doing that (and become famous as well), I know where I'd place my bet.
It's the same for child rearing. There's a sense of happiness and contentment when your children are happy and safe (or at a minimum there's usually uneasiness and dread when your children are unhappy or unsafe), so you try to make that the situation the one that makes you the most comfortable happy. It's an instinctual and emotional response, but doesn't necessarily make sense from a purely rational self-interest point of view.
We aren't saints, we're machines with wacky firmware that imparts interesting and had to evaluate value functions.
Patents don't hold back global progress any more than capitalism keeps people in poverty. If we went back a few hundred years and impose alternatives, would we be better off today? I doubt it.
The whole point of the patent system is to foster innovation, and free exchange of ideas. Without the patent system, people are incentivized to keep their inventions secret, and hide how they work, but patents require publishing the details. Some companies don't patent some things just so they can keep it secret.
The problem with the patent system is not the concept of patents, but what they've been allowed to apply to and how long the terms have increased.
Him patenting the idea meanshe has control over his options. It also prevents another entity, such as Intel or AMD discovering it and patenting it. If he wants, he can make it free to use for non-profiting or open source entities.
Edit: The capitalism / poverty comparison is meant to infer communism, as the alternative to a competition and financially motivated system. I don't think it's contentious to say capitalism ended up being the better system for getting people's standard of living raised, even is communism sounds good on paper. I don't think the relation to the patent system in comparison to some ideal sounding solution where people get some money somehow for giving their ideas to the world immediately is all that strained.
And if it seems like the patent system is being gamed to hinder innovation (not really in this case, but yes absolutely in the case of pharma) it should be revisited. Intellectual property laws are based in pragmatism, not natural law. If the costs begin to outweigh the benefits, they should be changed.
Thanks. I was worried I would go the whole day without spitting out my drink.
Even if it was purely mathematics, I think I would rather have someone patent it if possible and make it freely available than to leave it out and have someone else take a stab at patenting it, have the underfunded patent office fail to realize there is prior art, and grant the patent. Sure, you could effectively fight it, but until the system gets reformed enough to prevent most these abused, that's a lot of wasted resources (and having the patent lets them threaten others with it without actually bringing a case that could invalidate it).
Patents aren't copyrights. The term for patents is only about 20 years.
In any case, I don't think we should immediately vilify someone for using the patent system (and using it as originally intended, IMO), just because we are unhappy with the way it's been abused recently, as I think it has provided us great benefit over it's existence.
Where is the problem with such positions?
It's better, when you're arguing on the internet, to limit yourself to reasonable arguments that people are receptive to, and working to convince people.
I used to feel very strongly about patents (that they were "wrong") but, over time I've come to believe they are the least unreasonable protection for IP that also encourages long-term sharing. Trade secrets are worse because society as a whole doesn't get to benefit.
Would some ideal-world type situation for patents work? I doubt it. We have patents, and there are some upsides to that system, even if it has been abused recently. I think people have transferred a lot of their anger at the abuses to the concept of patents themselves. Here we have someone that patented something, and people are upset that he did that before knowing how he intends to use the patent. The patent could be free for non-commercial use. It could be free for many things. Or it could be that it's most likely to be used in hardware by a large corporation that prints chips and not individuals, and he'll license it to them and the most anyone will see of it is a few cents added to the production cost of each chip (not that anyone even knows what that is, since retail chip pricing is so crazy).
How we measure a system shouldn't be based on just the biggest successes and biggest problems (but those should be looked at), but on the long track record of what it does and how it performs. In that light, I think capitalism has shown itself a better system in the long run, and I think patents have shown their merit in the long run as well.
Can you elaborate? The proof that there are more irrationals than rationals is very straightforward, from my perspective.
In Constructivism, all statements have 3 possible values, not 2. They are true, false, and not proven. All possible objects must have a construction. So instead of talking about a vague "Cauchy sequence", we might instead have a computer program that given n will return a rational within 1/n of the answer.
The first thing to notice is that all possible things that could exist is contained within a countable set of all possible constructions. There can't be "more" irrationals than rationals.
But what about diagonalization? That proof still works. You still can't enumerate the reals. But why not? The answer is because determining whether a given program represents a real is a decision problem that cannot in general be solved by any algorithm. You are running into the same category of challenges that lie behind Gödel's theorem and The Halting Problem. It is not that there are "more" irrationals than rationals. It is that there are specific programs which you can't decide whether they represent reals.
From a constructivist's eyes, the traditional proof that there are more irrationals falls apart because you're reasoning about unprovable statements about arbitrary sequences whose logic could have been constructed with the same sort of logic that you're applying to them. Is it any wonder that you wind up concluding the "existence" of things that clearly don't actually exist?
Now stepping back from BOTH philosophies, the differences between them lie in different attitudes about existence and truth. Attitudes that underly the axioms which we use, and cannot possibly be proven one way or another. (Gödel actually proved that. Any contradiction in Constructivism is immediately a contradiction in classical mathematics. But conversely there is a purely mechanical transformation of any proof in classical mathematics which resulted in a contradiction, into a constructive proof that also results in a contradiction.)
However there is no logical argument that can disprove the constructivist view, in which there aren't "more" irrationals than rationals. And therefore the logical argument that there is must have some hidden implicit assumptions.
This is about as consequential as debating whether 1 is a prime number.