Floating Point Math
0.30000000000000004.comA couple of thoughts I've always had about floating-point arithmetic:
1. IMO it's unfortunate that most languages default to floating-point. Most programmers, most of the time, would be better served by slightly slower but less confusing alternatives (it's nice that Raku uses rational numbers by default: similarly for integers, it's great that Python uses arbitrary-precision integers by default). At any rate, programmers would be a lot less confused about floating-point arithmetic if they had to opt in to it explicitly, e.g. instead of 0.1 + 0.2 if they had to say something super-explicit like (just exaggerating a bit for effect, this is probably impractical anyway):
NearestRepresentableSum(NearestRepresentable("0.1"), NearestRepresentable("0.2"))
2. IMO when explaining floating-point arithmetic it helps to add a picture, such as this one (added to Wikipedia by a user named Joeleoj123 in Nov 2020): https://upload.wikimedia.org/wikipedia/commons/b/b6/Floating...
With this picture (or a better version of it), one can communicate several main ideas:
- There are a finite number of representable values (the green points on the number line),
- Any literal like "0.1" or "0.2" or "0.3" is interpreted as the closest representable value (the closest green point),
- Arithmetic operations like addition and multiplication give the closest green point to the true sum,
- There are more of them near 0 and they get sparser away from 0 (the "floating-point" part),
etc.
Further, by staring at this picture, and the right words, one can infer (or explain) many of the important properties of floating-point arithmetic: why addition is commutative but not associative, why it is a good idea to add the small numbers first, maybe even the ideas behind Kahan summation and what not.
> IMO it's unfortunate that most languages default to floating-point. Most beginning programmers would be better served …
Most languages, most of the time, are not used by beginners.
If you are using "beginner" to refer to the time spent, this is true.
However, if you use "beginner" to the knowledge gained, it might not be. If you only ever make webpages, even if you have made 100s you could still be a novice programmer because you never branched out enough to learn new programming concepts.
If a programming language makes it easy to do something moderately, but it is hard to do it well. Programmers who only know that language are likely to have a gap in their stills. Floating point (in most languages) is easy to gets the basics working, but are hard to do well and very hard to do perfectly. This leads to a lot of programmers not learning floating point well.
General purpose programming languages are complex tools.
In this specific case representing non-integer numbers effectively on a binary device is complex. If you use a different representation than IEEE floats you just give a different set of corner cases and unexpected outcomes.
Don't let a novice build software you need to be correct without supervision, and if you are a novice expect to make mistakes, just like if I were to build a website I wouldn't expect my style choices to render appropriately on a wide range of devices... that's complex too!
Whether or not that's true, you can remove "beginning" from my statement as it's not necessary (done, just edited, thanks): most programmers, most of the time, don't need the speed of floating-point everywhere (compared to fixed-point/scaled integers, or rationals, or interval arithmetic, or whatever), and when they do, the language could let them easily opt into it with a declaration like "use float" or whatever.
Every option here has tradeoffs and drawbacks: fixed point arithmetic suffers from a very limited precision range, rationals aren't even the same number set, cauchy sequences are precise but comparatively very slow… there's no one size fits all solution that's right in every circumstance.
Except, of course, at lower levels of abstraction - where IEEE floats are what the hardware implements. Lower level languages use 8-, 16-, 32-bit integers, they use IEEE floats and doubles, and they make these choices for pretty solid reasons.
Higher level languages make different choices (arbitrary precision integers are common in interpreted languages, eg). Libraries support all kinds of options up and down the stack.
Of course, but low-level languages call their floats...floats. Certain higher-level languages often call them numbers or decimals, which is why this confusion happens in the first place. It's like if a language had uint8 but called it Integer - yes, there are many uses for uint8, but there are also many cades where it's the wrong thing to use and it shouldn't be possible to use it accidentally.
> rationals aren't even the same number set
In what way are rationals not the same number set? In the strictest sense basically none of the proposed versions have the same number set, but in a broad sense, they all represent a useful subset of rationals, right?
In a broad sense, sure.
Could you elaborate what your intended meaning was? It felt to me like you were singeling out 'rationals' as not being the same number set. Maybe we also think of something different when talking about 'rationals'?
Maybe I also missed something obvious, so I'd like to satisfy my curiosity!
I meant that rationals are a subset of the reals, and while floats are also a subset of exact reals a "typical" fixed bitwidth implementation will have a significantly greater range in floats than rationals.
I don't know that it's necessarily as significant a difference as I'd first considered it to be, though.
You can't do trigonometry on the rationals, which would prevent any games, graphics software, audio mixing software etc from using the rationals.
I mean, you can, but you shouldn't. I don't think anyone is arguing that any representation is suitable for all usecases or that ieee754 should not be available in programming languages.
Also, I think I'm too tired by now, I get confused too much between the rationals as the rational numbers \mathbb{Q} and the rationals as an implementation of rational numbers using a quotient of two integers.
Agree. But experts/intermediates often gloss over language semantics in pursuit if getting something done. For me, floating point by-default is more often a nuisance
That doesn't really matter. Even if you had 20 years of experience in C++ or whatever, you could confidently write JavaScript code with floating point bugs in it, because "the type is called Number, obviously that isn't floating point". Beginner programmers might actually realise this sooner, since veterans aren't going to be writing console.log(0.3+0.2) as part of learning the language.
IMHO this does not follow, for a few reasons:
- An experienced programmer would know that IEEE FP hardware is ubiquitous. Why would a language eschew that hardware capability by default? If anything, I would assume that any unfamiliar general-purpose language DOES start from that point (using IEEE float to represent non-integer numbers) because of historical precedent.
- "Number" is about as vague as you can get for a type name. Maybe personal bias here, but I find that vagueness invites research up front. "Time to read the documentation."
(I still expect a language newbie to get various bugs in new Javascript code, because the footguns in that language differ from the footguns in something like C++.)
Should we really optimize for someone writing in a new language without reading anything about it? Like, if he/she doesn’t even know that js numbers are floats, just don’t even let them close to a program.
No we should not, nor am I advocating for that.
Thank you for your mention of the Raku Programming Language.
If you want to force usage of floating point arithmetic, you will have to indicate that in literal values. E.g. `0.1` would be a [Rat](https://docs.raku.org/type/Rat) (Rational number), and `0.1e0` would be a [Num](https://docs.raku.org/type/Num) (aka a floating point".
In Raku, to get the nearest representation, use the [.narrow](https://docs.raku.org/routine/narrow) method. So `42e0.narrow`, `42.0.narrow` and `42+0i.narrow` would all be an `Int`. Yes, Raku has complex numbers built in as well :-)
That would be another case of wasting a lot of time and electricity so the developer doesn't have to spend half an hour learning how a computer works.
Why should I have to learn how to do my job well? Programmer time is expensive! /s
Any other way of representing the real numbers is going to have gotchas. Rational numbers take up more space and are slower to use, but also have real drawbacks like not being able to do sqrt or having to worry about overflow when doing a comparison.
Ultimately, there is no substitute for knowing what you are doing.
If nothing else, I think compilers/linters should warn when trying to use equality/comparison operators between floats since most of the time it's mathematically wrong. All of my projects are filled with isApproxEquals(float1, float2)
That really depends on where the floats come from and how they have been manipulated. I have written quite a lot of code where comparing floats was perfectly sensible. I had to repeatedly revert changes by colleagues who didn't understand the code and had replaced A == B with something like isApproxEquals(A, B). This was in electrical design software where every millisecond counted.
To be fair, float point equality is often a red flag and often deserves a double-take (even if the result is, yes, it's correct).
A comment like "exact equality is deliberate here and valid because XYX and important for meeting performance requirements ABC" would help, unless it's a major part of the system, in which case the colleague should know that already.
And on their part, a check in with you for "hey, I don't understand why this equality is valid" would be better than assuming it's wrong and changing it.
I see a lot of this (generic approx-comparison functions) at work. It can catch some problems, true, but it becomes very cargo-cultish. They understand that the hardware rounds calculations, but they behave as if the hardware is nondeterministic. There's also very little thought going into an appropriate epsilon value, whether based on the calculation being done, or the tolerance of the overall output/algorithm.
It's a nice website explaining the problem lightly, but I think the cool part is the encyclopedic language list handling floating point numbers and the reference for bigdecimal support.
The only sentence I don't really like:
> When you have a base-10 system (like ours), it can only express fractions that use a prime factor of the base.
It's a weird mix of over- and under-generalization. The second half sounds like a feature of all number systems independent of the base, and we can express more numbers (just with a notion of 'repeating infinitely' or as fractions), that's why they even switch to "expressed cleanly" in the next sentence.
If I get more sleep and can think of a good way to express it, maybe I'll actually make a pull request ;)
> it can only express fractions that use a prime factor of the base.
IMO it could do better to explain why this is the case rather than state it as a fact, as it’s not immediately obviously true (at least to me).
A terminating decimal is equivalent to a fraction with a denominator that is a power of 10. Any fraction with a denominator that is a product of prime factors of 10 can be turned into a fraction with a denominator that is a power of 10. Thus the only fractions with terminating decimal representations are those with denominators which are a product of prime factors of 10.
Of course this is true for any base other than 10, but I couldn’t think of a term for “terminating decimal” with other bases.
That’s not a very good explanation. That second sentence
> Any fraction with a denominator that is a product of prime factors of 10 can be turned into a fraction with a denominator that is a power of 10.
isn’t sufficient. You also have to argue that any fraction with a denominator that is not a product of the prime factors of 10 cannot be written as a finite decimal.
If you do that you end up with a tautology.
A better and more rigid explanation would start with a rational p/q, with p and q relatively prime that can be written as some integer divided by 10^n, and reason from there.
I don't think you're being charitable here. Sure, their explanation wasn't perfect, but their line of reasoning was absolutely on point.
You almost gave a really good explanation yourself on why this should be the case but stopped short of it. Don't know why. Any terminating decimal can be written in the form a/10^{n} where a and n are both integers. After we have our p/q, there exists an integer c such that p/q · c/c = p/10^{n} if and only if q consists solely of the primes 2 or 5 (or both). And if not, then there isn't an integer c to satisfy said condition, thus making it impossible to write our p/q in the form of a/10^{n} (white still keeping the numerator an integer at least) so it's an infinitely repeating decimal.
You're right, my explanation was invalid.
My attempt: You can't express 1/3, 1/6, 1/7, or 1/9 in decimal without infinitely repeating digits; you can only express 1/2 and 1/5, and 2*5=10. In binary systems, you can only represent multiples of 1/2 without infinite repeating digits, so, 0.5, 0.25, 0.125 are all exact in binary floating point. 0.1 is 1/10, which needs that 5 you don't have in binary. Computers don't have infinite memory, so infinitely repeating digits are truncated at some point. As such, 0.1 + 0.2 in binary floating point is not exact, the same way adding 0.33333 + 0.66666 wouldn't exactly give you 1.0 in decimal.
This is pretty good for illustration to a layperson, thank you! Filling in a few other examples could be useful. For instance, why do 1/4 and 1/8 work in base-10?
I imagine you could create a table of the fractions 1/2, 1/3, ..., 1/10; prime factorization (e.g. 1/4 = 1/2 * 1/2), their decimal representation, their binary representation, and maybe for familiarity the sum-of-fractions represented by the binary representation. e.g. 0.101 meaning 1/2 + 1/8.
previous discussions: https://news.ycombinator.com/from?site=30000000000000004.com
Thanks! Macroexpanded:
0.1 and 0.2 = 0.3 - https://news.ycombinator.com/item?id=28390997 - Sept 2021 (2 comments)
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)
Such a shame that decimals don't get more attention. I program in Go a lot and they don't even have a fixed point number type built into the language. Floating point numbers always seems to be the default. And while there is support via third party packages, it makes everything harder to use, from communicating with databases to (de-)serializing data.
However, in reality most numbers I deal with can reasonably be assumed to have a maximum number of decimals and can be stored easily this way. I know way fewer examples where I'd need floating point precision than where I need a fixed number of decimals. But with poorer support I always fall back to using float.
In what context couldn't you just use an integer?
You can multiply and use integers but it's a bit ugly. Especially if you work across systems, you'll always need to store notations on the multiplier used. Having a decimal as a built in type with that information stored would be much easier.
But in the end I tend to use that for most numbers, especially as compression in time series also often better works on integers than floats if you have gradual changes in the numbers.
Multiplication context maybe?
Do you have a good blog post on choosing tolerances and ranges? I just started at a company where it’s probably about now that we should get smart with that. We do geometry so the problem gets even worse.
For an example of safe geometric calculation in floating point, see Google's S2 library:
Why don't we store fractions as fractions rather than floating point?
Finding a reasonably accurate fractional approximation to a number, even allowing a certain degree of suboptimality in the estimation, is not computationally efficient. So, computing with fractions almost immediately becomes computing with bigints, unless you get lucky and stuff cancels out.
If you start with the idea that you want to store every number in the same finite number of n bits, you’ve got a problem: you can store (at most) 2^n different numbers in n bits, but there are infinitely many numbers.
So, if you want to hold on to that idea, the question becomes what numbers best to pick.
If you go for rational numbers, you soon discover that addition of rationals is slow because you have to [1] multiply the denominators and find a greatest common divisor (example: 1/3 + 1/9 = (19 + 13)/(3*9) = 12/27 = 4/9)
You also will find that your denominators can rapidly get large, and that, in real life, you need to represent a fairly wide range of numbers (say at least between 10^-3 and 10^6). That means you either accept large, random rounding in calculations, or have to pick a large number of bits
Also, the math you have to do to find the closest rational for square roots and results of goniometric functions makes those functions slow.
So, you either have to give up the idea to store rationals, or the idea to store every number in the same finite number of n bits. IEEE chooses the former for performance reasons.
[1] assuming you want to have a single representation for each rational. You likely want, as you don’t want to waste space and because you want equality testing to be simple.
You can start there then wind up with floating point.
Say we have a 32 bit CPU. Let's store fractions in two halves, the numerator and denominator.
This turns out to be super inconvenient for irrational numbers. We can use an alternative representation where the number is in two halves, the integer half and fractional half. In other words your first 32 bits are 1X2^0...31 and second 32 bits are 1x2^-1...-32. This is called fixed point.
You run into a problem where this is usually extremely wasteful in the number of bits used, so you can fuse them into a single 32 bits used, and the binary decimal point is at the 16th bit, 18th bit, whatever you need. You just need to track it when multiplying or dividing numbers to handle the appropriate shifts. This is "fixed" point math, and it's what we did for decades because it's super cheap in hardware (it's the same integer adders/multipliers, just some extra work for division and shifting for multiplication).
You might even want the decimal point to move. Say your numbers are almost always less than 1, why use more than 1 bit for the integer part and in software, handle the overflows and change of decimal point when needed?
Well that software part is super complex, so you can implement some special hardware to do it. It's even really convenient to change the representation from a fixed integer and decimal half to a decimal mantissa and integer exponent. Now you've reinvented floating point. It would be great if there was a standard so all languages could agree on representation and hardware to implement it really fast. That's IEEE 754.
You can do that, but then you still leave out all the irrationals like sqrt(2) and pi.
Common Lisp does by default. Calling (/ 1 3) gives 1/3 which is a rational. The individual components of a rational number are bignums, so the size of the fraction is only limited to available RAM.
However, this is not enough in many cases. For example, how would you store pi? In the case of Lisp, pi is stored as a floating point number, and the conversion rules say that a mathematical operation between a rational and a floating point number yields a floating point number. This means that even though you have rational numbers, you still have to be aware of floating point.
You could store pi as a symbol.
Of course, ultimately this is going to be a compromise and I understand the choice of not storing common constants that way. In the end you'd end up just replicating common mathematical notation and computing with that is not going to be fast.
As soon as you want to do something with π, you have no choice but an approximation, so floating-point is completely appropriate.
same way we do now I guess? Approximate it. My vote is on 22 / 7how would you store pi?That’a a terrible approximation. Also requires memorising about the same amount of information as just memorising the digits.
The other answers pointed out some good reasons we use floats instead, but just a note -- Python at least has a "fractions" class.
Because that was too slow in the 1970s, when this particular corner of programming language design ossified.
Alternatively, people cared about performance then. Nowadays programmers would rather do the slow, easy thing so they don't have to think as hard.
The idea that it's somehow morally lacking to put less value on performance on machines are literally thousands of time faster than those used for early programming has always struck me as rather odd.
When I think of the problem what I see is the compiler pretends to be fast by forcing the programmer to deal with the problems. Bonus the solutions are inherently fragile and bug ridden. Which the programmer gets smugly blamed for.
What if you need to also make sure, sqrt(2) * sqrt(2) == 2? Even this is possible in many representations, but you can see my point I guess.
We all know this by now right? We know computers store numbers in binary (unless using BCD) and numbers like 1/10 and 1/3 can only be approximated in a finite number of bits. This isn't news is it?
Keep in mind that when something appears on the front page, it’s because enough people voted it up. I don’t actually know, but suspect that commenting on it may bump the score a little as well? Either way, if it’s uninteresting to you, I encourage voting up or submitting something more interesting.
Also keep in mind that because computing is a growing field, the majority of people in it are relatively new to the field, plus there are plenty of people here that don’t have CS degrees.
FWIW, there are many representations for real & floating point numbers. Rationals are an example of something that’s neither floating point nor BCD, and can represent 1/10 and 1/3 exactly. Here’s a fun example: https://iquilezles.org/articles/floatingbar/
Rational numbers can also be trated as quotient of two integers and stored with arbitrary precision by storing these two values, even with limited precision of 2x32 bit integers, that would perfectly accurately capture 1/3 and 1/10.
But I also don't think it is particularly 'news', the discussion on previous versions centered around the problems that arise from floats, such as inconsistent handling by tools and languages and 'inapropriate use' where the precision from floats is not good enough or misleading. So maybe it is more a "topic of interest".
Rationals have their own set of issues:
1) it's really slow slow. Adding two fractions involves three integer multiplications and then running the GCD to simplify the fractions.
2) just simply comparing two rational numbers involves multiplication, which may overflow.
3) you can't represent irrational numbers. You can't do square roots, for example.
Yes, all systems will have some drawbacks. My response was only geared towards this part:
> numbers like 1/10 and 1/3 can only be approximated in a finite number of bits
Maybe I should have been more explicit.
New people learn new things every day :)
Unfortunately no.
> Your language isn’t broken, it’s doing floating point math.
Hard disagree right from the start - if your language is doing floating point math by default (as in, if numeric literals and basic operators use floating point in the absence of explicit type annotations or tags), your language is broken. Maybe if it's hyper-targeted towards graphics or ML or some other field where floating point errors don't matter and performance is king, then I'd call it fine, but users of such languages probably aren't reading this page.
Now, I get what the author is saying - there isn't a bug in your interpreter, it's how it's designed. But that means it's broken by design.