perl-scripts/Math/nth_root_good_rational_approximations.pl

#!/usr/bin/perl

# Formula for computing good rational approximations to the n-th root of a number.

# See also:
#   https://www.mathpages.com/home/kmath434.htm

use 5.014;
use strict;
use warnings;

use experimental qw(signatures);
use Math::AnyNum qw(:overload iroot sum binomial);

sub f ($N, $r) {

    my $m = iroot($N, $r);
    my $R = $N - $m**$r;

    my @s = ((0) x ($r - 1), 1);

    return (
        $m, $R,
        sub ($n) {
            $s[$n] //= sum(map { my $j = $_; binomial($r, $j) * $m**($r - $j) * $R**($j - 1) * $s[$n - $j] } 1 .. $r);
        }
    );
}

my ($m, $R, $g) = f(10, 3);     # approximations for 10^(1/3)

foreach my $n (1 .. 20) {

    my $x = $g->($n);
    my $y = $g->($n + 1);

    my $t = ($m + $R * $x / $y);

    printf("%20s / %-20s =~ %s\n", $t->nude, $t->as_dec);
}

__END__
                   2 / 1                    =~ 2
                  13 / 6                    =~ 2.16666666666666666666666666666666666666666666667
                  28 / 13                   =~ 2.15384615384615384615384615384615384615384615385
                1088 / 505                  =~ 2.15445544554455445544554455445544554455445544554
                1409 / 654                  =~ 2.1544342507645259938837920489296636085626911315
                7603 / 3529                 =~ 2.15443468404647208841031453669594786058373476906
              590774 / 274213               =~ 2.15443469128013624445230532469284826029400502529
             3825397 / 1775592              =~ 2.15443468995129511734677786338302943468995129512
             2752258 / 1277485              =~ 2.15443469003549943834956966226609314395080959855
            64157404 / 29779229             =~ 2.15443469003176677273948227470899263375824807284
          2077169449 / 964136652            =~ 2.1544346900318856460193985032735795215883982388
          1120845673 / 520250476            =~ 2.15443469003188379591218288476875896217344354722
        174185580626 / 80849784601          =~ 2.1544346900318837127732819746711696004361257185
       1127891541661 / 523520878530         =~ 2.15443469003188372228223079040300983199070198122
        486890409328 / 225994508713         =~ 2.1544346900318837217374632236690845669751527933
      94581808509632 / 43900986624121       =~ 2.15443469003188372175993267421075826039322542243
     612438879438973 / 284268946407426      =~ 2.15443469003188372175928686483574181826893273791
       5954477565019 / 2763823657579        =~ 2.15443469003188372175929288136249910595910099978
   51357399784775318 / 23837993336440045    =~ 2.15443469003188372175929362914637034425598873999
   66510185987581361 / 30871293660146676    =~ 2.15443469003188372175929356318484885473783216603