Summation of functions of one positive integer variable

[SlimJim]

Suppose we have a function f(n) where n is a positive integer. We often need to calculate

S(m;n) = f(m) + ... + f(n). m <= n

This is a simple recursion for a given function f,

S(m;m) = f(m), S(m;n) = S(m;n-1) + f(n).

So what I am doing here is trying to make the function one of the parameters.

Sigma(f;m;n) = f(m) + ... + f(n)

Here is the definition of Sigma(f;m;n)

Let(

[Arg1 = Left(f;Position(f;"#";1;1)-1);

Arg2 = Right(f;Length(f) - Position(f;"#";1;1))];

Case(

m > n; "Undefined";

m = n; Evaluate(Arg1 & m & Arg2);

Evaluate(Arg1 & n & Arg2) + Sigma(f;m;n-1)))

Obviously this can be extended to provide the product

f(m)*...*f(n)

by simply replacing + by * in the final line of the definition of Sigma.

The format for calling Sigma is best understood by some examples. I have used # for the variable because I found out fairly quickly that other symbols caused problems in the splitting of the function. into Arg1 and Arg2. You need something that will not occur naturally in any function name that you might want to use. If problems arise it is easy enough to change # to something else for example might be better.

NOTE the function f(#) has to be enclosed in quotes "f(#)"

Simple examples:

Sigma("#^2";1;10) =385 gives the sum of the squares of the first 10 positive integers.

Sigma("GetNthRecord(fieldname;#)";1;Get(RecordNumber)) will sum all the values in fieldname (which has to be in fully specified format table::field) from the first to the current record in the found set.

If this is a well-known CF I would be pleased to have a reference, but I couldn't find it.

[SlimJim]

Version 2.

The advantage of posting, even when no comments are made is that you tend to look more closely at what you have and I noticed a disadvantage with the previous CF is that the variable # is only allowed once. So here is a new version of Sigma

Sigma(f;m;n) =

Case(m > n; "Undefined";

m = n; Evaluate(Substitute ( f ; "#" ; m ));

Evaluate(Substitute ( f ; "#" ; n )) + Sigma(f;m;n - 1))

which allows more than one occurrence of the variable in the function definition and is slightly less messy.

[Ender]

Looks good, though I'd use "x" instead of "#". A little more intuitive.

I've been trying to figure out something like this for solving integrals. How's your calculus? :tongue2:

[SlimJim]

I agree that # is not very intuitive but the Substitute means that I cannot use a symbol which occurs in a function name e.g. exp, unless I put some delimiters around it to make it clear which x is the variable.

My calculus is fine what are you looking for? When you say solving integrals do you mean calculating an integral or solving some sort of integral equation (the first might be Ok the latter not).

On a less positive note I am trying to use Sigma to write out a recursive calculation for the determinant of a matrix and I have hit a wall. It seems that if I use a recursive function as the argument in Sigma then FMP coughs out a ?

I know the function that I am using will calculate the determinant if written in full and it is fairly quick for matrices I've tested up to 4 x 4 so this "?" problem is not in the logic (famous last words). Is it possible to put one recursive function into the definition of another?

[Ender]

Good point about that x.

For that ?, you might double check the syntax in your expression. I seem to be able to use recursive functions as the f input in your Sigma() function.

I can't remember how determinates work, so you'll have to remind me. :qwery:

[SlimJim]

Before I answer your question about determinants I think it is necessary to point out that this is an exercise in learning about custom functions and in particular about the use of recursion.

It is not about calculating determinants. The recursive method is numerically inefficient and there are significantly better ways of calculating a determinant. Calculating for small values of the size up to about 5 or 6 can be done easily without recursion (with a function directly depending on the size - not using size as a parameter)

Having got that out of the way we need some preliminary definitions. Suppose A is a matrix with n rows and n columns and elements A(i;j). Make a submatrix A[i;j] by striking out row i and column j. Often called a cofactor matrix. Then using a mixed notation - part maths part FMP -which I hope has an obvious meaning

n = 1; Det(A) = A(1;1)

Det(A) = Sum(j = 1 to n;(-1)^(j+1)*A(1;j)*Det(A[1;j])

The function Sigma in this thread is an attempt to calculate the sum in the general definition of Det.

You can see the problem. Det is recursive and uses the recursive function Sigma which cannnot calculate without recursing Det etc. I have seen this called a twin recursion and I have no idea how to implement this as a custom function.

Anyway I cannot get it to work. I would welcome any suggestions but preferably of a general nature - how to you define twin recursions would be nice.

[Oldfogey]

Beng a bear of little brain, I always look for simple things.

Is it possible the ? is caused by your field being too small?

[SlimJim]

Thanks for the input. I am hoping this is something simple that I have overlooked but unfortunately that isn't it.

[-Queue-]

A ? will result if the function hits its iteration limit (which I believe is 10,000) without completing.

[SlimJim]

I think it is time to put up a file here. This is based on The Shadow's matrix math and is put up with his permission (not all the functions in his file are included here but the ones that are, are attributed) This file contains sufficient CF's to give a recursive definition of determinant which doesn't work . (14 CF's mostly elementary basically setting up a matrix data type)There are a number of records and evaluations explaining how the functions work. I would be grateful for any suggestions as to why this recursive fdefinition does not evaluate and even better suggestions as to how to put it right

matrixMath.zip

[Ender]

Hey Slim,

The problem seems to be that the Sigma() calling Det() calling Sigma() never has a chance to reduce. I'm not sure if there's a way to correct your algorithm because of the way Sigma() interprets the formula.

I thought about the way the determinate gets calculated, and decided to try it as an iterative problem, where each iteration excludes successive row and column, resets the row and column counter when all rows for a column have been checked, and stops when all columns have been checked.

This is what I came up with:

Det(matrix) =

//Det ( matrix ) =

Let(

n = Rows(matrix);

Case(

not IsMatrix(matrix); "Not a matrix";

Cols(matrix) ≠ Rows(matrix); "Undefined";

n = 1; GetCell(matrix;1;1);

DetSub(matrix; n; n; n)

)

)

DetSub ( matrix; i; j; n ) =

//DetSub ( matrix; i; j; n ) =

//Sub function of Det()

Case(i <= 0; 0;

Case(j <= 0; DetSub( matrix; i-1; n; n );

Case(

not IsMatrix(matrix); "Not a matrix";

Cols(matrix) ≠ Rows(matrix); "Undefined";

Rows(matrix) = 1; GetCell(matrix;1;1);

(-1)^(j+1) * DetSub(Cofactor(matrix;1;j); i; j-1; n) * GetCell(matrix;1;j)

)

)

)

This may not be working correctly yet, as I haven't really tested it, but hopefully it will give you another angle to try.

[SlimJim]

This method has one major advantage over mine - it produces an answer not a ? Unfortunately not the right answer yet. The first test is to try evaluating with an upper triangular matrix (GetCell(A;i;j) = 0 if i > j). Here the determinant is just the product of the diagonal elements. My method, which is clearly doomed, still produces the ? even in this simple case.

This is an interesting formula though - I'm now going to try to understand what exactly it is calculating.

[SlimJim]

Ender

I've been unable to work out what your method is actually calculating, the result seems to be independent of n which is a bit strange,

Any way I went back to my original method and made the Sigma recursion explicit. So I now have two recursive functions S and Det calling each other and the result seems to be the Determinant - I have no way of calculating determinants other than by hand so I've checked this with a selection of 2x2 and 3x3 matrices and some very simple (triangular) 4 x 4 and it seems to work.

First of all the explicit Sigma calculation

S(matrix;n) =

Case(

not IsMatrix(matrix);"Not a matrix";

Cols(matrix) ≠ Rows(matrix); "Undefined";

Rows(matrix) = 1;

GetCell(matrix;1;1);

n = 1;(-1)^(n+1) * Det(Cofactor(matrix;1;n)) * GetCell(matrix;1;n);

(-1)^(n+1) * Det(Cofactor(matrix;1;n)) * GetCell(matrix;1;n) + S(matrix;n-1)

)

and then the determinant

Det(matrix)=

S(matrix;Rows(matrix))

I would be interested to know if this really is the determinant. It is slow - even with a simple triangular 4 x 4 matric there is a perceptible delay (fraction of a second) before the answer comes up. With a triangular5 x5 matrix I estimate a 2-3 seconds delay.

[Ender]

Hey Slim,

After researching how determinants are supposed to work, I've removed the i loop from my algorithm and added another iterative call to get it to correctly add the successive columns. I've also added that basic case for the 2x2 matrix:

Det ( matrix ) =

//Det ( matrix ) =

Let(

n = Rows(matrix);

Case(

not IsMatrix(matrix); "Not a matrix";

Cols(matrix) ≠ Rows(matrix); "Undefined";

n = 1; GetCell(matrix;1;1);

DetSub(matrix; n; n)

)

)

DetSub ( matrix; j; n) =

//DetSub ( matrix; j; n ) =

//Sub function of Det()

Case(j <= 0; 0;

Case(

not IsMatrix(matrix); "Not a matrix";

Cols(matrix) ≠ Rows(matrix); "Undefined";

Rows(matrix) = 2; GetCell(matrix;1;1) * GetCell(matrix;2;2) - GetCell(matrix;1;2) * GetCell(matrix;2;1);//2x2 determinant

(-1)^(j+1) * DetSub(Cofactor(matrix;1;j); n-1; n-1) * GetCell(matrix;1;j) + DetSub(matrix;j-1;n)

)

)

This gives me the same results as your algorithm. Both algorithms seem to give the correct results up to a 4x4 matrix. My algorithm works for a 5x5 matrix, but not for a 6x6. Yours chokes on the 5x5. It must be hitting that 10,000 recusive computation limit.

I found these matrix calculators on the Internet:

http://home.att.net/~srschmitt/script_determinant3.html

http://home.att.net/~srschmitt/script_determinant4.html

http://home.att.net/~srschmitt/script_determinant5.html

I don't think there's a way to avoid the speed problems. It looks like for a matrix of size n, there are some O(n!) recursive computations (though since it's erroring out at 6x6, it implies there may be more recursive calls involved.)

[SlimJim]

Thanks for the links, its useful to be able to cross-check. I'm getting pretty much the same limitations as you. However, as I said earlier this is not about calculating determinants it concerns learning about custom functions and this has been an eye-opener. Although not that efficient my algorithm proves to me that you can do twin recursions in FMP custom functions so long as you do not have too many call-backs. The determinant is a particular bad example from this point of view.

[SlimJim]

In case anyone else is watching this thread I am reposting the matrix math file with the working definition of Det by Ender. Since Sigma is no longer used in that calculation it's definition has been removed.

matrixMath.zip

[Ender]

I know you seem to be more of a numbers guy, but for some more interesting recursion examples, you might check out (or try to build) some sorting functions. ???

[SlimJim]

Sorting - good idea.

{Musing: - Takes me back 25+ years when I was trying to find something not-too-mathematical for a bunch of students learning BASIC in a lab full of APPLE II's (or was it BBC Micros? memory fades) and we ended up programming a bubble sort. Wonderful machine the APPLE II, the pre-IBM PC with its ability to take plug-in cards on the motherboard; and then there was the Mac, the rich man's PET we used to call it and you have to be quite old to get that reference!}