Re: [boost] Arbitrary precision arithmetic

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
>> 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
>>
>>     
>
>
>
>   
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 
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2849.pdf. 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.