"Jarrad Waterloo" <jwaterloo@dynamicquest.com> wrote in message news:20060524184833.5667B14A8001@dqmail.dynamicquest.com...

Here are my comments concerning Maarten's infinite precision integer draft. I would not wait to submit this library to boost before these following features because people are in need of it now.

1) The ability to extract sub integers out of an integer such as the integer at bit offset 3 and length of 4. This is especially helpful in the area of RFID where large unsigned integers are partitioned into smaller integers.

Thanks for your comments. Extracting sub integers can also be done with the bitwise operators, for example partitioning the integer x into 4-bit length: integer mask( 1 ); mask <<= 4; --mask; integer xsh( x ), temp; while( !xsh.is_zero() ) { temp = xsh & mask; // do something with temp xsh >>= 4; }; So this ability is already available.

2) The ability to convert integer to bases other than base 10; any really from base 2-36

The iostreams of the compilers I know only alow bases 8, 10 and 16, see also [lib.std.manip] setbase manipulator. The bases 2, 4, 5 can be easily converted from these bases. The other bases don't seem to have a useful application; they are also not supported for base type int, and not supported by printf formats or stream manipulators.

3) An implementation of a fixed sized stack version of the integer_allocator. This may be useful for performance when someone is not working with an infinite precision integer but a very large one such as 512 or 1024 bits.

Users can implement such an allocator by deriving from integer_allocator, override and implement allocate, reallocate and deallocate, and activate it.

4) An unsigned version of the integer class that benefits from the higher performance of unsigned operations

Users can implement an unsigned_integer by deriving from integer, but this will not give any performance gain. By the way I think base type unsigned int is also not faster than base type int.

_______________________________________________ Unsubscribe & other changes:

http://lists.boost.org/mailman/listinfo.cgi/boost

Gerhard Wesp <gwesp@google.com> wrote:

This would violate Item 32 in Effective C++, 3rd ed. by Scott Meyers: Make sure public inheritance models "is-a". I suggest deriving from integer be disallowed in the TR2 proposal.

I second that. If the class has not been designed from the ground up (virtual functions, interface classes etc.) to allow sensible inheritance, it should be disallowed. I think that all STL classes follow that rule. B.

Bronek, Thanks for your comments. With respect to inheritance I take the opposite view: Inheritance is something that is part of C++ and therefore users are always allowed to derive from any class. There is no way of explaining to a user that for some technical reason (like the destructor is not virtual), it is not allowed to derive from a class. And as mentioned in my reply to Gerhard, every unsigned integer is an integer, so there is every reason to choose this design. Regards, Maarten. "Bronek Kozicki" <brok@rubikon.pl> wrote in message news:000d01c680b8$3b311cd0$4904a8c0@actix.com...

Bronek Kozicki <brok@rubikon.pl> wrote:

...

Gerhard Wesp <gwesp@google.com> wrote:

...

This would violate Item 32 in Effective C++, 3rd ed. by Scott Meyers: Make sure public inheritance models "is-a". I suggest deriving from integer be disallowed in the TR2 proposal.

I second that. If the class has not been designed from the ground up (virtual functions, interface classes etc.) to allow sensible inheritance, it should be disallowed. ^^^^^^^^^^

oops, I used too strong word here. I only hope than next sentence ...

...

I think that all STL classes follow that rule.

... might explain what I actually meant. But let mi clarify: if class does not make proper use of inheritance, it should not mislead its user that it been designed to do so. Virtual destructor is kind of declaration "this class is designed to be inherited from", but it does NOT make it "good OOP-player". It the property of the design that can be recognized by use of interfaces and virtual functions and not virtual destructor alone. If integer type does not employ this kind of design, it should not mislead its users by providing virtual destructor. Making destructor public and nonvirtual does not make inheritance "illegal", it just declares that class had not been designed to be used as a base class. And this is how in my opinion integer class is designed and I like this design. Virtual destructor would only add confusion - because it would raise questions about contract between base class and its children (there is no contract in the project, thus inheritance does not make sense).

B.

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

"Ben Artin" <macdev@artins.org> wrote in message news:macdev-641F43.15244027052006@sea.gmane.org...

In article <e56qh0$lu2$1@sea.gmane.org>, "Maarten Kronenburg" <M.Kronenburg@inter.nl.net> wrote:

...

And as mentioned in my reply to Gerhard, every unsigned integer is an integer, so there is every reason to choose this design.

If you believe that every unsigned integer is an integer, you should read Effective C++. Item 35, "Make sure public inheritance models 'isa'"

In the 3rd edition, "Make sure public inheritance models 'isa'" is item 32.

until you stop believing it.

What specific operations are you saying that the integer class supports but C++ unsigned integer class doesn't support? Meyer's Bird/Penguin flying argument only applies if there are operations supported by integers but not by unsigned integers, AFAIK. If in fact such operations exist, then it would be better to derive both from a common base class. But we need to know the specifics. --Beman

Ben Artin wrote:

If we are talking about infinite precision integers, then some example of reasonable invariants on integers that do not apply to unsigned integers might be:

a + (-a) = 0

Hold on for a second. We pretty well know what (-a) means for built-in unsigned integers (whose precision is limited), but that meaning is based on number of bits used to represent the number. Once you take "infinite precision" integer, that meaning is lost because we have no predefined number of bits used to represent the number. I mean that infinite precision integer cannot reproduce behaviour of built-in types. In other words, if you can "infinitely" extend given positive number towards +inifnity, does it make any sense to disallow its extension past zero? It makes me think that concept of "unsigned integer with infinite precision" is self-contradictory. B.

Sebastian Redl <sebastian.redl@getdesigned.at> writes:

Bronek Kozicki wrote:

...

In other words, if you can "infinitely" extend given positive number towards +inifnity, does it make any sense to disallow its extension past zero? It makes me think that concept of "unsigned integer with infinite precision" is self-contradictory.

No, it's not. Precision and signedness have nothing to do with each other. The main (only, really, when it comes down to it) difference between a signed and an unsigned integer is that an unsigned integer is defined never to have a value less than 0. There are very valid reasons to enforce such a restriction,

For example?

even when you want no upper limit (the term infinite precision is not really appropriate for integers).

-- Dave Abrahams Boost Consulting www.boost-consulting.com

In article <4479A423.8010904@getdesigned.at>, Sebastian Redl <sebastian.redl@getdesigned.at> wrote:

David Abrahams wrote:

...

Sebastian Redl <sebastian.redl@getdesigned.at> writes:

...

The main (only, really, when it comes down to it) difference between a signed and an unsigned integer is that an unsigned integer is defined never to have a value less than 0. There are very valid reasons to enforce such a restriction,

For example?

Various physical quantities only make sense for non-negative values.

Wait a minute... please name one physical quantity that is a) Always integer b) Never negative c) Not just an enum (i.e., not just a finite set of possible values) I can't think of one, which makes me think that your argument about physical values is irrelevant, as you'd never use an unsigned *integer* for a physical value. Ben -- I changed my name: <http://periodic-kingdom.org/People/NameChange.php>

Sebastian Redl <sebastian.redl@getdesigned.at> writes:

David Abrahams wrote:

...

Sebastian Redl <sebastian.redl@getdesigned.at> writes:

...

The main (only, really, when it comes down to it) difference between a signed and an unsigned integer is that an unsigned integer is defined never to have a value less than 0. There are very valid reasons to enforce such a restriction,

For example?

Various physical quantities only make sense for non-negative values.

Likewise, some make sense only between 0 and 2*pi or between 0 and 1, or... that doesn't mean we should define a separate floating point type to represent each of these ranges.

It would be conceivable to use a boundless unsigned integer as the value type in the PQS library. Things like length - something cannot have negative length, and having that restriction enforced by the type itself would be convenient.

Maybe those kinds of enforcements should be handled generally, with a range-checked wrapper.

I have no doubt that there are other applications too. size_t is unsigned - of course, a boundless int should not be necessary for specifying array indices, but similar applications might exist.

The unsigned builtins exist in order to squeeze the most out of a limited number of bits. An arbitrary precision int doesn't have that problem. -- Dave Abrahams Boost Consulting www.boost-consulting.com

On May 26, 2006, at 7:26 AM, Maarten Kronenburg wrote:

Every unsigned integer is an integer,

No. A (signed) integer will have a negation operator, such that 0 - x = - x, x + -x = 0, etc. An unsigned integer will not have this operator.

and every modular integer is an integer. So therefore in my opinion public inheritance can be used. Also I think there is no other way of defining an unsigned_integer.

Sure there is. What we want is to share nearly all of the implementation details without providing exactly the same interface. You can do that with a common base class (that is neither integer nor unsigned_integer). Doug

"Maarten Kronenburg" <M.Kronenburg@inter.nl.net> writes:

Douglas, This is the same discussion I had with Gehard about the negate(). Negating an unsigned with value zero is perfectly legal. When it is not zero, it can throw an exception, as a good numeric class is supposed to do.

Opening up the interface for to negation just because it somehow "makes sense" for one singular value of the type, thereby turning a static check into a dynamic one, seems like a terribly flawed design choice to me. -- Dave Abrahams Boost Consulting www.boost-consulting.com

"Douglas Gregor" <doug.gregor@gmail.com> wrote in message news:325920BA-D24C-475E-AB8C-85D9429C224B@cs.indiana.edu...

On May 26, 2006, at 7:26 AM, Maarten Kronenburg wrote:

...

Every unsigned integer is an integer,

No.

A (signed) integer will have a negation operator, such that 0 - x = - x, x + -x = 0, etc. An unsigned integer will not have this operator.

That isn't correct, AFAICT. An unsigned does support unary negation. 5.3/9 says "The operand of the unary - operator shall have arithmetic or enumeration type and the result is the negation of its operand. Integral promotion is performed on integral or enumeration operands. The negative of an unsigned quantity is computed by subtracting its value from 2n, where n is the number of bits in the promoted operand. The type of the result is the type of the promoted operand." Try the following program: #include <iostream> #include <cassert> int main( int argc, char * argv[] ) { unsigned u = 1; assert( (0 - u) == -u ); assert( (u + -u) == 0 ); std::cout << -u << " " << 0-u << " " << u + -u << std::endl; return 0; } It does not assert (GCC 3.4.4) and the output is: 4294967295 4294967295 0. --Beman

Beman Dawes wrote:

...

That isn't correct, AFAICT. An unsigned does support unary negation.

5.3/9 says "The operand of the unary - operator shall have arithmetic or enumeration type and the result is the negation of its operand. Integral promotion is performed on integral or enumeration operands. The negative of an unsigned quantity is computed by subtracting its value from 2n, where n is the number of bits in the promoted operand. The type of the result is

Perhaps we have to specify such an unsigned (modular) integer so that implementations can provide it. Such an unsigned_integer would then have a static method set_modulus( const integer & ). Then I should merge the unsigned_integer and modular_integer into unsigned_integer in the document. I will refer to [expr.unary.op] item in any case. "Sebastian Redl" <sebastian.redl@getdesigned.at> wrote in message news:4478BF17.7020404@getdesigned.at... the

...

type of the promoted operand."

The operator exists, but only for the language unsigned integers, which aren't really unsigned integers, but modulo integers, as is obvious from the definition of the negation. The same definition is impossible for a (theoretically) infinite-precision integer, because, lacking a number of bits in the representation (n), there is no 2^n from which can be subtracted.

Sebastian Redl _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

So the unsigned_integer would have a static method void set_modulus( const integer & ).

I'd prefer not to have a program-global modulus. Remember that we're also trying to put threading into TR2. Alternatives: - Optional modulus argument to certain functions. This seems to be the approach that Mathematica chooses. - Maybe a reference to the modulus in the constructor. [ Yes, I know that NTL uses the static modulus approach. Still, my gut feeling tells me this is suboptimal. ] BTW, it seems strange that modular arithmetic should restricted to unsigned integers. Regards -Gerhard -- Gerhard Wesp ZRH office voice: +41 (0)44 668 1878 ZRH office fax: +41 (0)44 200 1818 For the rest I claim that raw pointers must be abolished.

On Mon, May 29, 2006 at 10:49:29PM +0200, Maarten Kronenburg wrote:

Gerhard, Unfortunately I know nothing about threading. The integer class itself also has static variables, although not static integers. Will this then also be a threading problem?

I think that it would be bad idea to have static variables for more than one reason. If they can be changed, then that would be a problem for threading; but static variables give rise to other problems as well, like the global-initialization ordering fiasco. It would make it near impossible to use those types in constructors in a safe way (because the objects of those constructors COULD be used globally/statically too) or use them in a singleton for example. Imho, static members == huge problems, and should be avoided at all costs in something as general as a library. -- Carlo Wood <carlo@alinoe.com>

On Mon, May 29, 2006 at 04:36:45PM +0200, Gerhard Wesp wrote:

BTW, it seems strange that modular arithmetic should restricted to unsigned integers.

It is not. It is pure habbit to use the smallest positive integers from the equivalence class as representative (see my last post). There's some nice theory on this subject here: http://www.mathreference.com/grp,sub.html -- Carlo Wood <carlo@alinoe.com>

Though I agree that a modulo is needed / should be provided, I don't agree that it should be possible to set it at runtime. Below, I'll try to argue that we need two types: One for the infinite group of integers, and a templated one (so basically, infinite number of types) for the finite groups. Modulos are things that work on everything, also all operations. In math. one would write: x = 7 x + 5 == x * x [module 37] and that wouldn't change the fact that x is an integer. So, it makes more sense set a modulo with a global function, and not just for one specific variable (as everyone already seems to agree upon(?)). Ie, one can say x = 7 set_modulo(37); assert( x + 5 == x * x ); And that would be true. This would be pretty well defined, except for printing the value of variables. With a modulo set to 37, the integer values 7 and 44 (and -30, etc) are in the same equivalence class (they are equivalent) and any such integer can be taken represent such a class. Internally, any of those values would do, but in the end, I guess, we want the same value to be printed for the same equivalence class. We could define that the only printed representative of such equivalence class has to be the smallest natural number (>= 0), in which case that representative would have simularities with an unsigned int (certainly when the modulo is consider to be 2^32 in that case), but this is not possible when the modulo is 0. In that case you either DON'T have a group (there doesn't exist an additive inverse) OR you need the negative numbers. [Note: a 'group' is a set of elements for which both, addition and subtraction is well defined, along with a few other axiomatic demands- like that there has to exist a zero, (a + b) + c == a + (b + c), etc]. Even in math, there has to be made a pretty big difference between finite groups and the few existing groups with an infinite number of elements (which, in our case, would be just the (signed) integers). Now note that you can't add two numbers with different modulo, that wouldn't make sense -- but you CAN multiply an element of a finite group with an integer (defined as adding it to itself that many times). Therefore, this would be legal code: integer n = 88; set_modulo(37); x = y * n; where 'n' would still be 88, and not an equivalence class of 14. This is why I think we need TWO types: one for finite groups, and one for normal integers (the infinite group).

From Maarten's proposal I understand that he wants the same. He seems to propose to use 'integer' for the infinite group, and 'unsigned_integer' for the finite group (with a static method to set the modulo). The only thing I disagree with is the name 'unsigned_integer'. I think it should be called 'abelian_group', something like that. [Abelian group is a group for which a + b == b + a].

There is nothing 'unsigned' about it: For the non-mathematicians, this was the unary minus sign means: When x + y is defined (gives another well defined element of the group), then 0 (zero) is defined as the (single) element for which x + 0 == x for every element x of the (finite) group. Also, there will be a unique solution to the equation x + y == 0 for every element x. '-x' is defined to be the equivalence class (element) for which x + (-x) == 0, thus -x == y. An equivalence class can be seen as a (infinite) set of all integers that are equivalent. Modulo 37, we would have: { ..., -74, -37, 0, 37, 74, ... } { ..., -73, -36, 1, 38, 75, ... } { ..., -72, -35, 2, 39, 76, ... } . . . { ..., -38, -1, 36, 73, 110, ... } which are all 37 possible elements. If you want you could represent those classes with an integer between 0 and 37. Then you could write: 5 + 32 == 0 In other words, -5 == 32. This should definitely work: abelian_group<37> x, y; // Making up my own type for a moment. x = 5; y = -x; // Unary minus works. assert(y == 32); where every binary operation between an element from a finite group and an integer is taken to mean a binary operation between two elements of that finite group, where the second element was represented by the integer (thus, also, y == -5, and y == 69). This even holds for multiplication: you can still implicitely convert the integer you are multiplying with to the finite type before multiplying; but be aware: in that case multiplication must be well defined within the group, in other words, it must be a ring (which is a group for which also multiplication is defined). Fortunately, integers modulo some integer ARE rings. The following should also be legal code: integer n = 80; abelian_group<37> x = 5; abelian_group<7> y = 5; assert(x * n == 30); assert(y * n == 1); but can't do: assert(x == y); // Eror: should not compile. Imho, that can only be achieved in the way I did: by using a templated type for the finite groups. If you'd use a type 'unsigned_integer' with a static method set_modulo, then you can never write the first piece of code. I suppose that in practise that wouldn't be a major problem in most cases-- but you never know. The fact that it wouldn't be possible to pass two elements of different sized groups to a function might become a large problem. On Mon, May 29, 2006 at 03:55:01PM +0200, Maarten Kronenburg wrote:

In my opinion the unsigned integer with a modulus is required, which is generalizing the base type unsigned int (which is modular) to any modulus. So the unsigned_integer would have a static method void set_modulus( const integer & ). The only problem is what an unsigned_integer is when a modulus is not providid, that is when the modulus is zero. Then I propose that as the user did not provide any modulus, only in this case negating a non-zero unsigned_integer will be an error. Also I propose that such an unsigned_integer will be provided by implementations, and be added to the specification.

-- Carlo Wood <carlo@alinoe.com>

The user should set the modulus of the unsigned_integer once in the beginning. But for a mathematical modulo class, the user can make a template with an unsigned_integer data member, and a non-type template parameter that holds the modulus. Upon instantiation of that template, the unsigned_integer static set_modulus function must be called with that modulus. Or simply a static initialize() method in that template which does that, or a static variable of an init class, see The C++ Programming Language, 3rd ed., 10.4.9. The point is that then a template type is associated with the modulus. Regards, Maarten. "Gerhard Wesp" <gwesp@google.com> wrote in message news:20060529153226.GG29026@google.com...

On Mon, May 29, 2006 at 05:15:59PM +0200, Carlo Wood wrote:

...

One for the infinite group of integers, and a templated one (so basically, infinite number of types) for the finite groups.

This has limited usefulness. The more common applications of finite groups (crypto...) require moduli - well beyond of what's possible as a numeric template parameter and - determined at runtime.

...

and 'unsigned_integer' for the finite group (with a static method to set the modulo). The only thing I disagree with

Aaah, so I got this wrong all the time. I thought Maarten's unsigned_integer should be, well, an unsigned integer, without a modulus involved. So it should represent Z_p? Maarten, can you clarify?

Regards -Gerhard -- Gerhard Wesp ZRH office voice: +41 (0)44 668 1878 ZRH office fax: +41 (0)44 200 1818 For the rest I claim that raw pointers must be abolished. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

What do you mean with "modulus version"? When the modulus is a constructor argument, then I suppose each object can have its own modulus. Then it is not clear to me how arithmetic between different objects with different moduli should be done. Regards, Maarten. "Sebastian Redl" <sebastian.redl@getdesigned.at> wrote in message news:447B2789.3060304@getdesigned.at...

Maarten Kronenburg wrote:

...

In my opinion the unsigned integer with a modulus is required, which is generalizing the base type unsigned int (which is modular) to any modulus. So the unsigned_integer would have a static method void set_modulus( const integer & ). The only problem is what an unsigned_integer is when a modulus is not providid, that is when the modulus is zero. Then I propose that as the user did not provide any modulus, only in this case negating a non-zero unsigned_integer will be an error. Also I propose that such an unsigned_integer will be provided by implementations, and be added to the specification.

Or you drop unsigned_integer completely (David convinced me that it is not really needed) and only have a modulus version, which takes the modulus as a constructor argument. Then negation is always defined.

Sebastian Redl _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

On Mon, May 29, 2006 at 10:35:16PM +0100, Bronek Kozicki wrote:

modulus could be template parameter. In this case 1 - there is no static state (which complicates things a lot in multithreaded programs) 2 - number with different modulus are in fact distinct types 3 - if there is any kind of operation that can be performed between such distinct types, it can be safely defined in the interface, together with appropriate compile-time checking 4 - it is possible to optimize algorithms as function of the modulus, by using a different algorithm (by means of specialization).

Because it makes no sense to switch between different moduli, I can't think of a reason to NOT make it a template parameter. -- Carlo Wood <carlo@alinoe.com>

On Mon, May 29, 2006 at 05:04:46PM -0700, Geoffrey Irving wrote:

For an extremely common example of switching between different moduli, look at this:

http://mathworld.wolfram.com/ChineseRemainderTheorem.html

For example, RSA uses m_1 = p, m_2 = q prime, where M = pq is the public key.

I'm not convinced, to me it seems that all variables in those cases are just integers. The above page says: Let r and s be positive integers which are relatively prime [So, r and s are definitely just normal integers, element of N+] and let a and b be any two integers. [Also a and b are not an element of a finite group thus, they are plain integers, element of Z]. Then there is an integer N such that [Also N is an integer...] N = a (mod r) Well, as I said in a previous post: the modulo works on whole expressions. The above says: N is equivalent to a, if you work modulo r. It doesn't force N or 'a' to be element of Z_r. The question arises however: how would you implement this in code? I don't think the above equation is something you can do anything sensible with by itself -- at most you could already have a value of N and 'a', and then want to check if they are equal. You could do that as follows: if (abelian_group<r>(a) == N) ... or if (a == abelian_group<r>(N)) ... because it makes sense to have operator== implicitely convert a normal integer to the finite group of it's other argument. I'd agree that it might be annoying in this case that 'r' has to be a constant. But, that isn't an argument to not have templated finite group types. After all, neither a, nor N ARE finite. Perhaps we need notation/API like this: if (Modulo(r).equals(a, N)) or even using boost::foobar::equals; if (equals(a, N).modulo(r)) because casting one of the two arguments to Z_r before you start to compare isn't really defendable from a mathematical point of view (though valid, of course). The ideal situation would be to have an algorithm (for comparing two integers) that is optimised for a (runtime definable) modulo. Now, to get back that page. If you want to solve the set of equations: N == a (mod r) N == b (mod s) Then you need a function/algorithm especiall for that, for example: N = ChineseRemainder(a, b, r, s); I don't think it would even make sense to cast a or b to Z_r or Z_s respectively. What I meant when I said that I can't think of a case where you need to switch modulo, is that when you have an element of Z_p, then it doesn't really make sense to turn it into Z_q. The only exception being when q devides p. Thus: unsigned_integer x; unsigned_integer::set_modulo(r); x = N; unsigned_integer::set_modulo(s); // use x make no sense. Which is why I wonder why you wouldn't do: Z<r> x = N; Z<s> y = N; except for the case that r and s have to be dynamically determined. -- Carlo Wood <carlo@alinoe.com>

On Tue, May 30, 2006 at 09:20:59AM -0700, Geoffrey Irving wrote:

...

Z<r> x = N; Z<s> y = N;

As pointed out by someone else already, what if r = 2^30402457-1?

More fundamentally, encryption usually fails if the secret prime numbers are hard coded into the encryption code as template arguments. Unless you want the encryption code to recompile itself whenever it generates a new random key, that is.

Okay. I agree that it should be possible to have dynamic (or non-builtin integral) numbers for the modulo (say 'p'). One could still argue that in those cases it probably isn't necessary to work in Z_p, but well. A general library shouldn't post restrictions on practical use like that, I guess-- and you are right that a template argument would be limited to int or long long at most. The only real advantage of using a template argument is probably that you can make things faster during runtime - but as always, the algorithm used is much more important than some constant factor that one might gain there. So, I'm convinced ;). I'm okay with a library that allows the modulo to be set during runtime. -- Carlo Wood <carlo@alinoe.com>

Gerhard, Yes I read the item "Make sure public inheritance models "isa"". Therefore I told you that an unsigned integer is an integer. Negating an unsigned integer with value zero is very legitimate. Negating a unsigned integer that is not zero is like taking the square root of a negative integer. Subtracting unsigned_integer 12 from 10 must also throw an exception. That is what an unsigned_integer is: it cannot be negative. The wrap around option, like unsigned int 10 - 12 = 2^32 - 2, is actually a modular_integer with modulus 2^32. But the unsigned_integer does not have any modulus, because it is infinite precision. When users subtract unsigned int 12 from 10, I am sure they will be surprised to get 4294967294 (at least I was). Actually the unsigned int is a modular int with modulus 2^32. The unsigned_integer is an integer with some checks preventing it to become negative. In my opinion these checks are as common as checks preventing taking negative square roots or dividing by zero. Regards, Maarten. "Gerhard Wesp" <gwesp@google.com> wrote in message news:20060526120718.GE7522@google.com...

On Fri, May 26, 2006 at 01:26:00PM +0200, Maarten Kronenburg wrote:

...

Every unsigned integer is an integer,

Of course.

But, e.g., negate() doesn't make sense for an unsigned integer, right?

I can't do any better job than Scott to explain all this, I highly recommend you to read the respective chapter (if you didn't do so already). Perhaps it changes your mind.

Regards -Gerhard -- Gerhard Wesp ZRH office voice: +41 (0)44 668 1878 ZRH office fax: +41 (0)44 200 1818 For the rest I claim that raw pointers must be abolished. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Gerhard, Negating an unsigned_integer that is not zero is like taking the square root from a negative value, or dividing an integer by zero: an exception is thrown. We are dealing with numeric classes here. Regards, Maarten. "Gerhard Wesp" <gwesp@google.com> wrote in message news:20060526144945.GG7522@google.com...

On Fri, May 26, 2006 at 04:23:58PM +0200, Maarten Kronenburg wrote:

...

Negating an unsigned integer with value zero is very legitimate.

But the value may be non-zero.

E.g.,

unsigned_integer i = 4711; i.negate(); // i == ??

Having a method that is only defined, but a no-op, in the trivial case defies the purpose of having a method.

Regards -Gerhard -- Gerhard Wesp ZRH office voice: +41 (0)44 668 1878 ZRH office fax: +41 (0)44 200 1818 For the rest I claim that raw pointers must be abolished. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Pedro Lamarão writes:

Maarten Kronenburg escreveu:

...

Gerhard, Negating an unsigned_integer that is not zero is like taking the square root from a negative value, or dividing an integer by zero: an exception is thrown.

Why introduce this C++ exception for "integer division by zero"? Why not simply allow the implementation to hit the corresponding hardware exception?

FWIW, my $.02: there are two options. A) "Do as the ints do" (following Scott Meyers' advice), and hit hardware exceptions or specify some particular behavor; negating an unsigned int might be a no-op, or might generate some extremely large positive integer, or... B) "Do as we wish the ints did" and generate exceptions. I'd vote for A), not because I don't like exceptions, but because it's more consistent with the rest of the language, and also because there are situations where mathematical code needs to be _guaranteed_ not to throw anything. ---------------------------------------------------------------------- Dave Steffen, Ph.D. Fools ignore complexity. Software Engineer IV Pragmatists suffer it. Numerica Corporation Some can avoid it. ph (970) 419-8343 x27 Geniuses remove it. fax (970) 223-6797 -- Alan Perlis dgsteffen@numerica.us ___________________ Numerica Disclaimer: This message and any attachments are intended only for the individual or entity to which the message is addressed. It is proprietary and may contain privileged information. If you are neither the intended recipient nor the agent responsible for delivering the message to the intended recipient, you are hereby notified that any review, retransmission, dissemination, or taking of any action in reliance upon, the information in this communication is strictly prohibited, and may be unlawful. If you feel you have received this communication in error, please notify us immediately by returning this Email to the sender and deleting it from your computer.

As a response for a request for sub integers, in the document I will delete the is_even and is_odd member functions, and add: const integer highest_bit() const; const integer lowest_bit() const; const integer get_sub( const integer &, const integer & ) const; By the way here no size_type is used, because size_type suffices for the range of bytes, but not for the range of bits, which is a factor 8 larger. Regards, Maarten. "Maarten Kronenburg" <M.Kronenburg@inter.nl.net> wrote in message news:e55e0m$jnh$1@sea.gmane.org...

Jarrad, About the sub integers I was a little too easy, because my solution is not as fast as extracting sub integers. What you ask for is what substr is for strings. Now I think this should be added for performance reasons. Regards, Maarten.

"Jarrad Waterloo" <jwaterloo@dynamicquest.com> wrote in message news:20060524184833.5667B14A8001@dqmail.dynamicquest.com...

...

Here are my comments concerning Maarten's infinite precision integer draft. I would not wait to submit this library to boost before these following features because people are in need of it now.

1) The ability to extract sub integers out of an integer such as the integer at bit offset 3 and length of 4. This is especially helpful in the area of RFID where large unsigned integers are partitioned into smaller integers. 2) The ability to convert integer to bases other than base 10; any really from base 2-36 3) An implementation of a fixed sized stack version of the integer_allocator. This may be useful for performance when someone is not working with an infinite precision integer but a very large one such as 512 or 1024 bits. 4) An unsigned version of the integer class that benefits from the higher performance of unsigned operations

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Guillaume, Your questions are very legitimate. At some points it is argued that it is better to store the sign separate from the absolute value. As the absolute value is non-negative, there is no choice between ones and twos complement. I will make a remark in these member functions about this. This way the results of these member functions are indifferent to sign, and do not depend on machine word size. The counting starts with bit number 0. So is_odd now becomes lowest_bit() == 0. Sub integers exceeding the highest bit are of course as if the integer is padded with zero bits. With the current memory sizes, in my opinion the factor 8 is not purely theoretical. This way I also keep the migration to 64-bit out of my design, except of course for the integer_allocator class. Regards, Maarten. "Guillaume Melquiond" <guillaume.melquiond@ens-lyon.fr> wrote in message news:1148649293.19309.52.camel@saline... Le vendredi 26 mai 2006 à 14:08 +0200, Maarten Kronenburg a écrit :

As a response for a request for sub integers, in the document I will delete the is_even and is_odd member functions, and add: const integer highest_bit() const; const integer lowest_bit() const;

In my opinion, is_odd and is_even have a clearer meaning. When I read lowest_bit and highest_bit, a lot of questions come to my mind: Are they implementation-defined? Or are they the lowest and highest bits in a sign-magnitude representation of integers? Or is it a 2's complement representation? Or maybe a 1's complement representation? Is the highest bit of a positive integer always 1? Or will its value depend on the machine word size and the integer size? Do these functions really have to return an integer?

const integer get_sub( const integer &, const integer & ) const; By the way here no size_type is used, because size_type suffices for the range of bytes, but not for the range of bits, which is a factor 8 larger.

Same kind of question here: this member extracts a sub-integer with respect to which representation? For example, what does a sub-integer of a negative integer look like? Also I wouldn't worry too much about size_type being too short by a factor 8 :-). Somebody who really needs to use integers that long will probably use its own hand-crafted classes in order to be sure a library will not do any memory allocation to store them. Sorry if all these questions were already answered in your draft and I failed to find it. Best regards, Guillaume _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

OK, I will keep is_odd(), and delete is_even() because it is equal to !is_odd(). Is this OK with you? Regards, Maarten. "Hervé Brönnimann" <hbr@poly.edu> wrote in message news:77875A54-ED2A-4BC5-A840-522E3723B72D@poly.edu...

The counting starts with bit number 0. So is_odd now becomes lowest_bit() == 0.

But isn't lowest_bit() != 0 an overkill for checking that a number is even? (I mean, first computing the order of the lowest_bit, then comparing to 0...) I think there is room for lowest_bit / highest_bit as well as for is_odd and is_even. Perhaps it will be more readable than the idiom "integer(x) %2 == 0". -- Hervé Brönnimann CIS, Polytechnic University hbr@poly.edu _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Thank you for considering sub integers. Do you have a downloadable implementation of integer ready for people to play with? Where? Here are some final thoughts to consider?

Revisions:

...

1) The ability to extract sub integers out of an integer such as the integer at bit offset 3 and length of 4. This is especially helpful in the area of RFID where large unsigned integers are partitioned into smaller integers.

...

As a response for a request for sub integers, in the document I will delete the is_even and is_odd member functions, and add: const integer highest_bit() const; const integer lowest_bit() const; const integer get_sub( const integer &, const integer & ) const;

I would keep is_even and is_odd for performance and ease of use reasons because if highest_bit and lowest_bit represents a single bit than logically it should return a bool. Further, get_sub should have the following more frequently used overload. const integer get_sub( const unsigned long &, const unsigned long & ) const; This function is easier to use with constants, faster because of no conversions to heavier objects and the most commonly used case because even though infinite precision integers can have infinity of bits it is very unlikely that generally users will have a sub integer at offset 4 billion of length 4 billion. What number would that reprensent! Doesn't the number of atoms in the known universal end before 256 bits! Anyway my point repeated throughout is ease of use to the user of the library with the best speed using the least memory even if it means making a library slightly more complex with extra commonly used methods or objects.

...

2) The ability to convert integer to bases other than base 10; any really from base 2-36

...

The iostreams of the compilers I know only alow bases 8, 10 and 16, see also [lib.std.manip] setbase manipulator. The bases 2, 4, 5 can be easily converted from these bases. The other bases don't seem to have a useful application; they are also not supported for base type int, and not supported by printf formats or stream manipulators.

itoa does take radix at runtime instead of a enumeration compile time constant. As such I was hoping the following methods were added. const std::string to string(const integer & arg, const unsigned char radix) { // the implementation could use the algorithm where // the value is divided by the radix // the remained is pushed onto a stack of characters // and the dividend is fed back into this process until it is 0 } Obviously it would be nice to have a constructor that could reverse this process. This method may perform better if there was a division method

Jarrad, Thanks for your comments. There is no downloadable implementation yet because for obvious reasons I would like to wait until the design is finished. The is_odd() is kept, but the is_even() is deleted as it is equivalent to ! is_odd(). String constructor and converter are added for a radix up to 36, like itoa: explicit integer( const std::string &arg, unsigned int radix ); const std::string to_string( const integer &arg, unsigned int radix ); where 2<=radix<=36, otherwise other string constructor or converter is assumed. No unsigned char is used because some day some notation for any radix > 256 may be invented. The arguments of get_sub are integers, because the bit factor 8 is not theoretical with current memory sizes. Users may also use integers to hold bit patterns of any size and use only shift and bitwise operators, in combination perhaps with your get_sub! The performance hit will be negligible, because making the result will cost much more. But in the design decisions I state that implementations may add overloads (for example to your unsigned long), though this is not required. The division method that does / and % at the same time is present, see divrem under arithmetic non-member functions, and is indeed used for reading and writing integers. Creating integers with variable size on the stack, that is in any case something that I will not specify, but users that want to use these tricks can just override the integer_allocator. About performance of signed and unsigned integers: my guess is that there will not be much difference. Users can derive integer to make an unsigned_integer, but they can also decide to use integer and let the values never get negative. The last option is of course a little faster. About windows and GMP and boost: in my opinion there has to be a good interface first, and in any case you help reaching that point. Regards, Maarten. "Jarrad Waterloo" <jwaterloo@dynamicquest.com> wrote in message news:20060526133837.D30D42708024@dqmail.dynamicquest.com... that

does / and % at the same time. Whether or not these methods should be member functions instead of external or both is something I leave to be debated among OOP experts.

...

3) An implementation of a fixed sized stack version of the integer_allocator. This may be useful for performance when someone is not working with an infinite precision integer but a very large one such as 512 or 1024 bits.

...

Users can implement such an allocator by deriving from integer_allocator, override and implement allocate, reallocate and deallocate, and activate it.

Yes users can do this themselves but if this is something that would be frequently considered or built by users than it might be better to go ahead and make this library even more robust by providing it up front. Further if this library is to behave like native int that can be created on the stack and the heap than it would still be part of your architecture to allow integer to be created on the stack and heap.

...

4) An unsigned version of the integer class that benefits from the higher performance of unsigned operations

...

Users can implement an unsigned_integer by deriving from integer, but this will not give any performance gain. By the way I think base type unsigned int is also not faster than base type int.

Yes users can do this themselves but if this is something that would be frequently considered or built by users than it might be better to go ahead and make this library even more robust by providing it up front. Secondly, I had thought that a CPU processes unsigned faster than signed and having evaluated the code of other C++ integer libraries the code for unsigned was less than for signed. However, I am no expert so I could be wrong on this performance question. As my first thought, people are in need of this library now as a boost library or a preliminary boost library because most other libraries have awful license or is too difficult to build in a windows environment as is the case of GMP. Help!

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

"Maarten Kronenburg" <M.Kronenburg@inter.nl.net> writes:

Jarrad, You were right, I will change the const integer & parameters in get_sub into size_type, just like in the allocator class, and the highest_bit and lowest_bit will also return size_type. This also then holds for the shift parameters of the shift functions. When everything goes 64-bit the factor 8 argument will be history. Regards, Maarten.

<snip entire foregoing thread> http://www.boost.org/more/discussion_policy.htm#effective There are a number of points on that page from which your posts could benefit, Maarten. Posting as Moderator, -- Dave Abrahams Boost Consulting www.boost-consulting.com

On Mon, May 29, 2006 at 03:55:01PM +0200, Maarten Kronenburg wrote:

In my opinion the unsigned integer with a modulus is required, which is generalizing the base type unsigned int (which is modular) to any modulus.

I don't understand your motivation for such a type. IIUC there are two lines of reasoning: 1) There are applications where integers with negative values don't make any sense. But that is merely a special case of variables with a restricted range. There are also bigint applications where a variable can only take prime values or square free values or... Such restrictions are no less common than the case of non-negative integers, at least in my experience from computer algebra and cryptography. Therefore, as David Abrahms pointed out, there should rather be a generic solution for restricted types. 2) The native unsigned type is an integral type with mod 2^n semantics. Thus, there should also be a bigint type with mod 2^n semantics. Then why restrict yourself to the modulus 2^n? All arbitrary length integer packages I am familiar with also provide modular arithmetic for arbitrary modulus N. (Even if you cannot exploit the factorization of the modulus, modular arithmetic is much more efficient than integer arithmetic followed by a modulus operation. In fact, I would have no use for a bigint implementation without efficient modular arithmetic.) Most important is certainly the case that N is prime, but composed moduli are also often needed. The special case N = 2^n may perhaphs be the easiest one to implement, but from a potential user's point of view such a choice seems arbitrary and gratuitous. Christoph -- FH Worms - University of Applied Sciences Fachbereich Informatik / Telekommunikation Erenburgerstr. 19, 67549 Worms, Germany

On Mon, May 29, 2006 at 03:55:01PM +0200, Maarten Kronenburg wrote:

...

In my opinion the unsigned integer with a modulus is required, which is generalizing the base type unsigned int (which is modular) to any modulus.

I don't understand your motivation for such a type. IIUC there are two

"Christoph Ludwig" <cludwig@cdc.informatik.tu-darmstadt.de> wrote in message news:20060529163902.GE7459@castellio.textgrid.it.fh-worms.de... lines

of reasoning:

1) There are applications where integers with negative values don't make any sense.

But that is merely a special case of variables with a restricted range. There are also bigint applications where a variable can only take prime values or square free values or... Such restrictions are no less common than the case of non-negative integers, at least in my experience from computer algebra and cryptography.

Therefore, as David Abrahms pointed out, there should rather be a generic solution for restricted types. The unsigned_integer is actually a modular_integer with any modulus, although when the modulus is zero, it can be any non-negative integer. But users can make other integer classes with other restrictions. This is why these member functions and operators are virtual in the first place.

2) The native unsigned type is an integral type with mod 2^n semantics.

Thus,

there should also be a bigint type with mod 2^n semantics.

Then why restrict yourself to the modulus 2^n? All arbitrary length integer packages I am familiar with also provide modular arithmetic for arbitrary modulus N. (Even if you cannot exploit the factorization of the modulus, modular arithmetic is much more efficient than integer arithmetic followed by a modulus operation. In fact, I would have no use for a bigint implementation without efficient modular arithmetic.) Most important is certainly the case that N is prime, but composed moduli are also often needed. The special case N = 2^n may perhaphs be the easiest one to implement, but from a potential user's point of view such a choice seems arbitrary and gratuitous.

As mentioned above, the unsigned_integer is actually a modular_integer with any modulus, that can be set with the static function set_modulus. So it is not restricted to modulus of form 2^n. Users can also make a template with an unsigned_integer data member, and provide the modulus as a template non-type parameter.

Christoph

-- FH Worms - University of Applied Sciences Fachbereich Informatik / Telekommunikation Erenburgerstr. 19, 67549 Worms, Germany _______________________________________________ Unsubscribe & other changes:

http://lists.boost.org/mailman/listinfo.cgi/boost

Anyone else feel that there might be a better name out there for this facility than "Infinite Precision Integer"? Taking the first sentence of the draft:

The infinite precision integer is an integer that is not limited in range by the computer word length. I'm certainly no expert on math terminology, so someone please help me out if I'm confused here, but aren't "precision" and "range" quite distinct concepts?

It seems like "precision" isn't really what distinguishes this facility from that of the built-in integral types. E.g,. in what way can't the built-in int already represent its values with "infinite precision"? Ref: http://www.open-std.org/JTC1/SC22/WG11/docs/iso11404.pdf "ISO/IEC 11404:1996 Language Independent Datatypes (LID)" Defines 'Integer' as "the mathematical datatype comprising the exact integral values" with the properties of "exact" and "unbounded". Also, I'd stay away from the term infinite, especially when it's clearly constrained by something as finite as computer memory. Terms for "the infinities" are already defined by IEEE-754 have a meaning different from what seems to be intended here. Perhaps a better name for this facility might be "Unbounded Integer" or "Unrestricted Range Integer". (De-ranged Integer anyone?) In keeping with the C/C++ traditions of referring to the representational size (short, int, long, long long, etc.), another approach to might refer to them as "Unsized" integers. I can see why other libraries are called simply "bignum", "gmp", etc.. - Marsh

In message <44836B8B.1060803@mysteray.com>, Marsh J. Ray <marsh.boost@mysteray.com> writes

Anyone else feel that there might be a better name out there for this facility than "Infinite Precision Integer"?

- Integer - Unbounded Integer // a poor second, for me -- Alec Ross

| -----Original Message----- | From: boost-bounces@lists.boost.org | [mailto:boost-bounces@lists.boost.org] On Behalf Of Marsh J. Ray | Sent: 05 June 2006 00:24 | To: boost@lists.boost.org | Subject: [boost] Infinite precision integer draft (naming) | | Anyone else feel that there might be a better name out there | for this facility than "Infinite Precision Integer"? I strongly agree that this is not the best possible name. | In keeping with the C/C++ traditions of referring to the | representational size (short, int, long, long long, etc.), another | approach to might refer to them as "Unsized" integers. I like "unsized" too, FWIW. Paul PS I have followed superficially the very long discussion on signed v unsigned. I think there is a grave danger of spending so long on this issue that the opportunity to get the really important signed unsized integers is missed. Although unsignedness is sometimes useful, unlimited size integer are REALLY, REALLY useful. So I strongly agree with suggestions to stick to just signed for now, and get some code cut. --- Paul A Bristow Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB +44 1539561830 & SMS, Mobile +44 7714 330204 & SMS pbristow@hetp.u-net.com

"Joe Gottman" <jgottman@carolina.rr.com> wrote in message news:e52u60$h8i$1@sea.gmane.org...

"Maarten Kronenburg" <M.Kronenburg@inter.nl.net> wrote in message news:e5254e$tba$1@sea.gmane.org...

...

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.

There's a few members that I'd really like to see.

First, an operator unspecified_bool_type(), like the one found in shared_ptr. There's a lot of code that looks like the following:

long x = doSomething(); if (x) { //whatever.

If integer is going to be a drop-in replacement for long then it should

have

this functionality.

Thanks for your comments. The integer is not a drop-in replacement for any base type; because it accesses its data through a pointer, and has to check on certain conditions and carries etc, it is much slower than the base types. A conversion operator will generate ambiguities in expressions, even a bool conversion operator, because bool can be implicitly converted to int. Therefore no conversion operators are provided. In this case one should use: if( !x.is_zero() ) or if( x.get_sign() )

Second, it would be very nice if we could have a two-parameter constructor for emulating scientific notation:

integer googol(1, 100);

This can be done by: integer googol = pow( 10, 100 );

I'm not sure how technically feasible this second one is, but it would certainly be useful.

Joe Gottman

_______________________________________________ Unsubscribe & other changes:

http://lists.boost.org/mailman/listinfo.cgi/boost

Pedro, Thanks, I see it now in [lib.util.smartptr.shared.obs]. Thanks to you all for pointing me to this and solving my bool conversion problem. So if( x ) should be possible for integer x, and I will include this in my document, and test it for a few compilers. Regards, Maarten. "Pedro Lamarão" <pedro.lamarao@intersix.com.br> wrote in message news:e54msp$24k$1@sea.gmane.org... Maarten Kronenburg escreveu:

Thanks for your comments. The integer is not a drop-in replacement for any base type; because it accesses its data through a pointer, and has to check on certain conditions and carries etc, it is much slower than the base types.

He meant by "drop-in replacement" that an integer object should behave exactly like an int object, so that we could just replace int i; by integer i; and everything just work like magic. That would be highly desirable.

A conversion operator will generate ambiguities in expressions, even a bool conversion operator, because bool can be implicitly converted to int.

That can be avoided with the trick mentioned by the parent:

First, an operator unspecified_bool_type(), like the one found in shared_ptr.

The trick involves a pointer-to-member; those are not implicitly convertible to int, but are "testable for nullness". The unique_ptr proposal also uses this trick. -- Pedro Lamarão _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

It seems that if( x ) works with x any base type, also floating points. However it does not work with a type like complex. When in a template someone uses if( x ) then it is implicitly assumed that x is a base type. For that template to work with other numeric types like complex or integer, it should be replaced with something like if( x != T() ) when it should work for all numeric types, because if( x != 0 ) does not work with complex as it does not construct with base type int, only with if( x != 0.0 ) So the complex constructors are not explicit, and complex also does not have a conversion operator to bool. Regards, Maarten. "Maarten Kronenburg" <M.Kronenburg@inter.nl.net> wrote in message news:e54h1p$dkr$1@sea.gmane.org...

Joe, Forgot to mention that for conversion to bool type one can also use if( x != 0 ) which works for base type int and for type integer. This one should be used in templates. if( !x.is_zero() ) of if( x.get_sign() ) only works for type integer, and therefore should not be used in templates. So if there are templates which work with if( x ) where x is a template type parameter int, when this template should also work for template type parameter integer, this should be replaced by if( x != 0 ) This is a price that has to be payed for avoiding ambiguities generated with a bool conversion operator in integer. By the way I wonder if if( x ) also works when x is a floating point type like float, double or long double. Regards, Maarten.

"Joe Gottman" <jgottman@carolina.rr.com> wrote in message news:e52u60$h8i$1@sea.gmane.org...

...

"Maarten Kronenburg" <M.Kronenburg@inter.nl.net> wrote in message news:e5254e$tba$1@sea.gmane.org...

...

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.

There's a few members that I'd really like to see.

First, an operator unspecified_bool_type(), like the one found in shared_ptr. There's a lot of code that looks like the following:

long x = doSomething(); if (x) { //whatever.

If integer is going to be a drop-in replacement for long then it should

have

...

this functionality.

Second, it would be very nice if we could have a two-parameter constructor for emulating scientific notation:

integer googol(1, 100);

I'm not sure how technically feasible this second one is, but it would certainly be useful.

Joe Gottman

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

"Paul A Bristow" <pbristow@hetp.u-net.com> wrote in message news:E1FjC7o-0000md-FX@he303war.uk.vianw.net...

| -----Original Message----- | From: boost-bounces@lists.boost.org | [mailto:boost-bounces@lists.boost.org] On Behalf Of Maarten | Kronenburg | Sent: 24 May 2006 18:29 | To: boost@lists.boost.org | Subject: [boost] Infinite precision integer draft | | 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 I wonder if the get_sign could not be sign_bit to comform to floating-point types. I know that one could maintain there isn't a sign

bit

(it's a byte or more).

Thanks for your comments. I like the name get_sign more, just like for example get_time. Where did you find sign_bit?

2 If you have to write is_zero() instead of == 0, will this make

templated

code difficult?

The == 0 notation is always allowed, also in templates, but it is a little slower than is_zero(). The == 0 generates a temporary integer with value zero, by implicit converting constructor. But in templates that also should work for template type parameter int, the == 0 indeed must be used.

3 Is there a reason for starting with integer rather than unsigned

integer

(which sounds simpler). Will deriving unsigned integer from (signed) integer be less efficient that vice versa?

The unsigned integer is not simpler but more difficult than the integer, because the unsigned integer must do checks if an addition or subtraction result is negative. So for unsigned integer a simple -- can generate an exception.

4

2.3.1 Rationale

The destructor is virtual so that derivation of class integer is possible.

Should 'of' be 'from'?

Yes you are right, I will correct this.

5 Is there a reason why

const integer x( "0x12345678901ABCDEF" ); is not implemented?

when istream hex input is?

Yes you are right. The base for the streams is controlled with the basefield flag, but for the constructor from string one can check if it begins with "0" or "0x" or "0X" and set the base to 8 or 16 accordingly. I will add this to the constructor from string and char *.

6 You might like to reference other widely used implementations like NTL?

But this is long, long overdue as a Boost and Standard Library.

Good luck!

Paul

--- Paul A Bristow Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB +44 1539561830 & SMS, Mobile +44 7714 330204 & SMS pbristow@hetp.u-net.com

_______________________________________________ Unsubscribe & other changes:

http://lists.boost.org/mailman/listinfo.cgi/boost

| -----Original Message----- | From: boost-bounces@lists.boost.org | [mailto:boost-bounces@lists.boost.org] On Behalf Of Maarten | Kronenburg | Sent: 25 May 2006 15:38 | To: boost@lists.boost.org | Subject: Re: [boost] Infinite precision integer draft | | | > 1 I wonder if the get_sign could not be sign_bit to comform to | > floating-point types. I know that one could maintain there isn't a sign bit | > (it's a byte or more). | | I like the name get_sign more, just like for example get_time. agree, but ... | Where did you find sign_bit? C99 incorporation into C++ TR1 added signbit - but (intended?) only for floating-point perhaps?. | > 2 If you have to write is_zero() instead of == 0, will this make | templated code difficult? | | The == 0 notation is always allowed, also in templates, | but it is a little slower than is_zero(). | The == 0 generates a temporary integer with value zero, | by implicit converting constructor. | But in templates that also should work for template type | parameter int, the == 0 indeed must be used. Fine. | > 3 Is there a reason for starting with integer rather than unsigned | integer | > (which sounds simpler). Will deriving unsigned integer | from (signed) | integer | > be less efficient that vice versa? | | The unsigned integer is not simpler but | more difficult than the integer, I'm sure you are right. | > But this is long, long overdue as a Boost and Standard Library. | > | > Good luck! | > | > Paul | > | > --- | > Paul A Bristow | > Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB | > +44 1539561830 & SMS, Mobile +44 7714 330204 & SMS | > pbristow@hetp.u-net.com

"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:

http://lists.boost.org/mailman/listinfo.cgi/boost

"Sebastian Redl" <sebastian.redl@getdesigned.at> wrote in message news:447745E2.6040503@getdesigned.at...

Maarten Kronenburg wrote:

...

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

If a compiler ships with a slow standard library, there will be pressure on the vendor to make a better library. There is no need to specify complexity bounds that a vendor will do his best to reach anyway. I think the way integer is specified should follow the guidelines of how string is specified, as both try to act like a built-in type. There are no complexity bounds on, say, string::find_first_of, no requirement that it be O(N+M), where N is the string's length and M the number of characters being searched for. Yet it is certainly possible to implement it this way, instead of the naive O(N*M). If the library vendor is smart and there's a need for speed, it will be implemented in a good way. If there are tradeoffs between different functions, different libraries will offer different tradeoffs or a library will have a compile-time switch to choose. However, by specifying the complexity of a given function, you're limiting the implementer. This is particularly significant in a library full of possibly complex algorithms such as integer.

Thanks for your comments. When I relax the complexities then they will say that I allowed for too slow implementations. Let's keep the complexities in, and at least in my implementation they are fulfilled.

...

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.

Well, how do you explain it to users of std::string? The class has been quite happy without virtual destructors.

Then I ask you how to add two strings with different allocators.

...

Once again I argue that an unsigned integer is an integer, and a modular integer is an integer.

You are wrong here. Of course, given the abstract concept of an integer, an unsigned integer IS-A integer - just as a signed integer is. However, the integer you specify is not an abstract concept, but a concrete class - misnamed, actually, because it's a signed integer. (In the same way as int is assumed to be signed by default.) You can either make integer abstract and derive signed_integer and unsigned_integer from it. Or you can make it concrete, follow the core language in the implicit assumption that it is actually a signed integer, and not have the IS-A relationship between unsigned_integer and integer, thus not deriving one from the other. After all, an unsigned integer IS-NOT-A signed integer.

For an abstract base class, derivation is mandatory. This is not what I want, because I want non-demanding users to be able to use the class integer without derivation. On the other hand I also want demanding users to be able to use derivation for defining integers with specific properties such as an unsigned_integer or a modular_integer, and use mixed expressions. When I make the class concrete then users will never be able to derive from it, unless they make a new class with an integer data member and start all over again. I have thought this through, and I think the way it is, it serves both non-demanding and demanding users best with flexibility if needed.

...

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.

Where did the allocator come into this discussion? Anyway, compile-time polymorphism (i.e. templates) is also an option - make all binary or higher-order operations that work on integers templated on the allocators of all operands, put the burden of merging the allocation correctly on the implementers and specify which allocator is used by the result. Or do it as std::string does and simply don't allow cross-use of different allocator types. (This lack of interoperability has often been cited as a shortcoming, though. The solution here is to make the allocator runtime-polymorphic, not the integer.)

If I don't allow cross-use of different allocators, then no mixed expressions are possible. Why should the use of a different allocator for an integer prevent it from being added to an integer with another allocator? The integer needs to be run-time polymorphic for the same reason: why should it not be possible to add an unsigned integer to a signed integer?

...

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.

Like std::string did? You can't make everyone happy with any interface, but a minimal interface can at least claim a philosophy.

In my opinion the current design serves both non-demanding users (they can just use the class integer) and demanding users (they can derive from class integer, use an allocator, and use mixed expressions). Then (I hope) as many people as possible will be happy.

What C++ lacks here, IMO, is some sort of mixin concept - effectively a way to call free functions as if they were members of a class.

In my opinion C++ offers so many options that we have these useful discussions.

Sebastian Redl _______________________________________________ Unsubscribe & other changes:

http://lists.boost.org/mailman/listinfo.cgi/boost

Stefan, Templates provide compile-time polymorphism, while derivation provides run-time polymorphism. For using mixed expressions with different types, run-time polymorphism is required. Regards, Maarten. "Stefan Slapeta" <stefan@slapeta.com> wrote in message news:e5jfcb$pk0$1@sea.gmane.org...

Maarten Kronenburg wrote:

...

For an abstract base class, derivation is mandatory. This is not what I want, because I want non-demanding users to be able to use the class integer without derivation. On the other hand I also want demanding users to be able to use derivation for defining integers with specific properties such as an unsigned_integer or a modular_integer, and use mixed expressions. When I make the class concrete then users will never be able to derive from it, unless they make a new class with an integer data member and start all over again. I have thought this through, and I think the way it is, it serves both non-demanding and demanding users best with flexibility if needed.

Sorry, but 'configuration by inheritance' is by far the worst OO design 'idea' that has ever been invented by human being. It inhibits reuse instead of encouraging it and it's responsible for most of the problems in large OO systems I've seen so far. Furthermore, it's a completely wrong interpretation of inheritance. C++ provides perfect techniques to achieve what you want: templates and static configuration are very powerful tools to provide both flexibility and good design.

Stefan

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

"Maarten Kronenburg" <M.Kronenburg@inter.nl.net> writes:

Stefan, Templates provide compile-time polymorphism, while derivation provides run-time polymorphism. For using mixed expressions with different types, run-time polymorphism is required.

No, that's why we have templates. In fact, runtime polymorphism breaks down horribly with mixed type expressions. I suggest you google "binary method problem" to see why. Maarten, I may be speaking too soon because admittedly I have not followed every message in this thread, but at this point it looks to me like several of your proposed design choices are so far from what this group would be likely to accept that there would be little point in bringing such a library for review. It also seems as though you'd benefit more by trying to learn from your fellow Boosters than by arguing with them. I suggest you try to adopt a different approach. -- Dave Abrahams Boost Consulting www.boost-consulting.com

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

The LWG discussed this, and decided that the time-complexity should be specified tightly enough to require implementations that are broadly useful, but not so tightly as to require heroic efforts by implementors.

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.

The LWG also discussed this, and would like a fairly minimal approach (incidently, it is for TR2, not the standard itself). However, certain additional functions are required for real-world applications, and are more efficient if part of the implementation.

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.

Yes.

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

It might be possible to allow such an implementation by providing an escape clause. Perhaps something like: "Complexity requirements for certain functions may be relaxed if doing so allows improved complexity for other functions. Such complexity relaxations and improvements shall be documented by the implementation." Is that a good idea? I don't know enough about the problem domain to have a strong opinion. --Beman

On 5/26/06, Beman Dawes <bdawes@acm.org> wrote:

...

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.

The LWG also discussed this, and would like a fairly minimal approach (incidently, it is for TR2, not the standard itself). However, certain additional functions are required for real-world applications, and are more efficient if part of the implementation.

i'm just worried that using guesswork it's pretty hard to come up with the right set of "certain additional functions" my guess :O) would be that the additional functions in the current proposal are not that final set: - some of the functionality will move into a seriously revised & redesigned numeric_limits replacement (e.g. checking for a zero value and finding out the sign, together with constants for zero, one etc to allow generic programming) - some of the functionality will pretty fast become obsolete (e.g. i hope as soon as there's a useable integer, and people start to use it, much more efficient direct (non-integer based) modular artimetic classes will prop up, and integer itself won't be used long for modular arithmetic computations) IMHO stuff like sqr() in itself doesn't worth the risk of going beyond int

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

It might be possible to allow such an implementation by providing an escape clause. Perhaps something like: "Complexity requirements for certain functions may be relaxed if doing so allows improved complexity for other functions. Such complexity relaxations and improvements shall be documented by the implementation."

Is that a good idea? I don't know enough about the problem domain to have a strong opinion.

i think that's fine an alternative could be to simply state that all basic operations (+-*/%) should have less than O(N^2) (amortized?) complexity i personally wouldn't put restrictions on the rest of the interface: e.g. IMHO the complexity requirements on the constructors were made with positional number-system based implementations in mind (assuming that the constructor implementations consist of converting from one radix to another) also, i'm not sure how the allocation times were taken into account (if they were) br, andras

Maarten Kronenburg wrote:

Rene, In the meantime the get_sub has been added for bit access, see below.

Yes, I saw that before I sent the email. Hence I don't think it's sufficient.

This is not an iterator, but it may be sufficient for access of the binary representation. Is this also usefull for you?

size_type highest_bit() const; Complexity: O(N)

size_type lowest_bit() const; Complexity: O(N)

const integer get_sub( size_type startbit, size_type nbits ) const; Complexity: O(N)

There are a few problems with using those for "binary" access: * It is not optimal. Using the above would result in an O(N^2) algo for something that most of the time would be an O(1) operation (depending on the internal representation, at worse would be O(N)). * The representation that get_sub, highest_bit, lowest_bit, operate on is not defined. I don't see such a definition in the document either, AFAICT. So one couldn't even use the faster "int x = to_int(I.get_sub(0,16));" I don't care that much what the form of access looks like. The important aspect is having a *defined representation* that users can convert to and from. For example other access methods might be: // Iterators, like std::string::data: std::pair<word_type const *, word_type const *> integer::data() const; // Inserter, like std::string::copy: template <typename OutputIterator> void integer::copy(OutputIterator) const; // Stream like: template <typename Container> operator << (Container &, integer const &); Of course there would need to be a corresponding constructor to have the data round trip. -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo

Maarten Kronenburg wrote:

"Rene Rivera" wrote in message

...

I don't care that much what the form of access looks like. The important aspect is having a *defined representation* that users can convert to and from. For example other access methods might be:

// Iterators, like std::string::data: std::pair<word_type const *, word_type const *> integer::data() const;

// Inserter, like std::string::copy: template <typename OutputIterator> void integer::copy(OutputIterator) const;

// Stream like: template <typename Container> operator << (Container &, integer const &);

Of course there would need to be a corresponding constructor to have the data round trip.

But what should the iterator iterate over? Bits? Bytes?

A "word_type" you define, which at minimum would be bytes. And by you I mean the TR2 document you are proposing.

In my opinion get_sub of a bit or byte or whatever, with a converter like to_unsigned_int, gives you the O(1) access you require.

Sure, but it doesn't follow existing STL practices and norms.

Perhaps the user can define an iterator based on get_sub.

Of course, it's as simple as: ==== typedef boost::transform_iterator< boost::function< uint8_t (std::size_t) >, boost::counting_iterator<std::size_t> > I; integer n = 5; uint8_t get_uint8_n(integer * i, std::size_t n) { return i->get_sub(n*8,8); } I begin_i(I::base_type(0),boost::bind(&get_uint8_n,&n,_1)); I end_i(I::base_type(n.size(),boost::bind(&get_uint8_n,&n,_1,8)); std::vector<uint8_t> m(begin_i,end_i); ==== But first there's no integer::size(), and second it seems like a rather complex thing to push onto users (even given how simple the above is with the use of the Boost.Iterators and Boost.Bind libraries). -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo

Maarten Kronenburg wrote:

Rene, The user can define an iterator with the bit access functions highest_bit and get_sub.

OK, so there's an equivalent to size(). Which the iterator code I posted earlier would have to manipulate into the iteration interval.

The get_sub is O(1) when nbits is limited. Then the user must define what is iterated over, bits or bytes or words or...

No they don't, if you don't want them to. You can define a fixed unit your class iterates over. And even if you wanted the user to define what is iterated over you could make just the method that returns the pointers/iterators templated.

The integer class is not a template, because templates do not provide run-time polymorphism.

Reasoning, see circular. I guess I won't plan on switching from Botan's <http://botan.randombit.net> BigInteger class. Oh well, you win some you loose some :-\ <http://boost.org/more/discussion_policy.htm#effective> -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo

On 5/30/06, Rene Rivera <grafik.list@redshift-software.com> wrote:

...

const integer get_sub( size_type startbit, size_type nbits ) const; Complexity: O(N)

There are a few problems with using those for "binary" access:

* It is not optimal. Using the above would result in an O(N^2) algo for something that most of the time would be an O(1) operation (depending on the internal representation, at worse would be O(N)).

* The representation that get_sub, highest_bit, lowest_bit, operate on is not defined. I don't see such a definition in the document either, AFAICT. So one couldn't even use the faster "int x = to_int(I.get_sub(0,16));"

I don't care that much what the form of access looks like. The important aspect is having a *defined representation* that users can convert to and from. For example other access methods might be:

What can that defined representation be? I think it's the same question as: How would one represent an integer internally? (Earlier in this thread you mentioned that you would like to have this kind of access for performance reasons: eficiently implementing operations not supported by a stock integer.) For a high performance assembly implementation on an intel uP it can be a block of 32 bit words. For a resonably portable C++ implementation targeting the same uP it would be the same, except that only 31 bits are used, because in C(++) you do not have access to the carry flag, so you pay with memory for speed. Chosing any of these as the standardized one would force the other to create an O(N) interface for your "implementation access". If your operations are complex enough, and you can live with the above O(N) functions, let's go further: How about a negabinary (base -2 instead of base 2) representation? How about a non-binary representation with O(M(N)*logn(N)) access? How about a non positional representation with O(N^3) access? Either you seriously restrict the range of representations, and possibly render the best ones non-standard, or you end up with an "implementation access" that is unusable for your purpose. // Iterators, like std::string::data:

std::pair<word_type const *, word_type const *> integer::data() const;

This also raises memory handling issues: i suppose the pair would contain an begin and an end pointer -- who would own the memory? What about integers with user-defined allocators? br, andras

Andras Erdei wrote:

On 5/30/06, Rene Rivera <grafik.list@redshift-software.com> wrote:

...

...

const integer get_sub( size_type startbit, size_type nbits ) const; Complexity: O(N) There are a few problems with using those for "binary" access:

* It is not optimal. Using the above would result in an O(N^2) algo for something that most of the time would be an O(1) operation (depending on the internal representation, at worse would be O(N)).

* The representation that get_sub, highest_bit, lowest_bit, operate on is not defined. I don't see such a definition in the document either, AFAICT. So one couldn't even use the faster "int x = to_int(I.get_sub(0,16));"

I don't care that much what the form of access looks like. The important aspect is having a *defined representation* that users can convert to and from. For example other access methods might be:

What can that defined representation be?

I don't really care. But it could be the same representation used by the machine architecture for the int type, but extended to fit the number. Like the Java BigInt produces for example <http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html#toByteArray()>. Or what Maarten suggests on some other post.

I think it's the same question as: How would one represent an integer internally?

No at all.

(Earlier in this thread you mentioned that you would like to have this kind of access for performance reasons: eficiently implementing operations not supported by a stock integer.)

I said "optimal". Which for most operations would be O(N), possible O(logN) at best. My point is that having an operation take O(N^2) because of a bad design is, well, bad design :-) For whatever representation is provided other would have to translate to/from it.

// Iterators, like std::string::data:

...

std::pair<word_type const *, word_type const *> integer::data() const;

This also raises memory handling issues: i suppose the pair would contain an begin and an end pointer

That's what the above says.

-- who would own the memory?

Just like string, the integer would own the memory. That's why I put "const" above. It's a standard idiom.

What about integers with user-defined allocators?

Why would that matter? The allocator just manages memory. It's up to the integer to decide what to do with it. Again, look at std::string as an example. -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo