Space-efficient representation of potentially very large arbitrary-precision rationals?

Question

I'd like to know if there are good techniques for faithfully and (reasonably) representing rational numbers with forms similar to:

1. 2/3
2. 1/10
3. 4 * 10 ^ 1,000,000,000,000

I know arbitrary precision rationals can be represented by pairs of arbitrary precision integers, and they can be normalized using gcd, so operations like equality testing are efficient. But trying to represent (3) this way would quickly exhaust memory.

(3) can be dealt with efficiently and faithfully with a scientific-notation-like representation, but this can't faithfully represent all rationals.

Is there a way to get the best of both worlds, i.e. be able to both faithfully represent all rational numbers, and deal with very large numbers efficiently?

Answer 1

Is there a way to get the best of both worlds, i.e. be able to both faithfully represent all rational numbers, and deal with very large numbers efficiently?

No.

We cannot even represent all integers faithfully as well as deal with very large integers efficiently. If we want to express all integers between 1 and $2^{1,000,000,000,000}$ faithfully, we need about $1000,000,000,000$ bits, i.e. 1000G bits for a single number on average. If we do not have that many bits, pigeon hole principle tells us that there must be two numbers that will be represented exactly in the same way.

Almost nothing around that magnitude of bits can be said to be efficient by the absolute scale even if you get hold of most powerful supercomputers. In fact, multiplication of two integers with mere 1000001 digits within 2 seconds is consider a pretty hard problem on a programming site.

As D.W. pointed out, "the best you can do is probably to identify the classes of numbers you want to represent efficiently and then choosing a representation that handles those particular classes."

Or we can restricted our playingground to those numbers that can be represented faithfully easily and, hopefully, manipulated efficiently. For example, the search for the largest prime numbers are mostly restricted to the Mersenne numbers, which are of the form $2^n-1$. Mersenne primes include all top 5 largest primes known to mankind, the largest one being is merely $2^{82,589,933} − 1$, i.e. a humongous number with 24,862,048 digits.

Answer 2

Representing a rational number as ${a \over b} \times c^d$ where $a,b,c,d$ are integers can represent all three classes of numbers you mentioned efficiently. You can do standard operations on numbers represented in this way, but some of those operations will be inefficient: for instance, $10^{10000000}+1$ will be inefficient.

For any representation you have in mind, there will be some rational numbers that can be specified concisely in English but that require a huge amount of memory to represent with that representation scheme, so there is no one answer that will handle everything efficiently -- the best you can do is probably to identify the classes of numbers you want to represent efficiently and then choosing a representation that handles those particular classes.