4

The basic arithmetic a computer chip can do only works on numbers(integers or floating point) of a fixed size.

There are many algorithms that could be extended to work on numbers of arbitrary size (and some require them). Therefore, a way to store and perform arithmetic with arbitrary-size numbers is good to have.

For arbitrary-size integers, the approach usually is to take a list of bytes (which each can store a value in the 0-255 range) and have the final 'big number' (often shorted as bignum) then be base-256, by using each of these bytes as 'digits' (ducentiquinquagintiquinquesexa-its?).

For any non-integer arbitrary-sized real number, there exist two different ways of representation:

  • decimals, which consist of an arbitrary-size 'big number' mantissa and exponent. The number is represented by sign(+1 or -1) * mantissa * pow(base, exponent) (where base is usually 2 or sometimes 10)
  • rationals, which have an arbitrary size 'big number' numerator and denominator. The number is represented by numerator / denominator

In practice, I've found many more languages and libraries to use/support decimal data types than rational data types. An example of this are (SQL) data stores, which have a native DECIMAL data type but not a rational one.

Why is this the case? Why are decimal data types preferred over rational ones?

Qqwy
  • 4,709
  • 4
  • 31
  • 45
  • 1
    Probably because humans find 3.08049554263371 easier to comprehend than 8928492384932/2898394839844. – Jasmijn Aug 25 '16 at 11:44
  • 2
    @Robin That is only a matter of presentation; inside a computer, numbers are usually stored in binary, so internally it would be e.g. `01000000 01000101 00100110 11010111` for a simple float. Neither decimals nor rational numbers change this fact. – Qqwy Aug 25 '16 at 12:17

4 Answers4

7

One reason might be simply that programmers are more used to decimal number representations, or that their arbitrary-precision library does not support rationals.

Another reason might be an additional performance penalty:

One central operation you certainly have to do on rational numbers is to reduce numerator and denominator. If you keep computing (addition, multiplication, etc) on rational numbers, the numerator and denominator usually grow fast (e.g. when adding two numbers with no common factors).

Reducing rational numbers requires you to determine the greatest common divisor, which is an expensive operation compared to a simple addition of rational numbers.

In general, a/b + c/d can be computed by (a*d + c*b) / (b*d), that's three integer multiplications and one addition. However, this makes both numerator and denominator large. For instance, 1/3 + 1/6 = 9/18 instead of 1/2. (Of course, these can be made a bit more efficient, but the worst case complexity is the same.)

Thus, you need to compute the gcd. This is an additional computation step. (Although, from a theoretical point of view, the worst case complexity is probably the same as for decimal operations.)

Edit

Some more explanations why I suppose that rational arithmetic might be slower in practice that decimal arithmetic. (Though this should be tested, e.g. using gmp.)

Basic operations (add, multiply) on arbitrary precision integers and decimals have a theoretical complexity of O(log n), that is linear in the number of bits. Thus to add two decimals n, you require O(log n) time.

Rational numbers are represented by two arbitrary precision integers. A first observation one can make is that both numerator and denominator can have the same number of (decimal) digits than its decimal counterpart. (Though this is not true for all numbers, e.g. 1/3, and binary representation is also a different story. But in many cases, that's the case.)

Consider, e.g. 0.000000000000000994030870125414 (30 digits). In rational that is 5040335316639481 / 5070602400912917605986812821504 (16 + 31 digits). Thus, for a simple add, both representations require operations on approx. 30 digits—the decimal add operation is really only a digit-wise add, whereas add in rationals are three multiplications and one add - not counting the gcd.

Note: I am not advocating against rational numbers. It really depends on the application what representation is the most useful.

Community
  • 1
Martin Nyolt
  • 227
  • 2
  • 8
  • This is very interesting! I wonder, however, how decimals take care of the difference in exponents during `+ - * /` and how fast that operation would be. – Qqwy Aug 25 '16 at 12:24
  • 1
    @Qqwy I wrote [a Java class](https://gist.github.com/SOF3/be148a38cf974d4d49e624ec09d8dc0f) that simulates the floating point structure except that it has arbitrary length and base, implementing the `+` `-` `*` operations. If my implementation is similar to what the processor does, adding two floats will require comparison and subtraction of two exponents, then copying the exponent to the next float, then internally adding each digit in the exponentially larger float to the respective (`i + expDelta`) digit in the exponentially smaller float. This is much less heavy. – SOFe Aug 25 '16 at 13:03
  • 3
    Calculating the GCD is not expensive. It runs in linear time in the number of bits in the number. – kevin cline Aug 25 '16 at 19:17
  • I did not say it is expensive. I also said that the theoretical complexity is the same (`O(log n)` for both decimals and rationals, although I can make that more clearer). — Admittedly, I have no reference that the gcd is *in practice* more expensive, but that's what I assume. I will edit my post. – Martin Nyolt Aug 26 '16 at 07:35
2

A quibble

Arbitrary-precision decimals are actually fairly rare. E.g. although you mention SQL in the question, the SQL standard doesn't require implementations to support arbitrary precision. E.g. MS SQL Server only supports up to 38 digits of precision. Other libraries could more accurately be described as supporting variable precision rather than arbitrary precision: e.g. Java's BigDecimal operates within a MathContext which defines the precision of the results of an operation. A true arbitrary-precision implementation wouldn't require you to commit up front to the precision you will need in the future. (Yes, that means it must necessarily be lazy).

Relevance

Why am I making this distinction? Because when you're working with fixed precision (whether limited, as in SQL Server, or variable, as in Java) a series of operations uses a predictable amount of memory. When working with rationals, on the other hand, the memory usage can grow without bound.

This is an important difference which I believe goes a long way to explaining why historically language and library designers have favoured decimals over rationals. Particularly when you look at e.g. SQL, which is a product of an era when memory was much more restricted than today, it makes sense to choose a representation which allows you to bound your memory usage in advance.

Other plausible factors

I don't say that memory bounds are the only factor that influenced design decisions. There are two other plausible factors which come to mind readily:

  • The familiarity of the first generations of computer scientists with decimal tables of logarithms etc.
  • Hardware support. Back in the day, some instruction sets included instructions for operating on binary-coded decimal.
Peter Taylor
  • 4,012
  • 1
  • 24
  • 29
1

How do you represent an irrational number like e as a rational number?

You can get arbitrarily close, but that would require extremely huge numerators and denominators.

To avoid overflowing the memory for just one number, you'll have to limit how much precision, or how many places behind the decimal point, you'll like.

This you just do by using decimals.

Bent
  • 2,566
  • 1
  • 14
  • 18
  • representing an irrational number like e as a decimal with mantissa and exponent isn't better either? – gnat Aug 25 '16 at 12:09
  • The point being that you will have to chose your precision anyway. So why not user a simpler concept? – Bent Aug 25 '16 at 12:15
  • I actually see decimals and rationals as being equally complex, both in human understanding as in algorithic implementation. The matter of _efficiency_ is a different beast, however. – Qqwy Aug 25 '16 at 13:51
  • 1
    Floating-point formats are essentially rational representations, with severe restrictions placed on the denominator: in the case of IEEE-754 binary floating-point, the denominators are powers of two, for BigDecimal they are powers of ten. Allowing arbitrary denominators in rational arithmetic can lead to approximations that are *more* accurate while using the same number of bits. Trivial example: 1/3 – njuffa Aug 25 '16 at 17:18
0

For most applications, decimals are just efficient and good enough; and the specialized alternatives do exists, if needed.

Rational numbers are not very useful in real life. As soon as you leave the + - * / range, you are in irrational numbers, which per definition - cannot be written as 'a/b'.

Integers give you exact math for + - *; rational give you exact math for only /, and everything else (sqrt, log, sin, etc.) needs to support irrational numbers.

If you find an exact way to store irrational numbers exact (including transcendent irrational), that would be something that probably would be very useful. But that is not possible.

Aganju
  • 1,453
  • 13
  • 15
  • 3
    Your argument, 'irrational numbers cannot be stored i a rational data structure' is true, but it is equally true for a decimal data structure. On the other hand, numbers like `1/3` that have an infinite amount of decimals _can_ be stored in a rational data type but not in a decimal one. – Qqwy Aug 25 '16 at 12:11
  • Yes, but my point is that numbers like 1/3 are very seldom useful, only for special applications (and such implementations exist). Most real life math needs more than _rational_ numbers. Also, what is the gain of storing infinitesimal accuracy over 64 bits of accuracy? For _most_ applications, it does't matter. – Aganju Aug 25 '16 at 12:35
  • The main reason is the accumulation of rounding errors, which are bound to happen in any non-arbitrarily sized floating-point data structure. This makes it necessary to use something better when dealing with e.g. monetary values. Is a correct interpretation of your answer then: _"The difference between rationals and decimals doesn't really matter, because they are both too limited for anything but the basic(`+ - * /`) arithmetic operations"_? – Qqwy Aug 25 '16 at 12:44
  • Decimals and floats don't support irrational numbers either. So, most "real life math" on computers gets done without irrational numbers. – COME FROM Aug 25 '16 at 12:50
  • 1
    That's half of it, the other half is that decimals are 'good enough for 99.99% of uses'. There are solutions existing for special cases; they are just not useful as a standard solution. The question says _"Therefore, a way to store and perform arithmetic with arbitrary-size numbers is good to have."_ and I agree. Just not useful for everybody all the time. – Aganju Aug 25 '16 at 12:51
  • 1
    @Qqwy I suppose it is probably easier to compute `sin(sqrt(PI))` into a decimal rather than a rational, because reducing the precision of a float is probably easier than reducing the precision of a decimal in such cases. For example, if you compute square root using [this algorithm](http://stackoverflow.com/a/1624602/3990767), the base part quickly overflows. – SOFe Aug 25 '16 at 14:34