Re: [boost] Big integer library

From: Richard Peters (r.a.peters_at_[hidden])
Date: 2004-04-30 06:07:35

----- Original Message ----- 
From: "Paul A Bristow" <pbristow_at_[hidden]>
>
> I am absolutely certain we need a big integer in Boost.
>
> Your implementation, tests and documentation look fine, but I am unable
> to assess the relevant merits of your implementation and previous
> efforts, for example from Ronald Garcia.
>
> Perhaps you can indicate your take on this to stimulate some discussion?

Well, the main difference between these two libraries are that my library
uses expression templates to optimize out the use of (most) temporaries, in
contrast to other libraries proposed here. I wanted to try out what the
differences between these two attempts would be. So far, it resulted in a
lot more code. The difference in documentation is that my documentation
leaves the return type of operators unspecified to accomodate for expression
objects.

Another motivation for my library is to spice up the process of getting ANY
big_integer library into boost. I'm perfectly happy if the ideas in this
library are taken into another library which is to be incorporated into
boost, or if it is decided that the trade-offs of expression templates are
too large so that we can say 'well, this route is taken and proven to not be
worthwile'.

The big advantage of my library should be the performance gain from using
expression templates. Unfortunately, as I haven't got efficient
implementations of the underlying operators, I can't make fair comparisons
yet. The c++ wrappers at gmp use expression templates, which is an
indication that it is likely to provide a performance gain.

The difference between the expression-template approach versus the normal
approach is not purely implementation-related. There are cases where
expression templates have to be taken into account, for example:

    template<class T> T add_one(T x)
    { T y; y = x; return y + 1; }
    ...
    add_one(a + b);

When a and b are big_integers, the template parameter of add_one will have a
weird type (something like expression<add_ex<big_integer, big_integer> >)
which isn't useful for declaring y. Workarounds would be to use
add_one<big_integer>(a + b) or add_one(big_integer(a + b)). I admit that
this is ugly. Discussion here at boost must indicate whether this is a
reasonable trade-off or not. This is not yet documented, and the expression
class will be made non-copyable to avoid these kind of cases.

> PS Can you say which compilers 'like' it? Do you want others to try it
> out?

I have tried it at vc7.1, gcc3.2 and gcc3.4. The example and test file
compile and run successfully on all of them. Due to the use of partial
specializations, it will not compile on vc7.0 and below and other compilers
that do not support partial template specialization. I do not have access to
other compilers, it would be great if you or other persons could test it on
other compilers and give me feedback on the results.

best regards,

Richard Peters