4 ms·

Half-OT: What's the reason rationals aren't used often in programming?

by k__ 5y ago

mjburgess 5y ago
You mean full-precision integer representations? A percentage is effectively this -- and floats are often multipliers on integers which are "holding the precision". However it isn't clear what standards sorts of arithmetical use cases storing two integers helps with (over, say, integer & float, etc.).
- k__ 5y ago
  I'm not sure either, that's why I asked. :D
  - mjburgess 5y ago
    I'm not an expert but, certainly, (1) limited memory on historical machines necessitated a small-width representation of a real number; (2) limited cpus meant simple operations needed to be applied to this small-width representation in one go. Ie., your CPU is just a system for taking bit patterns and producing new bit patterns: (0000 0000) -> (1010 0101). So you want each individual number to be of a size the processor can operate on in one pass. By using two integers you gain some capacity (ie., you can still overflow), but lose memory and compute performance.
hansvm 5y ago
Rationals are typically slower (gcd operations) and prone to memory explosion if the set of possible denominators isn't extremely nice. If approximate answers suffice then a scheme like floats or doubles is usually good enough. If approximate answers suffice and floats or doubles have undesirable properties (weird density distributions, ranges larger than what your application needs, ...) then it's easy to hack something together with a few _bounded_ integer types which has better properties for your specific needs. In most other practical applications some kind of a fixed-precision decimal suffices. It's a bit slower than floats and might have undesirable memory characteristics, but broad classes of real-world numbers which need to be represented exactly (like financial data) are nicely represented. Compared with those (and other) schemes, what advantages do rationals have? Chiefly, they admit an exact representation of any rational number. If you can mitigate the downsides (e.g., by not having many possible denominator prime factors) and need those benefits then rationals might be a good fit. One practical situation where I occasionally like to use rationals is in account data -- credits, currencies, .... It lends itself to forward compatibility when new features are desired (most often that the smallest atomic unit in a currency changes or that some niche system wants to offer transactions for 1/3 of a unit). Such changes usually have small, nice, compatible denominators, so you don't have unbounded memory issues. More importantly, all such operations are exact by definition without any extra work on my part (the biggest challenges are in display and formatting if your business admits those sorts of oddities).
ekimekim 5y ago
If you mean "representing values as a pair of integers P, Q, such that the value = P/Q", the answer is that they're very expensive to work with. You generally need to be using arbitrary-length integers for P and Q, because the values get very large very quickly. And as the values get large, operations like finding the lowest common multiple (required for almost any operation between two rationals) get expensive. As an example of the kinds of runaway increase in P and Q I'm talking about, consider calcuating the sum of x/(x+1) for values of x from 1 to 999, using python's fractions module: >>> sum(Fraction(x)/(x+1) for x in range(1000)) Fraction(7075502361382798268120793110090229940258706389605508780354900641905867818691614397718938054011886551220308728288024788414601821895503124242001568659978565050184167864774563757893457200995977901194872761682228965032590045181707202517783731540396927542180527680245723964874429994374505238893797078720320991788231820649513569449454767125309918934132672543174716802507966087781714014833406311821646176291230132112749836042537756095388477483, 7128865274665093053166384155714272920668358861885893040452001991154324087581111499476444151913871586911717817019575256512980264067621009251465871004305131072686268143200196609974862745937188343705015434452523739745298963145674982128236956232823794011068809262317708861979540791247754558049326475737829923352751796735248042463638051137034331214781746850878453485678021888075373249921995672056932029099390891687487672697950931603520000) That's a 436-digit P and a 433-digit Q. Rational types like this can definitely be a good choice in a use-case where accuracy is important, and operations do not compound. But they're a poor default, which is why we generally see float types as the most common non-integer number representation.
- k__ 5y ago
  Makes sense. Thanks!
- renox 5y ago
  If languages used float-intervals instead of just float that would be a reasonable explanation. But Frink is the only language I know which default to floating point ranges.
lioeters 5y ago
I'm guessing the reason it's not often used in programming is due to slower performance and larger memory requirements. I typically see rationals (numerator/denominator pair) used in arbitrary-precision libraries. > ..Arithmetic with rational numbers can become unwieldy very quickly: 1/99 − 1/100 = 1/9900, and if 1/101 is then added, the result is 10001/999900. https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic
dkarl 5y ago
Few applications need them for correctness according to domain requirements. Compare with fixed-precision decimal encodings, which are mathematically less fundamental, but are common in programming because many applications require monetary amounts to be calculated using fixed-precision arithmetic. It's true that floating point calculations are much faster, but we do a lot of expensive things in code when we need to, and people do use rational types when they need exact rational arithmetic. It just doesn't happen very often.
marcosdumay 5y ago
You obviously can't have the entire rationals, because your computer's memory is finite. And if you are approximating anyway, adding space to the mantissa of both the numerator and denominator will approximate values about as well as adding space only into one of them (the actual gain grows with O(log(n)) of those sizes). Thus, if you won't work with exact numbers, the best choice to represent rationals is to place all bits you can at the mantissa of a single side, and just store the order of magnitude of the other side. And, for simplicity you want the mantissa on the numerator side. What is basically a floating point number. Things are very different if you will work with exact numbers.
- alisonkisk 5y ago
  > You obviously can't have the entire rationals, because your computer's memory is finite. This doesn't matter, because our programs and data are finite. Bignum (which is plain old Integer in Haskell) is unbounded, but commonm
  - marcosdumay 5y ago
    The memory size does not matter. For any finite size, you will get a closer approximation of the rationals from floating point than by a ratio of integers. The difference ratio only gets bigger when you add more memory.

Half-OT: What's the reason rationals aren't used often in programming?

by k__ 5y ago

Half-OT: What's the reason rationals aren't used often in programming?

You mean full-precision integer representations? A percentage is effectively this -- and floats are often multipliers on integers which are "holding the precision". However it isn't clear what standards sorts of arithmetical use cases storing two integers helps with (over, say, integer & float, etc.).

k__ 5y ago
I'm not sure either, that's why I asked. :D
- mjburgess 5y ago
  I'm not an expert but, certainly, (1) limited memory on historical machines necessitated a small-width representation of a real number; (2) limited cpus meant simple operations needed to be applied to this small-width representation in one go. Ie., your CPU is just a system for taking bit patterns and producing new bit patterns: (0000 0000) -> (1010 0101). So you want each individual number to be of a size the processor can operate on in one pass. By using two integers you gain some capacity (ie., you can still overflow), but lose memory and compute performance.

hansvm 5y ago

Rationals are typically slower (gcd operations) and prone to memory explosion if the set of possible denominators isn't extremely nice. If approximate answers suffice then a scheme like floats or doubles is usually good enough. If approximate answers suffice and floats or doubles have undesirable properties (weird density distributions, ranges larger than what your application needs, ...) then it's easy to hack something together with a few _bounded_ integer types which has better properties for your specific needs. In most other practical applications some kind of a fixed-precision decimal suffices. It's a bit slower than floats and might have undesirable memory characteristics, but broad classes of real-world numbers which need to be represented exactly (like financial data) are nicely represented. Compared with those (and other) schemes, what advantages do rationals have? Chiefly, they admit an exact representation of any rational number. If you can mitigate the downsides (e.g., by not having many possible denominator prime factors) and need those benefits then rationals might be a good fit. One practical situation where I occasionally like to use rationals is in account data -- credits, currencies, .... It lends itself to forward compatibility when new features are desired (most often that the smallest atomic unit in a currency changes or that some niche system wants to offer transactions for 1/3 of a unit). Such changes usually have small, nice, compatible denominators, so you don't have unbounded memory issues. More importantly, all such operations are exact by definition without any extra work on my part (the biggest challenges are in display and formatting if your business admits those sorts of oddities).

ekimekim 5y ago

If you mean "representing values as a pair of integers P, Q, such that the value = P/Q", the answer is that they're very expensive to work with. You generally need to be using arbitrary-length integers for P and Q, because the values get very large very quickly. And as the values get large, operations like finding the lowest common multiple (required for almost any operation between two rationals) get expensive. As an example of the kinds of runaway increase in P and Q I'm talking about, consider calcuating the sum of x/(x+1) for values of x from 1 to 999, using python's fractions module: >>> sum(Fraction(x)/(x+1) for x in range(1000)) Fraction(7075502361382798268120793110090229940258706389605508780354900641905867818691614397718938054011886551220308728288024788414601821895503124242001568659978565050184167864774563757893457200995977901194872761682228965032590045181707202517783731540396927542180527680245723964874429994374505238893797078720320991788231820649513569449454767125309918934132672543174716802507966087781714014833406311821646176291230132112749836042537756095388477483, 7128865274665093053166384155714272920668358861885893040452001991154324087581111499476444151913871586911717817019575256512980264067621009251465871004305131072686268143200196609974862745937188343705015434452523739745298963145674982128236956232823794011068809262317708861979540791247754558049326475737829923352751796735248042463638051137034331214781746850878453485678021888075373249921995672056932029099390891687487672697950931603520000) That's a 436-digit P and a 433-digit Q. Rational types like this can definitely be a good choice in a use-case where accuracy is important, and operations do not compound. But they're a poor default, which is why we generally see float types as the most common non-integer number representation.

k__ 5y ago
Makes sense. Thanks!
renox 5y ago
If languages used float-intervals instead of just float that would be a reasonable explanation. But Frink is the only language I know which default to floating point ranges.

lioeters 5y ago

I'm guessing the reason it's not often used in programming is due to slower performance and larger memory requirements. I typically see rationals (numerator/denominator pair) used in arbitrary-precision libraries. > ..Arithmetic with rational numbers can become unwieldy very quickly: 1/99 − 1/100 = 1/9900, and if 1/101 is then added, the result is 10001/999900. https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic

dkarl 5y ago

Few applications need them for correctness according to domain requirements. Compare with fixed-precision decimal encodings, which are mathematically less fundamental, but are common in programming because many applications require monetary amounts to be calculated using fixed-precision arithmetic. It's true that floating point calculations are much faster, but we do a lot of expensive things in code when we need to, and people do use rational types when they need exact rational arithmetic. It just doesn't happen very often.

marcosdumay 5y ago

You obviously can't have the entire rationals, because your computer's memory is finite. And if you are approximating anyway, adding space to the mantissa of both the numerator and denominator will approximate values about as well as adding space only into one of them (the actual gain grows with O(log(n)) of those sizes). Thus, if you won't work with exact numbers, the best choice to represent rationals is to place all bits you can at the mantissa of a single side, and just store the order of magnitude of the other side. And, for simplicity you want the mantissa on the numerator side. What is basically a floating point number. Things are very different if you will work with exact numbers.

alisonkisk 5y ago
> You obviously can't have the entire rationals, because your computer's memory is finite. This doesn't matter, because our programs and data are finite. Bignum (which is plain old Integer in Haskell) is unbounded, but commonm
- marcosdumay 5y ago
  The memory size does not matter. For any finite size, you will get a closer approximation of the rationals from floating point than by a ratio of integers. The difference ratio only gets bigger when you add more memory.