Re: [boost] Yet another bignum type

From: Maarten Kronenburg (M.Kronenburg_at_[hidden])
Date: 2006-11-25 10:17:30

"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.

>
<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.

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).

>
> 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.
Regards, Maarten.

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