Space-efficient representation of potentially very large arbitrary-precision rationals? I'd like to know if there are good techniques for faithfully and (reasonably) representing rational numbers with forms similar to:


2/3
1/10
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?
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.