1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465 |
- #!/usr/bin/perl
- # Daniel "Trizen" Șuteu
- # Date: 04 January 2019
- # https://github.com/trizen
- # Find a closed-form polynomial to a given sequence of numbers.
- # See also:
- # https://www.youtube.com/watch?v=gur16QsZ0r4
- # https://en.wikipedia.org/wiki/Polynomial_interpolation
- # https://en.wikipedia.org/wiki/Vandermonde_matrix
- use 5.020;
- use warnings;
- use Math::MatrixLUP;
- use Math::AnyNum qw(ipow sum);
- use List::Util qw(all);
- use experimental qw(signatures);
- sub find_poly_degree(@seq) {
- for (my $c = 1 ; ; ++$c) {
- @seq = map { $seq[$_ + 1] - $seq[$_] } 0 .. $#seq - 1;
- return $c if all { $_ == 0 } @seq;
- }
- }
- sub eval_poly ($S, $x) {
- sum(map { ($S->[$_] == 0) ? 0 : ($S->[$_] * ipow($x, $_)) } 0 .. $#{$S});
- }
- # An arbitrary sequence of numbers
- my @seq = (
- @ARGV
- ? (map { Math::AnyNum->new($_) } grep { /[0-9]/ } map { split(' ') } map { split(/\s*,\s*/) } @ARGV)
- : (0, 1, 17, 98, 354, 979, 2275, 4676)
- );
- # Find the lowest polygonal degree to express the sequence
- my $c = find_poly_degree(@seq);
- # Create a new cXc Vandermonde matrix
- my $A = Math::MatrixLUP->build($c, sub ($n, $k) { ipow($n, $k) });
- # Find the polygonal coefficients
- my $S = $A->solve([@seq[0 .. $c - 1]]);
- # Stringify the polynomial
- my $P = join(' + ', map { ($S->[$_] == 0) ? () : "($S->[$_] * x^$_)" } 0 .. $#{$S});
- if ($c == scalar(@seq)) {
- say "\n*** WARNING: the polynomial found may not be a closed-form to this sequence! ***\n";
- }
- say "Coefficients : [", join(', ', @$S), "]";
- say "Polynomial : $P";
- say "Next 5 terms : [", join(', ', map { eval_poly($S, $_) } scalar(@seq) .. scalar(@seq) + 4), "]";
- __END__
- Coefficients : [0, -1/30, 0, 1/3, 1/2, 1/5]
- Polynomial : (-1/30 * x^1) + (1/3 * x^3) + (1/2 * x^4) + (1/5 * x^5)
- Next 5 terms : [8772, 15333, 25333, 39974, 60710]
|