fatrat vs rat in raku

昨天,Solomon Foster 在 Facebook 的 Raku 小组上发布了一个例子:

my @x = 
    FatRat.new(1, 1), 
    -> $x { $x - ($x ** 2 - $N) / (2 * $x) } ... *

这段代码实现了牛顿找到 $N 平方根近似值的方法。重要的是它使用 FatRat 值来获得更高的准确性。

让我们运行 9 的平方根:

my $N = 9;

my @x = 
    Rat.new(1, 1), 
    -> $x { $x - ($x ** 2 - $N) / (2 * $x) } ... *;

.say for @x[0..7];

很快,它收敛到正确的值:

1
5
3.4
3.023529
3.000092
3.00000000140
3.00000000000000000033
3.0000000000000000000000000000000000000176

如果将数据类型缩小到 Rat,则在某个点之后,它不会足够宽以保留所有小数位:

1
5
3.4
3.023529
3.000092
3.00000000140
3.00000000000000000033
3

当然,绝对正确的结果会更快实现,但我们知道这是由于缺乏 Rat 与 FatRat 相比的容量,并且它可能不适用于非整数结果。让我们用 $N = 5 来迭代十次:

使用 Rat:

1
3
2.333333
2.238095
2.236069
2.23606798
2.236067977499790
2.23606797749979
2.23606797749979
2.23606797749979
2.23606797749979

使用 FatRat:

1
3
2.333333
2.238095
2.236069
2.23606798
2.236067977499790
2.2360679774997896964091736687
2.2360679774997896964091736687312762354406183596115257243
2.236067977499789696409173668731276235440618359611525724270897245410520925637804899414414408378782274969508176
2.23606797749978969640917366873127623544061835961152572427089724541052092563780489941441440837878227496950817615077378350425326772444707386358636012153345270886677817319187916581127664532263985658053576135041753378500

(我希望你的浏览器只是滚动代码块而不是将文本包装到新行中。)

好的,我们看到 FatRat 提供了更多数字。现在看一下 src/core/Rat.pm 中类的定义:

# XXX: should be Rational[Int, uint]
my class Rat is Cool does Rational[Int, Int] { . . . }

my class FatRat is Cool does Rational[Int, Int] { . . . }

这两个类都实现了一个参数化的 Rational 角色。在这两种情况下,参数都是相同的 - 分子和分母都应该是 Int 值。那么,如果我们使用相同的数据类型来表示分数,为什么牛顿逼近的结果是如此不同呢?让我们试着解决这个问题。

为了看看这个部分的部分是如何在角色中构建的,这里是他们的声明:

my role Rational[::NuT = Int, ::DeT = ::("NuT")] does Real {
    has NuT $.numerator = 0;
    has DeT $.denominator = 1;

所以,在这两种情况下,我们都有以下属性:

has Int $.numerator = 0;
has Int $.denominator = 1;

让我们来检查这些类型是否在黑盒子里面没有改变:

my $N = 5;
my @x = FatRat.new(1, 1), -> $x { $x - ($x ** 2 - $N) / (2 * $x) } ... *;

my $v = @x[7];
say $v.numerator.WHAT;
say $v.denominator.WHAT;

使用 FatRat 类型,程序确认 Ints:

$ raku sqr-fatrat.pl 
(Int)
(Int)

现在尝试 Rat 类型:

$ raku sqr-fatrat.pl 
No such method 'numerator' for invocant of type 'Num'.
Did you mean 'iterator'?
  in block <unit> at sqr-fatrat.pl line 10

什么?!你什么意思?这是否意味着值不再是 Rats 了?让我们来检查它并打印数据元素的类型。我们知道我们用Rat 值开始序列:

Rat.new(1, 1), -> $x { $x - ($x ** 2 - $N) / (2 * $x) } ... *;

尖端的块是下一个元素的生成器,所以这里没什么不好的。尽管如此,让我们在每个元素上调用.WHAT:

.WHAT.say for @x[0..10];

下面是它的输出:

(Rat)
(Rat)
(Rat)
(Rat)
(Rat)
(Rat)
(Rat)
(Num)
(Num)
(Num)
(Num)

前七项是 Rats,其余的则是 Nums!这就解释了为什么我们看到了不同的结果,当然。但为什么数据类型改变了?

慢慢尝试。首先,请在生成后立即查看值的类型:

my $N = 5;
my @x = 
    Rat.new(1, 1), 
    -> $x {
        my $n = $x - ($x ** 2 - $N) / (2 * $x);
        say $n.WHAT;
        $n;
    } ... *;

它会像以前一样打印相同的类型列表。

第二步是尝试在任何我们可以的地方强制使用数据类型:

my Rat $N = Rat.new(5);
my Rat @x = 
    Rat.new(1, 1), 
    -> Rat $x {
        my Rat $n = $x - ($x ** 2 - $N) / (2 * $x);
        say $n.WHAT;
        $n;
 } ... *;

运行该程序,看看它说什么:

(Rat)
(Rat)
(Rat)
(Rat)
(Rat)
(Rat)
Type check failed in assignment to $n;
expected Rat but got Num (2.23606797749979e0)
   in block <unit> at sqr-fatrat.pl line 5

这变得更加糟糕, 如果你强制FatRat,那么一切都保持良好。好的,现在是时候了解何时越过边界并更改了数据类型。

让我们更多地观察它,以便我们看到生成的数字的分子和分母,以及用于计算它的中间值的类型:

-> Rat $x {
    my $d = ($x ** 2 - $N);
    say $d;
    say $d.WHAT;

    my Rat $n = $x - $d / (2 * $x);
    say $n.WHAT;
    say $n.nude;
    $n;
} ... *;

这给了我们确认它突破的方法:

-4
(Rat)
(Rat)
(3 1)
4
(Rat)
(Rat)
(7 3)
0.444444
(Rat)
(Rat)
(47 21)
0.009070
(Rat)
(Rat)
(2207 987)
0.0000041
(Rat)
(Rat)
(4870847 2178309)
0.00000000000084
(Rat)
(Rat)
(23725150497407 10610209857723)
0
(Num)
Type check failed in assignment to $n; expected Rat but got Num (2.23606797749979e0)
 in block <unit> at /Users/ash/Books/raku.ru/sqr-fatrat.pl line 9

如你所见,在异常之前,分数的部分变得相当大,并且子表达的类型从Rat转变为Num。在那一刻,$ d的值接近零(这个值是正确答案和前一次迭代的近似值之间的误差)。

似乎我们正在接近最终目的地。再次看看$ d变量的变化:

say $d.perl ~ ' = ' ~ $d;

在最初的几次迭代中,它会精确到零:

-4.0 = -4
4.0 = 4
<4/9> = 0.444444
<4/441> = 0.009070
<4/974169> = 0.0000041
<4/4745030099481> = 0.00000000000084
0e0 = 0

使用FatRat值时不会发生这种情况:

FatRat.new(-4, 1) = -4
FatRat.new(4, 1) = 4
FatRat.new(4, 9) = 0.444444
FatRat.new(4, 441) = 0.009070
FatRat.new(4, 974169) = 0.0000041
FatRat.new(4, 4745030099481) = 0.00000000000084
FatRat.new(4, 112576553224922323902744729) = 0.0000000000000000000000000355
. . .

我们现在进入大鼠的操作(请记住$ d =($ x 2 - $ N)?):

multi sub infix:<**>(Rational:D a, Int:D b) {
    b >= 0
        ?? DIVIDE_NUMBERS
           (a.numerator ** b // fail (a.numerator.abs > a.denominator ?? X::Numeric::Overflow !! X::Numeric::Underflow).new),
           a.denominator ** b, # we presume it likely already blew up on the numerator
           a,
           b
       !! DIVIDE_NUMBERS
           (a.denominator ** -b // fail (a.numerator.abs < a.denominator ?? X::Numeric::Overflow !! X::Numeric::Underflow).new),
           a.numerator ** -b,
           a,
           b
}

在我们的例子中,b总是非负的,我们去我们的老朋友DIVIDE_NUMBERS。

sub DIVIDE_NUMBERS(Int:D nu, Int:D de, t1, t2) {
    . . .
    nqp::if(
        $denominator < UINT64_UPPER,
        nqp::p6bindattrinvres(
        nqp::p6bindattrinvres(nqp::create(Rat),Rat,'$!numerator',$numerator),
        Rat,'$!denominator',$denominator),
        nqp::p6box_n(nqp::div_In($numerator, $denominator)))))
}

是!最后,您可以看到,如果分母不够大,则会返回鼠编号。否则,nqp :: p6box_n函数会创建一个Num值。对于FatRat,有不同的分支不会执行检查:

nqp::if(
nqp::istype(t1, FatRat) || nqp::istype(t2, FatRat),
nqp::p6bindattrinvres(
    nqp::p6bindattrinvres(nqp::create(FatRat),FatRat,'$!numerator',$numerator),
    FatRat,'$!denominator',$denominator),

该函数是NQP的Raku扩展,docs / ops.markdown中有一个文档行:

## p6box_n
* p6box_n(num $value)
Box a native num into a Raku Num.

恭喜,我们已经追踪到了!