Re: [boost] Infinite precision integer draft

From: Andras Erdei (aerdei_at_[hidden])
Date: 2006-05-26 11:08:50

On 5/24/06, Maarten Kronenburg <M.Kronenburg_at_[hidden]> wrote:
>
> In the boost vault
> http://boost-consulting.com/vault/
> under Math - Numerics the document
> infintdraft.pdf contains the
> Proposal for an Infinite Precision Integer
> for Library Technical Report 2, Draft.
> Any comments are welcome.
>

1. My main concern is that both the interface and the specification seem to
be too implementation-driven.

For example, i don't see any reason for specifying the time-complexity of
the
operations: for STL containers it makes sense, as containers with the same
public interface are not interchangeable specifically because they provide
the same operations with different speed. In the case of the proposed
integer class i guess these complexity requirements are only an attempt
to force compiler vendors to provide optimized implementations. (Sidenote:
1.3.7. says "The performance of the arithmetic operations of the class
integer
should be optimal", without specifying the meaning of "optimal", maybe
something like "optimized", or "better than a naive implementations" would
be
better, if it is needed at all.)

IMHO these specifications are dangerous. One problem is internal
consistency. I haven't spent much time thinking this over, but e.g. 2.3.9.
says explicit integer( float arg ); has complexity O(1). How can we convert
e.g. 1e100 to an integer in O(1) time? I guess only if there is a <smallint,
base10exp> internal representation possibility. But is it possible to add
another integer to this one with O(N) complexity? I suspect not (the base10
-> base2 conversion is more complex).

Another danger is ruling out perfectly good implementations: e.g.
2.5.7 virtual integer & abs(); Complexity: O(1) is only possible with
the (proposed quasy) signed-magnitude representation (and if a
negabinary representation is twice as fast for + and *, then i want
that, instead of a fast abs()).

The interface itself also limits the implementation possibilities; e.g. i
don't see
how 2.5.3 int get sign() const; Returns: *this == 0 ? 0 : ( *this > 0 ? 1 :
-1 )
would apply to a fully signed-magnitude representation with separate +0
and -0. (I do not say here that such an implementation must be allowed,
although it would be nice e.g. for implementing a rational class to have
such
an integer, but that these limiting decisions should be made explicitly, in
the text, after reaching some kind of consesus, instead of implicitly, in
the
interface specification.)

2. Derivation

IMHO integer is a concrete class, not intended for public derivation.

IMHO unsigned_integer, modulo integers and all the rest are distinct
types, and must not be mandated by the standard to be in any kind
of inheritance relationship.

[Of course, internally an imlementation can use inheritance for code
reuse, but my guess would be that that is private inheritance anyway
(as it is implementation inheritance, not interface), and it would be
from a common base-class, instead of from one of the concrete,
end-user classes.]

3. Allocation

Under point 1.6 it says "An integer template class with an Allocator type
parameter cannot be used, because templates provide only compile-time
polymorphism [5], so that expressions with different template types are
not possible."

Can you provide more details about this?

4. Errors

I know that UB is bad, but i would still leave this part up to the
implementors.
Operations on arguments on which they make sense are defined anyway,
and e.g. whether implementors produce garbage on right-shifting a signed
value to gain some speed, or throw an exception, but slow down every
shift operation in exchange should be left to them to decide. Most serious
implementations will anyway provide an error-checking development
version, and bleeding-edge non-checking one anyway, only with the error
handling canonized one of those will be forced to be a non-standard
extension.
I would even refrain from standardizing optional error signalling: if an
implementation only "detects" division by zero by ending up doing an
int division by that zero, then let it be so.

5. Summary

It is high time to get an integer into the standard, but i would prefer a
very minimal (strictly int-mimicking, no additional operations etc) one.
Of course, the boost _implementation_ can provide a lot more than
this minimal integer, and when we have enough experience, then we
can bloat the interface to support common use-cases.

Similarly, let's restrict implementations as less as possible: if someone
ever comes up with a logarithmic integer class that provides O(N)
multiplication
in exchange for addition being O(N*logN), then let them do so -- if there is
a
non-trivial boost implementation, then hopefully no compiler vendor
will ever ship a naive implementation anyway.

br,
andras