Re: [boost] Yet another bignum type

From: Daryle Walker (darylew_at_[hidden])
Date: 2006-11-26 17:33:37

On 11/25/06 10:17 AM, "Maarten Kronenburg" <M.Kronenburg_at_[hidden]>
wrote:

> "Daryle Walker"  wrote in message
>> This is something I've been working on for the past few months.  It's in the
>> Sandbox and I just uploaded it to the new Vault as "big_radix_whole.tar.bz2"
>> under the "Math - Numerics" directory, i.e.
> 
> For this an interface should be proposed first, to be accepted by the LWG,
> see
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2020.pdf
> The Revision 2 of this document will be submitted soon.

This isn't going to be submitted to the C++ standard bodies.  The fact that
the radix and allocations are template parameters prevents my class from
having the hard core computational efficiencies that a concrete class can
have (hide implementation, use assembly).

[SNIP]
>> It's a run-of-the-mill bignum type.  It uses the philosophy of the STL
>> containers to use a separate template parameter for the memory allocations.
>> The type is radix-specific, also given as a template parameter.  It's of the
>> simplest bignum type, an arbitrary-length unsigned integer class.  (Signed
>> integers, fixed-point, floating-point, rational, etc., variants can all be
>> built off of this kind of bignum.)  As such, the renditions of the
>> traditional algorithms are fairly pure.  The biggest issue from a
>> mathematical standpoint is that the type can't be a proper ring, since it
>> doesn't support additive inverses (besides zero).  Every other arithmetic
>> operation (that doesn't need negative values) can work.  The work-around for
>> subtraction is the addition of "subtract-absolutely" member functions, which
>> compute the absolute value of the difference, and return a "bool" indicating
>> what the sign would have been.
> 
> The integer data should not be in an STL container, but in a contiguous memory
> block, so that an assembler module is possible for performance, see
> <http://www.swox.com/gmp> (see also my document referred to above).

It's not trying to compete for performance, but for exposing its mechanism
in a (hopefully) clear manner.  I used an STL container to reuse the
experts' memory strategies.  I used a deque, instead of a vector, since I
use push-front a lot.  A deque's piecemeal allocations is a substitute for
vector's reserve; contiguity doesn't matter since I'm using iterators.

>> Many of the operations are repeated, each with optimized algorithms for the
>> different sizes of the parameters.  Since the traditional method of
>> multiplication is actually a fused-add/multiply, member functions for such
>> fused actions were added.  There are many variants for shifting-up where
>> additions/subtractions start since it's faster than doing a separate
>> shifting operation first.  And it saves memory, which was an important goal
>> in all the algorithms, along with the strong exception guarantee.  Besides
>> the asserts, there is generally no protection for pre-condition violations
>> (except for exceptions for negative results, divides by zero, and
>> conversions).
>> 
>> There are commented-out plans for functions that do powers and (truncated)
>> roots, especially squaring and square-roots, and pseudo-reciprocals (for an
>> N-digit value, find another M-digit value, with M <= N, closest to giving a
>> product of Radix**2N, useful to implement exact-division by
>> multiply-by-reciprocal, which is cheaper for huge N).  What other routines
>> should be added?  Any hints on how to do said routines?  Should there be
>> Serialization?  Could Spirit and/or Regex be used for the I/O routines? Any
>> compiler workarounds to be added?
> 
> This is called requirements (see my document referred to above).
> I'm happy to discuss it here with anyone.

Are you talking about a rationale for this type?  I just did it because I
was always curious about C++ and the mechanics of computation, so I put the
two together.  I have compile-time selectable radices because our arithmetic
algorithms are radix-based, even though fixing the radix at a convenient
power of two would be better.  The allocation template argument is to match
STL, even though using a non-template base class with instances passed at
run-time would be better.  Both ideas combined would improve the code by
shifting everything into a *.cpp file.  (I'm using *.ipp files now because
the core *.hpp file reached a hard-to-navigate 2500 lines before I was a
quarter through.)  Because the theoretical purity has compromised
computational practicality, I can't compete with other bignum libraries out
there (especially since they are built from many man-years of work).

-- 
Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT hotmail DOT com