Re: [boost] Arbitrary precision arithmetic

Subject: Re: [boost] Arbitrary precision arithmetic
From: Scott Johnson (engineerscotty_at_[hidden])
Date: 2009-08-18 17:49:36

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
> http://www.open-std.org/JTC1/sc22/WG21/docs/papers/2005/n1901.html
> 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:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>

-- 
engineer_scotty (no, not that one)
If life gives you lemons, drink Hefeweizen