[boost] Big integer continued

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.