On 11/25/06 10:17 AM, "Maarten Kronenburg" <M.Kronenburg@inter.nl.net> 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