"Andras Erdei" <aerdei@gmail.com> wrote in message news:7fe28deb0605260808j7af82ba6k897d3dca5d5dd435@mail.gmail.com...
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.)
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
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
convert 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: