Boost logo

Boost :

From: Marcin Kaliciñski (kalita_at_[hidden])
Date: 2005-04-28 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.open-std.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
C-style 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 in-the-middle algorithms, such as
Karatsuba multiplication. Performance-oriented 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 multi-processor
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