On Tue, 2010-11-30 at 00:20 -0800, Scott McMurray wrote:
On Mon, Nov 29, 2010 at 18:19, Dave Abrahams <dave@boostpro.com> 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