Programming Challenge by Charles Bovaird This is the fourth in a series of articles addressing the programming methods used to solve this problem. Although this problem was posed to members of the Danbury Area Computer Society, Inc., non-DACS members can express their interest by emailing to mathsig@dacs.org. The following articles are available on the Internet. A key objective of this article is to introduce the power of the APL language in solving mathematical problems. http://dacs.org/archive/0711/index.htm – page 7, Spiral Matrix Problem definition and challenge The following solution is using the APL (A Programming Language). It involves a mathematical process called polynomial regression to determining the polynomial factors for the algebraic solution to the problem. This APL program uses a “matrix division” function to perform the polynomial regression. Polynomial regression is a special application of linear regression. The algebraic solution in the third article identified a third degree polynomial that suggested using polynomial regression to solve the spiral matrix problem. A type (3) method – Matrix algebra solution by Charles Bovaird (mathsig@dacs.org) using A Programming Language (APL). In algebra the C code [2*n*(8*n*n + 15*n + 13)/3] can also be expressed as [(16n3 + 30n2 + 26n)/3] or [1 x0+ 8 2/3 x1 + 10 x2 + 5 1/3 x3] in third degree polynomial form. The general formula for a third-degree polynomial is: f(x) = A0 x0 + A1 x1 + A2 x2 + A3 x3 + … Once we have recognized we are dealing with a polynomial we can use polynomial regression to determine the polynomial factors. In this illustration the “quad divide” ( The APL programming language facilitated matrix operators in its first release about 1966. Matrix operators were introduced into other popular programming languages at a later date as the cost of computer use decreased and mathematical computing techniques became more practical for engineering and management science techniques. The following solutions using the APL language require manually working out the matrix to six rows. The input vectors (X and Y) are derived from the first six rows illustrated here from the following worksheet taken from the Feb. 2008 DACS.DOC.
The APL function POLYFIT1 below used column A and G of the spreadsheet without the values in row 1. The value 1 is accounted for in statement [ 5 ]. The regression is performed in statement [ 4 ] and put into variable C which match the “A” values in the general formula. f(x) = A0 x0 + A1 x1 + A2 x2 + A3 x3 + … Statement [ 5 ] raises 501 to the powers 0 1 2 3, multiplies the result by the values in C and sums the values adding 1 for the missing center cell to get the result 66171001 in variable “E”. (See notes for reading APL code.)
The following APL function POLYFIT3 below used column B and H from the (above) spreadsheet without the values in row 1. The regression is performed in statement [ 4 ] and put into variable C which match the “A” values in the general formula. f(x) = A0 x0 + A1 x1 + A2 x2 + A3 x3 + … Statement [ 5 ] raises 1001 to the powers 0 1 2 3, multiplies the result by the values in C, and sums the values to get the result 66171001 in variable “E”.
Notes:
Charles Bovaird (mathsig@dacs.org) |
) operator in the APL programming language will be used to get the least squares approximations (in this case—exact for integer numbers) for a third degree polynomial.
Mugs and more, visit CafePress to order