
Boost : 
From: Marcin Kaliciñski (kalita_at_[hidden])
Date: 20050428 14:39:18
Hi,
I got the big integer proposal document id wrong, it is actually n1744,
here's a link to it:
http://www2.openstd.org/jtc1/sc22/wg21/docs/papers/2005/n1744.pdf
I think there are 2 major, separate issues with big integer class: interface
and implementation.
1. Interface
Class name is 'integer'. Some sort of rationale for this name is in n1744:
"just like std::string introduces a variable length string to complement
char[N], this class introduces an integer class without a fixed size".
It will be a signed integer. Unsigned version could also be done, but does
it give anything extra?
I plan to make the interface closely resemble that of boost::rational, as it
was already accepted into boost. What I like about it is being minimalistic.
I'd like to follow that style, it is much easier to add new functions later
than to remove existing ones. What I plan to have initially:
 construction from long
 construction from const char *, possibly also std::string (strings with
Cstyle number literals, but with unlimited length)
 addition, subtraction, multiplication, division, modulo
 increment, decrement (pre and postfix)
 unary plus and minus
 all comparisons
 bitwise operations (and, or, xor, not).
 shifts
 conversion to unspecified bool type
 stream input and output
There's an issue with some of the bitwise operations, as they are only well
defined for integers of fixed size. What should for example
~boost::integer(0) return? Ideally an infinitely long integer filled with
binary 1s.
boost::rational does not have a conversion operator to integer type, which
is good as most of rationals are not integers. Should boost::integer have
such an operator, with runtime range checking?
2. Implementation
Current implementation uses the following representation:
bool sign;
std::vector<some unsigned integer type> ;
The basic question is how far should I go with performance optimization? It
is of course impossible for one person to achieve the performance level of
some estabilished big integer libraries, such as GMP.
Addition and subtraction of large integers can be done very efficiently in
assembly language of most processors, for example on 80x86 by utilizing
carry flag. Portable C++ implementation would be probably about a magnitude
slower. I haven't measured that, but I have a portable implementation and it
does a lot of ifs just to detect integer overflows.
Unlike boost::rational, implementation of some big integer operations
(multiplication, division) is not easy, depending on the performance we are
trying to get. There are several multiplication algorithms with different
complexity bounds. The fastest known is Strassen multiplication using FFT,
as far as I know. There are also some inthemiddle algorithms, such as
Karatsuba multiplication. Performanceoriented libraries choose one of them
depending on multiplicands sizes. Implementing all that may be a real pain,
and implementing that in assembly language optimized for some processor is a
task outside my capabilities. And there are also multiprocessor
multiplication algorithms...
Another idea would be to write portable, potentially slow implementations
only, and allow boost::integer to use some existing libraries internally,
when user really cares about speed.
cheers,
M.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk