Detour from Sin

I spent the first two days of YAPC furiously working on overhauling the trig tests every chance I got. On Wednesday, however, I suddenly changed my focus, and I’ve been working on something else ever since. What happened?

Simple: my improved trig tests ran up hard against a major Rakudo limitation. So I’ve been working on fixing it so I can get back to working on those tests. The issue was this: on a 32-bit system, you could only enter about nine digits in your Num constants. The tenth digit would make the action for handling a Rat or Num blow up, and either give an error or incorrect results.

This is something of a problem when you are automatically generating code, because writing a Num usually gets you 15 digits.

So, I set out to fix Rakudo’s Rat / Num constant handling. First I hand wrote a parser, which I ended up not using. Then I coded up a a beautiful functional approach to handling converting the string components to a number. Something like this (for Rat):

$result = [+] $int-part.comb(/\d/).reverse.kv.map(-> $i, $d { $d.Int * 10 ** $i });
$result += [+] $frac-part.comb(/\d/).kv.map(-> $i, $d { $d.Int / 10 ** ($i + 1) }); 

(Note: reconstructed from memory, may not actually work as given.) This worked great, and had the happy property of properly returning a Rat if possible, and promoting to a Num if needed for additional precision. (Basically, because all the basic components of the math are simple ints, and the math operations correctly promote as needed.)

There was only one problem with this approach: it took eight times as long to do its job as the original. I tried rewriting it in a more iterative fashion. Then it only took seven times as long. Still not acceptable.

I toyed around with other ideas for reworking the solution, but finally, at about the fourth hour of my drive home from YAPC, I hit on the problem with this approach. Every one of those simple math operations was necessarily a multi call. Three of those were required for each digit. No wonder it was slow!

That in mind, I decided on a new approach. The basic problem with the original Rakudo approach was that it treated the various components of the numeric constant as Ints, which can easily (and sometimes ungracefully) overflow. But there is a standard Rakudo trick for handling overflow in Ints gracefully: do the math internally as a Num, and then cast the result to Int only if possible. This can be done entirely in PIR for speed -- no worrying about multis for the math, it's all done explicitly in num.

Then the resulting bits are combined in Perl 6, so that multi dispatch on the math operations gets you the correct type results. It took a bit of doing, but I just pushed the resulting code to github.

Now, this solution isn't perfect. I'm pretty sure it's possible to construct extreme cases where the step-by-step algorithm would have returned a Rat, but the new one returns a Num. And if you actually have 64-bit Ints available, you might lose a few digits of precision, because Num have less -- but this is a problem throughout Rakudo, not just here.

But in general, this solution should be acceptably fast and come much closer to doing the right thing than the previous version did.

About these ads

Tags:

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: