On 5/24/06, Maarten Kronenburg <M.Kronenburg@inter.nl.net> 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