🔬41. Converting Num to Rat in Perl 6

In Perl 6, you can easily coerce numerical values from one type to another. One of the interesting conversions is Num to Rat.

For example, take the value of π and convert it to a fraction:

$ perl6 -e'say pi.Rat.perl'
<355/113>

Indeed, 355/113 is 3.14159292035398, which is close to π. The default maximum error is built-in in Rakudo and is set to 10–6.

Algorithm

The implementation of the method is located in the src/core/Num.pm file. Let us read it line by line. First, the signature:

method Rat(Num:D: Real $epsilon = 1.0e-6, :$fat)

Here, you see $epsilon, a positional parameter with the default value, and a flag, :$fat, which you should set if you want to have a FatRat value. The first action is creating a variable that is either a Rat or a FatRat:

 my \RAT = $fat ?? FatRat !! Rat;

The next step is a test whether the number is a number and is not infinite:

 return RAT.new: (
     nqp::iseq_n(self, self) ?? nqp::iseq_n(self, Inf) ?? 1 !! -1 !! 0
   ), 0
 if nqp::isnanorinf(nqp::unbox_n(self));

Another quick check — return immediately if the value is already an integer:

my Num $num = self;
$num = -$num if (my int $signum = $num < 0);
my num $r = $num - floor($num);

if nqp::iseq_n($r,0e0) {
    RAT.new(nqp::fromnum_I(self,Int),1)
}

At this point, we have a first approximation: the $num variable contains an integer part. The rest is shown in the picture:

IMG_1969

Seriously speaking, the rest of the method is an implementation of the numerical approximation, which tries to find such numerator and denominator so that the fraction is close enough to the value in question.

First, some values are initialised and prepared:

 my Int $q = nqp::fromnum_I($num, Int);
 my Int $a = 1;
 my Int $b = $q;
 my Int $c = 0;
 my Int $d = 1;

Now, $q and $b (which is the numerator) are the most rough integer approximation, and $d (denominator) is set to 1.

The rest is a loop, which stops when an accurate enough fraction is found:

while nqp::isne_n($r,0e0) && abs($num - ($b / $d)) > $epsilon {
    my num $modf_arg = 1e0 / $r;
    $q = nqp::fromnum_I($modf_arg, Int);
    $r = $modf_arg - floor($modf_arg);

    my $orig_b = $b;
    $b = $q * $b + $a;
    $a = $orig_b;

    my $orig_d = $d;
    $d = $q * $d + $c;
    $c = $orig_d;
}

And finally, a Rat value is built:

RAT.new($signum ?? -$b !! $b, $d)

Approximation

When using the Num::Rat method, as we saw, you can set the precision you need. For example:

$ ./perl6 -e'say pi.Rat(1)'
3

$ ./perl6 -e'say pi.Rat(0.1)'
3.142857

I also added some debug output to see the steps that the algorithm comes through. Surprisingly, it converges very quickly.

$ ./perl6 -e'say pi.Rat.nude'
3/1 = 3
22/7 = 3.142857
333/106 = 3.141509
(355 113)
$ ./perl6 -e'say pi.Rat(1e-10).nude'
3/1 = 3
22/7 = 3.142857
333/106 = 3.141509
355/113 = 3.141593
103993/33102 = 3.141593
104348/33215 = 3.141593
208341/66317 = 3.141593
(312689 99532)
$ ./perl6 -e'say e.Rat.nude'
2/1 = 2
3/1 = 3
8/3 = 2.666667
11/4 = 2.75
19/7 = 2.714286
87/32 = 2.71875
106/39 = 2.717949
193/71 = 2.718310
1264/465 = 2.718280
1457/536 = 2.718284
(2721 1001)

 

2 thoughts on “🔬41. Converting Num to Rat in Perl 6

  1. I always figured we should really do an “exact” value when converting a Num to a FatRat, but never was ambitious enough to figure out how to portably get the information out of a floating point value.

    Like

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s