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