[boost] Yet another bignum type

From: Daryle Walker (darylew_at_[hidden])
Date: 2006-11-24 19:24:29

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.
<http://www.boost-consulting.com/vault/index.php?action=downloadfile&filenam
e=big_radix_whole.tar.bz2&directory=Math%20-%20Numerics&>.  The files might
choke on some systems, since I used naked min & max and the test file has
#pragma marks all over it.  (My IDE function-lists all the test modules as
"BOOST_AUTO_TEST_CASE()", without anything in the parentheses, so I needed
the marks to navigate the huge file.)  I'm using Xcode 2.4, with Apple's
special GCC, on a Mac OS X 10.4.8 PowerPC system.  The only documentation
right now is the Doxygen comments.

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.

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?

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