-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1

...

Hi! I'm a long-time user (and admirer) of the Boost libraries, and I've just uploaded a new one to the Boost Vault for consideration: the Extended Integer (XInt) library, a unlimited-precision integer library that I've been working on for the last few months. I'd like to request a preliminary review of it, please.

Well - BigInts have become like London Buses - you wait for ages and then six of them come along ;-)

Your Xint looks interesting, Boost styled (if not Boost-style tests), and Boost licence. Docs (though not Doxygen/Quickbook) and no examples. But these are trivial issues.

I can adapt the test suite, if someone could point me toward some description of how. I'm not sold on Doxygen as a good way to handle documentation, mostly because I've never seen any really good docs written in it. I did put an example in, in the documentation -- the Fibonacci example. There are a couple others in there too, like the one showing how the exception-blocking works. If it would help to have them as separate files too, that wouldn't be much of a problem.

I've not been following the WG21 discussions of Bigger Integers - perhaps you can summarise their response to N1744 (was is "we are too busy dealing with C++0X?").

Unfortunately I don't know anything about their response, or where I could find it. I didn't even know they'd addressed it until last week, when I saw mention of n1692 and n1744 in some older posts to this list. But I would have written that code even if they'd decided against it, because I had a need for it myself, for one of my own programs.

PS I note it doesn't (yet) specialise std::numeric_limits?

numeric_limits is something that is very highly desirable/essential for many applications (for example the Boost.Math package relies on this, and had to add it to be able to use the NTL package and GMP package).

I've put it on the to-do list. Though how useful it might be at this point is questionable... I doubt that very many packages test the is_bounded member, and most of the interesting non-floating-point-specific fields aren't specified when it's false.

NaN is essential IMO (if only to act as a 'missing value' marker (though I would favour a separate NaN for this purpose from std::numeric_limits<>::quiet_naN();

Sorry, I don't quite understand what you're suggesting I do in that last paragraph, if anything. The library has a NaN built in already, and numeric_limits<>::quiet_NaN is specified as being "meaningful for floating point types only." - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkus210ACgkQp9x9jeZ9/wRbigCgtQnj4a7N0rnUxbASwVYBSxmT 0Y8AoL0f8rBtYiQ3Z8IvE6761ma/vgzH =+b+O -----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1

you definitely ought to try doxygen out! once you used to it saves you time and nerves (did i use this word right?) documenting your code with doxygen style (for example) comments makes it TRULY self documented

That's one way to approach self-documenting code. :-)

forgot to say, i like your exception blocking mechanism

Thanks! It took a while to come up with it. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkutM2IACgkQp9x9jeZ9/wRysQCgtdkCGjCooZ8koF33aIvGBHHA 83sAoIlP4J2PPP9j0TpKOpeFJ0fMolgm =pX+Z -----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1

I'd leave doing work on docs and testing until you get more positive feedback.

Doxygen can work well (especially when used with Quickbook, but needs to have useful comments in the C++ code to be more than a list of classes, functions...). (I used to think Doxygen was used as an excuse not to write docs ;-)

That was the impression that I've gotten about it too. The docs that I've seen written with it are close to useless, not much better than simply reading the source code. I try to make my documentation more useful than that.

...

I did put an example in, in the documentation -- the Fibonacci example.

Sorry I didn't spot these - I expected to find in an /examples subfolder.

As I said, I can put it there too, if it would be useful. I usually go to the documentation first, and figured most other people would too. For larger examples, I'd definitely put them there, and just provide a link in the docs.

[...] is not encouraging, for reasons unclear.

http://www.linux2you.dk/JTC1/SC22/WG21/docs/papers/2008/n2598.html

gives the status of the above along with N1744 Michiel Slaters on which yours is based as "open" rather than rejected.

But should not necessarily deter you :-)

A working Boost library in widespread use might change things?

It would also keep programmers that prefer to use C++ from being forced to Python or another language, just for the large integer support. :-)

(But the ghost of GMP's GPL licence haunts Big Integer proposals. As I've said elsewhere, a really good solution must be switchable to use GMP, if your license requirements permit).

I can see the desirability of that. But that said, it shouldn't be all that difficult to write a wrapper for pretty much any external library, to adapt it to whatever interface xint ends up using. I'm aiming for a Boost-licensed native C++ implementation for now, as that seems to be what has been missing to date.

PS Would you collaborate with a GSoC student to do the Boost-style docs and tests, and more examples?

I'm willing, though I don't really think there's enough work for more than one person.

...

...

PS I note it doesn't (yet) specialise std::numeric_limits?

I've put it on the to-do list.

I think NaN *is* meaningful for your integer type. However this is a minor detail that can added later.

I agree, and I'll add it to the numeric_limits definition. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkutNxwACgkQp9x9jeZ9/wRMOgCaA64AYS0/oByVjSOL3yPMUwp4 Y7wAniY5prMF2niuvnF9Zn1ZW1EqibMM =DbTR -----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1

i had a look at the docs and i find the lib pretty cool the docs seem pretty clear to me (even though i don't like this plain style of docs)

I can "pretty them up" before the final release. I just wanted to get the information itself written down for review.

i have a copuple of suggestions

first, to make 'xint::integer' consistent (if i were you) i'd make all public member functions non-member friend functions because 'int' and other fundamentals have no member functions

Most of the non-operator member functions are there because n1692 required them.

and second, the docs lack algorithmic complexity estimation for operations as an end user i would like to know the order of time and/or space an operation will cost me

Easy enough to supply. I'll put it on the to-do list for the second review.

BTW i like the presence of implicit sharing my only question is can i make it (the sharing) thread safe by defining 'XINT_THREADSAFE'? (hm... here arises a question about operations thread safety notes in the docs)

That's covered. From the Compile-Time Options page: - ------------------------8<--------------------------- #define XINT_THREADSAFE This disables the copy-on-write optimization that the library uses by default, sets the exception-blocking code to work on a per-thread basis, and protects some shared resources from multiple simultaneous accesses, allowing fully thread-safe operation. You are still responsible for ensuring that only one thread can access any specific integer at a time. When this option is used, you must also link your program with the Boost.Thread library. - ------------------------8<--------------------------- I should probably move that information to the Thread-Safe Operation page instead, and just point the Compile-Time Options page to it. It would fit better there.

i don't like the template constructor however you can ignore this point since i can not provide any arguments yet

I tried several different ways to convert native integer types to xint::integer. That's the best one I found. If you could suggest an alternative, I'd certainly be willing to entertain it.

what about compile time fixed precision ints? like 'xint::fixed<128>' with '128' denoting number of bits (or bytes?)

I don't see any obvious reason why that couldn't be implemented on top of xint::integer. It should only require a fairly simple set of template wrappers. I think it should be deferred until the underlying library makes it through the review process though. Also, I'm noting who made suggestions for the library, for an acknowledgments page. Do you prefer to be known only as "Pavel", or do you have a publicly-known last name? - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkutK1QACgkQp9x9jeZ9/wTGegCgrGrrICQTbna4Nbklmn9cEMI7 TJ8An0pWiGJmKPnf8n1KMs+gnAn/dxOl =LqqK -----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1

...

I tried several different ways to convert native integer types to xint::integer. That's the best one I found. If you could suggest an alternative, I'd certainly be willing to entertain it.

template<class T> explicit integer(const T& arg, typename boost::enable_if<boost::is_integral<T> >::type* = 0);

That would essentially be identical to what I've got now, but would only be active on integer types? - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkutQakACgkQp9x9jeZ9/wSwwQCfYB1c6ufh9k11JqUXVHj1N29i 5TsAoICNrrht92KpABGRtJsQM0yahcYw =OUlg -----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1

...

This disables the copy-on-write optimization that the library uses by default [...]

I'm not convinced that integers should be COW. What situations do you forsee where COW would be helpful but move semantics wouldn't suffice?

As described on the rationale page of the documentation, the primary reason I'm using copy-on-write is that move semantics aren't widely available yet. Portability is one of my primary goals, and while I've seen references to a move-semantics-emulator in Boost, I've also seen suggestions that it relies on the compiler to somehow recognize it. That doesn't sound fully portable to me. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkutiIsACgkQp9x9jeZ9/wQhngCdEsfZVM2akyS+mY8BS9utOHmE TaQAoIItLKnFEaIVEhCc6JZyWKah66hV =1izb -----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1

...

As described on the rationale page of the documentation, the primary reason I'm using copy-on-write is that move semantics aren't widely available yet. Portability is one of my primary goals, and while I've seen references to a move-semantics-emulator in Boost, I've also seen suggestions that it relies on the compiler to somehow recognize it. That doesn't sound fully portable to me.

Have you looked at the (proposed) Boost.Move library by Ion (available from the sandbox)?

It does a pretty good job of emulating move semantics for compilers that lack rvalue references.

No, I wasn't aware of its existence. I haven't seen it mentioned on this list in the last couple weeks, is it under review for official acceptance? If not, no offense, but I can't use it. I'll be happy to do so when it's an official part of the Boost library though.

Not sure what you're referring to by "suggestions that it relies on the compiler to somehow recognize it"...can you elaborate?

I finally tracked down the reference. From the "Thread Management" documentation page of Boost.Thread: - ------------------------8<----------------------- Objects of type boost::thread are movable, however, so they can be stored in move-aware containers, and returned from functions. [...] [Note: On compilers that support rvalue references, boost::thread provides a proper move constructor and move-assignment operator, and therefore meets the C++0x MoveConstructible and MoveAssignable concepts. With such compilers, boost::thread can therefore be used with containers that support those concepts. For other compilers, move support is provided with a move emulation layer, so containers must explicitly detect that move emulation layer. See <boost/thread/detail/move.hpp> for details.] - ------------------------8<----------------------- I misremembered it slightly, but the general argument still stands: move semantics aren't widely available yet, so the copy-on-write behavior of XInt is necessary for now. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuuE7UACgkQp9x9jeZ9/wQ80wCdFUWFSNPngv5BpocWnbml+mPZ gVsAoO6hMycPIp/h8zFgmnSG48emMonL =V0vo -----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1

...

...

Have you looked at the (proposed) Boost.Move library by Ion (available from the sandbox)? [...]

No, I wasn't aware of its existence. I haven't seen it mentioned on this list in the last couple weeks, is it under review for official acceptance?

AFAIK, it is in the review queue.

Ah, excellent. As soon as it's approved, I'll be happy to take advantage of it.

I understand your hesitation. [...] I think the advantages that move emulation has over copy-on-write (better performance, simpler implementation, thread safety) outweigh its disadvantages (the framework built around boost::rv<T> is still somewhat experimental), so I would urge you to take a look at it in the near future.

Certainly. It should allow XInt to run at copy-on-write speeds, even in thread-safe mode -- a major improvement, and one that I'd jump at.

...

...

Not sure what you're referring to by "suggestions that it relies on the compiler to somehow recognize it"...can you elaborate?

I finally tracked down the reference. From the "Thread Management" documentation page of Boost.Thread: [...]

Right, *containers* (not compilers) must detect that move emulation layer. So COW does have an additional advantage: better performance with non-move-aware containers.

Yes, exactly. I'm not sure what's involved with making a container move-aware, but I'm fairly certain that the STL's containers aren't at present. I don't know whether the Boost.Move library will suffer from the same limitation.

A suggestion (perhaps not a good one): replace the thread-safe implementation of xint::integer with a move-aware one, and allow either to be chosen via preprocessor defines.

If Boost.Move doesn't have the limitation mentioned above, then I'll probably get rid of the copy-on-write stuff completely. It wouldn't have any advantage that I can think of, at least for the moment.

The choice of using COW or move emulation might be regarded more as an implementation issue, but (I'm guessing) will probably be brought up again during review.

I think I can defend the decision if it is. :-)

I will try to take a look at the rest of the library shortly.

Thanks. I appreciate the feedback. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuuq+sACgkQp9x9jeZ9/wQrbwCgySb5iD38QmEldkYWePd4AS78 ROYAoKfbtVIJHZwJ8VjBNHS89gtIPKZe =lqiF -----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1

[...] So for the time being, at least for the thread-safe version (which I guess could just be called the "move-aware" version, if you still end up with a COW version), I think you should use a custom implementation of emulated rvalue references [...]

I'll certainly look into it. Thanks for the advice. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuu1MsACgkQp9x9jeZ9/wTCrQCdFQA7+hYkjLGXEFJgxMU8TEIr PZkAoPHwwF21ttQl7PybE8mlKhyd+P4q =6joh -----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1

...

As described on the rationale page of the documentation, the primary reason I'm using copy-on-write is that move semantics aren't widely available yet. Portability is one of my primary goals, and while I've seen references to a move-semantics-emulator in Boost, I've also seen suggestions that it relies on the compiler to somehow recognize it. That doesn't sound fully portable to me.

Please could you be more explicit. Do you know some compilers on which Boost.Move doesn't works?

As I described later in that branch of the thread, that statement was based on a comment in the Boost.Thread documentation (which I misremembered anyway). It didn't refer to the Boost.Move library. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuvzB8ACgkQp9x9jeZ9/wS+NACeLiYYilXCmglwU7lFRkX48uZf 7tEAnAiho3bkSdryHGTYm1XQhzws+XYc =xG0m -----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1

...

...

first, to make 'xint::integer' consistent (if i were you) i'd make all public member functions non-member friend functions because 'int' and other fundamentals have no member functions

Most of the non-operator member functions are there because n1692 required them.

i wasn't aware of it but my first statement still holds

'Fraid I have to disagree with it then. n1692 compatibility is more important to me than trying to make it look exactly like a built-in type. *Work* like a built-in type, yes... look like one, no.

on the other hand looking at .net ints and double having 'toString()' and other member it's becoming a common practice

I don't see any viable reason to pretend that it's not a class.

you may wonder what other people think about it

Certainly. And if more than a few people tell me that they agree with you, I'll reconsider my position. :-)

...

...

what about compile time fixed precision ints? like 'xint::fixed<128>' with '128' denoting number of bits (or bytes?)

I don't see any obvious reason why that couldn't be implemented on top of xint::integer. It should only require a fairly simple set of template wrappers. I think it should be deferred until the underlying library makes it through the review process though.

in my view a templated version must be somewhat different as i figured out you use memory allocation for arbitrary precision objects

Rather difficult to do it any other way. :-)

and one won't want to pay this overhead for simple (portable) int128 for example an 'xint::fixed<N>' (let's call it this way for now) must be a pod-like type which reuse all of the algorithms for 'xint::integer'

Then the fixed-size types will have to be implemented later, if there's enough call for them. For this stage, I'm concentrating on arbitrary-sized integers.

...

Also, I'm noting who made suggestions for the library, for an acknowledgments page. Do you prefer to be known only as "Pavel", or do you have a publicly-known last name?

well, let it be just Pavel

As you wish. :-)

...

I'm aiming for the more casual user of large integers. [...]

...

Don't think that those people don't exist -- the whole reason I started writing it was because I was in the first camp myself. :-) I suspect that people like that make up the vast majority of those who need a large integer library.

you read other's minds, don't you?

Only when it's convenient. ;-)

i believe once you have state-of-the-art public interface for your lib you can easily switch to virtually any implementation so i don't see a problem here at all

I agree. The interface is generic enough that it should fit just about any similar library out there. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuuEG0ACgkQp9x9jeZ9/wR86wCfd6kWCHVApjF7FDgNVllnfu2k 4TMAn030+PvvAnqHkVEQ0J/5Z55vZNbu =l5JP -----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1

I saw a couple of issues: * The operators should be defined in namespace xint, so they will be found by ADL.

Done. I wasn't sure where they should go.

* If you provide random functions, it should be as a specialization of boost::uniform_int. Ideally, however, boost::uniform_int would just work.

I'm not familiar with that part of Boost.Random. I'm not sure how xint::random_by_size could be properly mapped to it, though the other three options could.

random.cpp:80 std::transform(mString.begin(), mString.end(), mString.begin(), zero); this could be std::fill(mString.begin(), mString.end(), '\0');

Done, and thanks. I just grabbed the first thing that I knew. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkutO3EACgkQp9x9jeZ9/wTyrwCcDYw420BAMmpCW5SUUlLZsekR NAgAoLSAcUgGef0fmdZaeQmmBdXroEJz =Rpvz -----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1

"Random Number Functions The library includes a secure random number generator, primarily to support the random_prime function, but a user-friendly interface is also available to developers using the library."

*Mersenne Twister is not a cryptographic PRNG*

Hm, you're right. I didn't realize that it could be predicted after so few values. I'll re-work that part to use /dev/urandom or RtlGenRandom directly when they're available. On systems where they're *not* available, is there a better choice of generator, given an (unpredictable) user-supplied seed value? - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkutP+UACgkQp9x9jeZ9/wSn8ACgictlL+BVXaSDUMQwKP6iMoPx xOsAnRuhUNu8RkAzm91SS1pr39yhewEd =1g3x -----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1

...

...

*Mersenne Twister is not a cryptographic PRNG*

Hm, you're right. I didn't realize that it could be predicted after so few values. I'll re-work that part to use /dev/urandom or RtlGenRandom directly when they're available.

On systems where they're *not* available, is there a better choice of generator, given an (unpredictable) user-supplied seed value?

All the Boost.Random generators are linear and therefore insecure. Can you just use boost::random_device instead of writing your own wrapper?

I could use that instead of /dev/urandom and RtlGenRandom, but then the library wouldn't compile on systems where boost::random_device isn't available. My goal was to make something that would work regardless of whether such a device was available, and leave it up to the person using the library whether they want to continue when it isn't. So again, given that it's going to be less secure, is there a better choice than the Mersenne Twister for systems where no random device is available? - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkutRw0ACgkQp9x9jeZ9/wQyIQCeP8BfUKt6YdOvLevvgmOt/3hN EY0An39R6usHl189H0mjUwsyo5yvqaVf =nzKd -----END PGP SIGNATURE-----

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1

...

So again, given that it's going to be less secure, is there a better choice than the Mersenne Twister for systems where no random device is available?

Why not simply accept a Boost.Random (P)RNG, so the users can decide how random they want it to be? If you provide something that you expect will be used for security, it's a *feature* for it to fail when there's no CRNG available.

I started answering this by defending my current design, on the argument that it's easier to use than one that requires the user to know about random number generators himself. But after thinking about it, I *could* provide a plug-in interface to whatever RNG the user wants to use, and simply default to a less secure (but always available) RNG. That should satisfy all camps -- those who need cryptographically-secure RNGs can plug them in, and those who don't care can use the default RNG and never worry about it. I'll put that on the to-do list for the next iteration. - -- Chad Nelson Oak Circle Software, Inc. * * * -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkuthv0ACgkQp9x9jeZ9/wT1XwCeNf2uly1FC6xrMIIMP1BSZIBA +u0AnRi661xGaOTQ2UiGIDBelMme6X1V =1XOp -----END PGP SIGNATURE-----

AMDG Chad Nelson wrote:

Steven Watanabe said:

...

All the Boost.Random generators are linear and therefore insecure. Can you just use boost::random_device instead of writing your own wrapper?

You didn't mention that boost::random_device is only available for Linux and BSD.

I suppose I should have mentioned this--especially since I just fixed this about two weeks ago. In Christ, Steven Watanabe