Subject: Re: [boost] Arbitrary precision arithmetic
From: Jarrad Waterloo (jwaterloo_at_[hidden])
Date: 2009-08-19 09:07:27
Scott Johnson wrote:
> A few other thoughts for things which might be useful--
> 1) a natural type (an unsigned arbitrary precision type). Comes up often,
> and many crypto apps work on unsigned rather than signed ints.
> 2) different division policies as template paramters. One policy option
> would be how division by zero is handled (undefined, exception, use of
> NaN/INF encodings); another would be rounding mode (floor, ceiling, to zero,
> bias-free, throw-if-not-exact, unspecified, etc). Default options, I would
> be think, would be round-to-floor and throw-on-div-by-zero.
> 3) potentially, boost::rational could support NaN/INF encodings as well, for
> those applications where division by zero shouldn't throw.
> 4) certain "combo" operations, such as multipy-accumulate, ternary add and
> subtract, simultaenous div/mod, and modular operations (plus, minus, times)
> ought to be part of the bigint class. Efficient algorithms for things like
> multiplication ought to as well (and selected by default as appropriate).
> 5) crypto-specific algorithms, and things which can be efficiently
> implemented on top of standard arithmetic, should best be put in a separate
> numerical library.
> On Tue, Aug 18, 2009 at 5:50 AM, Jarrad Waterloo <jwaterloo_at_[hidden]
>> Scott Johnson wrote:
>>> This is my first post to the mailing list, so I'll try not to act stupid.
>>> The recent release of Boost (1.39.0), in the boost::rational library
>>> documentation, broadly hints at (and expresses a fond wish for) an
>>> arbitrary-precision integer ("bignum") library; however none currently
>>> exists within Boost. There are numerous such libraries out in the wild
>>> (many targeted towards C); though some of them are under incompatible
>>> (One interesting starting point would be libtommath, by Tom St. Denis; it
>>> appears to be a pretty robust and functional C library; which now has a
>>> wrapper--albeit one that doesn't meet boost standards. It also contains
>>> numerous other useful number-theoretic functions, many of which appear to
>>> not be dependeing on the underlying bigint type. And it's in the public
>>> domain, or at least appears to be...)
>>> Searching through the mailing list, I've seen numerous references to
>>> creating such a thing, some of them dating back nearly ten years--but none
>>> yet seems to exist. This is something, I think, which would be Really
>>> Useful to add to boost. I wasn't able to locate any current boost project
>>> or proposal to create such a thing--though it's certainly possible I
>>> up the wrong keyword(s).
>>> So, my possibly impertinent newbie question: Is anyone (seriously)
>>> on such a thing, for inclusion in boost? Are there any nasty (political)
>>> obstacles to such a thing being added?
>> I would love to have such a library and been begging for it for quite a
>> while. I don't have much experience in assembly especially 32 bit assembly
>> else I might have attempted this myself. Please if you do attempt this keep
>> the following things in mind.
>> 1) On the C++0x Standard Library wishlist (revision 5) found at
>> there are these items
>> a) Infinite-precision integer arithmetic
>> b) Full-width integer operations
>> "a" is what you are referring to but it has a dependency for efficiency on
>> "b" so it may be good to propose both libraries and split the work among
>> multiple people. These also shows that their is great interest.
>> 2) Don't limit yourself to cryptographic applications. Big numbers have
>> applications in identification and other scientific fields. As such one
>> might be perfectly content with fixed sized stack allocated [unsigned] int
>> types. Ex. std::bitset<512> -> uint<512>
>> 3) Think pluggable. Start with a standard C++ implementation even if it is
>> slow as long as it work and then gradually, on latter releases, replace or
>> allow choosing faster implementations. Who knows this might allow others to
>> plug GMP or other implementations into it. [Consider virtual functions,
>> function pointers, facets. Most in past conversations have offered strong
>> resistance to virtual functions.]
>> Unsubscribe & other changes:
Number 4, "certain 'combo' operations", is a similar thought expressed
in "Full-width integer operations".
If you want to know what should go into its public interface consider
is the current proposal for decimal floating point types. Being another
numeric type for C++ this proposal should give you an idea of what
functions are needed; at least as a goal.
I agree with the need for a Number 1, unsigned large number type. If
this is considered please add partition methods, a function that can get
a bigint from an bigint that starts at bit offset and goes for bit
length aka.bitfields where a bigint is the struct.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk