Re: [boost] [mpl-cf] [RFC] MPL Real Numbers using Continued Fractions

Subject: Re: [boost] [mpl-cf] [RFC] MPL Real Numbers using Continued Fractions
From: Hal Finkel (half_at_[hidden])
Date: 2010-11-30 14:11:38

On Tue, 2010-11-30 at 00:20 -0800, Scott McMurray wrote:
> On Mon, Nov 29, 2010 at 18:19, Dave Abrahams <dave_at_[hidden]> wrote:
> >
> > For some inexplicable reason, the very fact that there's someone on
> > this list who knows enough about math to ask that question makes me
> > really, really happy.
> >
> 
> I'm glad :)
> 
> For anyone else who wants to know just about as much as me:
> <http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/cfINTRO.html>
> :)
> 
> I did a quick experiment, and it seems for phi, you need about 20 ones
> for a float and 40 ones for a double:
> 
>     typedef float T; // or double
> 
>     cout << setprecision(numeric_limits<T>::digits10+2);
>     cout << (sqrt((T)5) + 1) / 2 << "\n\n";
> 
>     int steps = 1;
>     T value = 1;
>     while (1 + 1/(1 + 1/value) != value) {
>         ++steps;
>         value = 1 + 1/value;
>         cout << steps << ": " << value << "\n";
>     }
> 
> I don't think that's practical to specify, as such :P
> 

I had not thought of that, but yes, in the convention used by the
implementation, that probably is the bound (+-1).

> However, perhaps you could limit it to some smaller number, but allow
> the last term to be a repeating specifier of some kind.  It would be
> much more palatable to specify (ignoring that the constants would
> probably have to be int_c):

In the current implementation, I provide cf_c<...> for that purpose.

> 
>     typedef cf<1, repeat<1>> phi;
>     typedef cf<0, 2> half;
>     typedef cf<1, repeat<2>> root_2;
>     typedef cf<1, repeat<8, 2>> half_of_root_5;

In case you did not notice, I provide these constants (except
alf_of_root_5) to length 20 in boost/mpl/cf/constants.hpp

I had thought it may be useful to allow for metafunctions which act as
infinite stream generators, since then numbers like sqrt(2) could be
represented "exactly." Care would be necessary to make sure that
operations on such objects did not infinitely recurse. Also, it would be
important to keep the performance impact in mind; When I added the
integer-overflow checks into the arithmetic routines the compile times
increased by a factor of 2, and those are relatively simple checks.

> 
> This still isn't a full solution, though, since the one everyone will
> ask about can't be nicely shortened:
> 
>     typedef cf<3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 3> pi; //
> hopefully enough...
> 

There are other (more-complicated) representations in which pi has a
simple form, but the everything else becomes more complicated...
See, for example: http://en.wikipedia.org/wiki/Pi

> And it obviously makes implementing math and comparisons much harder.
> 
> BTW, how do you avoid floating point annoyances when calculating the
> runtime value?  I'd assume that cascading inversions would be a
> terrible idea.

That was also my original assumption, but I found it worked pretty well
in practice. For one thing, I've chosen a convention such that all of
the (non-zero) integers have the same sign, This means that there is no
"catastrophic cancellation," and also makes implementing the comparison
ops relatively simple (comparison is cheap compared to arithmetic).

To be fair, my original use case was the generation of ratios of pi for
use in FFT kernels, and as you've noted above, all of the integers in
the pi expansion are fairly small (and there are a lot of 1s), so maybe
it is not entirely representative, but I've yet to encounter a case
where this has caused a problem. That having been said, I've not really
tried to find such a case either. I can certainly think about this more
carefully.

 -Hal

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