4 ms·

$YOUR_FAVORITE_LANGUAGE almost certainly has a rational library for it. Give it a try and use it for some serious mathematical purpose; nothing will show you wh

by jerf 7y ago

$YOUR_FAVORITE_LANGUAGE almost certainly has a rational library for it. Give it a try and use it for some serious mathematical purpose; nothing will show you why we don't do that all the time like trying it. I invite you to ignore any syntactic issues that may arise, like perhaps having to use x.Add(y) instead of x + y. If those were the fundamental problems, the solution would be trivial. That's not the fundamental problem with rational numbers being the pervasive default; the problem is that for your increased precision, you pay for algorithms that you are used to being O(1) in space and time, albeit with potentially imprecise results, suddenly taking on seemingly-random values for both, with disturbing amounts of things like "O((log2 denominator + log2 numerator)^2)" showing up and then stacking on top of each other (^4, ^6, ^8, etc.).

rini17 7y ago
What operation takes O((log2 denominator + log2 numerator)^2) for fixed-length fractions? Basic arithmetic operations are constant time. Rounding is too mathematically well-understood and should have efficient implementation. All the rest you say applies to floating point alike, plus with fractions is much easier to test whether the result is accurate or not.
- jerf 7y ago
  Your original post used the term "rational" when I read it, which is usually used to describe a library in which numbers are represented as arbitrary-length integers, expanded as needed to maintain accuracy. Those tend to explode pretty quickly in real usage as the arbitrary-length integers grow quickly. In this post you say "fixed-length fractions", but I don't know exactly what that is: https://www.google.com/search?hl=en&q=fixed%2Dlength%20fractions https://www.google.com/search?hl=en&q=fixed%2Dlength%20fract... Some of my natural expansions I can see how they'd have algorithmic complexity equal to floats, but they're going to have similar (not identical, but similar) pathological cases. Based on what you sketch in your post, if you mean, two fields of fixed-length integers, that's got all kinds of problems that will be a non-starter; redundant representations means the equality operator becomes more complicated than a bitwise comparison involving factoring (IEEE floating point has some issues here but they're at least designed to be amenable to hardware, this factoring thing is going to be a problem at base silicon levels), plus redundant representations means you're wasting valuable bit patterns, you can't represent anything bigger than a MAX_NUM / 1 so you're going to pay a lot for larger numbers, etc., and you still have the problem that your operations won't be closed and you'll be approximating anyhow; you're going to end up with most of floating point's problems anyhow. I know there are alternatives to floating point, such as "universal coding": https://insidehpc.com/2018/05/universal-coding-reals-alternatives-ieee-floating-point/ https://insidehpc.com/2018/05/universal-coding-reals-alterna... They would also have similar complexity to floats, but move the pathological behaviors around. (The question in terms of trying to replace floats isn't whether you can get rid of the pathological behaviors; you can't, just by the nature of the beast. But nothing says you can't hide the pathological behaviors under the carpet, under the couch, in the corner of the room, instead of having it pretty close to sitting in the middle of the commonly-traveled path.)
waqf 7y ago
And yet if you announced to a general audience of programmers that you had a marvellous new programming language that guarantees performance but doesn't guarantee correctness, you'd be laughed out of the room.
- papln 7y ago
  Of course, a general audience of programmers prefers JavaScript and Python, because we want our languages to be both slow and incorrect. More seriously, general programming always prefers performance over correctness, because correctnes is expensive and very few programs are rocket surgery where perfect correctness matters. We have languages decdicated to correctnes, like Ada and Coq. They are very niche because they are slow and they require a lot of work the programmer doesn't want to do to hold up their end of the bargain.

by jerf 7y ago

rini17 7y ago

What operation takes O((log2 denominator + log2 numerator)^2) for fixed-length fractions? Basic arithmetic operations are constant time. Rounding is too mathematically well-understood and should have efficient implementation. All the rest you say applies to floating point alike, plus with fractions is much easier to test whether the result is accurate or not.

jerf 7y ago
Your original post used the term "rational" when I read it, which is usually used to describe a library in which numbers are represented as arbitrary-length integers, expanded as needed to maintain accuracy. Those tend to explode pretty quickly in real usage as the arbitrary-length integers grow quickly. In this post you say "fixed-length fractions", but I don't know exactly what that is: https://www.google.com/search?hl=en&q=fixed%2Dlength%20fractions https://www.google.com/search?hl=en&q=fixed%2Dlength%20fract... Some of my natural expansions I can see how they'd have algorithmic complexity equal to floats, but they're going to have similar (not identical, but similar) pathological cases. Based on what you sketch in your post, if you mean, two fields of fixed-length integers, that's got all kinds of problems that will be a non-starter; redundant representations means the equality operator becomes more complicated than a bitwise comparison involving factoring (IEEE floating point has some issues here but they're at least designed to be amenable to hardware, this factoring thing is going to be a problem at base silicon levels), plus redundant representations means you're wasting valuable bit patterns, you can't represent anything bigger than a MAX_NUM / 1 so you're going to pay a lot for larger numbers, etc., and you still have the problem that your operations won't be closed and you'll be approximating anyhow; you're going to end up with most of floating point's problems anyhow. I know there are alternatives to floating point, such as "universal coding": https://insidehpc.com/2018/05/universal-coding-reals-alternatives-ieee-floating-point/ https://insidehpc.com/2018/05/universal-coding-reals-alterna... They would also have similar complexity to floats, but move the pathological behaviors around. (The question in terms of trying to replace floats isn't whether you can get rid of the pathological behaviors; you can't, just by the nature of the beast. But nothing says you can't hide the pathological behaviors under the carpet, under the couch, in the corner of the room, instead of having it pretty close to sitting in the middle of the commonly-traveled path.)

waqf 7y ago

And yet if you announced to a general audience of programmers that you had a marvellous new programming language that guarantees performance but doesn't guarantee correctness, you'd be laughed out of the room.

papln 7y ago
Of course, a general audience of programmers prefers JavaScript and Python, because we want our languages to be both slow and incorrect. More seriously, general programming always prefers performance over correctness, because correctnes is expensive and very few programs are rocket surgery where perfect correctness matters. We have languages decdicated to correctnes, like Ada and Coq. They are very niche because they are slow and they require a lot of work the programmer doesn't want to do to hold up their end of the bargain.