1.99999999.... == 2.0
There are limits to computer representation of floating point numbers. Computers are finite state, floating point numbers are not.
sigh
No, floating point numbers are finite state. That’s the whole point behind this discussion. There are only so many possible floating point numbers representable in so many bits.
I never understand this confusion - you have finite memory - with this you can only represent a finite set of real numbers. So of course all the real numbers can’t be mapped directly.
This confusion is also helped along by the fact that the input and output of such numbers is generally still done in decimal, often rounded, that both decimal and binary can exactly represent the integers with a finite number of digits, and that the set of numbers exactly representable with in a finite decimal expansion is a superset of those exactly representable in a finite binary expansion (since 2 is a factor of 10).
bc <<< "0.1 + 0.2"
.3
bc <<< "1.0E4096 +1 -1.0E4096"
1.000000
node -e "console.log(1.0E128 +1 -1.0E128)"
0
python -c "print(1.0E128 +1 -1.0E128)"
0.0
The focus should be on _rational_ numbers. This particular example is all about representation error - precision is implicated, but not the cause.
Ignore precision for a second: The inputs 0.1 and 0.2 are intended to be _rational_. This means they can be accurately represented finitely (unlike an irrational number like PI). Now when using fractions they can _always_ be accurately represented finitely in any base:
1/10=
base 10: 1/10
base 2: 1/1010
2/10=
base 10: 2/10
base 2: 10/1010
This is the key: rationals cannot always be represented finitely in floating point formats, but this is merely an artifact of the format and the base. Different bases have different capabilities:
1/10=
base 10: 0.1
base 2: 0.00011001100110011r
2/10=
base 10: 0.2
base 2: 0.00110011001100110r
1/3=
base 10: 0.33333333333333333r
base 2: 0.01010101010101010r
If you can grok that key point (representation error), here's the real understanding of this problem:
Deception 1: The parser has to convert '0.1' decimal into base 2, which will cause the periodic significand '1001100110011' (not accurately stored at any precision)... yet when you ask for it back, the formater magically converts it to '0.1' why? because the parser and formater have symmetrical error :) This is kinda deceptive, because it makes it look like storage is accurate if you don't know what's going on under the hood.
Deception 2: Many combinations of arithmetic on simple rational decimal inputs also have rational outputs from the formatter, which furthers the illusion. For example, nether 0.1 or 0.3 are representable in base 2, yet 0.1 + 0.3 will be formatted to '0.4' why? It just happens that the arithmetic on those inaccurate representations added up to the same error that the parser produces when parsing '0.4', and since the parser and formatter produce symmetric error, the output is a rational decimal.
Deception 3: Most of us grew up with calculators, or even software calculator programs. All of these usually round display values to 10 significant decimals by default, which is quite a bit less than the max decimal output of a double. This always conceals any small representation errors output by the formatter after arithmetic on rational decimal inputs - which makes calculators look infallible when doing simple math.
Edit: this is not a blanket statement. It was meant in the context.
Floating point is extremely useful. Too bad so many people have no idea how and when to use it. Including some people that design programming languages.
Please, tell me, mister, how would you perform complex numerical calculations efficiently?
I guess we should just forget about drones and bunch other stuff because 90% of developers have no clue how to use FP?
var n = get_n() // valid to .5g
n = transform(n)
...
<input value={n.toFixed(5)}> // 5 carried over here
In a proper-numbers lang, if someone needed FP numbers, they could just 0.1f. Otherwise 0.1 would mean just that, and counting by 0.1+rand(100) from 1000000 to 0 would not make you scratch your head at the end of the loop and worry whether the rest is just a FP error or an algorithmic error which must be fixed.
90% of developers who know how to use FP still hate it in non-FP tasks, because there is no 0.1nobs literal, how about that.
If your calculation turned out to be incorrect it doesn't matter if it's efficient. Correct FP calculation requires error analysis, which is a concrete definition of "how to use it". If you mostly use packaged routines like LAPACK, then you don't exactly need FP; you need routines that internally use FP.
(While decimal fixed point does solve this particular problem, the part that solves it is the decimal, not the fixed point. Decimal floating point is equally capable of adding 0.1 to 0.2)
No, it does not. Please, don't make it seem harder than it needs to.
99% applications, if you don't do anything stupid you are completely fine.
If you care for precision so much the last digit make difference for you you are probably one of very few cases. I remember somebody giving an example circumference of solar system showing uncertainty of the value of Pi available as FP to cause couple centimeters of error at the orbit of Pluto, or something like that.
(Edit: found it: https://kottke.org/16/03/how-many-digits-of-pi-does-nasa-use)
Most of the time floating point input is already coming with its own error, you are just adding calculation error to the input uncertainty. But the calculation error is so much smaller than in most cases it is safe to ignore it.
For example, if you program a drone, you have readings from IMU which have not nearly the precision of the double or even float you will be working on.
There is also various techniques of ordering the operations to minimize the resulting error. If you are aware which kinds of operations in which situations can cause huge resulting error it is usually very easy to avoid it.
Only very special case is if you try to subtract two values calculated separately and matching almost exactly. This should be avoided.
This is a common misconception. Or "anything stupid" is quite broader than you think.
The main issue with FP arithmetic is that effectively every calculation incurs an error. You seem to aware of catastrophic cancellation, but it is problematic not because of the cancellation but because the error is proportional to the input, which can wildly vary after the cancellation. Non-catastrophic cancellation can still cause big errors in a long run for a large range of magnitudes. A long-running process thus requires some guard against FP errors, even if it's just a reality check (like, every object in the game should be in a skybox).
Alternatively you do not run a long-running process. I don't think you fly a drone for days? Probably you won't fly a drone that long even without FP, but using FP does prohibit many things and thus affects your decision. For example game simulations tend to avoid FP because it can accumulate errors and it is also hard to do FP calculation in a repeatable way (in typical environments). If I chose to use FP for simulations I effectively give up running simulations both in servers and clients---that kind of things.
My controller running moving horizon estimator to simulate thermal system of the espresso machine and Kalman filters to correct model parameters against measurements runs 50 times a second and works fine for days, thank you, using floats on STM32.
I have written huge amount of embedded software over past 20 years and I am yet to do any error analysis with focus on actual floating point inaccuracy. Never saw any reduced performance of any of my devices due to FP inaccuracy. That's because I know what kind of things can cause those artifacts and I just don't do that stupid shit.
What you describe are just no-noes you should not be doing in software.
There exists huge amount of software that works for years at a time, heavy in FP math, and it works completely fine.
If drones were not limited in flight time they would also work fine because what you describe is just stupid errors and not a necessity when using FP math.
Game simulations don't use FP mostly because it is expensive. Fixed point is still faster and you can approximate results of most calculations or use look up tables to get the result that is just fine.
Some games (notably Quake 1 on the source code which I worked after it became available) do require that the simulation results between client and server are in lockstep but this is in no way necessity. Requiring lockstep between client and server causes lag.
What newer games do, they allow client and server run simulations independently even when they don't agree exactly, and then reconcile the results from time to time.
If you ever saw your game partner "stutter" in flight, that was exactly what happened -- the client and the server coming to an agreement on what is actual reality and moving stuff into its right place.
In that light, there is absolutely no problem if after couple of frames the object differs from official position by 1 tenth of a pixel, it is going to get corrected soon.
Go do your "error analysis" if you feel so compelled, but don't be telling people this is necessary or the software isn't going to work. Because that's just stupid. Maybe NASA does this. You don't need to.
In this case, "doing anything stupid" includes equality checks. This is the sort of footgun that a huge number of people are going to run into.
The representation means that 2.9999999999 = 3.00000000
I am not confused. You cannot use equality in floating point. Why is anybody surprised by that? That is my point
(I did say floating point before when I ment real. A bit confused!)
I wasn't saying you were confused, I was saying I believe I understand how the general confusion around the whole issue arises.
(If decimal floating point had been commonly used instead of binary, the same class of issues would still exist, but I don't think people would be nearly so surprised by them).
Incidentally: the fact that 0.1+0.2 does not equal 0.3 is not something you could quibble with, that is absolutely reasonable for a floating point standard. It would be insanity to base it off of base 10 instead of base 2.
- Keep rational numbers; you also have an unbounded integer so that's to be expected. (Well, unbounded integers are visible, while unbounded denominators are mostly invisble. For example it is very rare to explicitly test denominators.)
- Use decimal types with precision controlled in run time, like Python `decimal` module. (That's still inexact, also we need some heavy language and/or runtime support for varying precision.)
- Use interval arithmetic with ordinary floating point numbers. (This would be okay only if every user knows pitfalls of IA: for example, comparison no longer returns true or false but also "unsure". There may be some clever language constructs that can make this doable though.)
- You don't have real numbers, just integers. (I think this is actually okay for surprisingly large use cases, but not all.)
[1] https://python-history.blogspot.com/2009/02/early-language-d... (search for "anecdote")
There are also many classes of softwares where FP inaccuracy is simply no problem---such as 3D rendering where the worst FP error is probably z-fighting. Not every application of FP requires "correct" calculation.
> What newer games do, they allow client and server run simulations independently even when they don't agree exactly, and then reconcile the results from time to time.
That's not what "newer" games do, it's what games that can withstand the trade-off do. In particular if the outcome of a particular action is crucial to players you can't reconcile that (projectiles are canonical examples); once the player observed the outcome it's done. Reconcilation thus typically happens in the animation level, so that it can hide the delay until the outcome is observed. This does not actually require the simulation---an simple interpolation is frequent AFAIK---so your point is irrelevant.
There are several genres of games where the lockstep simulation remains pretty much the only way, and thus FP is discouraged. Not because FP is expensive, which had been false for quite a long time anyway (no game developer uses the "fast" inverse square root algorithm any more).
What you need to avoid using is special functions that can vary based on your CPU model. Once you do that, integer lockstep and floating point lockstep are of similar difficulty.
The closest you can get is some systems like Matlab/Octave that specialize in working with numbers.
I just suspect that alternatives bite people less frequently than floating point does.
0.1 + 0.2 != 0.3
This actually makes me wonder if anyone's ever attempted a floating-point representation that builds in an error range, and correctly propagated/amplified error over operations.
E.g. a simple operation like "1 / 10" (to generate 0.1) would be stored not as a single floating-point value, but really as the range between the closest representation greater than and less than it. The same with "2 / 10", and then when asking if 0.1 + 0.2 == 0.3, it would find an overlap in ranges between the left-hand and right-hand sides and return true. Every floating-point operation would then take and return these ranges.
Then floating point arithmetic could be used to actually reliably test equality without ever generating false negatives. And if you examined the result of calculation of 10,000 operations, you'd also be able to get a sense of how off it might maximally be.
I've search online and can't find anything like it, though maybe I'm missing an important keyword.
Yes, that turns out to be exactly it [1]. Looks like there's even at least one JavaScript library for it [2].
It seems like such a useful and intuitive idea I have to wonder why it isn't a primitive in any of the common programming languages.
The problem is that the user wants to write 1/10 and 2/20 and 3/10 but those numbers aren't really in the binary system.
The user gets some numbers (let's call them A, B and C) that aren't the same but they fool people at first because they not only deserialize as 0.1 but the they also serialize from 0.1. Trouble is that A + B != C but some other number.
Excel tries to hide it but the real answer is to keep the exponent in base 10 if you plan to read and write numbers like 137.036 or 9.1E-31. How the mantissa is doesn't matter, it could be base 7 for all I care -- it is just an integer.
Interval math is for much tougher problems like recursion of
k * x * (1-x)
The flip side is that you generate plenty of false positives once your error ranges get large enough. This happens pretty readily if you e.g. perform iterations that are supposed to keep the numbers at roughly the same scale.
x---0.1 + 0.2 ---x
x---0.3---x
For me, floating-point equality would be if there are any parts that overlap. Basically "=" would mean "to the extent of the floating-point accuracy of this system, these values could be equal".
If you're doing a reasonably limited number of operations with values reasonably larger than the error range, then it would meet a lot of purposes -- you can add 0.5 somewhere in your code, subtract 0.5 elsewhere, and still rely on the value being equal to the original.
The equality test in floating point numbers is comparing against the epsilon.
Math.abs(0.3 - (0.1 + 0.2)) < Number.EPSILON
Using the epsilon for comparison is not mentioned in the article. Floating point absorption is also not mentioned in the article.
This entire discussion and the fact this is on the front page of HN is pretty disappointing and sad.
Is this really a surprise for you? if it is... have you ever implemented any logic involving currency? You may want to take another look at it.
Math.abs(1.8 - (0.1 + 0.2 + 0.9 + 0.6)) < Number.EPSILON
Also, you generally really shouldn't be implementing any currency logic using floating point numbers, yikes. Stick to integers that represent the value in cents, or tenths of cents, or similar. Or, even better, a DECIMAL data type if your platform supports it.
I genuinely hope you've never written financial software that judges if the results of two calculations are equal via the method you've described.
Floating point arithmetic is good enough for science, should be good enough for commerce too, no? Why is commerce special?
0.30000000000000004 - https://news.ycombinator.com/item?id=21686264 - Dec 2019 (402 comments)
0.30000000000000004 - https://news.ycombinator.com/item?id=14018450 - April 2017 (130 comments)
0.30000000000000004 - https://news.ycombinator.com/item?id=10558871 - Nov 2015 (240 comments)
0.30000000000000004 - https://news.ycombinator.com/item?id=1846926 - Oct 2010 (128 comments)
Resisting temptation to list floating-point math threads because there are so many:
https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...
This is the TXR Lisp interactive listener of TXR 256.
Quit with :quit or Ctrl-D on an empty line. Ctrl-X ? for cheatsheet.
TXR works even if the application surface is not free of dirt and grease.
1> (+ 0.1 0.2)
0.3
2> (set *print-flo-precision* 17)
17
3> (+ 0.1 0.2)
0.30000000000000004
4> 0.1
0.10000000000000001
5> 0.2
0.20000000000000001
6> 0.3
0.29999999999999999
The IEEE double format can store 15 decimal digits of precision such that all those decimal digits are recoverable. If we print values to no more than 15 digits, then things look "artificially clean" for situations like (+ 0.1 0.2).
I made *print-flo-precision* have an initial value of 15 for this reason.
The 64 bit double gives us 0.1, 0.2 and 0.3 to 15 digits of precision. If we round at that many digits, we don't see the trailing junk of representational error.
Unfortunately, to 15 digits of precision, the data type gives us two different 0.3's: the 0.299999... one and the 0.3.....04 one. Thus:
7> (= (+ 0.1 0.2) 0.3)
nil
From what I’ve seen with most recent grads, the education is shifting more and more towards algorithms, with experience mostly involving the use of existing libraries/frameworks, rather than lower level implementations that us “old timers” were forced to implement ourselves, thanks to lack of accessibility to freely usable code. I think GitHub, StackOverflow, and Google have changed the mental model of software development, significantly. I don’t think that’s a bad thing at all since it should free up some beans, especially for someone new to the field.
Not knowing this will bite you eventually, but it’s fairly trivial to work out.
"SELECT .1 + .2;" does return 0.3
However,
CREATE TABLE t1 (f FLOAT);
INSERT INTO t1 VALUES(0.1),(0.2);
SELECT SUM(f) FROM t1;
// returns 0.30000000447034836
https://en.wikipedia.org/wiki/Numerical_tower
One change I'd consider making to Scheme, and to most high-level general-purpose languages (that aren't specialized for number-crunching or systems programming), is to have the reader default to reading numeric literals as exact.
For example, the current behavior in Racket and Guile:
Welcome to Racket v7.3.
> (+ 0.1 0.2)
0.30000000000000004
> (+ #e0.1 #e0.2)
3/10
> (exact->inexact (+ #e0.1 #e0.2))
0.3
By default, that would give the programmer in this high-level language the expected behavior.
And systems programmers, people writing number-crunching code, would be able to add annotations when they want an imprecise float or an overflowable int.
(I'd also default to displaying exact fractional rational numbers using familiar decimal point conventions, not the fractional form in the example above.)
For example: just treat numbers as strings and write code that adds the digits one by one and does the right carries
Now that I think about it, is this the whole point of the Java BigDecimal class?
> all.equal(0.1+0.2,0.3)
[1] TRUE
> identical(0.1+0.2,0.3)
[1] FALSEand see me in the morning.
Coq < Compute 0.1.
Toplevel input, characters 8-11:
> Compute 0.1.
> ^^^
Warning: The constant 0.1 is not a binary64 floating-point value. A closest
value 0x1.999999999999ap-4 will be used and unambiguously printed
0.10000000000000001. [inexact-float,parsing]
= 0.10000000000000001
: floatWith proper rounding and I/O these are not generally an issue.
Specifically I'm thinking about python, the literal x.x should be for Decimal and float should have to be imported to be used as an optimization if you need it.
Complexity wise that actually seems to give an equally simple "shortest answer" method - nextafter up and down and using text processing find the first digit that changes, see if it can be zero, if not choose the lowest value it can be an increment by one, remove the rest of the string accordingly, and right trim any 0s from the resulting.
>>> 0.1 + 0.2
0.30000000000000004
If you don't want this to happen, use fixed-point numbers, if they're supported by your language, or integers with a shifted decimal point.
Personally, I think if you don't know this, it's not safe for you to write computer programs professionally, because this can have real consequences when dealing with currency.
http://pages.cs.wisc.edu/~david/courses/cs552/S12/handouts/g...
What controls this rounding?
e.g., in an interactive python prompt i get:
>>> b = 0.299999999999999988897769753748434595763683319091796875
>>> b
0.3[1] See my past comment for the overview: https://news.ycombinator.com/item?id=26054079
>>> f'{b:.54f}'
0.299999999999999988897769753748434595763683319091796875
>>> f'{x:.16g}'
0.3
>>> f'{x:.17g}'
0.29999999999999999 > 1.1 + 2.2
3.3
> 1.1 + 2.2 == 3.3
True
I think the problem is the act of caring for the least significant bits.
If you care for least significant bits of a floating point number it means you are doing something wrong. FP numbers should be treated as approximations.
More specifically, the problem above is assuming that floating point addition is associative to the point of giving you results that you can compare. In floating point order of operations matters for the least significant bits.
FP operations should be treated as incurring inherent error on each operation.
IEEE standard is there to make it easier to do repeatable calculations (for example be able to find regression in your code, compare against another implementation) and for you to be able to reason about the magnitude of the error.
Pencil-and-paper floating-point numbers like 1.23 x 10^5 are approximations of measurements (if we are doing science or engineering), but are inherently exact. Calculators bear that out, because calculators use base 10 floating-point, like pencil-and-paper calculations.
0.3 being inexact is only an artifact of the floating-point system being in a different base. No matter how many digits we throw at it, we cannot represent 0.3 in binary floating point. Not 64 bits, not 1024 bits, not 65535 bits.
If we use binary notation for floating-point numbers, they likewise become exact, in terms of representation. The inexactness we deal with then is the familiar type that we know from pencil-and-paper calculations: truncation to a certain number of digits after performing an operation like addition or multiplication.
But that truncation will not happen in a calculation in which both input operands are exactly represented, and the result is also exactly representable!!!
If base ten were used, 0.1 + 0.2 would be 0.3, exactly.
If we use power-of-two values, and combinations thereof, we don't have the problem:
1> (= 0.625 (+ 0.125 0.5))
t
2> (set *print-flo-precision* 17)
17
3> 0.625
0.625
4> 0.5
0.5
5> 0.125
0.125
6> (+ 0.125 0.5)
0.625
7> (= 0.25 (sqrt 0.0625))
t
As an example of a Scheme-ish `#lang`, here's a Racket `#lang sicp` that I made to mimic MIT Scheme, as well as add a few things needed for SICP: https://github.com/sicp-lang/sicp/blob/master/sicp/main.rkt
It would be even easier to make a `#lang better-scheme`, by defining just a few changes relative to `racket-base`, such as how numbers are read.
For HN, I'd like to point out that it was a historical accident that Java looked like it did, as far as the Web was concerned.
IIRC, Java looked like it did to appeal to technical and shrinkwrap developers, who were using C++ or C. (When I was lucky to first see Java, then called Oak, they said it was for embedded systems development for TV set-top boxes. I didn't see Java applets until a little later.)
But the Web at the time was intended to be democratizing/inclusive (like BASIC, HyperCard, and Python). And the majority of the professional side was closer to what used to be called "MIS" development (such as 4GLs, but not C/C++). And in practice, HTML-generating application backends at the time were mostly written in languages other than C/C++.
I'm sympathetic to the rebranding of the glue language for Java applets (and for small bits of dynamic), to be named like, and look like, Java. That made sense at the time, when we thought Java was going to be big for Web frontend (and I liked the HotJava story for a thin-client browser extended on-demand with multimedia content handlers). And before the browser changed from hypertext navigator to GUI toolkit.
But it's funny that we're all using C-descendant syntax only through a series of historical accidents, when that wasn't even what the programmers at punctuated points in its adoption actually used (we only thought it would be, at the time the decisions were made).
* (= (+ 0.1 0.2) 0.3)
T
Meanwhile, in Rakudo, 0.1 is a Rat: a rational number where the numerator and denominator are computed.
You can actually get the same underlying behavior in Common Lisp:
(= (+ 1/10 2/10) 3/10)
julia> 1//10 + 2//10 == 3//10
true
Edit: it seems that Raku uses rationals as a default [1], so it doesn't suffer from the same problem by default.
Yeah, exactly, Raku defaults to a rational number type for these kinds of numbers. I honestly think that is a perfectly fine way to do it, you're not using Raku for high performance stuff anyway. It's not so different from how Python will start to use arbitrarily sized integers if it feels it needs to.
Raku by default will convert it to a float if the denominator gets larger than a 64-bit int, but there's actually a current pull request active that lets you customize that behavior to always keep it as a Rat.
Really interesting language, Raku!
0.1e0 + 0.2e0
1.1e0 + 2.2e0 == 3.3e0
0.29999999999999998 or 0.29999999999999999 are less misleading but wasteful. Remember they are not only visible to users but can be serialized in decimal representations (thanks to, e.g. JSON).
In fact, most uses of FP are essentially lies, providing an illusion of real numbers with a limited storage. It is just a matter of choosing which lie to keep.
Fixed-point numbers (aka "decimal" type in Java, C# and others) are the preferred way to deal with this problem as I mentioned in this same discussion hours ago.
Now, in the example you presented, you have a round-off error amplication problem where the round-off error grows larger than the epsilon. You can avoid that using the Kahan summation algorithm.
https://en.wikipedia.org/wiki/Kahan_summation_algorithm
const arr = [0.1, 0.2, 0.9, 0.6];
let sum = 0.0;
let c = 0.0;
for(let i = 0, l = arr.length; i < l; i++) {
y = arr[i] - c;
t = sum + y;
c = (t - sum) - y;
sum = t;
}
Having developed a significant amount of perfect precision math libs over the years, rationals do explode for lots of common computations. That is the main reason they are not standard in all computing. They also cannot represent a lot of desired results.
The problem is rational number performance slows exponentially (or uses large amounts of RAM) for many common uses, which will kill scripts, unless they suddenly fix precision (i.e., no longer exact) or change to float (also a surprise for people).
Setting them as floats has the odd numerical issue, which is not that bad, but doesn't require a host of other mitigations to prevent other bad surprises.
For example, summing 1/n^2 for n=1 to 100000 as floats runs quickly and is very close to the exact answer. As rationals the numerator and denominator require working with 86000 digit numbers.
Also, does raku still do this?
say (1/6+1/6).raku #<1/3>
say (1/10+1/10).raku #0.2
That seems surprising, does it not?
both are Rats, they just get stringified differently
It is basically useless for numerical computation when you perform iterations. Even good convergent algorithms can diverge with interval arithmetic. As you accumulate operations on the same numbers, their intervals become larger and larger, growing eventually to infinity. It has some applications, but they are quite niche.
Are there really cases where current FP arithmetic gives an accurate result, but where the error bounds of interval arithmetic would grow astronomically?
It seems like you'd have to trust FP rounding to always cancel itself out in the long run instead of potentially accumulating more and more bias with each iteration. Is that the case?
Wouldn't the "niche" case be the opposite -- that interval arithmetic is the general-purpose safe choice, while FP algorithms without it should be reserved for those which have been mathematically proven not to accumulate FP error? (And would ideally output their own bespoke, proven, interval?)
Most often, yes; the probability distribution of your number inside that interval is not uniform, it is most likely very concentrated around a specific number inside the interval, not necessarily its center. After a few million iterations, the probability of the correct number being close to the boundary of the interval is smaller than the probability of all your atoms suddenly rearranging themselves into an exact copy of Julius Caesar. According to the laws of physics, this probability is strictly larger than zero. Would you think it "unsafe" to ignore the likelihood of this event? I'm sure you wouldn't, yet it is certainly possible. Just like the correct number being near the boundaries of interval arithmetic.
Meanwhile, the computation using classical floating point, typically produces a value that is effectively very close to the exact solution.
> It seems like you'd have to trust FP rounding to always cancel itself out in the long run instead of potentially accumulating more and more bias with each iteration. Is that the case?
The whole subject of numerical analysis deals with this very problem. It is extremely well known which kinds of algorithms can you trust and which are dangerous (the so-called ill-conditioned algorithms).
Say x = 4.0 ± 1.0. What is x / x?
It should be x / x = 1.0 ± 0.0, but interval arithmetic will give you [3/5, 5/3].
Notice the interval is objectively wrong, as the result cannot be anything other than 1.0. Now imagine what happens if you do this a few more iterations. Your interval will diverge to (0, +∞), becoming useless.
The moral of the story (which may be more obvious in hindsight): interval arithmetic is a local operation; error analysis is a global operation. Naturally the former cannot substitute for the latter.
With interval arithmetic, either a programmer would understand that floating point numbers are not actually numbers but intervals... or they wouldn't, and get surprised.
So I don't really see much upside. If you know that you need interval arithmetic, chances are that you're already using it.
Consider x in [-1, 1], and y in [-1, 1]. x*y is also in [-1,1], and x-y in [-2, 2]. But now consider actually that y=x. That's consistent, but our intervals could be smaller than what we've computed.
I mean, intervals as large as whole numbers might make sense if your calculations are dealing with values in the trillions and beyond... but isn't the point of interval arithmetic to deal with the usually tiny errors that occur in FP representation?
Numerical analysis was a field invented to give realistic error bounds.
`Math.pow(2, 55)+1 === Math.pow(2, 55)` returning true
> Sure, but what's the use case for mathematics where you don't know what side of an asymptote you're on?
Knowing which side of the asymptote you're on does not solve this problem or even ameliorate it.
If you have "scope1.x/scope2.x" then they don't cancel out, but that's not "x/x"
And if you save a value for later, and change x, then that value isn't x anymore.
(I assume you're using = to state the value, not as an assignment operator.)
But if, in your code, you've copied x to y (not by reference), then it seems that x / y would correctly be [3/5, 5/3]. This is a feature, not a bug.
In any case, since intervals are more likely to be more like ± 0.000000000000001 when dealing with basic common non-iterative calculations, it doesn't seem like a problem in practice even if the compiler/interpreter doesn't optimize it away?
You're moving the goalposts here. Those are HUGE if's. You went from something you could trivially implement in any language to something that requires a LOT of infrastructure and will severely limit your options.
How are you going to handle (x - z) / (x + z) when z = 0? How are you going to handle f(x) / g(x) when they turn out to compute the same value in different ways?
You go from "I need to change float to interval<float>, give me 15 minutes" to "I need a computer algebra system, let me figure out if I can embed Mathematica/SymPy/Maple/etc. into program so I can do math." And even when you do that you STILL won't be able to handle cases where the symbolic engine can't simplify it for you. Which in general it won't be able to do.
> But if, in your code, you've copied x to y (not by reference), then it seems that x / y would correctly be [3/5, 5/3]. This is a feature, not a bug.
No, that is most definitely a bug. The correct result is 1.0, but you're producing [3/5, 5/3]. If that's not a bug to you then you might as well just output (-∞, +∞) everywhere and call it a day. You can insist on calling it a "feature" if it makes you feel better, but that won't change the fact that it's still just as useless (if not actively harmful) for your intended calculation as it was before.
Contrast this with just leaving it as a float instead of an interval, where you would've gotten the correct answer.
> In any case, since intervals are more likely to be more like ± 0.000000000000001, it doesn't seem like a problem in practice even if the compiler/interpreter doesn't optimize it away?
That's only after 1 iteration. Notice that in my example the error was multiplicative, not additive. Run more iterations and your error will magnify.
But there's nothing "wrong" about it, it's correct -- that's how it's designed to work. If you're starting with non-extreme values and just miniscule floating-point errors and iterate 1,000 times with basic arithmetic I still don't see how it's going to cause a problem. E.g.:
Math.pow((1 + Number.EPSILON), 1000) => 1.000000000000222
If you're multiplying a million or billion times then that's where I can now understand you should be an expert an numerical analysis in the first place to have any confidence in your result, and you know whether or not your float result can be trusted or not at all.
But the good thing is that if you don't know what you're doing, started with interval arithmetic and it ballooned to (-∞, +∞), then that's a strong signal you shouldn't necessarily be trusting the algorithm's results at all, and to go talk to someone with a background in numerical analysis, right?
Whereas if you iterate a million times and the interval is still miniscule compared to your values, you have absolute confidence you're fine. Seems useful to me -- not useless or actively harmful at all.
> It should be x / x = 1.0 ± 0.0, but interval arithmetic will give you [3/5, 5/3].
This is the “dependency problem” which is eliminated in many cases, and mitigated in others, by rewriting so identical (vs. merely in components) values appear only once; when you might need a numerical answer at one point (if possible) but to use the value in further computations, this can be done by storing and manipulating values symbolically and extracting numerical results as needed.
Even if this may come out as a bit snarky, this is a very good, honest, and helpful answer. At least, it would be helpful to extremely skeptical people like me. I'm a bit like crazygringo, and I cannot be convinced of anything until I have tried it myself and dirtied my hands with it.
To crazygringo: for a concrete, real-world example, try to implement a Kalman filter (a very simple numerical algorithm) using interval arithmetic. It simply doesn't work. You'll see that you cannot extract any useful result from the output of the computation. The implementation of an "interval Kalman filtering" is a (niche) subject of current research, where various very complicated algorithms are being invented to try to reproduce the nice properties of Kalman filtering--even when using something obviously inappropriate like interval arithmetic. For an intuitive understanding, assume that the input data are quantized to integer values, so that the starting intervals are of length 1.
> Contrast this with just leaving it as a float instead of an interval, where you would've gotten the correct answer.
But if I type into my console:
var a = 0.1; var b = a + 0.2; b -= 0.2; b == a;
Heck, to use your own division example:
(0.1 + 0.2 - 0.2) / 0.1 ==> 1.0000000000000002
Anyways, thanks for trying to explain.
(0.1 + 0.2 - 0.2) / 0.1 ==[+/- .001] 1.0 => True
Now you've got me learning about how affine arithmetic can help with the dependency problem but has its own drawbacks. Thanks for pointing me in that direction!