Re: [boost] Yet another bignum type

From: Tobias Schwinger (tschwinger_at_[hidden])
Date: 2006-11-26 12:49:00

Maarten Kronenburg wrote:
> For this an interface should be proposed first, to be accepted by the LWG,
> see
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2020.pdf
> The Revision 2 of this document will be submitted soon.

<snip>

> This is called requirements (see my document referred to above).
> I'm happy to discuss it here with anyone.

Maybe the upcoming Revision 2 already addresses it and I really don't want to sound disencouraging (in fact I appreciate your effort and the fact that you provide an optimized assembler version is a very big plus) but anyway. 

     There is no excuse to have the synopsis dictate runtime polymorphism, here:

Although a natural number is a special kind of integer, the integer should extend the functionality of the natural number and not vice versa. This scenario leads to (what I call) the "superset interface problem"; IOW. the base class contains the most extended implementation and derived classes can only polymorphicly mask it or use (what Gamma et al. call) the Template Method pattern to hook into it. So, if we wanted to extend things consistently to have a rational class we'd have to make it the base class.
Further, there are contexts (such as e.g. implementing a scripting language that uses arbitrary precision arithmetic per-se) where the performance penalty of virtual dispatch could be significant.

==> That kind of design doesn't work too well.

The easiest way out of our design troubles is to use converting constructors for widening conversion. Unfortunately we trade one performance problem for another - no cost for virtual dispatch but therefore extra cost for allocation and copying, which might perform worse.

==> Better design but no better implementation.

The second easiest way is to use templates to create an integer view for appropriate types that models the concept Integer.

    // pseudo code
    template<class LHS, class RHS>
    integer operator+ ( viewable_as_integer<LHS> const & lhs
                      , viewable_as_integer<RHS> const & rhs)
    {
        typename purified_integer<LHS>::type actual_lhs 
           = purified_integer_view<LHS>(lhs.derived());
        typename purified_integer<RHS>::type actual_rhs 
           = purified_integer_view<LHS>(rhs.derived());

        // perform operation on (actual_lhs, actual_rhs)
        // return result
    };

'purified_view' is an identity function (by-reference) in case the argument is already an Integer. Otherwise it creates an integer view of its argument. After the purification actual_lhs and actual_rhs both model the Integer concept.
This approach is already tricky to get entirely right. Note that I deduce 'viewable_as_integer<D>'. Every type convertible to an integer would inherit from this template specialized with its own type. I do it to restrict the arguments matched by the operator, here.

We can even go further by applying Expression Templates. This way we can collect lots of useful information about the expression and exploit it for optimization. Further, we wouldn't need to redundantly do the purify stuff - the evaluator could handle it instead. However, it's even trickier to get right.

==> Enforcing implementation details is bad. The synopsis can be kept (partially) unspecified and concepts (IOW valid expressions and their semantics) should be documented instead.

Regards,

Tobias