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:59:03

On Tue, 2010-11-30 at 16:11 +0100, Karsten Ahnert wrote:
> > Actually, ignore that statement. You only need two integers for a0 +
> > 1/a1, in general you need more. For example, if you look at the test
> > program (basic.cpp in the archive), it provides some examples (where the
> > floating-point output is float, double, long double):
> > 
> > 3/2 + 1/4 = [ 1 1 3]
> > 1.75
> > 1.75
> > 1.75
> > 
> > 1/7 + 1/15 = [ 0 4 1 3 2 2]
> > 0.209524
> > 0.20952380952381
> > 0.209523809523809524
> > 
> > There are other continued fraction representations where any rational
> > can be represented with a fixed number of integers (a0 + b0/(a1 + ...)),
> > but the algorithms are a little more complicated, and I fear the compile
> > times would increase.
> 
> I was looking for something very similar to that, altough I believe
> compile times are to long for realistic problems. Especially the example
> with sine and cosine took approximately 10 minutes on my PC. But who
> knows? Maybe compilers are fast enough in some years...
> 

What compiler were you using (just curious)? I think it takes g++ about
that long on my netbook too. The trig functions are slow, probably too
slow for (most) practical application, but having real numbers
themselves might be useful. Maybe someone with more experience could
speed up the entire implementation ;)

> I have also two little questions:
> 1. Can one express for example 1.25e-10 in an easy manner, for example
> by simply specifying the exponent?

1.25e-10 = [0, 8000000000], but you'd have to do the calculation
beforehand and write:
cf_c<0, 8000000000ll>
or, for some extra compile time, write:
boost::mpl::times< cf_c<1, 4> /* 1 + 1/4 */ , cf_c<0, 10000000000ll> /*
0 + 1/10^10 */ >::type

> 2. Can one use different representations of rational number, maybe
> boost::ratio? I guess this could be difficult to work with the
> elementary operations.

Not currently, but it is the same as writing boost::mpl::divides<
cf_c<a>, cf_c<b> >::type, so it would be simple to add. I know that
boost units has mpl rationals internally, so interfacing with them
should also be possible.

Or do you mean converting directly to rationals? That might work now
(I've not tried it), but the value() function is templated on the return
type.

The advantage of working with continued fractions instead of rationals
is that the individual integer elements of the continued fractions tend
to stay small, even when the rational numerator and denominator get
large (and would overflow your integer type).

 -Hal

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