
Boost : 
From: Daryle Walker (darylew_at_[hidden])
Date: 20061124 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.boostconsulting.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 functionlists 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 runofthemill bignum type. It uses the philosophy of the STL
containers to use a separate template parameter for the memory allocations.
The type is radixspecific, also given as a template parameter. It's of the
simplest bignum type, an arbitrarylength unsigned integer class. (Signed
integers, fixedpoint, floatingpoint, 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 workaround for
subtraction is the addition of "subtractabsolutely" 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 fusedadd/multiply, member functions for such
fused actions were added. There are many variants for shiftingup 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 precondition violations
(except for exceptions for negative results, divides by zero, and
conversions).
There are commentedout plans for functions that do powers and (truncated)
roots, especially squaring and squareroots, and pseudoreciprocals (for an
Ndigit value, find another Mdigit value, with M <= N, closest to giving a
product of Radix**2N, useful to implement exactdivision by
multiplybyreciprocal, 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk