18
$\begingroup$

(By rationals, I mean fractions. So, 0.5 would be stored as 1/2.)

There's only one language I know of which does this. So, what are the advantages and disadvantages of it?

$\endgroup$
11
  • 1
    $\begingroup$ @SolomonUcko I thought it meant numbers which have a decimal place. Do you want me to change it to "real"? And I'm thinking of Vyxal. $\endgroup$
    – The Thonnu
    May 16, 2023 at 17:11
  • 8
    $\begingroup$ Lots of language support both. Most Lisps I know use rationals and devolve into floats when you do something like sqrt that's inherently imprecise. Raku works similarly. $\endgroup$ May 16, 2023 at 17:42
  • 2
    $\begingroup$ Every single CAS language does this, for very obvious reasons. $\endgroup$
    – SK-logic
    Jun 28, 2023 at 10:56
  • 3
    $\begingroup$ It would be interesting for a rational number's representation to include an extra 64 bits for a floating-point value, and have all operations perform both calculations. It's already big and slow, so it wouldn't make much difference to the performance, but it would make it easy to observe how much difference the two values have when the results are displayed. (e.g. for a specific application, confirming that the rational numbers do give a significantly better answer, or discovering that they really weren't needed.) $\endgroup$ Jun 28, 2023 at 12:18
  • 1
    $\begingroup$ @RayButterworth if you want to see how much precision you're losing by using floating point, there is interval arithmetic for you. It can even be fast and hardware-assisted. $\endgroup$
    – SK-logic
    Jun 29, 2023 at 8:39

7 Answers 7

32
$\begingroup$

Floating-point vs rational representation

Advantages of rational representation:

  • Precision: rational numbers are exact. 1/7 prints as 1/7. 1/7 in floating-point prints as 0.14285714285714285. When doing complex arithmetic floating-point numbers will start to have minor offsets like 5.7000000000000152
  • Consistency: because of precision, rational numbers don't suffer from floating-point errors [2], so they don't have issues like (0.1 + 0.1 + 0.1 != 0.3)
  • Easier to understand: rational numbers are taught in elementary school, whereas many people don't understand how floating-point numbers actually work
  • Easier to reason about mathematically: Because we have more literature on rational numbers than floating-points. Also, they're easier to reason about formally (e.g. prove theorems): when proving theorems about floating-point arithmetic, you have to handle its inconsistency, which makes the proofs much harder

Advantages of floating-point representation:

  • Performance: Floating-point arithmetic is much faster than rational arithmetic, computers have built-in hardware and floats have been designed to be used in AAA games, neural network simulations, and other speed-critical processes. It also uses lower energy consumption
  • Space: If you define rational numbers to take up bounded space (e.g. i32 / i32), you severely restrict the range of numbers that can be represented, and you essentially lose all of the advantages described above since you can no longer represent the results of certain arithmetic. So rational numbers are usually defined to take up unbounded space. But this means they almost always take up most space than floating-point, and depending on the computation, their space requirements increase fast.
    • Floating-points can represent extremely large and extremely small finite values in 64-bits (as large as 1.8e308 and as small as 4.9406564584124654e-324), by skipping intermediate numbers (i.e. 1.8e308 - 1 == 1.8e308). Rational numbers can also represent numbers of these size but they take up a lot of memory
  • Floating-point can approximate any real number: there's also π, e, "sqrt(n)" and other numbers which don't have explicit representations in floating point, but do have approximate ones. Approximating floating-point numbers is practically always ok because they are already inaccurate. But if you decide to approximate rational numbers, you lose the "exact" advantage, and must be careful on how you approximate to avoid losing the others.

Alternate number representations

What if you want to exactly represent irrational numbers as well? You can extend your number definition to include not only rational numbers, but other constants and functions. Or, you can just directly encode mathematical formulas. The downside of this representation is that it's very complex and canonicalization varies from difficult to literally undecidable; you will have equivalent numbers that can't be proven equivalent, you will have numbers that you don't know are positive or negative, etc..

There are even more alternate representations. Fixed-point lets you represent exact numbers like currency as integers by putting the decimal at an arbitrary position (e.g. 3.54 represented by the integer 354, 400.62 represented by the integer 40062). This representation is very similar to integers, and has most of their benefits and drawbacks which can be discussed in a separate question. Then there are esoteric representations like logarithmic, tapered floating-point, and interval arithmetic, many of which have specific use cases (for instance, intervals can be used to put a precise bound on how much a floating-point could be inaccurate, to maintain consistency as described above).

See here for more info.

How are they used in practice?

Floating points are used much more than rational numbers. In fact, often when developers need precision, they figure out a way integers instead of decimals at all, such as in Elliptic Curve Cryptography. The space complexity and degraded performance are a big issue.

However, rational numbers are still very important, particularly in scientific computing where precision is important and performance is negotiable. Some languages have rational numbers in their standard library including C++, Clojure, Racket (in fact, most lisps), Python, Julia, Haskell (see more)

$\endgroup$
5
  • 3
    $\begingroup$ Another interesting alternative is the floating bar representation. Basically it is a fixed number of bits, but a few bits are used to control how many of the remaining bits are used for the numerator vs. the denominator. $\endgroup$
    – kaya3
    May 16, 2023 at 18:34
  • 3
    $\begingroup$ Good answer! One minor nitpick: while it's true that not all real numbers are rational, that has nothing to do with +/- Infinity and NaN, which are not real numbers. (And it would be pretty easy to represent them in a rational number type as 1/0, -1/0, and 0/0.) $\endgroup$
    – DLosc
    May 16, 2023 at 18:40
  • 1
    $\begingroup$ Another approach that a language I'm working on uses is storing numbers as infinite series of rationals. So you get the precision of rationals, the acceptable fuzziness of floats with irrational values, and...the performance of neither :p $\endgroup$ Jun 29, 2023 at 16:39
  • 1
    $\begingroup$ @RydwolfPrograms How does this compare to the Cauchy definition of real numbers? $\endgroup$
    – James Wood
    Jul 5, 2023 at 22:03
  • 2
    $\begingroup$ @JamesWood Never heard of it. Looks like it's very similar though, so you've just given me a useful search term for finding prior work :p $\endgroup$ Jul 6, 2023 at 1:10
8
$\begingroup$

I am implementing a language that uses rationals by default. Let me tell you why.

The other answers are correct that performance and memory use are worse with rationals. My rationals are 32 bytes against an 8-byte, 64-bit floating point double.

And yet most uses of programming languages are for one-off scripts. The vast majority, in fact. In those cases, the programmer/user just wants to accomplish the task at hand and move on, not caring about performance because it's probably "good enough."

It's best if they don't have to worry about stupid issues like overflow, underflow, catastrophic cancellation, or any such type of bug.

So by default, my language uses rationals. In fact, users will also be able to attach units to numbers and will handle all conversions itself; the user just says the input units and the output units.

This will avoid bugs for the 99% case of a quick script when performance doesn't matter.

Of course, it will also have floating point, fixed-point, and standard integers. You'll also be able to attach units to those.

So yes, the cons the other answers listed exist. But the biggest pro of rationals, in my opinion, is that they help the user avoid bugs.

$\endgroup$
2
  • $\begingroup$ Are you aware of the Frink programming language? It sounds like there is some overlap regarding numeric types (including intervals) and units and unit conversions. $\endgroup$ Jun 29, 2023 at 5:25
  • 2
    $\begingroup$ Very aware. I was going to generate my units from Frink's incredibly awesome and downright snarky units file. The thing with Frink is that it focuses on being a bc-like language rather than a general-purpose one, so I'm making a more general-purpose one. And yes, I'll have intervals too. $\endgroup$ Jun 29, 2023 at 11:38
7
$\begingroup$

Why not both?

That is, make your “real” type a variant that can store either an exact rational or an approximate floating point value.

You could make rational the “default”, in that literal 0.1 would represent the fraction 1/10. But 0.1f would be the floating-point approximation 0xCCCCCCCCCCCCD × 2-55 = 0.1000000000000000055511151231257827021181583404541015625 (assuming IEEE 754 double).

The operations +, -, *, and / on rationals, plus int / int division, would return a rational. But any arithmetic involving floating-point, and any non-rationality preserving mathematical functions like trig or logarithms would return a floating-point value.

That way, you get exact arithmetic when you can, and approximate arithmetic when you need it. If rational arithmetic is hurting performance for a particular algorithm, a simple typecast to float or multiplication by 1.0f will force floating-point arithmetic.

$\endgroup$
5
$\begingroup$

Advantages

  • Rationals can exactly represent a much wider range of numbers. One-third would be finitely representable.
  • Floating point errors would be unheard of.

Disadvantages

  • It is computationally much more expensive to compute with arbitrary-sized rationals.
  • If you do not reduce them, they may take up a lot more memory, even with the same number. 1/1 takes up a lot less space than 100000/100000.
$\endgroup$
4
  • 6
    $\begingroup$ Worth stressing that there's not only a little but rather a huge gulf between the efficiency of computing with floats (with support built into the processor) and arbitrary-size rationals. $\endgroup$
    – Noldorin
    May 16, 2023 at 18:31
  • $\begingroup$ Is the computational penalty just a legacy? If we had good reasons to always use rationals instead of floating-point, then processors would have built-in rational arithmetic, and rational arithmetic would be as fast as floating-point arithmetic, wouldn't it? Or would it still be prohibitively expensive to have to compute gcd too often to simplify fractions? $\endgroup$
    – Stef
    Jun 28, 2023 at 16:38
  • 5
    $\begingroup$ @Stef: The technical difficulty with hardware rational support is that you'd need support for arbitrary-sized integers, which aren't suited to fixed-size registers and ALUs. Unless you imposed a restriction like “numerator and denominator must each fit in 64 bits”, but then you'd lose exact arithmetic. $\endgroup$
    – dan04
    Jul 5, 2023 at 16:15
  • 2
    $\begingroup$ For a given representation size, floating-point can represent more numbers (and a bigger range), because every non-NaN float represents a distinct value. There's holes in the rational space, because, e.g. ²⁄₄ == ¹⁄₂. $\endgroup$ Jul 19, 2023 at 15:18
3
$\begingroup$

What are the advantages and disadvantages of implementing reals as rationals?

The biggest disadvantage is that it is not possible. There are countably infinitely many rationals, i.e., there are exactly as many rationals as there are natural numbers. However, there are uncountably infinitely many reals, i.e., there are strictly more reals than there are rationals (infinitely more, in fact).

Therefore, reals cannot be represented as rationals. This has been known for at least 2500 years when the irrationality of √2 was proven by the Pythagoreans in Ancient Greece.

$\endgroup$
8
  • $\begingroup$ Did you see the other answers that say it is possible? This is wrong. $\endgroup$ Jun 28, 2023 at 11:19
  • 1
    $\begingroup$ @Starship-OnStrike You cannot represent all real numbers on a computer. This is a direct result of the cardinality issues Jörg mentions. In particular, you cannot represent the uncomputable real numbers. These are particular real numbers that you cannot represent on a computer, regardless of how you try to represent them. See the answers here, for example. Also this $\endgroup$ Jun 28, 2023 at 14:40
  • 5
    $\begingroup$ This argument applies equally against both rational and floating-point representations, and also every other representation. In fact it's worse for IEEE 754 floating-point representations, because they are limited to a finite number of representable numbers, whereas rational representations using bigints can at least represent countably many numbers (subject to memory availability). $\endgroup$
    – kaya3
    Jun 28, 2023 at 16:05
  • 1
    $\begingroup$ @kaya3-supportthestrike That is true, but it seems like this is important to mention those things when the question is "What are the advantages and disadvantages of implementing reals as ..." regardless of what follows the word "as," since the question is already not (fully) possible. This answer relates to the "implementing reals ..." part rather than the "... as rationals" part and both parts are important to the question, IMHO. $\endgroup$ Jun 28, 2023 at 16:41
  • 2
    $\begingroup$ @DavidYoung I think it is utterly unimportant. The question is about rational representations compared to other representations, not about whether reals should or shouldn't be represented by a data type at all. Even so, the fact that a representation isn't perfect doesn't mean that a representation isn't possible. $\endgroup$
    – kaya3
    Jun 28, 2023 at 16:47
3
$\begingroup$

Fractions allow absolute precision with values where operations with floats would be only approximate. Even such innocently looking fractions like 0.1 are infinite in they binary representation as used by computer, so results are not precise. 0.1 decimal is 0.00011001100110011 ... binary.

While in many cases this rounding error is small and not worth to be cared about, there are algorithms and use cases where it accumulates over many iterations, making result totally wrong.

$\endgroup$
3
$\begingroup$

There are no advantages and disadvantages, because in real programs, people will need both depending on the situation.

For example, if you are representing money, and using floats, it may make a number slightly off in some cases, and causes a lot of hassle. And if you just multiply the number by 100 or anything appropriate for the currency unit you are using, it may make it easier for someone to accidentally type the wrong number. A fixed point type is what you would want. Fraction is a generalization to a fixed point type. On the other hand, if you are adding a lot of relatively small reals with unequal denominators together, you could easily get a denominator so large that wastes memory and makes the computation slow. Floating points would be necessary in this case.

So, whatever you choose, if people use your language a lot and use it for every task, they will want to also define the other by themselves. So it's a good idea to have them both. If you have to choose only one, notice that there is little to no performance loss if someone defines a rational type by themselves, but there is very much for a floating point type, because in this case it's very likely it would not be able to use the floating point instructions of the CPU.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .