
Boost : 
From: Marco (mrcekets_at_[hidden])
Date: 20070324 04:56:50
On Fri, 23 Mar 2007 20:32:55 +0100, Kevin Sopp <baraclese_at_[hidden]>
wrote:
>> (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>
{
public:
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:
> http://www.cs.ubc.ca/local/reading/proceedings/spe9195/spe/vol24/issue6/spe903.pdf
>
> Kevin
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
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 email client: http://www.opera.com/mail/
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk