#!/usr/bin/perl

# Lagrange-Method to regressively calculate the value of any
# element of a sequence, by using the input values of already
# existing elements of the sequence
# this could be easily modulized as a perl module
# for simplicity it is kept in one file
#
# copyleft 2007 by dennisg <bluedrago@gmx.de>
#

use strict;
our @elements; # 5.2, 3,-4, 0, 19.1
my $x;
my $product;
my $sum = 0;
my $steps = 0;
my $e = 0;

# main program ----------------

# print this only if no arguments are given:
print "usage: lagrange.pl arg1 [arg2] following_args
where arg1 = N. step of the sequence to calculate (for N=0 it's the first of the following_args)
if arg2 is set to 'steps' the intermediate steps are printed
the arguments following after that will be used as the sequence's values

example:
lagrange.pl 3 steps 2 4 6 8 10" if !$ARGV[0];

# put the value from the beginning of our arguments as
# the x value we want to calculate
# and remove it from the beginning of the array
$x = shift @ARGV;

# check if this argument equals "steps"
# and remove it from the array if yes
$steps = shift @ARGV if $ARGV[0] eq "steps";

# begin iterating through the rest of our arguments
foreach (@ARGV)
{
	# just match correctly formed numbers or math. fractions
	if ($_ =~ /^([-]?[0-9]+[.]?[\/]?[0-9]?)$/)
	{
		# print it, if we want to see the steps:
		print "adding element Index: $e := $_\n" if $steps;
		# use "eval" to evaluate math. fractions
		$elements[$e++]=eval($_);
	}
}

# print the result
print("a($x) = ".lagrange($x)."\n");

# -----------------------------


# function to calculate lagrange - one input argument for the position of x

sub lagrange {
	# set the first input argument to $x and don't care about the rest
	$x = shift;

	for (my $i = 0; $i <= $#elements; $i++)
	{
		# print what we are doing, if "steps" is set
		print "i = $i :\n" if $steps;

		# we need to have the default product variable set to 1
		# otherwise we have a multiplication by zero the first time
		# which we don't want of course!
		$product = 1;

		# iterate through the j's
		for (my $j = 0; $j <= $#elements; $j++)
		{
			# but just do something if j is not the same as i
			if ($i != $j)
			{
				# multiplicate with the next step
				$product=$product*(($x-$j)/($i-$j));
				# print what we are doing, if "steps" is set
				print "\tj = $j\tproduct: $product * ($x-$j)/($i-$j)\n" if $steps;
			}
		}
		# print what we are doing, if "steps" is set
		print " current sum: $sum + $elements[$i] * $product" if $steps;
		# multiplicate the whole product with the current element
		$sum=$sum+$elements[$i]*$product;
		# also print the result of this sum if "steps" is set
		print " = $sum\n--------------\n" if $steps;
	}
	return $sum;
}

exit 0;