Continued Fractions

Four months ago I created Math::ContinuedFractions on Github. But I didn’t actually post any code to it. But I’ve finally started, pushing t/00-experiments.t. It’s very simple so far, but that’s because I’m slowly feeling my way through this unfamiliar subject.

I tried to link the Wikipedia equation graphic for a continued fraction, but that just lost me the first draft of this post, so instead I’ll link to the Wikipedia page. It is the source of our first algorithm, for converting a number to a continued fraction:

sub make-continued-fraction (Real $x is copy) {
    gather loop {
        my $a = $x.floor;
        take $a;
        $x = $x - $a;
        last if $x == 0;
        $x = 1 / $x;
    }
}

This returns the components of the continued fraction as a lazy list. It passes the first few simple tests I’ve thrown at it, but I’m a bit worried about $x = 1 / $x. Should this maybe be FatRat math instead of normal math? I’m not clear on the implications one way or the other.

Unfortunately, the Wikipedia page doesn’t shed any light on how to do basic arithmetic on continued fractions. HAKMEM gives a complete overview on basic continued fraction arithmetic, but I find it quite hard going. MJD has a nifty talk on the subject, including some algorithms I hope to implement soon. Unfortunately, he doesn’t get into the tricky stuff.

Luther Tychonievich has a nice blog post on the subject which brings up a problem I have not seen mentioned elsewhere. Some pretty basic operations may not work because they need every (infinite) input term to determine the first output term. His example is squaring the square root of 2. As I understand it, the problem is that the first term (the integer part) flits back and forth between 1 and 2 as each addition term is fed to the code. It can never settle down on one or the other.

Incidentally, my code fails miserably in Rakudo, but works in Niecza. Unfortunately for this project, Niecza cannot currently handle overloading the arithmetic operators for a new type, which means I’ll have to figure out how to get things working on Rakudo at some point.

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: