You are not logged in.
I am trying to approximate the factorial function f(n)=n*(n-1)*(n-2)*...*1 using a Lagrange polynomial. The idea of the Lagrange polynomial is to know some function values and to form an approximation function.
If I understand right here are not links allowed?!?! So if you want to learn more about Lagrange Polynomial, then use Google...and same about factorial function.
I've been staring at my code for hours, looking for errors in it, but I can't find any. The Lagrange polynomial produces nonsense values. Could someone help? I would be more than grateful if someone could find a error in my code.
Known values are:
f(100)=100!
f(200)=200!
f(300)=300!
f(400)=400!
program FactorialAndLagrange;
uses math;
var f: array [1..2,0..3] of Extended;
x0,x1,x2,x3,y0,y1,y2,y3,x,Pol:Extended;
ind:Integer;
function factorial(m: Extended):Extended ; //counts m!
var i,result: Extended ;
begin
if m=0 then result:=1 else
begin
result:=1;
i:=1;
while i<=m do
begin
result:=result*i;
i:=i+1;
end;
end;
factorial:=result;
end;
begin
f[1,0]:=100;
f[1,1]:=200;
f[1,2]:=300;
f[1,3]:=400;
ind:=0;
while ind<=3 do
begin
f[2,ind]:=factorial(f[1,ind]);
writeln(f[1,ind],' ',f[2,ind]);
ind:=ind+1;
end;
x0:=f[1,0];
x1:=f[1,1];
x2:=f[1,2];
x3:=f[1,3];
y0:=f[2,0];
y1:=f[2,1];
y2:=f[2,2];
y3:=f[2,3];
x:=0;
while x<=1000 do
begin
Pol:=0;
Pol:=Pol+(((x-x1)*(x-x2)*(x-x3))/((x0-x1)*(x0-x2)*(x0-x3)))*y0;
Pol:=Pol+(((x-x0)*(x-x2)*(x-x3))/((x1-x0)*(x1-x2)*(x1-x3)))*y1;
Pol:=Pol+(((x-x0)*(x-x1)*(x-x3))/((x2-x0)*(x2-x1)*(x2-x3)))*y2;
Pol:=Pol+(((x-x0)*(x-x1)*(x-x2))/((x3-x0)*(x3-x1)*(x3-x2)))*y3;
writeln('x=',x,' ','Pol=',Pol,' = ','Factorial=',Factorial(x));
x:=x+100;
end;
end.Offline
Hi Keckman, I just briefly looked at your code. From your definitions: You treat the partial polynomials as *numbers* (correct me if I err, but the extended data type is not suitable for polynomials but just for real numbers). Well, the factorial of 1000 e.g. would require about 8530 binary digits ... After all, you have to deal with polynomials using tuples / lists of their respective coefficients. Hope this is not too patronizing: But the Lagrange polynomials are a real pain; why not use the Newton polynomials (look for "divided differences"). But I'm afraid you won't get good approximations in this case just with say a 3rd degree polynomial.
Offline
Factorial Calculation: Ensure that your factorial function handles large numbers correctly. Factorials grow very quickly, so you might need to use a more robust data type or library that supports arbitrary-precision arithmetic if your current setup isn't handling large numbers well.
Interpolation Points: The values you're using for interpolation (100!, 200!, 300!, 400!) are extremely large. Make sure the Lagrange polynomial is being computed with correct precision and that you handle very large numbers properly in your calculations.
Lagrange Polynomial Calculation: Double-check the polynomial formula and make sure the indices and arithmetic operations are correctly implemented. Small mistakes in the formula can lead to large discrepancies in the results.
Testing and Debugging: You might want to test with smaller, more manageable numbers to ensure that your polynomial interpolation is working as expected before scaling up to large factorials.
Offline