Boost logo

Boost :

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]
>> wrote:
>> Scott Johnson wrote:
>>> Greetings.
>>> 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
>>> licenses.
>>> (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
>>> C++
>>> 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
>>> looked
>>> up the wrong keyword(s).
>>> So, my possibly impertinent newbie question: Is anyone (seriously)
>>> working
>>> on such a thing, for inclusion in boost? Are there any nasty (political)
>>> obstacles to such a thing being added?
>>> Thanks!
>> 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
looking at This
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, gregod at, cpdaniel at, john at