I'm looking for a reasonably(*) space-efficient way to encode arbitrary-precision decimals (e.g. BigDecimal), such that when sorting the bit-pattern of the encodings lexicographically, the numbers will be sorted numerically. This is related to this Stackoverflow question.
One simple/naive approach to this would be to convert the number to some IEEE-like representation with some 8-byte exponent (which is what RR in the NTL does?), but obviously this is quite an inefficient(*) representation.
Is there perhaps some other approach to this? Are there any optimizations possible for arbitrary-precision Integers? The encoding need not support any other operations than sorting (and, if possible, decoding the number again).
(*) By reasonably speace-efficient I don't mean cramming bits together into bytes like IEEE-754 does. I just don't want to have any unnecessarily large fields that will remain mostly empty in a large number of situations (as would be the case with an 8-byte exponent). The motive for this is that the (encoded) number will later on be processed by this scheme, which takes a few milliseconds per byte to run.
The runtime-efficiency of the encoding/decoding on the other hand isn't much of an issue (anything less than 10 ms for 128 bytes of data will still be overshadowed by the runtime of the OPE scheme liked above).
(Also note, this should be a decimal representation, so there are to precision-issues due to "binary stuff".)