Re: [boost] Infinite precision integer draft

From: Maarten Kronenburg (M.Kronenburg_at_[hidden])
Date: 2006-05-26 11:52:19

"Andras Erdei" <aerdei_at_[hidden]> wrote in message
news:7fe28deb0605260808j7af82ba6k897d3dca5d5dd435_at_mail.gmail.com...
> 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.)

Thanks for your comments.
When an implementation is very slow,
it will not be useful at all, and not be used.

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

Yes you are right, I will change it to O(N),
even though N in this case is limited.

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

Yes, another internal representation may yield
a bit better performance in some special cases.
But the checking on identical objects (a+=a)
or on carries remains, so don't expect too much.

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

To my knowledge the base type int does not
have a +0 and a -0.
So therefore I see no reason to specify this.

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

Derivation is a part of C++, so in my opinion
users must be able to derive from class integer
to make an integer with special properties.
How would you explain to a user that whatever
he/she does with integer, derivation is not an option,
because the destructor does not happen to be virtual.
This is what it boils down to in the end.

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

Once again I argue that an unsigned integer is an integer,
and a modular integer is an integer.
An unsigned int is actually a modular int with modulus 2^32.
When an integer with a certain allocator must be used
in an expression with an integer with another allocator,
then run-time polymorphism is the only option.

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

Try adding a wstring to a string,
or two strings with different allocators.
You will get a compile time error.
By derivation and run-time polymorphism,
you will not get a compile-time error.

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

Then my indication of exception conditions is just an
indication what errors may occur.
Note that I did not specify any throw().

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

The integer as specified will strictly mimic the int.
As mentioned to others I will add a unspecified-bool
conversion to be able to use if( x ) with x an integer.
But making a "basic" integer and then making it a data member
of a "full" integer, I do not recommend that strategy.
I recommend to make the interface right and complete
from the beginning.

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

Agreed.

>
>
> br,
> andras
> _______________________________________________
> Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
>