Re: [boost] Yet another bignum type

From: Tobias Schwinger (tschwinger_at_[hidden])
Date: 2006-11-26 19:40:41

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

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

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

>> 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)!

<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)?

Regards,

Tobias