Re: [boost] Yet another bignum type

From: Maarten Kronenburg (M.Kronenburg_at_[hidden])
Date: 2006-11-26 16:07:43

> 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.

Thanks for the comments.
The fact is that an unsigned integer is an integer, and a modular integer is
an integer, and an allocated integer is an integer. They have the same
member functions and operators, only modified a little bit. And I would like
to use pointers, so runtime polymorphism is required. What do you need more
for derivation? A rational in my design would simply consist of two integer
data members, the numerator and the denominator. I don't see any problem
here.

> 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.

I have measured the performance hit of the vtable for the simple prefix
operator++ and it was negligible (although of course I did not do it for all
compilers).

>
> ==> 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
>     };

This is very nice but in my opinion does not add very much to the simple
binary operators for integers that I gave. Also take into account the
evaluation problem of expressions with unsigned results but signed
temporaries that I mentioned in the Introduction -> Classes derived from
class integer -> The class unsigned_integer. Equivalent mathematical
expressions should give identical results.

>
> '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.
>

The expression templates you refer to should be generic for any arithmetic
type, not just for the integer, and should be proposed in a separate
proposal.

> ==> Enforcing implementation details is bad. The synopsis can be kept
(partially) unspecified and concepts (IOW valid expressions and their
semantics) should be documented instead.
>
In this case, as this is a basic type to be implemented and used under
performance-critical environment, the details of the interface should be
hammered out as much as possible.
Below is an example of usage that I have added to the document (hope it
comes through readable).
Regards, Maarten.

class heap_allocator : public integer_allocator
{ private:
  HANDLE the_heap;
public:
  heap_allocator()
  { the_heap = HeapCreate( 0, 0, 0 ); };
  ~heap_allocator()
  { HeapDestroy( the_heap ); };
  void * allocate( integer::size_type n )
  { return HeapAlloc( the_heap, 0, n ); };
  void * reallocate( void * p, integer::size_type n )
  { return HeapReAlloc( the_heap, 0, p, n ); };
  void deallocate( void * p )
  { HeapFree( the_heap, 0, p ); };
};

heap_allocator global_heap_a; // create heap
heap_allocator global_heap_b; // create second heap

int main()
{ modular_integer<1>::set_modulus( 16 );
  modular_integer<2>::set_modulus( 11 );
  allocated_integer<1>::set_allocator( & global_heap_a );
  allocated_integer<2>::set_allocator( & global_heap_b );
  integer x( 4 );
  modular_integer<1> z( 10 );
  allocated_integer<1> a( 3 );
  integer * p = new allocated_integer<2>( -7 );
  integer * q = new modular_integer<2>( 3 );
  z += x * a; // z becomes 6 = 22 mod 16
  x -= z; // x becomes -2
  a *= x; // a becomes -6
  *q += a; // *q becomes 8 = -3 mod 11
  a.swap( *p ); // swaps a and *p by value
// ...
  delete p;
  delete q;
  modular_integer<1>::set_modulus( 0 ); // cleanup static memory
  modular_integer<2>::set_modulus( 0 ); // cleanup static memory
}