BigInteger, BigDecimal, etc...
Sam Ruby
rubys at intertwingly.net
Thu Aug 21 07:01:19 PDT 2008
On Tuesday's call, Mark Miller asked me to look into whether an
unlimited precision decimal could help address requirements from places
like cryptography for unlimited precision integers.
The short answer is that the result would make decimal less usable, less
portable, less efficient, less future proof, and would provide less than
optimal support for unlimited precision integers.
It is also worth noting that Java, Python, and Ruby all faced similar
choices, and decided to provide separate data types for "big" or "long"
integers and decimal quantities. Given current and foreseeable
hardware, it really makes sense to do cryptography using binary integers
rather than decimal integers, and you certainly would want to minimize
Very Long binary<-->decimal conversions.
But, just to be sure, I asked Mike Cowlishaw, and he provided the following:
1. There's no standard for infinite precision arithmetic -- there are
several possible ways of doing it, and it's not obvious which is right
(IEEE 754r committee debated this at great length, and even had one form
in the draft, covering both binary and decimal -- but couldn't agree on
the details, so it went back out). Java BigDecimal (with no
MathContext) is one way, but it's very slow -- multiplications lead to
ever-longer numbers -- and division is a mess.
2. IEEE 754-2008 does allow arbitrary precision arithmetic, in the sense
that there is a destination format for any result, and that format can
have any precision, p. But there must be a precision (which might be
very large) associated with every operation.
3. 34 digits (decimal128) is the largest IEEE 754 Basic format. There
are no commonly used values > 34 digits in decimal.
4. IEEE 754 interchange formats for decimal are all multiples of 32 bits
(not truly arbitrary), so arbitrary precision cannot be deduced from the
size of an interchange format (additional information giving p must be
supplied). This can be in the context, like rounding mode, but for most
operations a default is needed, and 34 is a good one.
5. There is no hardware support for arbitrary or infinite precision
arithmetic > 34 digits (and nor is there likely to be). Hardware
support for the IEEE 754 basic decimal formats is implemented in two
architectures already (power.org and IBM system z).
6. Arbitrary precision is much more complex to implement in software.
It's about twice as slow for the basic format sizes, and of course might
require memory allocation. This means that arithmetic operations can
fail due to a memory allocation error -- an exception that would not be
expected in most arithmetic contexts.
7. Arbitrary precision functions (exp, log, squareroot, trig functions,
etc.) are much harder to implement than those with a small maximum
precision (even those are hard enough at 34 digits where exhaustive
testing is impractical). For some, algorithms for generating
correctly-rounded results are not known (e.g., power(x, y)), and where
they are known they are not trivial. See, for example Properly Rounded
Variable Precision Square Root, T. E. Hull and A. Abrham, ACM
Transactions on Mathematical Software, Vol. 11 #3, pp229–237, ACM Press,
September 1985.
8. Arbitrary precision means there must also be an exponent range
specified (this is not just a matter of precision), so overflow can be
detected and gradual underflow effected.
- - - - -
There are probably more reasons...
Note that the fixed size could be extended to arbitrary size (with p and
emax in the context) at a later date.
- Sam Ruby
More information about the Es-discuss
mailing list