B
Brian Troutwine
Here's my finished Lagrange polynomial finder. It runs, and unless a
stress test suggests otherwise (to be performed overnight), works
excellently, but merely is really slow. Any suggestions to get it running
faster?
#!/usr/bin/perl
use diagnostics;
use strict;
use Getopt::Std;
use Math::BigRat;
#Variables
#zork is a common array to allow for different input sources
#The starting zero allows us to use this algorithm for as few
#as two input values. Hopefully the next version will allow
#for one term, but that's trivial to do by hand.
my @zork = (0);
our @equation = (0);
our @poly1 = ("");
our @poly2 = ("");
our $opt_f = "";
getopt("f");
#Opens pipe if no -f used
if($opt_f eq ""){
foreach my $foo (<>){
push @zork, Math::BigRat->new($foo);
}}
#Opens file specified by -f
else{
open(FOO, "<$opt_f") || die("File does not exist.");
my @bar=<FOO>;
close(FOO);
foreach my $bar (@bar){
push @zork, Math::BigRat->new($bar);
}}
chomp @zork;
#$i represents the number of the term we're working with.
for( my $i = 0; $i <= $#zork; $i++){
my $thisy = Math::BigRat->new($zork[$i]);
#Creates denominator for each term.
my $denominator = Math::BigRat->new('1/1');
for( my $j = 0; $j <= $#zork; $j++){
if ($j != $i){
$denominator *= ($i - $j);
}}
#Makes array of n's in (x-n) where n is
#all integers from 0 to $#zork except
#$i.
my @numerator;
for( my $k = 0; $k <= $#zork; $k++){
if ($k != $i){
push @numerator,(-$k);
}}
#Computes numerator as polynomial
for(my $l = 0; $l<=$#numerator; $l++){
#The polynomials will be arrays in which any position
#will hold the coefficient of the corresponding power
#of x. For example, the first position (0) will hold
#the constant (the coefficient for x^0).
if($l == 0){
@poly1 = (0,1);
$l++;
}
@poly2 = ($numerator[$l],1);
my @neweq = (0);
#To multiply our polynomials, we take each of the
#terms of the first polynomial, and multiply them
#by each of the terms of the second, and add the
#resulting coefficient to the sum of their positions
for(my $m=0; $m<=$#poly1; $m++){
for(my $n=0; $n<=$#poly2; $n++){
$neweq[$m+$n] += Math::BigRat->new($poly1[$m] * $poly2[$n]);
}}
#Set poly1 to the new equation for the next loop through
@poly1 = @neweq;
}
#To avoid decimals, we've used fractions to multiply
#each of our terms by.
for(my $o=0; $o<=$#poly1; $o++){
$poly1[$o] *= $thisy / $denominator;
}
#Adding up our polynomials, because we want to simplify
for(my $p=0; $p<=$#poly1; $p++){
$equation[$p] += $poly1[$p];
}
}
my $flag = 0;
#Output
for(my $q = $#equation; $q >= 0; $q--){
#Doesn't output zero terms
unless($equation[$q] == 0){
#No plus if it's first or negative, it just makes sense
if (($flag != 0) && ($equation[$q] > 0)){
print "+";
}
print $equation[$q];
#Prints x except for on constant, and power except for
#first power
unless($q == 0){
print "x";
}
if($q > 1){
print "^$q";
}
print "\n\n";
$flag++;
}}
#In case somebody happens to only input zeroes, we don't want
#to leave that poor bastard with no output.
if ($flag == 0){
print "0\n";
}
Thanks.
stress test suggests otherwise (to be performed overnight), works
excellently, but merely is really slow. Any suggestions to get it running
faster?
#!/usr/bin/perl
use diagnostics;
use strict;
use Getopt::Std;
use Math::BigRat;
#Variables
#zork is a common array to allow for different input sources
#The starting zero allows us to use this algorithm for as few
#as two input values. Hopefully the next version will allow
#for one term, but that's trivial to do by hand.
my @zork = (0);
our @equation = (0);
our @poly1 = ("");
our @poly2 = ("");
our $opt_f = "";
getopt("f");
#Opens pipe if no -f used
if($opt_f eq ""){
foreach my $foo (<>){
push @zork, Math::BigRat->new($foo);
}}
#Opens file specified by -f
else{
open(FOO, "<$opt_f") || die("File does not exist.");
my @bar=<FOO>;
close(FOO);
foreach my $bar (@bar){
push @zork, Math::BigRat->new($bar);
}}
chomp @zork;
#$i represents the number of the term we're working with.
for( my $i = 0; $i <= $#zork; $i++){
my $thisy = Math::BigRat->new($zork[$i]);
#Creates denominator for each term.
my $denominator = Math::BigRat->new('1/1');
for( my $j = 0; $j <= $#zork; $j++){
if ($j != $i){
$denominator *= ($i - $j);
}}
#Makes array of n's in (x-n) where n is
#all integers from 0 to $#zork except
#$i.
my @numerator;
for( my $k = 0; $k <= $#zork; $k++){
if ($k != $i){
push @numerator,(-$k);
}}
#Computes numerator as polynomial
for(my $l = 0; $l<=$#numerator; $l++){
#The polynomials will be arrays in which any position
#will hold the coefficient of the corresponding power
#of x. For example, the first position (0) will hold
#the constant (the coefficient for x^0).
if($l == 0){
@poly1 = (0,1);
$l++;
}
@poly2 = ($numerator[$l],1);
my @neweq = (0);
#To multiply our polynomials, we take each of the
#terms of the first polynomial, and multiply them
#by each of the terms of the second, and add the
#resulting coefficient to the sum of their positions
for(my $m=0; $m<=$#poly1; $m++){
for(my $n=0; $n<=$#poly2; $n++){
$neweq[$m+$n] += Math::BigRat->new($poly1[$m] * $poly2[$n]);
}}
#Set poly1 to the new equation for the next loop through
@poly1 = @neweq;
}
#To avoid decimals, we've used fractions to multiply
#each of our terms by.
for(my $o=0; $o<=$#poly1; $o++){
$poly1[$o] *= $thisy / $denominator;
}
#Adding up our polynomials, because we want to simplify
for(my $p=0; $p<=$#poly1; $p++){
$equation[$p] += $poly1[$p];
}
}
my $flag = 0;
#Output
for(my $q = $#equation; $q >= 0; $q--){
#Doesn't output zero terms
unless($equation[$q] == 0){
#No plus if it's first or negative, it just makes sense
if (($flag != 0) && ($equation[$q] > 0)){
print "+";
}
print $equation[$q];
#Prints x except for on constant, and power except for
#first power
unless($q == 0){
print "x";
}
if($q > 1){
print "^$q";
}
print "\n\n";
$flag++;
}}
#In case somebody happens to only input zeroes, we don't want
#to leave that poor bastard with no output.
if ($flag == 0){
print "0\n";
}
Thanks.