#!/usr/bin/perl -w
# A simple analysis of Horner's method versus the standard method of evaluating
# polynomials.
#
# Matt Sparks
# http://f0rked.com
use strict;
use Time::HiRes qw(time);

# The polynomials used in this program takes the form
#   a_n * x^n + a_(n-1) * x^(n-1) + ... + a_0
# Thus, a_0 is the first number in the following list, and the coefficients
# are listed in ascending order. Obviously, a coffeicient of zero effectively
# eliminates that term.
my @coeff=(3,4,5,61,4,-1,0,23,6,1,5,2,6,1,-6,7,2,45,7,2,2,4,11,6,-8,2,0,9,-13,31);
#my @coeff=(2,2,2);

sub stringize {
    my(@a)=(@_);
    my $str;
    for(my $i=$#a;$i>=0;$i--) {
        $str.=$a[$i]."x^$i + " if $a[$i];
    }
    return substr($str,0,-3);
}

sub horner {
    my($x,@a)=(@_);
    my $i=$#a; # highest index (highest cofficient)
    my $s=$a[$i];
    while($i>0) {
        $s=$s*$x+$a[$i-1]; # new sum = sum * x + next cofficient
        $i--;
    }
    return $s;
}

sub standard {
    my($x,@a)=(@_);
    my $s;
    for(my $i=0;$i<=$#a;$i++) {
        $s+=$a[$i]*($x**$i);
    }
    return $s;
}

my $x=13;
my $it=100000;
my $start;
my ($m_s,$m_h);
print "Evaluating ".stringize(@coeff)." at x = $x\n";

print "Timing $it iterations of the standard method:\n";
$start=time;
for(1..$it) {
    standard($x,@coeff);
}
$m_s=time-$start;
print "Done. Duration: $m_s seconds.\n";

print "Timing $it iterations of Horner's method:\n";
$start=time;
for(1..$it) {
    horner($x,@coeff);
}
$m_h=time-$start;
print "Done. Duration: $m_h seconds.\n";

print "Horner's method ran ".sprintf("%.3f",($m_s-$m_h)/$m_s*100)."% faster.\n";