Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

fizbin's scratchpad

by fizbin (Chaplain)
on Jun 01, 2004 at 17:01 UTC ( #358236=scratchpad: print w/replies, xml ) Need Help??

fizbin's stupid web game

A method for finding a polynomial of degree <= n-1 to fit n values given for the integers 1,2,3,...

Note that Math::Polynomial has its own version of this in the function "interpolate", which is probably faster. Also note that while polynomial interpolation has its uses, it's generally considered invalid to use it as I do here, since the interpolation is likely to be completely unrelated to the original function outside the bounds of the interpolation points.


use bigrat; use strict; # These are library routines for polynomial arithmetic - I could have +used # Math::Polynomial, but it's incompatible with "use bigrat", which I w +anted # to use. # A polynomial is represented as an arrayref - the first term is the # constant term, the next term is the x^1 term, then x^2, etc. sub polymult { my ($a, $b) = @_; if (ref($a) ne 'ARRAY') {$a = [ $a ];} if (ref($b) ne 'ARRAY') {$b = [ $b ];} my $ans = []; for my $i (0..$#{$b}) { $ans = polyadd($ans, [ (0) x $i, map {$_*($b->[$i])} @$a ]); } $ans; } sub polyadd { my ($a, $b) = @_; if (ref($a) ne 'ARRAY') {$a = [ $a ];} if (ref($b) ne 'ARRAY') {$b = [ $b ];} if ($#{$a} < $#{$b}) { ($a, $b) = ($b, $a); } my $ans = [ @$a ]; for my $i (0..$#{$b}) { $ans->[$i] += $b->[$i]; } $ans; } sub polyeval { my ($x, $a) = @_; if (ref($a) != 'ARRAY') {return $a;} if (@$a == 0) {return 0;} if (@$a == 1) {return $a->[0];} my $prev = polyeval($x, [ @{$a}[1..$#$a] ]); my $ans = ($a->[0] + $x * $prev); $ans; } # Now on with the show # Here place the given numbers plus whatever other ones you want # to have show up later my @values = qw ( 1 2 3 4 29 52 125 ); # The values you want to fit my @xvals = (1..scalar(@values)); # The values you want to check my @exvals = (@xvals, scalar(@values)+1); my $P = [ shift @values ]; my $i = 0; my $Q = 1; while (@values) { $Q = polymult($Q , [-$xvals[$i],1]); $i++; my $newval = shift @values; my $oldval = polyeval($xvals[$i], $P); my $ratio = polyeval($xvals[$i], $Q); next if ($newval == $oldval); my $addition = polymult($Q, ($newval - $oldval) / $ratio); $P = polyadd($P, $addition); } print "Polynomial: [ @$P ]\n"; print "cross-check of series, plus one more term:\n"; for my $v (@exvals) {print polyeval($v, $P), " ";} print "\n";

Regular expression speed comparison, or a meditation on such
I still need to add bleadperl numbers to this, and I may be redoing all my numbers soon enough (I'm getting a spiffier machine), but 5.9.3 was added and, well, it didn't do as well as it should have.

Note to self: Remember that Tilly came up with this in a chatterbox golfing session:
perl -pe'$\=($\*32768.5+ord)%4**8 .$/for/./gs}{'

What does this code do? It computes the same checksum as BSD's historic "sum" program. It's sum1 on http://ppt.perl.org/commands/sum/sum.theo

Log In?
Username:
Password:

What's my password?
Create A New User
Chatterbox?
[Corion]: I just found out that in $current_top_prior ity_project , the part I am in is not even in the top three worries. That's somewhat bad, not because I'm happy with being a top worry but because that means that I don't even know how bad the rest ...
[Corion]: ... of the situation is :-)
[marto]: it's good to know that things can always get worse :P
[hippo]: Ignorance can be bliss
[Corion]: hippo: Yeah - I'll just avoid the project lead :)
[Corion]: marto: Yeah, it helps with the perspective :-D

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (9)
As of 2017-07-26 08:11 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    I came, I saw, I ...
























    Results (385 votes). Check out past polls.