Boost logo

Boost :

From: Marco (mrcekets_at_[hidden])
Date: 2007-03-24 04:56:50

On Fri, 23 Mar 2007 20:32:55 +0100, Kevin Sopp <baraclese_at_[hidden]>

>> (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;
> Both can be supported easily because you can simulate a realloc via
> std::allocator functions. So you just need to specialize a struct on
> the allocator type then either simulate the realloc() or call the real
> realloc().

Ok, I thought to something like this:

template< typename BlockType = block_t,
           typename Allocator = bigint_allocator<BlockType> >
class big_integer;

where block_t is architecture dependent (but we can think it as unsigned
int) and we have:

template< typename T >
class bigint_allocator : public std::allocator<T>
     pointer reallocate( pointer p, size_type n );

I've omitted ctors and typedefs.

> Both can be supported easily because you can simulate a realloc via
> std::allocator functions

do you mean that it's possible to use std::allocator methods in order to
grow allocated space without the need to initialize it again with old data
or do you mean only that it's possible to implement both policies: the
first with std::realloc and the second using std::allocator ?
In the second case the bigint_allocator template signature could become
template< typename T, typename policy_tag > where policy_tag could be
realloc_policy_tag or destroycreate_policy_tag (two empty structs, but it
could be also possible use an enum as template parameter).

>> (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;
> One can make these thresholds user definable at compile time because
> they may be different for each platform. One could write a simple test
> which prints suggested thresholds.

it's a good idea :)

>> (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;
> Or template<unsigned int N, typename T = unsigned int> where T is the
> base type of the value array, i.e. array<T> data_;

oh yes, I actually meant something like that.

>> (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;
> Not just a matter of performance but also one of interface, usually
> bigint will be used with data that comes from outside the program so
> programmer has to be prepared to catch bigint exceptions. This could
> be parameterized <bool use_exceptions = true/false>. A member variable
> to hold some state about the bigint will be useful, that way you can
> check for overflow, divide by zero and encode +inf, -inf, etc.

>> (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;
> I suggest as above having a state variable, I suspect checking for the
> states gets lost in the noise especially when the numbers get large.

I don't know if checking for states doesn't matter compared to the
complexity of multi precision algorithms. It's possible, I should try.

parametrization for infinity, NaN and exception it's ok;
anyway what I wanted to point out it's that in the case there is a
performance loss, managing infinity and undefined states, then it is
better to implement different classes and it's so even using template
parameters: for instance classes big_integer<WITH_INF> and
big_integer<WITHOUT_INF> ( WITH_INF = true, WITHOUT_INF = false, and I've
omitted the other template parameters ) will exdend a common class in such
a way to share as much as possible, but they will be two different
template specialization of <bool use_inf>.

>> Question : is it possible to get good performance without implement the
>> basic algorithms in assembler ?
> First bigint needs to be portable then one can easily add optimized
> paths for different architectures (and assemblers). About the
> question, I don't know - if you do alot of number crunching fast is
> never fast enough ;)
> Btw, this paper made big int division much more understandable to me:
> Kevin
> _______________________________________________
> Unsubscribe & other changes:

Thanks a lot for your comments and for the article link I'll read it as
soon as possible :)

Regards, Marco

Using Opera's revolutionary e-mail client:

Boost list run by bdawes at, gregod at, cpdaniel at, john at