11 ms·
Inventor Claims to Have Solved Floating Point Error Problem
- payne92 9y agoHere’s the issued patent: https://www.google.com/patents/US9817662 https://www.google.com/patents/US9817662 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.
- everybodyknows 9y agoThe beauty of the patent is that it will never be tested, being of no practical value, for numerous reasons already mentioned in other comments, plus a few more not worth the bother of going into. 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 https://news.ycombinator.com/item?id=16015371
- payne92 9y ago"Win-win"...not at all. 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.
- speps 9y agoAnd immediately patents it... so no one else can use it. EDIT: and for some other methods: https://en.wikipedia.org/wiki/Unum_%28number_format%29 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 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.
- neilsimp1 9y agoI mean, it's unfortunate, but can you blame him?
- InclinedPlane 9y agoYes.
- algorithmsRcool 9y agoAt a glance this reads similar to Interval Arithmetic in that it places bounds on how much error a value carries. Is there something more novel to his approach? https://en.wikipedia.org/wiki/Interval_arithmetic https://en.wikipedia.org/wiki/Interval_arithmetic
- mark-r 9y agoI think the novel part is in the encoding of the error in the bits of the value. It's hard to see how much value this patent really holds.
- danbruc 9y agoWithout reading the patent it sounds a lot like interval arithmetic [1] which sounds like a really good idea at first but is not without its own problems. For example the inverse 1/x for an interval x like [-1,+1] containing 0 consists of two intervals (-∞,-1] and [+1;+∞). [1] https://en.wikipedia.org/wiki/Interval_arithmetic https://en.wikipedia.org/wiki/Interval_arithmetic
- nraynaud 9y ago"In addition, though the embodiment presented herein represents an apparatus and associated method for bounded floating point addition and subtraction, it is presented as an example of bounded floating point operations. By extension, the same inventive apparatus for calculating and retaining a bound on error during floating point operations can be used in other floating point operations such as multiplication, division, square root, multiply-add, and other floating point functions." The hard part has been left as an exercise for the examiner.
- relate 9y agoIn your example, this would correspond to having the number x = 0 +-1 and then wanting to compute 1/x. If your number can potentially be zero, why would you want to use it as a divisor?
- danbruc 9y agoThe problem remains if you wrap the division in a non-zero check. Or maybe the interval [-1,+1] is already kind of a lie, i.e. x is known to be in the interval but you additionally know that x is non-zero when you are about to perform the division. The example is just meant to illustrate the problem that using a single interval is not good enough to track error bounds in the general case.
- whyever 9y agoYou could always just return nan in that case, like for normal arithmetic.
- 9y ago
- ajennings 9y agoIs this different from/better than? unums: https://en.wikipedia.org/wiki/Unum_(number_format) https://en.wikipedia.org/wiki/Unum_(number_format) interval arithmetic: https://en.wikipedia.org/wiki/Interval_arithmetic https://en.wikipedia.org/wiki/Interval_arithmetic
- lisper 9y agoNo.
- deleted 9y ago[deleted]
- ronnybrendel2 9y agoIs this https://en.wikipedia.org/wiki/Interval_arithmetic https://en.wikipedia.org/wiki/Interval_arithmetic ? I.e. you carry the lower and upper bound all the way?
- jmull 9y agoIn the patent he contrasts his "apparatus" with interval arithmetic. He says IA greatly increase computation (while his method doesn't) and requires twice as much storage (while his method doesn't. 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.
- simias 9y ago>The inventor patented a process that addresses floating point errors by computing “two limits (or bounds) that contain the represented real number. These bounds are carried through successive calculations. When the calculated result is no longer sufficiently accurate the result is so marked, as are all further calculations made using that value.” 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.
- wyldfire 9y ago> a floating point operation raises the "inaccurate" flag, how do you deal with that? You can trap. ...but then again, existing arithmetic traps are not uniformly enabled by default.
- chmike 9y agoThis looks so obvious. How could this be patented ? The real question is why no one already implemented it ? It wouldn't surprise me if it already exist.
- DonaldFisk 9y agoIf no one's thought of it before, how can it be obvious? If they have thought of it, the prior art can be brought to the attention of the patent office and the patent invalidated.
- cwmma 9y agoPatent in case anyone is curious https://encrypted.google.com/patents/US9817662 https://encrypted.google.com/patents/US9817662
- deleted 9y ago[deleted]
- gvb 9y agoThanks for the link. 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.
- pacaro 9y agoThe usual advice w.r.t. patents is to not read them. 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
- amdavidson 9y agoUnless you are planning to infringe (which is knowing in itself), this is very bizarre advice. Reading a patent is more likely to make you not infringe upon it than to make you knowingly infringe upon it.
- justrobert 9y agoReading a patent will make you not infringe in the short term, but will you remember you got the idea from that patent in ten years? 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.
- mark-r 9y agoAccidental infringement is possible whether you've read the patent or not. I was once told not to even mention the possibility of the existence of a patent as that would be evidence used to go for triple damages. Perverse incentives indeed.
- ktpsns 9y agoEven worse, a patent for a "processor design, which allows representation of real numbers accurate to the last digit" is obviously nonsense. Pi (=3.141...) is a real number where there is no "last digit".
- leetcrew 9y agoI assume it means accurate to the last digit of the representation, not the number being represented. obviously the latter would be absurd to suggest.
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]
- nraynaud 9y agoit's the patent for a circuit, and you can take the the sentence the other way around "the displayed number is the denoted one", not "any real number can be represented".
- meuk 9y agoI think he describes a procedure which guarantees that the last digit of the representation is exact. So that we (in decimal) can have 3.14 as a representation for pi, but never 3.13 or 3.15. But this is hardly 'solving floating point errors' and hardly novel. 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).
- gibrown 9y agoIt doesn't actually sound like he "solved" it. More like he put error bounds around it and can detect when the error is more than X. > 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 https://www.google.com/search?q=floating+point+error+bounds
- cavanasm 9y agoIANAL, but if other companies have already done it and it's that easy to find, then it wouldn't be a good patent troll, because there's obvious and easily discoverable prior art (which would invalidate the patent anyway).
- agar 9y agoConsidering the over-the-top language ("a game changer for the computing industry") and questionable or imprecise comments like, "[it] allows representation of real numbers accurate to the last digit" (um, who reads that without thinking of irrational numbers?) it sounds too much like a sales pitch and not like serious research. 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.
- nraynaud 9y agoit's a journalist writing the article, they want clickbait.
- iiv 9y agoThe journalist quoted the "inventor".
- TallGuyShort 9y agoOr a PR person was involved. I've been quoted in press releases saying stuff I never said, and it's par for the course, apparently.
- nraynaud 9y agoyou are right, I went to read the PR after commenting, it's cringy.
- matt4077 9y agoHow can it be "clickbait" if it's in the article? What am I supposed to click on? 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.
- known 9y agoHas he solved http://0.30000000000000004.com/ http://0.30000000000000004.com/
- shmolyneaux 9y agoNot really, the idea is to store the amount of error in the binary representation of the number. When converting from decimal "0.3" to this floating point representation, it's more like 0.30000000000000004 ± 0.00000000000000004
- cvoss 9y agoI don't think he has. With his approach you would get results that are honest about their precision, like '3 plus-or-minus .0000000000000010'. That still doesn't help you decide whether or not the result is actually 3.
- whyever 9y ago> “In the current art, static error analysis requires significant mathematical analysis and cannot determine actual error in real time,” reads a section of the patent. “This work must be done by highly skilled mathematician programmers. Therefore, error analysis is only used for critical projects because of the greatly increased cost and time required. In contrast, the present invention provides error computation in real time with, at most, a small increase in computation time and a small increase in the maximum number of bits available for the significand.” 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 https://github.com/fredrik-johansson/arb
- bringtheaction 9y agoDoes anyone know a similar library for Rust?
- whyever 9y agoArb depends on lots of other numerical libraries (namely FLINT, MPFR and GMP or MPIR). If you want pure-Rust alternatives, the ecosystem is just not there yet.
- fdej 9y agoIt's a plain C library with an API very similar to GMP, so an option would be to wrap it from Rust, which should not be too difficult.
- fdej 9y agoI'm the main author of Arb. Note that it's an arbitrary-precision library. It's ~100x times slower than hardware floating-point because of using arbitrary-precision floating-point numbers implemented entirely in software. But if you have to do arbitrary-precision arithmetic to begin with, Arb's error tracking only adds negligible further overhead. 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.
- sundarurfriend 9y ago> “Apparatus for Calculating and Retaining a Bound on Error During Floating Point Operations and Methods Thereof” 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.
- ben11kehoe 9y agoMathematica has the cool ability to do symbolic tracking of numerical precision, for the ability to tell you when, for example, your differential equation solver is giving you meaningless results.
- exabrial 9y agoIs there a reason why we can't have that as a compiler warning?
- dragontamer 9y agoBecause it depends on the algorithms you put a float through. 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)
- DougBTX 9y agoYes you can, if your programming language supports dependent types: https://bluishcoder.co.nz/2013/05/07/ranged-integer-types-and-bounds-checking.html https://bluishcoder.co.nz/2013/05/07/ranged-integer-types-an...
- shmolyneaux 9y agoThe floating point error problem has not been solved. This patent describes a floating-point representation that includes fields for storing error information. The standard IEEE floating-point representation has three fields: a sign field, an exponent field, and a mantissa (or significand). This patent proposes reducing the size of other fields and adding additional fields to store error information. The error information would be updated by hardware during regular operations. The patent proposed adding a configurable amount of precision to the numbers. If an operation exceeds this limit, an insufficient significant bits signal "sNaN(isb)" would be raised. 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.
- _bxg1 9y agoYeah. It seems like just a clever mitigation technique, which could prove useful in the fields he mentioned (military, industrial, etc.), but it's far from the wholesale solution he claims.
- enervate 9y agohow is this better than checking if its within some value by some epsilon manually?
- kbenson 9y agoIt depends on how you interpret "floating point error". If by that you mean the error the error inherent in the representation, it actually increases that through loss of precision, as you note. If you interpret it as "problems caused by lack of precision in floating point" (i.e. the patriot missile problem references in the article is a "floating point error"), then the tracking of precision will allow you to easily know when you've hit an error threshold that is unacceptable, allowing you to avoid those problems.
- jovial_cavalier 9y ago> If an operation exceeds this limit, an insufficient significant bits signal "sNaN(isb)" would be raised. What about for binary repeating decimals like 0.3? Wouldn't it always raise that signal?
- umanwizard 9y agoObvious crank.
- Dangeranger 9y agoWouldn't something like what Douglas Crockford built with DEC64 be more useful and practical?[0] [0] http://dec64.com/ http://dec64.com/
- ggggtez 9y agoYou can't patent math.
- titzer 9y agoHe reinvented interval arithmetic, it sounds like. 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.
- hedora 9y agoUnless the article is missing some important nuances, this is just "range arithmetic" or "interval arithmetic"from the 1950's. Here's a wikipedia page explaining how it works: https://en.wikipedia.org/wiki/Interval_arithmetic https://en.wikipedia.org/wiki/Interval_arithmetic
- tomxor 9y agoTerrible title with a terrible description of the invention. What he is doing appears so be interval arithmetic: https://en.wikipedia.org/wiki/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.
- pizza 9y agoHere's a link to the patent https://patents.google.com/patent/US9817662B2/en?oq=No.+9%2c817%2c662 https://patents.google.com/patent/US9817662B2/en?oq=No.+9%2c...
- tlb 9y agoI wrote an interval arithmetic package once too. It was slow, because it had to change the FP rounding flags multiple times for some operations. 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.
- beyondCritics 9y agoThis appears to be complete nonsense.