Hi all, I made a new release of my multiprecision integer library with the following changes: - improved documentation - serialization support - bugfixes - improved benchmark tool - prime generation has been reworked - probably some other things which I forgot I believe it's pretty much ready for review now. The mp_int reference section is slightly lacking in a few places, but other than that I think it's pretty solid. I have a few things in mind for the future of this library: - improved division and squaring algorithms according to the papers on my disk. - an implementation of an mp_int proxy type that acts on preallocated memory, but does not manage memory itself. This can then be used to improve the runtime of several algorithms. - expression template support There is pregenerated html documentation under libs/mp_math/doc/html/ http://www.boostpro.com/vault/index.php?action=downloadfile&filename=mp_math_v03.zip&directory=Math%20-%20Numerics& Kevin Sopp
Great! Thanks for the quick fix Kevin. Cheers, Mikko Kevin Sopp wrote:
Hi all,
I made a new release of my multiprecision integer library with the following changes:
- improved documentation - serialization support - bugfixes - improved benchmark tool - prime generation has been reworked - probably some other things which I forgot
I believe it's pretty much ready for review now. The mp_int reference section is slightly lacking in a few places, but other than that I think it's pretty solid.
I have a few things in mind for the future of this library:
- improved division and squaring algorithms according to the papers on my disk. - an implementation of an mp_int proxy type that acts on preallocated memory, but does not manage memory itself. This can then be used to improve the runtime of several algorithms. - expression template support
There is pregenerated html documentation under libs/mp_math/doc/html/
Kevin Sopp _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Kevin Sopp wrote:
I made a new release of my multiprecision integer library
I personally find the words arbitrary precision or multiprecision ambiguous. I never know which one means that the numbers grow as needed and which ones means that it can work with any size, but fixed (which is useful to simulating hardware).
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Kevin Sopp Sent: 06 October 2008 14:40 To: boost@lists.boost.org Subject: [boost] [mp_int] new release
I made a new release of my multiprecision integer library with the following changes:
- improved documentation - serialization support - bugfixes - improved benchmark tool - prime generation has been reworked - probably some other things which I forgot
I believe it's pretty much ready for review now. The mp_int reference section is slightly lacking in a few places, but other than that I think it's pretty solid.
This looks very useful but I note that http://www.boost.org/development/requirements.html#License and current Boost practice is that all the files include the Boost license text. (This should include the .qbk as well - as a Quickbook comment. Tedious but you can paste). [/ mp_int.qbk Copyright Kevin Sopp. Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt). ] (This is to allow people to use it without hassle from their legal people - which like to go over everything with a fine tooth comb). I don't see that your 'in the public domain' (rather ill-defined?) is any different from the Boost license text, so this is a mainly cosmetic matter. For some or all the source code, you could also include Tom St. Denis in the copyright too? Paul --- Paul A Bristow Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB +44 1539561830 & SMS, Mobile +44 7714 330204 & SMS pbristow@hetp.u-net.com
Hi Paul,
This looks very useful but I note that
http://www.boost.org/development/requirements.html#License
and current Boost practice is that all the files include the Boost license text. (This should include the .qbk as well - as a Quickbook comment. Tedious but you can paste).
I know about that, and I think this license requirement wasn't written with a public domain library in mind. I believe it is also possible to add a noinspect comment in the file to silence the inspection script.
I don't see that your 'in the public domain' (rather ill-defined?) is any different from the Boost license text, so this is a mainly cosmetic matter. For some or all the source code, you could also include Tom St. Denis in the copyright too?
Public Domain specifically means that there is no copyright on the code. I could create a dual release with the Boost license for Boost and put up the public domain version somewhere else but that is not what I would like to do.
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Kevin Sopp Sent: 07 October 2008 12:45 To: boost@lists.boost.org Subject: Re: [boost] [mp_int] new release
Hi Paul,
This looks very useful but I note that
http://www.boost.org/development/requirements.html#License
and current Boost practice is that all the files include the Boost license text. (This should include the .qbk as well - as a Quickbook comment. Tedious but you can paste).
I know about that, and I think this license requirement wasn't written with a public domain library in mind. I believe it is also possible to add a noinspect comment in the file to silence the inspection script.
I don't see that your 'in the public domain' (rather ill-defined?) is any different from the Boost license text, so this is a mainly cosmetic matter. For some or all the source code, you could also include Tom St. Denis in the copyright too?
Public Domain specifically means that there is no copyright on the code. I could create a dual release with the Boost license for Boost and put up the public domain version somewhere else but that is not what I would like to do.
I can understand that two versions is a bad idea. But I am puzzled at your reluctance to claim copyright (and hence to use the Boost licence which deliberately gives all the rights of a public domain thing - and frees you of all responsibility too). In many countries, if you have written it, you have copyright anyway. What is your objection? Paul --- Paul A Bristow Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB +44 1539561830 & SMS, Mobile +44 7714 330204 & SMS pbristow@hetp.u-net.com
I can understand that two versions is a bad idea.
But I am puzzled at your reluctance to claim copyright (and hence to use the Boost licence which deliberately gives all the rights of a public domain thing - and frees you of all responsibility too).
In many countries, if you have written it, you have copyright anyway.
That's why you need to give it away explicitly to make it public domain.
What is your objection?
Copyright is the basic barrier that hinders adoption of code, with public domain code that last barrier falls. Anyone can use it for whatever purpose without any restrictions, it's the ultimate adoptable code.
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Kevin Sopp Sent: 07 October 2008 15:29 To: boost@lists.boost.org Subject: Re: [boost] [mp_int] new release
I can understand that two versions is a bad idea.
But I am puzzled at your reluctance to claim copyright (and hence to use the Boost licence which deliberately gives all the rights of a public domain thing - and frees you of all responsibility too).
In many countries, if you have written it, you have copyright anyway.
That's why you need to give it away explicitly to make it public domain.
What is your objection?
Copyright is the basic barrier that hinders adoption of code, with public domain code that last barrier falls. Anyone can use it for whatever purpose without any restrictions, it's the ultimate adoptable code.
My understanding is that this just isn't correct. There has been a lot of work to create the Boost license that achieves exactly this effect - and worldwide - and even approved by lots of real lawyers (IANAL of course!). So I strongly suggest you use the Boost license - it really does ensure that everyone can freely use it - achieving your objective to give away without any liability. Paul PS Since most of your potential 'customers' are would-be GMP users, put off by the GPL, a comparison of features might be useful? --- Paul A Bristow Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB +44 1539561830 & SMS, Mobile +44 7714 330204 & SMS pbristow@hetp.u-net.com
On Tue, Oct 7, 2008 at 10:29, Kevin Sopp <baraclese@googlemail.com> wrote:
I can understand that two versions is a bad idea.
But I am puzzled at your reluctance to claim copyright (and hence to use the Boost licence which deliberately gives all the rights of a public domain thing - and frees you of all responsibility too).
In many countries, if you have written it, you have copyright anyway.
That's why you need to give it away explicitly to make it public domain.
"Just as there is nothing in the law that permits a person to dump personal property in the public highway, there is nothing that permits the dumping of intellectual property into the public domain — except as happens in due course when any applicable copyrights expire. Until those copyrights expire, there is no mechanism in the law by which an owner of software can simply elect to place it in the public domain." ~ From "Why the Public Domain Isn't a License", by Lawrence Rosen, attorney and former OSI general counsel, at http://rosenlaw.com/lj16.htm
Kevin Sopp schrieb am Dienstag 07 Oktober 2008 um 13:45:
Public Domain specifically means that there is no copyright on the code. I could create a dual release with the Boost license for Boost and put up the public domain version somewhere else but that is not what I would like to do.
FYI, at least in Germany and Austria one cannot release something as public domain as a private person. So you have to have a proper copyright statements to avoid copyright trouble for us Krauts ;) . Best, -- Maik
FYI, at least in Germany and Austria one cannot release something as public domain as a private person. So you have to have a proper copyright statements to avoid copyright trouble for us Krauts ;) .
You cannot release it into the public domain but you can give others the right to use it without restrictions. I think I may need to do something like SQLite - they state at the top of each file `The author disclaims copyright to this source code.`
------------------------------------------------- From: "Kevin Sopp" <baraclese@googlemail.com> Sent: Monday, October 06, 2008 8:40 AM To: <boost@lists.boost.org> Subject: [boost] [mp_int] new release
Hi all,
Hi Kevin, Looks very interesting :). I'm trying to use your library with my lazy_exact type by wrapping it in boost::rational< mp_int<> >. The problem I've run into is that I need a specialization of std::numeric_limits< mp_int<> > in order to use boost::rational with it. Do you have such a traits specialization? Cheers, Brandon
I made a new release of my multiprecision integer library with the following changes:
- improved documentation - serialization support - bugfixes - improved benchmark tool - prime generation has been reworked - probably some other things which I forgot
I believe it's pretty much ready for review now. The mp_int reference section is slightly lacking in a few places, but other than that I think it's pretty solid.
I have a few things in mind for the future of this library:
- improved division and squaring algorithms according to the papers on my disk. - an implementation of an mp_int proxy type that acts on preallocated memory, but does not manage memory itself. This can then be used to improve the runtime of several algorithms. - expression template support
There is pregenerated html documentation under libs/mp_math/doc/html/
Kevin Sopp _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
-------------------------------------------------- From: "Mathias Gaunard" <mathias.gaunard@ens-lyon.org> Sent: Monday, October 06, 2008 5:50 PM To: <boost@lists.boost.org> Subject: Re: [boost] [mp_int] new release
Kevin Sopp wrote:
I made a new release of my multiprecision integer library
I personally find the words arbitrary precision or multiprecision ambiguous. I never know which one means that the numbers grow as needed and which ones means that it can work with any size, but fixed (which is useful to simulating hardware).
I have this same issue. From my tests I suspect his grows arbitrarily. I would propose a name change to reflect that. I'm sure this has been discussed before. big_int seems popular if a bit crude. Assuming it is arbitrary, arbitrary_precision_int? (perhaps convenience typedefs?) I tend to prefer descriptive names to abbreviations; though I concede I may be in the minority.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Wed, Oct 8, 2008 at 11:01, Brandon Kohn <blkohn@hotmail.com> wrote:
-------------------------------------------------- From: "Mathias Gaunard" <mathias.gaunard@ens-lyon.org> Sent: Monday, October 06, 2008 5:50 PM To: <boost@lists.boost.org> Subject: Re: [boost] [mp_int] new release
Kevin Sopp wrote:
I made a new release of my multiprecision integer library
I personally find the words arbitrary precision or multiprecision ambiguous. I never know which one means that the numbers grow as needed and which ones means that it can work with any size, but fixed (which is useful to simulating hardware).
I have this same issue. From my tests I suspect his grows arbitrarily. I would propose a name change to reflect that. I'm sure this has been discussed before. big_int seems popular if a bit crude. Assuming it is arbitrary, arbitrary_precision_int? (perhaps convenience typedefs?) I tend to prefer descriptive names to abbreviations; though I concede I may be in the minority.
I'm not a fan of that one, since LLVM has an "APInt" class which represents a fixed, but arbitrary, precision integer. How about unbounded_int? It fits nicely with the is_bounded in numeric_limits. ~ Scott
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Scott McMurray Sent: 08 October 2008 16:11 To: boost@lists.boost.org Subject: Re: [boost] [mp_int] new release
On Wed, Oct 8, 2008 at 11:01, Brandon Kohn <blkohn@hotmail.com> wrote:
-------------------------------------------------- From: "Mathias Gaunard" <mathias.gaunard@ens-lyon.org> Sent: Monday, October 06, 2008 5:50 PM To: <boost@lists.boost.org> Subject: Re: [boost] [mp_int] new release
Kevin Sopp wrote:
I made a new release of my multiprecision integer library
I personally find the words arbitrary precision or multiprecision ambiguous. I never know which one means that the numbers grow as needed and which ones means that it can work with any size, but fixed
I have this same issue. From my tests I suspect his grows arbitrarily. I would propose a name change to reflect that. I'm sure this has been discussed before. big_int seems popular if a bit crude. Assuming it is arbitrary, arbitrary_precision_int? (perhaps convenience typedefs?) I tend to prefer descriptive names to abbreviations; though I concede I may be in the minority.
I'm not a fan of that one, since LLVM has an "APInt" class which represents a fixed, but arbitrary, precision integer.
How about unbounded_int? It fits nicely with the is_bounded in numeric_limits.
So are you proposing two names: bounded_int - arbitrary but fixed (maximum?) size integer unbounded_int - grows to accommodate a size (bounded only by machine memory). As an aside, does this scale to floating-point? If we were to produce a Boost equivalent to NTL quad_float bounded_float and RR - arbitrary but fixed (default 50 decimal digits) and an unbounded Exact real, for example to unbounded_float (or unbounded_real) similar to exact real - but then exact_real would be more obvious? and bounded_float or bounded_real But then one wants to encode the real precision? float, double, quad_float, octo_float... Paul --- Paul A Bristow Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB +44 1539561830 & SMS, Mobile +44 7714 330204 & SMS pbristow@hetp.u-net.com
On Wed, Oct 8, 2008 at 12:30, Paul A Bristow <pbristow@hetp.u-net.com> wrote:
So are you proposing two names:
bounded_int - arbitrary but fixed (maximum?) size integer
unbounded_int - grows to accommodate a size (bounded only by machine memory).
I'm just proposing the latter name, as the documentation specifies that the integers "grow dynamically as needed". I would be interested in a general facility for arbitrary-sized integers (so I could add 2 64-bit numbers on any architecture as bounded_int<65>s, for example, with no possibility of overflow), but that's out of scope for this proposal. (It would be nice if it could be done just with a different allocator, but I don't think that's feasible, currently.)
As an aside, does this scale to floating-point?
If we were to produce a Boost equivalent to NTL quad_float bounded_float and RR - arbitrary but fixed (default 50 decimal digits) and an unbounded Exact real,
for example to
unbounded_float (or unbounded_real)
similar to exact real - but then exact_real would be more obvious?
I dislike exact_real, since there are obviously an infinite number of reals that cannot be held exactly.
and bounded_float or bounded_real
But then one wants to encode the real precision? float, double, quad_float, octo_float...
I presume the bits of mantissa and exponent would be template parameters.
Scott McMurray wrote:
I would be interested in a general facility for arbitrary-sized integers (so I could add 2 64-bit numbers on any architecture as bounded_int<65>s, for example, with no possibility of overflow), but that's out of scope for this proposal. (It would be nice if it could be done just with a different allocator, but I don't think that's feasible, currently.)
I am also interested in this. It would be very useful in conjunction with boost::rational. Using gmp's mpq_class for rationals or mp_int with boost::rational is overkill in my case because I can bound the precision I need in a given algorithm to a specific number of bits known at compile time. I would prefer to allocate those as fixed sized bounded integers on the stack instead of dynamically allocating variable sized integers, which would confer significant constant factor improvement in efficiency of both runtime and memory consumption. Luke
How about unbounded_int? It fits nicely with the is_bounded in numeric_limits.
So are you proposing two names:
bounded_int - arbitrary but fixed (maximum?) size integer
unbounded_int - grows to accommodate a size (bounded only by machine memory).
My plan was to call a fixed precision integer fp_int. I think it's a good idea to keep the name short for such a basic arithmetic type. I can make it clearer in the introduction that mp_int stands for multiple precision integer which grows dynamically in size / has unbounded precision. I really like the name mp_int, I would accept ap_int though.
On Wed, Oct 8, 2008 at 22:33, Kevin Sopp <baraclese@googlemail.com> wrote:
My plan was to call a fixed precision integer fp_int. I think it's a good idea to keep the name short for such a basic arithmetic type. I can make it clearer in the introduction that mp_int stands for multiple precision integer which grows dynamically in size / has unbounded precision. I really like the name mp_int, I would accept ap_int though.
"Choose meaningful names - explicit is better than implicit, and readability counts. There is a strong preference for clear and descriptive names, even if lengthy." ~ http://www.boost.org/development/requirements.html#Design_and_Programming People can always typedef unbounded_int<> mp_int; if they want to. (I'd probably use a typedef anyways, since I find <> everywhere aesthetically distasteful.) Kim Barrett's suggestion of just calling it integer is rather nice. Especially if integer<> were integer<unbounded> and it were also possible to specify integer<bounded<256> >, for example. (Or infinite/fixed, or ...) I downloaded it and played a bit; everything seemed intuitive enough. There's an interesting project for someone to expression template it, too =)
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Kevin Sopp Sent: 09 October 2008 03:34 To: boost@lists.boost.org Subject: Re: [boost] [mp_int] new release
How about unbounded_int? It fits nicely with the is_bounded in numeric_limits.
So are you proposing two names:
bounded_int - arbitrary but fixed (maximum?) size integer
unbounded_int - grows to accommodate a size (bounded only by machine memory).
My plan was to call a fixed precision integer fp_int. I think it's a good idea to keep the name short for such a basic arithmetic type. I can make it clearer in the introduction that mp_int stands for multiple precision integer which grows dynamically in size / has unbounded precision. I really like the name mp_int, I would accept ap_int though.
I really, really don't like any of these names :-( fp_int sounds something to do with Floating Point (nonsense of course ;-) mp_int doesn't say anything obvious to me. Neither seem to me to meet Boost's preference for "Clarity before curtness". I think it must be really obvious if the type is bounded/fixed, or will grow. It's not for the writers - it's for the *readers* of programs who need to know immediately what sort of fancy integer beast is being used (without RTFM). Ideally, a Boost library should at least fix the naming for both types, and the structure too? Paul --- Paul A Bristow Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB +44 1539561830 & SMS, Mobile +44 7714 330204 & SMS pbristow@hetp.u-net.com
------------------------------------------------- From: "Kevin Sopp" <baraclese@googlemail.com> Sent: Monday, October 06, 2008 8:40 AM To: <boost@lists.boost.org> Subject: [boost] [mp_int] new release
Hi all,
I made a new release of my multiprecision integer library with the following changes:
- improved documentation - serialization support - bugfixes - improved benchmark tool - prime generation has been reworked - probably some other things which I forgot
I believe it's pretty much ready for review now. The mp_int reference section is slightly lacking in a few places, but other than that I think it's pretty solid.
Hi Kevin, I managed to scrabble together a dumb numeric_limits specialization and was able to proceed with my tests. My I'm able to use my lazy_exact type with arbitrary precision integer classes by way of boost::rational. So I'm able to do comparison tests between your class and mpz_class. There seem to be some issues with the mpz_class with respect to the normalization test in boost::rational, but I was able to get success by commenting out these BOOST_ASSERTs. (not of import to your lib, but wanted to point it out if anyone else has tried...) Anyway, I think I've run into a few bugs with mp_int<> when used in a boost::rational. First there is no A % B operation which is const (boost::rational complained as it tries to do a mod operation on a const int_type.) I added one and got past this. During the normalization step of boost::rational the numerator and denominator are normalized by the gcd of the two. In one case I was testing the %= operator of mp_int<> was causing an infinite loop in the boost::math::gcd call. I made an attempt at a fix (though I didn't really spend much time on it.. so I'm not sure what if any side-effects) // TODO currently the sign of the remainder is the sign of the divisor // i.e. rhs. This is inconsistent with C99, for which it is the sign of // the dividend. I don't know about C++0x yet. template<class A, class T> mp_int<A,T>& mp_int<A,T>::operator %= (const mp_int<A,T>& rhs) { mp_int<A,T> remainder; divide(rhs, &remainder); //if (remainder.sign_ != rhs.sign_) //! I commented these out to get past my issue (as it seems the negative remainder is what the result should be in this case) // remainder += rhs; //! I'm sure more scrutiny of the sign differences between *this*, rhs, and remainder are required to get it right in all cases. swap(remainder); return *this; } The case I had fail was when normalizing (-16384)/(16384). (-1/1). So it was infinite looping on boost::math::gcd( mp_int<>( -16384 ), mp_int<>( 16384 ) ); The next issue I've had which I haven't been able to get past is when I initialize an mp_int<> with std::numeric_limits< long >::max(); In this case the issue I'm having may not be a bug at all.. I'm not certain. I am attempting to create a quick and dirty heuristic to convert a rational into a double (for rough calculations in test) and so first tried an iterative system which takes an mp_int<> and iteratively divides it by mp_int<>( max_long ) until the value will fit into a long. Coupled with some creative bookkeeping, my hope is to be able to check if the calculations are in the right direction. Here is what I've done so far: double rational_cast( const boost::rational< boost::mp_math::mp_int<> >& src ) { typedef boost::mp_math::mp_int<> int_t; int_t num = src.numerator(); int_t den = src.denominator(); int_t maxLong( (std::numeric_limits<long>::max)() ); int_t q = num / den; int_t r = num % den; double x=0,n=0,d=0; while( q > maxLong ) { x += boost::numeric_cast<double>( (std::numeric_limits<long>::max)() ); q -= maxLong; } x += boost::numeric_cast<double>( q.to_integral<long>() ); while( den > maxLong ) { d += boost::numeric_cast<double>( (std::numeric_limits<long>::max)() ); den -= maxLong; } d += boost::numeric_cast<double>( den.to_integral<long>() ); while( r > maxLong ) { n += boost::numeric_cast<double>( (std::numeric_limits<long>::max)() ); r -= maxLong; } n += boost::numeric_cast<double>( r.to_integral<long>() ); return x + n/d; } I know that there is a possibility that these loops may simply take a very large amount of time (and there are probably other issues with what I'm trying...). My first calculation with the lazy_exact type using this is to approximate pi, and in this case I have confirmed that q is 3. The subsequent loops seem to run infinitely however, and inspection of the subtractions of maxLong inside mp_int<> do not seem to be fruitful (the used_ field never seems to go down, and the value in digits_ bounces around significantly large values which do not decrease monotonically as one would expect). When I inspected the value for maxLong, digits_ contained the correct value, but used_ was set to 1 (is this correct?). The values in n, r, and d seemed to have a correspondence between the number of digits specified in digits_ field and the value in the used_ field. (I.e. digits_ 2334974798 has used_ = 10, but digits_ = 2147483647 used_ = 1 for maxLong ).
I have a few things in mind for the future of this library:
- improved division and squaring algorithms according to the papers on my disk. - an implementation of an mp_int proxy type that acts on preallocated memory, but does not manage memory itself. This can then be used to improve the runtime of several algorithms. - expression template support
There is pregenerated html documentation under libs/mp_math/doc/html/
Kevin Sopp
Respectfully, Brandon
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
First there is no A % B operation which is const (boost::rational complained as it tries to do a mod operation on a const int_type.) I added one and got past this.
How does the function you added look like? I'm not sure I understand why you would want to do a mod operation on a constant type. a = b % c; // b and c are constant a %= b; // b is constant Both are supported.
During the normalization step of boost::rational the numerator and denominator are normalized by the gcd of the two. In one case I was testing the %= operator of mp_int<> was causing an infinite loop in the boost::math::gcd call. I made an attempt at a fix (though I didn't really spend much time on it.. so I'm not sure what if any side-effects) ... The case I had fail was when normalizing (-16384)/(16384). (-1/1). So it was infinite looping on boost::math::gcd( mp_int<>( -16384 ), mp_int<>( 16384 ) );
Is it possible for Boost.Rational to delegate to the mp_math::gcd (which should be faster than math::gcd)? mp_math::gcd handles mixed negative/positive numbers just fine.
double rational_cast( const boost::rational< boost::mp_math::mp_int<> >& src ) { ... }
I cannot confirm that you hit a bug here. While trying to see what is going on I discovered an unrelated bug in the to_string conversion using decimal output which happens in rare cases (it will swallow a midnumber zero when it lies on a certain boundary). Can you provide me with some starting values?
-------------------------------------------------- From: "Kevin Sopp" <baraclese@googlemail.com> Sent: Thursday, October 09, 2008 6:21 PM To: <boost@lists.boost.org> Subject: Re: [boost] [mp_int] new release
First there is no A % B operation which is const (boost::rational complained as it tries to do a mod operation on a const int_type.) I added one and got past this.
How does the function you added look like? I'm not sure I understand why you would want to do a mod operation on a constant type. a = b % c; // b and c are constant a %= b; // b is constant Both are supported.
Sorry, you are right. I confused the two issues. I had to add: mp_int operator - () const; //unary negate. The code which triggered this error was in common_factor_rt.hpp ( boost/math ) template < typename IntegerType > inline IntegerType gcd_integer ( IntegerType const & a, IntegerType const & b ) { // Avoid repeated construction IntegerType const zero = static_cast<IntegerType>( 0 ); IntegerType const result = gcd_euclidean( a, b ); return ( result < zero ) ? -result : result; //This was call was causing it.. as result is const. } I added a const version to make the error go away: // unary negate template<class A, class T> inline mp_int<A,T> mp_int<A,T>::operator - () const { mp_int copy = *this; return -copy; }
During the normalization step of boost::rational the numerator and denominator are normalized by the gcd of the two. In one case I was testing the %= operator of mp_int<> was causing an infinite loop in the boost::math::gcd call. I made an attempt at a fix (though I didn't really spend much time on it.. so I'm not sure what if any side-effects) ... The case I had fail was when normalizing (-16384)/(16384). (-1/1). So it was infinite looping on boost::math::gcd( mp_int<>( -16384 ), mp_int<>( 16384 ) );
Is it possible for Boost.Rational to delegate to the mp_math::gcd (which should be faster than math::gcd)? mp_math::gcd handles mixed negative/positive numbers just fine.
This isn't something that seems to be specializable via a policy or anything so.. not that I'm aware of. The problem is that it infinite loops on a %= operation. When I changed the %= to reflect that the value was the remainder it worked. Why is it that you add the rhs in the event that the sign of the remainder is not the same as the rhs term? In the case I have described it is stuck (infinite loop) on the %= operation with the following states for *this and rhs: - this - digits_ 0x0036c9d0 unsigned int * 1 unsigned int used_ 1 unsigned int capacity_ 3 unsigned int sign_ 1 int - rhs - digits_ 0x0036c988 unsigned int * 16384 unsigned int used_ 1 unsigned int capacity_ 2 unsigned int sign_ -1 int After the divide operation here is the remainder: - remainder - digits_ 0x0036c908 unsigned int * 0 unsigned int used_ 1 unsigned int capacity_ 2 unsigned int sign_ 1 int The sign is different from rhs, and so it adds rhs to the remainder. - remainder - digits_ 0x0036c908 unsigned int * 16384 unsigned int used_ 1 unsigned int capacity_ 2 unsigned int sign_ -1 int And the this->swap( remainder ) - this- digits_ 0x0036c908 unsigned int * 16384 unsigned int used_ 1 unsigned int capacity_ 2 unsigned int sign_ -1 int So the operation is: 1 % -16384 And the code is just swapping -> this->swap( rhs );. I.e : 1 % -16384 == -16384? // :D I don't think so!
double rational_cast( const boost::rational< boost::mp_math::mp_int<> >& src ) { ... }
I cannot confirm that you hit a bug here. While trying to see what is going on I discovered an unrelated bug in the to_string conversion using decimal output which happens in rare cases (it will swallow a midnumber zero when it lies on a certain boundary). Can you provide me with some starting values?
Let me see: The operation is: den -= maxLong; Here are the initial values: - den - digits_ 0x003023e0 unsigned int * 185745031 unsigned int used_ 10 unsigned int capacity_ 10 unsigned int sign_ 1 int - maxLong - digits_ 0x002fd470 unsigned int * 2147483647 unsigned int used_ 1 unsigned int capacity_ 2 unsigned int sign_ 1 int After one iteration: - den - digits_ 0x003023e0 unsigned int * 2333228680 unsigned int used_ 10 unsigned int capacity_ 10 unsigned int sign_ 1 int - maxLong - digits_ 0x002fd470 unsigned int * 2147483647 unsigned int used_ 1 unsigned int capacity_ 2 unsigned int sign_ 1 int 2nd iteration: - den - digits_ 0x003023e0 unsigned int * 185745033 unsigned int used_ 10 unsigned int capacity_ 10 unsigned int sign_ 1 int - maxLong - digits_ 0x002fd470 unsigned int * 2147483647 unsigned int used_ 1 unsigned int capacity_ 2 unsigned int sign_ 1 int 3rd iteration: - den - digits_ 0x003023e0 unsigned int * 2333228682 unsigned int used_ 10 unsigned int capacity_ 10 unsigned int sign_ 1 int - maxLong - digits_ 0x002fd470 unsigned int * 2147483647 unsigned int used_ 1 unsigned int capacity_ 2 unsigned int 4th iteration: - den - digits_ 0x003023e0 unsigned int * 185745035 unsigned int used_ 10 unsigned int capacity_ 10 unsigned int sign_ 1 int - maxLong - digits_ 0x002fd470 unsigned int * 2147483647 unsigned int used_ 1 unsigned int capacity_ 2 unsigned int sign_ 1 int The pattern seems to be that subtracting maxLong from den nets a +2 gain on den. den values: 185745031 185745033 185745035 185745037 ... Hope this helps, very happy to see an integer library coming down the pipe :). Cheers, Brandon P.S. Let me know if I can be of any more assistance.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Sorry, you are right. I confused the two issues. I had to add: mp_int operator - () const; //unary negate.
You are right this function needs to be added. I implemented this as free function now.
operation. When I changed the %= to reflect that the value was the remainder it worked. Why is it that you add the rhs in the event that the sign of the remainder is not the same as the rhs term?
I don't know, it's what libtommath does so I just did the same ;-) I've always wanted to change it, but somehow forgot about it. It will now give the expected result.
The pattern seems to be that subtracting maxLong from den nets a +2 gain on den. den values: 185745031 185745033 185745035 185745037
Okay I will look into it, btw there's a mp_int<>::print() function which prints the internal representation to cout.
P.S. Let me know if I can be of any more assistance.
Oh you're doing well, just keep on testing. I will upload a new version with the bugfixes to the vault soon. Thanks for your help, Kevin
Here are the initial values:
- den - digits_ 0x003023e0 unsigned int * 185745031 unsigned int used_ 10 unsigned int
Since 185745031 is smaller than maxLong it should never enter the loop to subtract it. And I can confirm by manually subtracting it that it gives the right result. However a used count of 10 is definitely wrong thus signaling that it is actually larger than maxLong. How do you create the input? den seems to be corrupted before it even enters the function.
-------------------------------------------------- From: "Kevin Sopp" <baraclese@googlemail.com> Sent: Friday, October 10, 2008 10:25 AM To: <boost@lists.boost.org> Subject: Re: [boost] [mp_int] new release
Here are the initial values:
- den - digits_ 0x003023e0 unsigned int * 185745031 unsigned int used_ 10 unsigned int
Since 185745031 is smaller than maxLong it should never enter the loop to subtract it. And I can confirm by manually subtracting it that it gives the right result. However a used count of 10 is definitely wrong thus signaling that it is actually larger than maxLong.
Ah, yes.. good point. It is pulled out of the boost::rational< mp_int<>
::denominator() call. So it will have undergone many arithmetic operations by the time I call it. I have an approximation algorithm for pi which I'm doing. Here's the code, perhaps you can replicate from it:
template <typename T, unsigned int Iterations> T calc_pi() { T intermediate_result(0); T numerator(0); T pi; for( int k = 0; k <= Iterations; ++k ) { if( k%2 ) { numerator = -1; } else { numerator = 1; } intermediate_result += numerator / ( T(2) * T(k) + T(1) ); pi = T(4) * intermediate_result; } return pi; } You'll need these: template <> class numeric_limits< boost::mp_math::mp_int<> > { private: typedef boost::mp_math::mp_int<> Type; public: static const bool is_specialized = true; static const int digits = 0; static const int digits10 = 0; static const bool is_signed = true; static const bool is_integer = true; static const bool is_exact = true; static const int radix = 2; static const int min_exponent = 0; static const int min_exponent10 = 0; static const int max_exponent = 0; static const int max_exponent10 = 0; static const bool has_infinity = false; static const bool has_quiet_NaN = false; static const bool has_signaling_NaN = false; static const float_denorm_style has_denorm = denorm_absent; static const bool has_denorm_loss = false; static const bool is_iec559 = false; static const bool is_bounded = false; static const bool is_modulo = false; static const bool traps = false; static const bool tinyness_before = false; static const float_round_style round_style = round_toward_zero; static Type min() { return static_cast<Type>(0); } static Type max() { return static_cast<Type>(0); } static Type epsilon() { return static_cast<Type>(1); } static Type round_error() { return static_cast<Type>(1); } static Type infinity() { return static_cast<Type>(0); } static Type quiet_NaN() { return static_cast<Type>(0); } static Type denorm_min() { return static_cast<Type>(1); } }; } // namespace std Call it like this: typedef boost::rational< mp_int<> > rational_int; rational_int pi = calc_pi< rational_int, 100>();
How do you create the input? den seems to be corrupted before it even enters the function. _______________________________________________ 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 Brandon Kohn Sent: 10 October 2008 16:37 To: boost@lists.boost.org Subject: Re: [boost] [mp_int] new release -------------------------------------------------- From: "Kevin Sopp" <baraclese@googlemail.com> Sent: Friday, October 10, 2008 10:25 AM To: <boost@lists.boost.org> Subject: Re: [boost] [mp_int] new release
I've tried to use your simple "general use" example in your documentation with MS Visual studio 9.0 Sadly it fails to compile with an Internal compiler error :-( 1>Compiling... 1>demo_unbounded_int.cpp 1>i:\trunk\boost\mp_math\mp_int\detail\string_conversion_constants.hpp(44) : fatal error C1001: An internal error has occurred in the compiler. 1>(compiler file 'msc1.cpp', line 1411) 1> To work around this problem, try simplifying or changing the program near the locations listed above. 1>Please choose the Technical Support command on the Visual C++ 1> Help menu, or open the Technical Support help file for more information 1> i:\trunk\boost\mp_math\mp_int\detail\string_conversion_constants.hpp(47) : see reference to class template instantiation 'boost::mp_math::detail::max_power<MpInt,Base>' being compiled This is a bit of a showstopper ;-) Or am I doing something silly? Any suggestions about what to try changing? Thanks Paul --- Paul A Bristow Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB +44 1539561830 & SMS, Mobile +44 7714 330204 & SMS pbristow@hetp.u-net.com PS
I'll also need these for sure so it would be nice if they were added to the next release:
template <> class numeric_limits< boost::mp_math::mp_int<> > { private: typedef boost::mp_math::mp_int<> Type; public: static const bool is_specialized = true; static const int digits = 0; static const int digits10 = 0; static const bool is_signed = true; static const bool is_integer = true; static const bool is_exact = true; static const int radix = 2; static const int min_exponent = 0; static const int min_exponent10 = 0; static const int max_exponent = 0; static const int max_exponent10 = 0; static const bool has_infinity = false; static const bool has_quiet_NaN = false; static const bool has_signaling_NaN = false; static const float_denorm_style has_denorm = denorm_absent; static const bool has_denorm_loss = false; static const bool is_iec559 = false; static const bool is_bounded = false; static const bool is_modulo = false; static const bool traps = false; static const bool tinyness_before = false; static const float_round_style round_style = round_toward_zero; static Type min() { return static_cast<Type>(0); } static Type max() { return static_cast<Type>(0); }
static Type epsilon() { return static_cast<Type>(1); }
static Type round_error() { return static_cast<Type>(1); }
static Type infinity() { return static_cast<Type>(0); }
static Type quiet_NaN() { return static_cast<Type>(0); }
static Type denorm_min() { return static_cast<Type>(1); } }; } // namespace std
participants (9)
-
Brandon Kohn -
Kevin Sopp -
Kim Barrett -
Maik Beckmann -
Mathias Gaunard -
Mikko Vainio -
Paul A Bristow -
Scott McMurray -
Simonson, Lucanus J