[MPL.Math] updates for double
I've now added a BOOST_MPL_CFC_NO_MATH_DOUBLE macro that is defined in <boost/mpl/aux_/config/math_double.hpp> when it is known that BOOST_MPL_MATH_DOUBLE won't compile. Please send me your compiler-platform configuration if BOOST_MPL_MATH_DOUBLE doesn't work for you. Peder, The double_::aux::get_value function still returns a number 2^16 times too big on MSVC 7.1 when the input is a whole number. Cromwell D. Enage __________________________________ Yahoo! Mail - PC Magazine Editors' Choice 2005 http://mail.yahoo.com
On 10/31/05, Cromwell Enage <sponage@yahoo.com> wrote:
I've now added a BOOST_MPL_CFC_NO_MATH_DOUBLE macro that is defined in <boost/mpl/aux_/config/math_double.hpp> when it is known that BOOST_MPL_MATH_DOUBLE won't compile. Please send me your compiler-platform configuration if BOOST_MPL_MATH_DOUBLE doesn't work for you.
Peder, The double_::aux::get_value function still returns a number 2^16 times too big on MSVC 7.1 when the input is a whole number.
I do not observe this on my VC7.1 compiler. What I see, is another effect: Using setprecision(40) causes some overflow in the iostream formatting of double, so that 800.0 is outputted as 8000000. This error is only present for whole numbers. Reducing setprecision to 36 eliminates the problem, and for every extra digit of precision you specify, you get another 0 appended. Also, BOOST_MPL_MATH_DOUBLE is very unstable on VC7.1, For whole numbers between 10 and 100 it ICE's (Not so for negative whole numbers between -100 and -10) Adding a . at the end of the number, prevents the ICE. typedef BOOST_MPL_MATH_DOUBLE(56) type; <-ICE typedef BOOST_MPL_MATH_DOUBLE(56.) type; <-OK I also found a continued fraction representation for tangent that converges much faster (and better) than any of the series representation I have found: http://functions.wolfram.com/ElementaryFunctions/Tan/10/ Here is an implementation of this series. It is much faster on the tangent.cpp test file, and doesn't give warnings for double_.... Works in the range -pi/2,pi/2 (Remove the double/tangent.hpp overload first :) template <typename NumericTag> struct tangent_impl { /* * Continued fraction representation (http://functions.wolfram.com/ElementaryFunctions/Tan/10) */ template < typename AngleSquare , typename I , typename FractionCount > struct fraction { private: typedef typename eval_if< less<plus<int_<1>,I>,FractionCount> , fraction<AngleSquare,plus<int_<1>,I>,FractionCount> , mpl::int_<1> >::type next_term; public: typedef typename minus< plus< times<int_<2>,I>,int_<1> > , divides<AngleSquare,next_term> >::type type; }; template < typename Angle , typename SeriesCount > struct apply #if !defined BOOST_MPL_CFG_NO_NESTED_FORWARDING : divides<Angle,typename fraction<times<Angle,Angle>,int_<0>,SeriesCount>::type> { #else { /* * Metafunction class return type. */ typedef typename divides< Angle , typename series<times<Angle,Angle>,int_<0>,SeriesCount>::type >::type type; #endif /* BOOST_MPL_CFG_NO_NESTED_FORWARDING */ }; }; Regards, Peder.
Cromwell D. Enage
__________________________________ Yahoo! Mail - PC Magazine Editors' Choice 2005 http://mail.yahoo.com _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
By the way: We don't need the specialization of sine and exponential for double anymore. Since the rounding scheme has been changed, the default implementation will give a good enough approximation of the result. I have added a new mpl_math_fix.zip to the vault, with a new implementation of tangent, plus an implementation of natural logarithm, logarithm.hpp (both using continued fraction representations) Regards, Peder
--- Peder Holt wrote:
By the way: We don't need the specialization of sine and exponential for double anymore. Since the rounding scheme has been changed, the default implementation will give a good enough approximation of the result.
I have added a new mpl_math_fix.zip to the vault, with a new implementation of tangent, plus an implementation of natural logarithm, logarithm.hpp (both using continued fraction representations)
Excellent! I've now added a power function to the mix, implemented in terms of exponential and logarithm. A more efficient implementation that uses fractions or other series functions may come later. Cromwell D. Enage __________________________________ Start your day with Yahoo! - Make it your home page! http://www.yahoo.com/r/hs
Excellent!
I've now added a power function to the mix, implemented in terms of exponential and logarithm. A more efficient implementation that uses fractions or other series functions may come later.
Cromwell D. Enage
Great! I tried implementing a power using fractions, but it turned out that for larger exponents its convergence rate was very poor. (I needed ~100 recursions for something like 10^20) What we should do, is add a specialization for power with integral exponent. This is a very fast algorithm (also in respect to compile-time efficiency) What we could do, is to split power(z,a) into two: power(z,floor(a))*power(z,a-floor(a)); Regards, Peder
__________________________________ Start your day with Yahoo! - Make it your home page! http://www.yahoo.com/r/hs _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
--- Peder Holt wrote:
I tried implementing a power using fractions, but it turned out that for larger exponents its convergence rate was very poor. (I needed ~100 recursions for something like 10^20).
Yeah, that stinks.
What we should do, is add a specialization for power with integral exponent. This is a very fast algorithm (also in respect to compile-time efficiency).
The current implementation calls integral_power if it detects that exponent::tag is the same as integral_c_tag, unsigned_big_integral_tag, or big_integral_tag.
What we could do, is to split power(z,a) into two: power(z,floor(a))*power(z,a-floor(a));
Ah, a specialization for fractional exponents. We could use integral_part for the floor function, but if a itself is very large (>= 2^30), then minus<a,integral_part<a> > will yield a mixed_number, not a double. fractional_part<a> returns a rational regardless of magnitude. What I'll do is: 1) Create an internal metafunction in the double_::aux namespace that does what fractional_part does now. 2) Change fractional_part so that it returns a double. 3) Implement numerator and denominator specializations that use the metafunction in 1). Then, with fractional_power as a template nested within power_impl, we can return: times< integral_power<z,integral_part<a> > , fractional_power<z, fractional_part<a> > > Cromwell D. Enage __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com
On 11/3/05, Cromwell Enage <sponage@yahoo.com> wrote:
--- Peder Holt wrote:
I tried implementing a power using fractions, but it turned out that for larger exponents its convergence rate was very poor. (I needed ~100 recursions for something like 10^20).
Yeah, that stinks.
What we should do, is add a specialization for power with integral exponent. This is a very fast algorithm (also in respect to compile-time efficiency).
The current implementation calls integral_power if it detects that exponent::tag is the same as integral_c_tag, unsigned_big_integral_tag, or big_integral_tag.
Great! Most of the job is done already, then.
What we could do, is to split power(z,a) into two: power(z,floor(a))*power(z,a-floor(a));
Ah, a specialization for fractional exponents. We could use integral_part for the floor function, but if a itself is very large (>= 2^30), then minus<a,integral_part<a> > will yield a mixed_number, not a double. fractional_part<a> returns a rational regardless of magnitude.
What I'll do is: 1) Create an internal metafunction in the double_::aux namespace that does what fractional_part does now. 2) Change fractional_part so that it returns a double. 3) Implement numerator and denominator specializations that use the metafunction in 1).
Then, with fractional_power as a template nested within power_impl, we can return:
times< integral_power<z,integral_part<a> > , fractional_power<z, fractional_part<a> > >
Hmm. Looking closer at the issue, it seems that the continued fraction approximation of power is poor no matter what :( Evaluating the expression pow(20.5,0.98) A continuing fractions implementation needs 73recursions to get the same accuracy as the runtime equivalent for double. The series: z^a == Sum[(Log[z]^k/k!) a^k, {k, 0, Infinity}] requires 27 recursions, but the code is very simple: template <typename Tag1,typename Tag2> struct power_impl { template<typename LogZ,typename A,typename I,typename SeriesCount> struct series { private: typedef typename eval_if< less<typename I,SeriesCount> , series<LogZ,A,typename I::next,SeriesCount> , mpl::int_<1> >::type next_term; public: typedef typename plus<1,times<divides<LogZ,I>,a,next_term>::type type; }; }; Regards, Peder
Cromwell D. Enage
__________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
--- Cromwell Enage wrote:
What I'll do is: 1) Create an internal metafunction in the double_::aux namespace that does what fractional_part does now. 2) Change fractional_part so that it returns a double. 3) Implement numerator and denominator specializations that use the metafunction in 1).
Then, with fractional_power as a template nested within power_impl, we can return:
times< integral_power<z,integral_part<a> > , fractional_power<z, fractional_part<a> > >
Done. --- Peder Holt wrote:
The series: z^a == Sum[(Log[z]^k/k!) a^k, {k, 0, Infinity}] requires 27 recursions, but the code is very simple:
The series looks exactly like e^(a log z), which is what we have right now. I tried to make BOOST_MPL_MATH_DOUBLE work for GCC in strict mode over the weekend. In particular, I tried to take advantage of the feature that allows double to be implicitly cast to long long in an integral constant expression. (For those of you who are just joining us, GCC is currently treating int(...) and static_cast<...>(...) as runtime functions. Not even BOOST_MPL_AUX_STATIC_CAST is working for me.) However, GCC 3.4 and above no longer support double& as a non-type template parameter, and integral_c<long long, double_value> also fails. So, I'm at a loss here. If any GCC experts out there notice anything that I've missed--other than relaxed mode--please let me know. The syntax for BOOST_MPL_MATH_DOUBLE is much more elegant than string_c_to_double, and we'd like for everyone to be able to use it. Cromwell D. Enage __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com
On 11/7/05, Cromwell Enage <sponage@yahoo.com> wrote:
--- Cromwell Enage wrote:
What I'll do is: 1) Create an internal metafunction in the double_::aux namespace that does what fractional_part does now. 2) Change fractional_part so that it returns a double. 3) Implement numerator and denominator specializations that use the metafunction in 1).
Then, with fractional_power as a template nested within power_impl, we can return:
times< integral_power<z,integral_part<a> > , fractional_power<z, fractional_part<a> > >
Done.
--- Peder Holt wrote:
The series: z^a == Sum[(Log[z]^k/k!) a^k, {k, 0, Infinity}] requires 27 recursions, but the code is very simple:
The series looks exactly like e^(a log z), which is what we have right now.
Ok :) I have implemented the compile-time inverse_sine and inverse_tangent (the latter only for x<=1) but have a bit of a problem with arcus_cosine, which is defined as pi/2-inverse_sine. Also, inverse_tangent for x>=1 is defined as pi/2+something. So far, all implementations of math metafunctions should work with both double_ and your mixed_number etc. types, but once we introduce a constant, the result type is given, unless there is some clever way of defining the constant several times for all the different input types. Also, I have managed to squeeze more performance out of the compiler by replacing integral operations in the metafunctions with BOOST_STATIC_CONSTANT. e.g. template <typename NumericTag> struct logarithm_impl { /* * Continued fraction representation (http://functions.wolfram.com/ElementaryFunctions/Tan/10) */ template < typename Arg , typename I , typename FractionCount > struct fraction { private: typedef typename eval_if< less<I,FractionCount> , fraction<Arg,typename I::next,FractionCount> , I >::type next_term; BOOST_STATIC_CONSTANT(int,coefficient=(((I::value)+1)/2)*(((I::value)+1)/2)); public: typedef typename plus< I, divides< times< int_<coefficient>, Arg >, next_term > >::type type; }; template < typename Arg , typename SeriesCount > struct apply #if !defined BOOST_MPL_CFG_NO_NESTED_FORWARDING : divides<Arg,typename fraction<Arg,int_<1>,SeriesCount>::type> { #else { /* * Metafunction class return type. */ typedef typename divides< Arg , typename fraction<Arg,int_<1>,SeriesCount>::type >::type type; #endif /* BOOST_MPL_CFG_NO_NESTED_FORWARDING */ }; }; I think it should be possible to only use 4 arithmetic meta-operation per term, typically (a+b*x*next)/c where a,b and c are calculated using BOOST_STATIC_CONSTANT Regards, Peder
--- Peder Holt wrote:
I have implemented the compile-time inverse_sine and inverse_tangent (the latter only for x<=1)
Are those arcsine and arctangent metafunctions? There's an existing implementation of arctangent that should work for all real numbers.
but have a bit of a problem with arcus_cosine, which is defined as pi/2-inverse_sine.
A problem, indeed.
So far, all implementations of math metafunctions should work with both double_ and your mixed_number etc. types, but once we introduce a constant, the result type is given, unless there is some clever way of defining the constant several times for all the different input types.
Looks like we'll need a pi<> metafunction that takes in a numeric tag such as double_tag and an integral constant defining a series limit. Since your double has a fixed precision, pi<double_tag> can return a simple typedef and ignore the series limit, while the primary definition of pi<> has to return the result of the series. We're not making a "constants library" in the usual sense, so maybe we can get away with it. If all interested parties agree with this plan, the next question is, where should we put pi<>? So far, I have two candidates: * boost::mpl::math, since zero<> also resides there * boost::mpl::math::constants
Also, I have managed to squeeze more performance out of the compiler by replacing integral operations in the metafunctions with BOOST_STATIC_CONSTANT.
Yeah, I've discovered this with big_integral, too. Only backward-compatibility concerns have held me back from employing this technique elsewhere. (I don't have a Class B compiler on-hand though, so I don't know if my fears are unjustified.) [snip code]
I think it should be possible to only use 4 arithmetic meta-operation per term, typically (a+b*x*next)/c where a,b and c are calculated using BOOST_STATIC_CONSTANT
I'll #ifdef 0 out the code to be replaced. Cromwell D. Enage __________________________________ Yahoo! Mail - PC Magazine Editors' Choice 2005 http://mail.yahoo.com
On 11/9/05, Cromwell Enage <sponage@yahoo.com> wrote:
--- Peder Holt wrote:
I have implemented the compile-time inverse_sine and inverse_tangent (the latter only for x<=1)
Are those arcsine and arctangent metafunctions? There's an existing implementation of arctangent that should work for all real numbers.
I didn't notice. I'll check it out an look at its convergence rate.
but have a bit of a problem with arcus_cosine, which is defined as pi/2-inverse_sine.
A problem, indeed.
So far, all implementations of math metafunctions should work with both double_ and your mixed_number etc. types, but once we introduce a constant, the result type is given, unless there is some clever way of defining the constant several times for all the different input types.
Looks like we'll need a pi<> metafunction that takes in a numeric tag such as double_tag and an integral constant defining a series limit. Since your double has a fixed precision, pi<double_tag> can return a simple typedef and ignore the series limit, while the primary definition of pi<> has to return the result of the series. We're not making a "constants library" in the usual sense, so maybe we can get away with it.
If all interested parties agree with this plan, the next question is, where should we put pi<>? So far, I have two candidates:
* boost::mpl::math, since zero<> also resides there * boost::mpl::math::constants
boost::mpl::math, then probably.
Also, I have managed to squeeze more performance out of the compiler by replacing integral operations in the metafunctions with BOOST_STATIC_CONSTANT.
Yeah, I've discovered this with big_integral, too. Only backward-compatibility concerns have held me back from employing this technique elsewhere. (I don't have a Class B compiler on-hand though, so I don't know if my fears are unjustified.)
Don't think this is an issue. MSVC6.5 at least prefers BOOST_STATIC_CONSTANT, as they are much easier to handle than excessive template instantiations.
[snip code]
I think it should be possible to only use 4 arithmetic meta-operation per term, typically (a+b*x*next)/c where a,b and c are calculated using BOOST_STATIC_CONSTANT
I'll #ifdef 0 out the code to be replaced.
Ok. Regards Peder
Cromwell D. Enage
__________________________________ Yahoo! Mail - PC Magazine Editors' Choice 2005 http://mail.yahoo.com _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
--- Peder Holt wrote:
--- Cromwell Enage wrote:
There's an existing implementation of arctangent that should work for all real numbers.
Correction: it also only converges for |x| <= 1.
I didn't notice. I'll check it out an look at its convergence rate.
It's the Maclaurin series, and it's rather slow.
If all interested parties agree with this plan, the next question is, where should we put pi<>? So far, I have two candidates:
* boost::mpl::math, since zero<> also resides there * boost::mpl::math::constants
boost::mpl::math, then probably.
I'll take a shot at it for the next update.
Only backward-compatibility concerns have held me back from employing this technique elsewhere. (I don't have a Class B compiler on-hand though, so I don't know if my fears are unjustified.)
Don't think this is an issue. MSVC6.5 at least prefers BOOST_STATIC_CONSTANT, as they are much easier to handle than excessive template instantiations.
Noted.
I'll #ifdef 0 out the code to be replaced.
Ok.
And what did I do instead? I reimplemeted a majority of the advanced metafunctions by using Boost.Preprocessor to unroll the recursion. (You must now #define the corresponding limit macro for each metafunction, and you have a hard limit of 255 depending on the metafunction, but it beats exceeding the template instantiation depth.) Best of all, euler.cpp compiles and works just fine. Cromwell D. Enage __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com
On 11/9/05, Cromwell Enage <sponage@yahoo.com> wrote:
--- Peder Holt wrote:
--- Cromwell Enage wrote:
There's an existing implementation of arctangent that should work for all real numbers.
Correction: it also only converges for |x| <= 1.
I didn't notice. I'll check it out an look at its convergence rate.
It's the Maclaurin series, and it's rather slow.
I have a series available that converges for X>1. I'll implement it once the pi<> template is ready. <snip>
And what did I do instead? I reimplemeted a majority of the advanced metafunctions by using Boost.Preprocessor to unroll the recursion. (You must now #define the corresponding limit macro for each metafunction, and you have a hard limit of 255 depending on the metafunction, but it beats exceeding the template instantiation depth.) Best of all, euler.cpp compiles and works just fine.
Great job! I did the same for tangent, and compile times for tangent.cpp dropped from 18 to 12 seconds. Btw. How about making the syntax a bit clearer by dropping the BOOST_PP_MUL etc. syntaxt? Why not just: typedef typename minus< \ int_<1> \ , times< \ divides< \ angle_squared \ , int_< \ (\ (BOOST_MPL_LIMIT_MATH_SINE_SERIES-x)*2+1\ )*\ (\ (BOOST_MPL_LIMIT_MATH_SINE_SERIES-x)*2\ )\ >\ > \ , BOOST_PP_CAT(prefix, x) \ > \ >::type \ I think this is more readable, and less limited (BOOST_PP_MUL(129,2) exceeds 256, not that it matters much, as we should never have this long series :) Have uploaded a version of tangent that uses the preprocessor, plus a version of arcus_sine and an alternative arcus_tangent that does not :) to the vault. Regards, Peder
Cromwell D. Enage
__________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
--- Peder Holt wrote:
I have a series available that converges for X>1. I'll implement it once the pi<> template is ready.
I just learned that when a compiler sees a plain struct or a full specialization inherit from an MPL expression, it eagerly evaluates the expression, whehter or not the program actually asks for the struct/specialization. This is fine for pi<double_tag>, but bad news for pi<rational_tag> and pi<mixed_number_tag>, because I don't yet have a generic way of representing 1/5 and 1/239 -- Hmmm. Maybe I should implement an inverse metafunction. Yeah, that'll solve this particular problem.
Btw. How about making the syntax a bit clearer by dropping the BOOST_PP_MUL etc. syntax? Why not just:
typedef typename minus< \ int_<1> \ , times< \ divides< \ angle_squared \ , int_< \ (\
(BOOST_MPL_LIMIT_MATH_SINE_SERIES-x)*2+1\ )*\ (\
(BOOST_MPL_LIMIT_MATH_SINE_SERIES-x)*2\ )\ >\ > \ , BOOST_PP_CAT(prefix, x) \ > \ >::type \
I think this is more readable, and less limited (BOOST_PP_MUL(129,2) exceeds 256, not that it matters much, as we should never have this long series :)
Will do.
Have uploaded a version of tangent that uses the preprocessor, plus a version of arcus_sine and an alternative arcus_tangent that does not :) to the vault.
Okay, I'll check them out. Cromwell D. Enage __________________________________ Yahoo! Mail - PC Magazine Editors' Choice 2005 http://mail.yahoo.com
The metafunctions pi & e are ready. Not sure what to call them collectively in the upcoming documentation, though. "Constant Metafunction" sounds like an oxymoron. Maybe "Numeric Tag Metafunction" would be a better description. --- Cromwell Enage wrote:
Maybe I should implement an inverse metafunction. Yeah, that'll solve this particular problem.
Done. See example/euler.cpp for usage. --- Peder Holt wrote:
Btw. How about making the syntax a bit clearer by dropping the BOOST_PP_MUL etc. syntax?
Done.
Have uploaded a version of tangent that uses the preprocessor, plus a version of arcus_sine and an alternative arcus_tangent that does not :) to the vault.
I've modified arcus_sine so that it now uses Boost.Preprocessor. Cromwell D. Enage __________________________________ Yahoo! FareChase: Search multiple travel sites in one click. http://farechase.yahoo.com
On 11/11/05, Cromwell Enage <sponage@yahoo.com> wrote:
The metafunctions pi & e are ready. Not sure what to call them collectively in the upcoming documentation, though. "Constant Metafunction" sounds like an oxymoron. Maybe "Numeric Tag Metafunction" would be a better description.
Great! I'll start working on some more metafunctions, then. I would prefer it if we dropped the BOOST_MPL_MATH_DOUBLE in the definition of the pi-constant for double. This because BOOST_MPL_MATH_DOUBLE gives less presicion than string_c_to_double. Numeric tag metafunction does not ring well in my ears. I'll give it some thought. Regards Peder
--- Peder Holt wrote:
I would prefer it if we dropped the BOOST_MPL_MATH_DOUBLE in the definition of the pi-constant for double. This because BOOST_MPL_MATH_DOUBLE gives less presicion than string_c_to_double.
Done.
Numeric tag metafunction does not ring well in my ears. I'll give it some thought.
Perhaps "Tagged Constant" sounds better. (API-breaking change: boost::mpl::math::zero now models this concept; it accepts a numeric tag as its parameter, no longer a numeric constant.) Cromwell D. Enage __________________________________ Yahoo! Mail - PC Magazine Editors' Choice 2005 http://mail.yahoo.com
participants (3)
-
Cromwell Enage -
David Abrahams -
Peder Holt