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