[boost] Google SoC 2007 Big Integer project

From: Marco (mrcekets_at_[hidden])
Date: 2007-03-22 16:09:29

Ok, problably this is the N-th proposal that you read for the big integer  
project, with N large as you like :), and this isn't an upside for my  
application, anyway these are my ideas:

(1) evaluate the need for a specific allocator because std::allocator  
doesn't provide a reallocate method, and growing allocated space could be  
a better policy than a create/destroy policy;

(2) minimize useless object copy: where it's possible we'd have to adopt a  
move semantic technique as described in   
"http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1690.html#Library-Only  
Move Solution" ;

(3) use different algorithms according to the size of the numbers  
involved, the GMP library can be taken as an example and Knuth's TCP Vol 2  
as a reference for the algorithms' implementation;

(4) decide if we have to use exception handling C++ constructs for  
arithmetic exceptions ( divide by zero, etc) or simply abort the program;  
this is essentially a matter of performance;

(5) implement ctors in order to inizialize a big integer from standard  
arithmetic type and obviously from a number represented by a string;  
implement conversion functions to arithmetic types and string types;

(6) implement common arithmetic, shift, bitwise and comparison operators;
using the boost::operator library would be usefull where this doesn't lead  
to a performance loss;

(7) implement io stream operator;

(8) basic functions: sign(), odd(), abs(), etc; numeric functions pow,  
sqrt, etc; algebric and combinatorial functions: factorial, gcd, etc.;  
there are a lot of functions we could implement : all depend on the  
avaible time;

(9) decide if it's worth creating a specific class unsigned big integer;

(10) about fixed size big integer I had tought to something like this:
template< unsigned int N > class big_int; where N are the number of bits  
which have to be used;

(11) make all that working on the larger number of architectures; write  
down library documentation, implement correctness and performance tests;

(12) it would be nice to support infinity and indefinite forms, but it  
could mean performance problems because we'd have to evaluate all possible  
cases, maybe it will be better realize a specific wrapper/adaptor class  
for such a goal, moreover this class adaptor could be used also for  
standard integral type;

Question : is it possible to get good performance without implement the  
basic algorithms in assembler ?

Comments and critiques to my ideas are welcome.

Thanks Marco

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/