Re: [boost] Yet another bignum type

From: Maarten Kronenburg (M.Kronenburg_at_[hidden])
Date: 2006-11-27 09:01:15

"Tobias Schwinger"  wrote in message
> Maarten Kronenburg wrote:
> > 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.
>
> Sounds like parametrization - a perfect scenario to use a class
template...

Templates provide compile-time polymorphism, but in this case run-time
polymorphism is required (see my example of usage below). If I have a
pointer to an integer, I don't care how it's allocated, I just want it to
behave at runtime like an integer. This is what I think runtime polymorphism
is about.

>
> > And I would like to use pointers, so runtime polymorphism is required.
>
> Why do you need runtime polymorphism to use pointers?
>
> Use pointers to a polymorphic base to battle the redundancy you invented
by not using a template in the first place?
>
> > What do you need more for derivation?
>
> A compelling reason.
>
> And while we're at it: I don't see no reason for the allocator not to be a
template, either. You also wouldn't need an extra allocated_integer class.
Not to mention inconsistency with the STL (yeah, I notice there's an
additional reallocate member function in your allocator, but I guess it's
better to add it to std::allocator than to require a new, polymorphic one).
>

The reason for derivation I already gave, also with the example of usage.
The STL allocator has a few drawbacks. How do you add two strings with
different allocators? As they become different template types (and not
derived), you will get a compile-time error. This is not a problem for
different char traits (which are impossible to concatenate anyway), but
adding a differently allocated string could be possible. Another problem:
when serialization of memory access is needed, how to do that with the STL
allocator? For the integer_allocator that is not a problem: just add a mutex
to the static allocator object. More allocated integer classes can even
share the same static allocator object. Now I am not saying that the STL
string or allocator design is wrong, because it is used in different
contexts, but the priorities for the integer may be a bit different.

> > 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.
>
> An integer _is_a_ rational while the rational has more functionality.
> My point was that in cases like this one an "is-a" relationship does not
justify runtime polymorphism, because it makes things inflexible.

In my opinion runtime polymorphism makes the integer types more flexible to
use at runtime. Templates make things more flexible at compile time.

>
> >> 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).
>
> What did you compare it to? The built-in type int? In that case I'd find
it very hard to believe that the overhead will be negligible (regardless of
the compiler and unless you have unacceptable overhead elsewhere)!
>

No, I compared the prefix operator++ of an integer class that is not derived
with virtual member functions and operators, with one that is. The
difference should then be the effect of the vtable.

> <code>
> > This is very nice but in my opinion does not add very much to the simple
> > binary operators for integers that I gave.
>
> No, it adds nothing. But can potentially remove inflexibility and overhead
;-).
>
> > 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.
>
> I don't see any problem: All it takes is to leave out the overloads for
unsigned and make the assignment operators of the unsigned throw when an
implicit narrowing conversion (which I personally find questionable in
itself) fails to fit.
>
> > Equivalent mathematical expressions should give identical results.
>
> <snip>
>
> > 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.
>
> Maybe. But it certainly is the way to make equivalent mathematical
expressions give identical results (even without paying for it):
>
>     http://tinyurl.com/qtyhh // experimental design draft
>
> I wouldn't dare to make it a standard proposal, though.
>
> > 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.
>
> Especially if things are performance-critical you should either leave
space for optimization or optimize it to the end. A fully optimized, generic
component should not be optimized for a particular case. I believe that your
implementation rocks for large numbers, but I'm pretty sure there is still
plenty of room for improvement when benchmarking against a built-in integer.
>
> <snip>
> > ...
> > 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 );
>
> That mix of tagging plus static functions is weird, at least (not to say
scary). I guess I might know what you're up to, though. What about a
template parameter that specifies the type of some Singleton for the modulus
and a template & ctor parameter for the allocator (a la STL)?
>

This is difficult to explain, but I will try it just the same. The integer
(and its unsigned, modular and allocated variants) are basic types, just
like for example the string is. Now I agree it is possible to use singletons
and object factories etc., but should these also be used for a basic type
like an integer? The integer is very close to the hardware, it is more like
a driver. A driver is always an abstract class interface with virtual
functions. The integer should also be designed close to the hardware, with
just the simple language elements. Hope this gives an answer to your
question.
Regards, Maarten.

>
> Regards,
>
> Tobias
>