15 ms·
I remember in college when we learned about this and I had the thought, "Why don't we just store the numerator and denominator?", and threw together a little C+
by _bxg1 7y ago
I remember in college when we learned about this and I had the thought, "Why don't we just store the numerator and denominator?", and threw together a little C++ class complete with (then novel, to me) operator-overloads, which implemented the concept. I felt very proud of myself. Then years later I learned that it's a thing people actually use: https://en.wikipedia.org/wiki/Rational_data_type https://en.wikipedia.org/wiki/Rational_data_type
- miketuritzin 7y agoReminds me of this Inigo Quilez article on experimenting with rendering using rational numbers: https://iquilezles.org/www/articles/floatingbar/floatingbar.htm https://iquilezles.org/www/articles/floatingbar/floatingbar....
- _bxg1 7y agoI actually ran into a bug recently while implementing my first raytracer, where the point calculated from the sphere-intersect test would just occasionally end up inside the sphere due to floating point imprecision, so the diffuse sample rays would have their origins completely in the dark, leading to randomly black pixels. Solved it by bumping every intersection out by 0.01 in the direction of its normal. And then of course there have been several other "x.abs() < 0.01" cases for various purposes. So I could definitely see that being an interesting experiment.
- munchbunny 7y agoThat's really interesting - hadn't thought of that before. To fix that, would you be able to do a square of the magnitude comparison with the radius and just bump the borderline cases, or is it more efficient without the extra branching?
- _bxg1 7y agoI just did it across the board; since the error is in the floating-point noise I don't know if I'd even trust a comparison on that. Plus, the discrepancy between "bumped" and "unbumped" samples might cause some visible artifacts.
- cellular 7y agoDirect3D used to have a Z-bias for a similar problem: rendering pictures hanging on walls at a far Z depth. Their whql tests even tested for it. It was fun discovering all the corner cases while debugging drivers.
- Smaug123 7y agoThis phenomenon has a name, by the way: "shadow acne" (which is actually a more general phenomenon, but this is an example of it).
- daniel-thompson 7y agoHere's some good reading on robust ways to fix this without an arbitrary epsilon bump: http://www.pbr-book.org/3ed-2018/Shapes/Managing_Rounding_Error.html http://www.pbr-book.org/3ed-2018/Shapes/Managing_Rounding_Er...
- gowld 7y ago"Why don't we just" because it's harder than one thinks. https://en.m.wikipedia.org/wiki/Arbitrary-precision_arithmetic https://en.m.wikipedia.org/wiki/Arbitrary-precision_arithmet... and gets harder when you want exact irrationals too https://www.google.com/search?q=exact+real+arithmetic https://www.google.com/search?q=exact+real+arithmetic
- amelius 7y agoAlso, it's a lot less efficient, so it should only be used if absolutely necessary.
- contravariant 7y agoAlthough this does make me wonder what happens if you round the rational once the numerator/denominator becomes too big. But maybe that just results in all the floating point weirdness again, just not for small rationals.
- jacobolus 7y agoThe result is that your number system (a) makes many common operations dramatically more computationally expensive, (b) has less predictable rounding which is very tricky to reason about, (c) generally gives worse results for the same bit budget. Instead of e.g. evenly spaced numbers, you get spacing like https://en.wikipedia.org/wiki/Minkowski%27s_question-mark_function https://en.wikipedia.org/wiki/Minkowski%27s_question-mark_fu... One thing you can try is storing a floating point numerator and a floating point denominator, and renormalizing them by bit shifts instead of finding GCDs. This lets you avoid rounding errors for small ratios. For general purposes this advantage isn’t really worth doubling the number of bits and complicating arithmetic for though. See e.g. https://observablehq.com/@jrus/qang https://observablehq.com/@jrus/qang
- Koshkin 7y agoBut rationals are more expensive to compute with (compared to floating-point; this is another example of the trade-off between performance and accuracy.)
- _bxg1 7y agoYeah, I assumed as much. I wasn't really thinking about that at the time, but knowing now that it exists in the wild, the only conceivable reason for it not to be used everywhere would be some kind of performance penalty.
- leetcrew 7y agoit's also a range-storage trade-off. if you use two fixed width integers to represent a rational, the minimum and maximum values are the same as that of the integer type. floating point gives a far wider range for the same number of bits.
- jdmichal 7y agoI'm sure there's some subtlety I'm missing, but isn't it actually the same trade-off? A 64-bit float can only represent 52-bit integers exactly. Anything above that, and you don't even have integer-level precision on the number anymore... This sliding scale of precision is exactly why floats are terrible at the kinds of operations that would cause you to use a rational instead.
- leetcrew 7y ago> I'm sure there's some subtlety I'm missing, but isn't it actually the same trade-off? not exactly, unless you consider space efficiency to be an aspect of performance (which is certainly reasonable). a naive implementation of rationals using two int32_t's only covers the range of a single int32_t, despite using as many bits as the double. it's also a trade-off between range and consistent precision, of course. this certainly isn't some deep insight into number representation, just a quick point for the benefit of people who haven't thought much about rational data types before.
- 7y ago
- loopz 7y agoIt's actually in use in many places, for things like handling currency and money, and for when you get funny corner cases involving rounding such numbers and pooling the change. Whenever I see someone handling currency in floats, something inside me wither and die a small death.
- recursive 7y agoCurrency handling is almost never done with rationals (numerator and denominator) and is frequently (and correctly so!) done with fixed or floating point decimal types.
- larrik 7y agoThis is false. It's not correct to handle currency with floating point types.
- simias 7y agoThey said floating point decimal types which probably means BCD.
- recursive 7y agoThere are different implementations, and BCD is only one of them. Another popular one is a mantissa and exponent, but the exponent is for a 10-based shift rather than the typical floating point.
- anonydsfsfs 7y agoIEEE 754 defines decimal floating point: https://en.wikipedia.org/wiki/Decimal_floating_point#IEEE_754-2008_encoding https://en.wikipedia.org/wiki/Decimal_floating_point#IEEE_75...
- jhj 7y agoTbey mean radix-10 floating point, as compared to the radix-2 floating point you are thinking of. The packing of the decimal fractional digits in the significand of a radix-10 FP number need not be in BCD, it can use other encodings (e.g., DPD or something else). 0.3 is exactly representable in radix-10 floating point but not radix-2 FP (would be rounded to a maximum of 0.5 ulp error as seen in the title), for instance, just as 1/3 = 0.3333... is exactly representable in radix-3 floating point but neither radix-2 or radix-10 FP, etc.
- megous 7y agoNot all numbers are rational.
- pg_is_a_butt 7y agoAll numbers are equal to 1 in a number base of themselves.
- ktpsns 7y agoAnd not all numbers are real. And IEE 754 floating point numbers do not even cover all real numbers.
- banachtarski 7y agoAll floating point numbers are rational numbers.
- simias 7y agoAn other compromise in to use fixed point which is effectively a rational with a fixed denominator. Extremely popular on machines which can handle integer arithmetics but not floating point (since you can trivially do fixed-point arithmetics using integer operations, you just need to be very careful when you handle overflows). If you look at the code of old school games (including classics like Doom if memory serves) the game engine used fixed-point to work on commodity hardware without FPU. There's also BCD (binary coded decimal) that can solve some problems by avoiding the decimal-to-binary conversions if you're mainly dealing with decimal values. For instance 0.2 can't usually be represented in binary but of course it poses no problem in BCD.
- danbolt 7y agoFixed/floating is an interesting tradeoff for many real-time strategy games too where changes in game state are a synchronized simulation. Fixed point math in software can give more reliable and cross-platform math operations, but with a performance cost (eg: Homeworld: Deserts of Kharak). Using the CPU's floating-point hardware is faster, but you often have to ensure the correct CPU registers are set before doing calculations and those registers can be changed by other software such as a DirectX driver or the operating system (eg: Age of Empires II, Rise of Nations. etc).
- reitzensteinm 7y agoI currently build deterministic multiplayer WebGL games in Unity, built via C#->IL2CPP->Emscripten->WASM. The server is the same code base running on Microsoft's .Net runtime. The chances of being able to run deterministic floating point calculations across this stack is basically zero (even leaving aside that the games are often run on ARM chips), and so we use this library when floats are absolutely necessary (but more often just plain longs): https://github.com/asik/FixedMath.Net https://github.com/asik/FixedMath.Net It is a little terrifying that e.g. normalizing a vector involves a while loop, but all things considered the whole thing runs surprisingly well. (I agree with everything in your post, just thought I could add a real world field report)
- 7y ago
- elwell 7y agoClojure has Ratio numbers. https://clojuredocs.org/clojure.core/rationalize https://clojuredocs.org/clojure.core/rationalize
- phoe-krk 7y agoSome langs have that in their standard included batteries. (Shameless Common Lisp plug: http://clhs.lisp.se/Body/t_ration.htm http://clhs.lisp.se/Body/t_ration.htm)
- banachtarski 7y agoYes including C++, the language mentioned in the parent post (`std::ratio`)
- protomyth 7y agoHandling quantities with varying Unit of Measures is made quite a bit easier by using numerator and denominator pairs.
- tim333 7y agoWhen I was reading about this I thought why don't the print functions just by default round to the nearest 10 decimal places or similar so 0.30000000000000004 prints as 0.3 unless you specify you don't want that. And I wrote a function in javascript to round like that though it was surprisingly tricky and messy to do so.
- hzhou321 7y agoYou either feel smart by wondering why people don't use rationals, or feel smart by wondering why people use rationals.
- enriquto 7y agowhat do you mean by "rationals"? infinite precision? because finite precision rationals are not associative and much worse than floats in many senses.