|
|
Boost : |
Subject: Re: [boost] [mp_int] new release
From: Brandon Kohn (blkohn_at_[hidden])
Date: 2008-10-09 20:32:23
--------------------------------------------------
From: "Kevin Sopp" <baraclese_at_[hidden]>
Sent: Thursday, October 09, 2008 6:21 PM
To: <boost_at_[hidden]>
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
>
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk