Fermat is an interactive system for mathematical experimentation. It is a super calculator - computer algebra system, in which the basic items being computed can be real numbers, rational numbers, complex numbers, modular numbers, multivariable polynomials, rational functions, or polynomials modulo other polynomials.

There are several versions of Fermat, in two different senses of the word "version." Originally Fermat ran under Apple's MPW development system, which provides a Unix-like interface. Later, stand-alone versions were produced as well with Metrowerks CodeWarrior. Since MPW is now freely available from Apple by ftp, the MPW versions remain a reasonable choice for their ease of use. But the stand-alone versions compiled for PPC processors are faster, assuming of course that one has a Macintosh PowerPC. Any Mac purchased since around 1996 is a PPC. The other sense of "version" involves the basic "type" one is computing with. One can work over the rationals, in which numerical values are ratios of integers of unlimited size, or over the reals, in which case numerical values are the classic "floats" of about 18 significant digits. One version of Fermat, called QFermat, works over the rationals, and the other, called FFermat, works over floats. Originally there was a single program that allowed one to convert back and forth between these types, but that became unwieldy.

In FFermat one can extend the basic real type to complex arithmetic - arithmetic of ordered pairs in which multiplication follows the defining property of the field of complex numbers; the ground ring becomes C. In QFermat one may choose to work modulo a specified integer n, thereby in effect changing the ground ring from Q to Z/n.

Choosing modular (or complex) mode establishes the ground field (or ground ring) F. On top of this may be attached any number of unevaluated variables t₁, t₂, ..., t_n, thereby creating the polynomial ring F[t₁, t₂, ..., t_n] and its quotient field, the field of rational functions, whose elements are called quolynomials. Further, polynomials p, q,... can be chosen to mod out with, creating the quotient ring F(t₁, t₂, ...)  / < p, q, ... > , whose elements are called polymods. Finally, it is possible to allow Laurent polynomials, those with negative as well as positive exponents. Once the computational ring is established in this way, all computations are of elements of this ring.

Fermat has extensive built-in primitives for array and matrix manipulations, such as submatrix, sparse matrix, determinant, normalize, column reduce, and matrix inverse. It is consistently faster than some well known computer algebra systems - orders of magnitude faster in many cases.

Fermat is a complete programming language. Programs are called functions, and their use is typical of that in many languages. Programs and data can be saved to an ordinary file that can be examined as any other file, read during a later session, or read by some other software system.

FFermat has powerful, simple, but extremely flexible graphics capabilities. Any numerical values created by any Fermat program can be plotted as easily as they can be written as digits. It is easy to produce two- and three- dimensional graphs of functions, with real or complex domain and range. Objects consisting of lines, points, or polygons can be defined and then rotated, translated, cut up, or strung together to form animation sequences, or movies. Numerical solutions of differential equations, such as planetary motions, can be displayed as movies. Surfaces can be graphed as hidden-line objects or shaded objects.

For the sake of speed, one can write subprograms in C or Pascal and invoke them from Fermat.

Fermat has several unique features that enhance debugging. It is possible to interrupt Fermat by pressing the command key, examine the state of a computation, and then resume it. Error diagnostics are very specific - much more so than in some other systems, which struggle to tell you that an error has occurred somewhere before the last semicolon.

Via arrays, Fermat allows for string processing. The built-in array primitives permit substring and concatenation operations.

The features in Fermat reflect my own interests. It began as a kind of arbitrary precision APL. Surprised that it was much faster in manipulating matrices than the computer algebra system that I had access to at the time (on a VAX), I extended it to help in my research in low dimensional algebraic topology. Polynomial variables were added for the same reason. Research in computational group theory and algebraic number theory suggested several new features and changes in old ones (see Appendix 3, Example 1). I also used it to teach numerical analysis to graduate students, where the complex number and polynomial data types were extremely useful.

I envision the users of Fermat to be rather sophisticated in both mathematics and programming. (Of course, you don't have to do any programming to use Fermat as a matrix and polynomial calculator, or to produce stunning graphics.) At many places in the design and implementation of Fermat I had to balance the conflicting goals of flexibilty and safety. That is, whether to allow the user certain freedoms or language features that might perhaps be abused, or to circumscribe the user in the name of safety. Since I regard the users as sophisticated, I have usually chosen freedom.

Fermat is by no means complete. Future extensions will include more factoring, Grobner bases, color graphics, and graphics of higher dimensional objects.
 
 

Basic features - a simple example:

When the user invokes the system he sees the prompt character   >  ; the interpreter is waiting for a command of some sort. The user could enter: 8+23 < enter > , and the system responds immediately with 31, and the prompt character again. The user could enter any arithmetic expression following the usual syntax, such as (8-3)*(178-96)/2 < enter > . ( < enter > means press the return or enter key. In MPW, you must press the enter key.)

Fermat always responds with a value after every user command. If there is no obvious scalar output associated with a command, it responds with 0. For example, the creation of an array or function yields a 0.

The result of a computation may be stored for later use. The syntax of " set x equal to 8+23" is

> x := 8 + 23             [blanks may be inserted for clarity]

31

Fermat ignores blanks inside long integer constants, as 222 333 444 = 222333444.

The name  x  may or may not have been used before. The user can now compute expressions in x, like

> y : = (x-29)*x - 60

2
 

If the formula is going to be used frequently, the user will want to give it a name, say  F

> Function   F(t) = (t-29)*t - 60.

0               [0 is the computed result of a function definition]
 
 

The t is called a formal parameter or just parameter. Any number of parameters is allowed.

The user can now enter commands like

> y : = F(x)

2
 

Notice that F(31) has been computed, stored in y, and the answer displayed.

> F(27+y+1)

-30

Here F(30) has been computed and displayed, but not stored anywhere by the user. The latest computed result arising from a terminal command is stored in the system variable, where it can be accessed via the symbol !' (option-t), until a later result supplants it (!'  is a built-in function described in the later chapter on built-in functions).

When the Fermat interpreter is awaiting user commands, we say that it is in the lowest level. When it is executing functions, it is in a higher level

In rational mode, adding 1/3 + 1/6 produces 1/2. Note well: rational numbers are computed and there is no roundoff of any sort. Values not whole integers are also displayed as decimals, to a precision (called the display constant) selected by the user. For example, with display constant 3, 1/3 will be displayed as

               1/3 or 0.33333333 33333333 33333333

(3 blocks of 8 digits). Setting the display constant to 0 turns off this feature.

Computed values and function definitions can be saved from one session to the next. They are stored in an ordinary ASCII file that can be edited with an ordinary word processor. This file is called the save file or, when being read, the input file.

Fermat uses the ordinary character set of most languages, plus several special symbols on the MacIntosh keyboard, like p (which is option-p) and · (which is option-8). These symbols will be described in this manual as they are encountered. They are summarized in Appendix 2.

In the MPW versions, the user must press the enter key, not the return key at the end of a line. In the stand-alone versions, use return. You may enter long commands that occupy more than one line by putting the continuation character ,, on the end of each line (except the last, of course). Then (in MPW) use the mouse to highlight the entire command, and hit enter. (",," is a single character, namely shift-option-w). This continuation character essentially means " ignore the invisible end-of-line character." There are two occasions when it is not needed, inside multi-line comments and inside multi-line character strings (also called literals). See the later chapters on "Comments" and "Character Strings."

Don't erase the prompt character   >    If you do accidentally, you have to put it back. But you can change the prompt, to the empty string if desired, with the command &M.

Let's continue the example of a Fermat session. Suppose the user has a file of previously saved data called " stuff". He uses the imperative read command

> &(R = 'stuff')

to open the file for reading and bring the data into this session. Suppose there is a 3 X 3 matrix [x]. To see it, he can use the short form of array display,

> ![x

which results in

> [x] : = [[  1,

3,

12,   ,,

2,

7,

-5,  ,,

0,

24,

-4   ]]

To compute the determinant the command is

> D[x]             [or Det[x]; the result is:]

692

The user decides to compute the characteristic polynomial of [x]. First he adjoins a polynomial variable t:

> & ¶

Change of polynomial variable.             [Fermat prompts for the name.]

Enter variable name:

> t

The user subtracts the variable t from every element in the main diagonal. This is done with:

> [y] : = [x] - [t]             [  [t] means a diagonal matrix, 3 X 3 since [x] is.]

Just to look at it, he displays [y]:

> ![y

> [y] : = [[  -t+1,      3,  12,  ,,

2,    -t + 7,  -5,  ,,

0,    24,  -t - 4   ]]

Then invoking determinant computes the desired polynomial:

> w : = D[y]

-t³ + 4t² - 89t + 692

(There is a built-in function Chpoly to more quickly compute characteristic polynomials in QFermat.)

To check the Cayley-Hamilton Theorem, the user decides to evaluate this polynomial at the matrix [x], using the built-in command · for polynomial evaluation:

> w·[x]

[[  0,

0,

0,  ,,

0,

0,

0,  ,,

0,

0,

0   ]]

The user decides to change the ground ring from the present Z[t] to Z[t]/ < t²+1 > . He gives the imperative form of the mod-out-by-polynomial command

> &(P = t² + 1, 1)

The extra "1" tells Fermat that t²+1 is irreducible, so an integral domain results. Then the command

> 1/(t+1)           yields:

(-t+1)/2

Everything will be saved to the file " stuff2", via the save command(s):

> &(S = 'stuff2')

> &s

The user now exits:

> &q

bye
 

Interpreter commands
 
 
 

Interpreter commands affect system-wide globals, perform I/O, or display variables or functions. Most begin with the symbol & and have the syntax & < symbol > . There are also the cancel commands  @ < name > , and the terminal I/O commands  ! and  ?  . (Note: The brackets < and > are not entered by the user - they designate that < symbol > and < name > are elements of syntax of the language. A < symbol > is a key-stroke. A < name > is a legal Fermat name, a sequence of up to ten digits or letters of the alphabet, beginning with a letter.) Many of the & commands can be used as toggle switches to flip a global back and forth between two possibilities, or as imperative commands to force the global into a certain position. There is a later paragraph on the imperative form of switches.

A Word to the Wise

Don't leave a toggle switch on unless you wish to use it. Don't adjoin a polynomial variable unless you are going to use it. Every capability costs a little in performance.

Another Reminder

With the stand-alone versions you use < return > and with the MPW versions you use < enter > .

Cancel

@ : delete a variable, array, or function; erase it; cancel.

To delete a list of items, say variables x, y, array [x], and functions F and G, enter   @(x, y, [x], F, G). The list may be in any order.

Occasionally, after many computations, one develops a large number of now useless arrays, often many of the same name. (This can't happen with ordinary variables.) To delete all arrays named [x], enter @[*x]. To delete all arrays (a powerful command!) enter @[**].

Similarly, during a session of active experimentation and creation of functions, one often develops many versions of the same function. To erase all but the latest version, the delete command has a purge option, indicated syntactically by angle brackets, < and > (less than and greater than). To purge the function G, enter @ < G > . Mnemonically, you are erasing a "vector full" of G's. This can also be done with arrays, and can be done as part of a list of deletions.

@ can also be used to break out of certain modes, if you change your mind. See under &r, &s, and ?.

The & < symbol > commands

&a: Toggle switch to change array initial indexing value. By default it is 1, which means the first entry in array [x] is x[1], uniformly for all arrays. For two-dimensional arrays, the first element is x[1,1]. Entering this command changes the constant to 0, so the first element of array [x] is x[0] or x[0,0]. Note that the creation of arrays is unaffected - indeed the arrays themselves are unaffected, it is only the accessing of arrays that changes. See the later chapter on "Variables and Arrays" for more information.

&b: Toggle switch to control closing of input file when a syntax error occurs while reading. When on and an error occurs, the file is closed. This makes it easier to use a word processor to edit the file. See &r.

&d: Change the display constant. In rational mode, the display constant is the number of blocks of 8 significant digits to the right of the decimal point displayed by the interpreter when a non-integer is displayed. If the display constant is 0, this feature is disabled. This can also be affected by the options after a display "!" command (see below). If you enter &d, you will be prompted to enter the new display constant. Alternatively, use the imperative form described below.

&D: Set the determinant cutoff. Two basic ways to compute the determinant are expansion by minors and Gaussian elimination. As everyone knows, the first is an O(n!) method and the second is an O(n³) method, so is " of course" superior. But 5! = 120 and 5³ = 125. Furthermore, it is far easier to multiply polynomials than to divide them. Fermat runs a hybrid of these two, and the determinant cutoff is an integer that controls the switchoff point. Setting &D = -1 lets Fermat decide where to switch off. Setting &D = n means begin with Gaussian elimination and do the last n rows by minors. Therefore, &D = 0 means Gaussian elimination all the way. Type &D, and you will be prompted for the value. The imperative form &(D = ...) can be placed inside a function. The default cutoff is not always the best if there are lots of complex quolynomials in the matrix.

&e: Toggle switch to change error handling in higher command levels. When turned on, Fermat will attempt to recover from certain errors in a certain situation. See the later chapter "Popping, Pushing, Debugging, and Panic Stops". Entering &e again turns this feature off.

&E: Toggle switch to eliminate the extra blank line that Fermat puts on the screen between lines of input and output.

&f, &F: List all current functions. Only the names and parameter lists of each will be displayed. To list the complete body of the functions as well, enter &F* or &f*. To list the body of only the function named G, type &F,G  , &f,G  , &F < G  , or &f < G. These all have the same effect. The choices exist so that the user doesn't have to release the shift key when entering the command. ( < and comma are on the same key.)

To facilitate the editing of functions, Fermat will display the function with the continuation character ,, (shift-option-w) at the end of each line. You can easily change part of the function on the screen, cancel the function with @, and then enter the amended version from the screen. Alternatively, you don't have to cancel the old version - the new version is stacked on top of the old. [You can also purge the old version(s), keeping only the most recent, as explained in the chapter "Functions."] Note well: this character ,, should not appear in an input file and is not part of the function definition.

&g: Report the status of the system-wide "globals". If you can't remember that you are in modular mode or not, what file you are saving to, what the array initial index is, etc., enter this command. Several globals, such as namelength (&l), error-push (&e), and random divisor (&¿), are not mentioned unless they have been changed from the default.

&h: Report the heap size - the number of bytes of memory that have not yet been allocated. Reasonably, one hopes the heap size to be at least a couple meg.

&m: Change the command interrupt level, the ability to interrupt a computation by pressing the command key. See below under "Popping, Pushing, Debugging, and Panic Stops".

&M: Change the prompt. If you don't like > for a prompt, change it to something else. &M will ask you for the new prompt. If you wish no visible prompt, change it to either the empty string, by hitting < enter > immediately, or change it to the end-of-line character (ASCII 13) by typing one blank and then hitting < enter > . These two will seem equivalent until the interpreter enters a higher command mode (see the chapter on "Popping, Pushing, Debugging, and Panic Stops".)

&l: Change the maximum possible length for names. See the chapter on "Names".

&N: Toggle switch to cut off "noise," suppress the displaying of all results (until &N is entered again). Displaying of individual results can be suppressed by typing colon before < enter > . For example,  x : = 1000!: will correctly assign x, but nothing will be displayed on the terminal screen.

&n: Toggle switch for "modpolyreadin." See polynomial read-in below.

&o: Used to save specified variables to the output file. For example,  !(&o, x, y)  writes the value of x and y to the previously defined output file. See &s, below.

&p: Change into modular ground ring. See the later chapter " Arithmetic Modes".

&P: Polynomial mod-out. You will be prompted to enter the polynomial to mod out by. For example, you could enter t² + 1 to simulate the field of complex numbers. &P can also be used to stop modding out, by entering -t after the prompt. See the chapter on "Polymods".

&q: Quit.

&r, &R: read from input file, loading previously saved functions and variables. An input file may be created using an ordinary editor or the save command (see &s below). Each line of text will be treated as if the user had entered it during a Fermat session (except that end-of-line will be ignored). There must be a semicolon after each complete command, except after comments or multiline literals in functions. Fermat will not read beyond the first semicolon it sees on the line. Reading ceases when the &x command is met. The file should end with the &x command (see &x below).

The input file must not itself contain a read command.

The first time you enter &r, if you do so from the keyboard, you will be prompted for the name of the file to be read from. If the first read command is made from a function, use the imperative form:  &(R = < filename > )  . Later calls to &r will take up where the last one stopped - i.e., after the &x. (More information below under " Imperative form of switches".)

It is possible to read from another, different file by entering &R. You will be prompted for the name of the file. The old file will be closed and data will be read from the new file. If you wish to put this command in a function, use the imperative form  &(R = < filename > ). For the rules of filename formation, see the later chapter on "Names".

To close the file without opening a new one, use the command &(R = ·). See &b.

If you entered &R by mistake, just enter "@" as the name of the file, and the read will be aborted.

It is not an error to try to read from an empty file; nothing happens. In practice this occurs when the user mistypes the name of the file. In some systems, such as MPW, the user discovers the problem only much later after a lot of frustration. To prevent this annoying situation, Fermat issues a warning message when it tries to read from an empty file.

&s, &S: Specify and save to an output file. The current variables and functions will be written to (the end of) an ordinary text file, which can be edited and later read during another Fermat session. The previous contents of the file are not erased.

&s and &S are not strict analogs or duals of &r and &R. It is possible to do a "dumb save" that has no analog in reading.

The first time you enter &s, if you do so from the keyboard, you will be prompted for the name of the file to be saved to. Nothing will be written to the file you name. You have so far only specified its name. Upon the second &s command, all of the current functions and variables will be written to the file in human readable (and Fermat readable) form. Each succeeding &s likewise saves all the current functions and variables.

If you have been saving data to one file and wish to change to another, enter &S. Nothing will be written to the file you name. You have so far only specified its name. You will be prompted for the name of the new file. The old file will be closed (which means that if MPW or Fermat crashes, the saved material should survive¹). Subsequent commands &s will save data to the new file. If you wish to put the &S command in a function, use the imperative form  &(S = < filename > ). For the rules of filename formation, see the later chapter on "Names."

Each call of &s adds more stuff to the previous contents of the file.

To close the file without opening a new one, use the command &(S = ·).

Inserted in the saved file will be the commands &p, &a, &¶, etc., reflecting the arithmetic mode (ground ring), initial array index, polynomial variables, etc. In this way, if you read the saved file in your next Fermat session, all these globals will be restored to their status at the moment you saved the file. (More information on this below under " Imperative form of switches".)

It is possible to do a "dumb save" in which raw data only is appended to the save file. Use the display command  !  along with &o, as in  !(&o, x, y,x+y), which writes the current values of x, y, and x+y to the file that has already been specified as the save file.

If you entered &S or &s by mistake, just enter "@" as the name of the file, and the command will be aborted.

Note: input and output cannot be to the same file.

&t: Toggle switch to turn automatic timing on/off. When on, the length of time in seconds that each command or calculation takes will be displayed right after the result of that command or calculation is displayed. The measured time does not include the time it takes to display the result - which, for very large numbers, can be substantial. The accuracy is to within 1/60th of a second. Most useful when entered from the keyboard; if included in a function, a flood of data will likely result.

&T: Report the time since the host computer was turned on. The number returned is actually the number of "ticks" that have elapsed - a tick is 1/60 th of a second. This command can be used to measure how long part of a function takes to run, by setting a variable equal to &T, then performing the computation, then computing the difference between &T (a second call) and the variable. &T is not affected by modular mode.

&U: Toggle switch to enable ugly printing. When on, Fermat will display long integers and polynomials in the style of other computer algebra systems (Maple). This facilitates communication between Fermat and the others.

&v: List all current variables. Their values as well as their names will be displayed unless &N (see above) has been set. Alternatively, in QFermat, follow with a colon to suppress the values.

&V: Turn on "verbose display." Will display the progress of the more involved and time-consuming procedures, such as Chpoly, Smith, or matrix inverse. A good thing to turn on; try it.

&x: Stop reading from the input file. This command provides a break, allowing the input file to contain data in blocks, whose reading can be interrupted by computation. The next read command causes reading to begin right after the &x. There should be an &x at the end of the file.

&¿: Change the default divisor for the random number generator. More on this below under built-in functions, ¿ = random number. ¿ is the upside down question mark, shift-option-/.

&m: Toggle switch to turn modular arithmetic off/on in modular mode. Do not use it in the situations when modular mode is automatically turned off (and then on again): during the computation of exponents (i.e., following ^Ù), in array coordinates, in character strings, after S or P, and in format specifications, such as !!x:8. More on this later under " Arithmetic Modes". The variant local form  &m( < expression > ) turns modular mode off, computes the expression, then restores modular mode.

Because typing &m(... is sometimes awkward, the symbol _ may also be used to suppress modular, but only if it is followed by a constant, i.e., a string of digits, possibly preceded with a minus, no larger than 2³¹ - 1.

& oe: list-of-monomials display. See Appendix Four.

&P: Push new command level. Begin new computation. More on this later in the chapter "Popping, Pushing, Debugging, and Panic Stops".

&p: Pop command level - return to lower level. Return to computation on that level.

&·: Panic stop - return to lowest command level after an interrupt.

&¶: Adjoin a new polynomial variable: allow manipulation of polynomials in an unevaluated variable. The user is prompted to enter the variable name. If entered within a function, use the imperative form  & ( ¶ = t)  to directly supply the name. (The "paragraph sign" ¶ is option-7 on the keyboard.) There can be up to 121 such variables. Names cannot be repeated.

You can drop the polynomial variable t by entering -t after the prompt.

See the later chapter on polynomials for another use of the symbol ¶, "polynomial read-in."

&±: toggle switch to change Laurent. When on, Laurent polynomials are allowed - those with negative exponents. When this switch is changed, all the current variables are scanned and their format changed if appropriate. For example, 1/t will become t ^-1 if Laurent is now true. See the later chapter on Laurent polynomials.

&|: toggle switch to affect the value returned by the built-in function mod. When on (the default) mod returns non-negative values, so that -2 | 3 = 1. When off, n | m simply returns the remainder produced by dividing n by m, so -2 | 3 = -2. The second choice executes very slightly faster; it takes an extra step to ensure that a non-negative is returned.

&B: toggle switch to change the block on the Chpoly polynomials. This is rather technical; see the later chapter on "The Dangerous Commands."

Imperative Form of Switches

The switches &±, &a, &e, &p, &N, &|, &t and a few others can be used in an imperative sense rather than the toggle sense described above. &¿, &m, &M, &d, &D, &P, &R, and &S can also be used imperatively, i.e., in a non-interactive way. To turn timing on, whatever the current status, enter  &(t=1). Similarly, to turn it off, enter  &(t=0). 1 means on, 0 means off. To forcefully enter modular mode with modulus n, use  &(p = n). To get to rational mode in this way, use  &(p=¥). (¥ is option-5 on the keyboard). Similarly for the others.

&(S = < filename > ) is equivalent to entering &S, and then responding with < filename > when prompted. This form does it all at once without the prompt. It can therefore be placed in a function. Similarly for &(R = < filename > ). For the rules of filename formation, see the later chapter on "Names." You may also use a character string stored in an array to name the file, as in &(S = [x]). This allows file names to be computed within functions.

&(¿ = < expression > ) sets the random divisor.

When you save to a file using &s or &S, the appropriate commands will be inserted to record the status of polynomials, modular mode, etc. It is this imperative form of these commands that is placed in the saved file.

Terminal Input/Output, List Output, and Dumb Save

!(variable, array): write to terminal; display on the CRT screen. If F(x) = x*x + !x, F returns x² and displays x on the screen. This could also be written F(x) = x*x;  !x. The first version will return the value x² (since !x returns value 0), the second will return 0 (the last value computed - displaying returns value 0). Another possibility is F(x) = !x; Return(x*x).

You can display written messages, such as:

!x does not move up to a new line, so the next use of this command will continue displaying on the same line. Using  !  by itself,   !;   will start a new line of output. Alternatively, to display and move up all at once, use the double exclamation: !!x.

!x will not necessarily display x immediately; rather, the data will be displayed when MPW decides that its buffer is full. To force the immediate display, use !!x.

List Output: You can use the syntax

In any mode, there is a certain minimum amount of spacing that can't be overridden.

Note that the spacing feature applies only to list output - !x:8 is illegal.

!!(x, y, ...) will display a list and then move up to a new line.

Dumb Save: You can append raw data (as opposed to the "prepared" data the &s command creates) to a save file by using &o as the first argument in a list output command, such as  !!(&o, x, y, x+y). &o means the previously specified save file.

Note that !!(&o, x, y, ...) is fine but !!(&T, x, y, ...) is an error. If the first argument in a list display starts with & then it must be &o.

Displaying Arrays: Two formats are available for both ordinary and Sparse arrays, " short form" and "long form." The short form is the same for both, but the long form is not. [See the chapter "Variables and Arrays" below for more about Sparse arrays.]

First, for ordinary arrays: Since numbers in Fermat are often many digits long or complicated fractions, the long format display ![a] conveniently shows one value of the array per line, in column-major order. If you expect a matrix to be composed of small integers, however, the short form ![a is nice: it displays the matrix in the familiar square pattern. Analogously with list output, the command ![x:8 will add spaces after every displayed number. However, ![x]:8 is illegal - indeed, it makes no sense.

The long form displays the name and coordinates as well as the value of each entry. For example, if you have x[2,2] with x[i,j] = i+j, ![x] produces:

The short form: Fermat displays the name of the matrix, as in:

> [x] := [[  1,

3,

12,   ,,

0,

24,

-5   ]]

(Note the commas, the double square brackets, and the continuation character.) You may change any of the components, change the name if you wish, and enter the entire matrix (by highlighting it with the mouse), such as:

> [y] := [[  2,

3,

12,   ,,

0,

24,

-5   ]]

where x -> y and 1 -> 2.

Note: In the interests of saving both time and space, Fermat will not display all of a huge number (integer constant) within a matrix when writing to the console terminal. It only displays the first couple hundred digits.

Sparse arrays:

The long form displays the array as a list of rows, only showing those entries that are not zero. For example, if [x] is Sparse, ![x] may produce:

> [x] :=  [ [ 1,  [2, -1],  [3, 19]]  ,,

[ 2,   [1, 8],    [2, -2]]  ,,

[ 3,   [2, -1],  [3, 9]] ]

This [x] has in row 1 a -1 in column 2 and a 19 in column 3, in row 2 an 8 in column 1 and a -2 in column 2, etc. The dimensions of [x] are not apparent from the long form; it may have more than 3 rows, so long as all entries are zero there.

The short form is the same as for ordinary matrices. If the above [x] is 3 X 3, ![x produces:

> [x] := [[  0,

-1,

19,   ,,

8,

-2,

0,   ,,

0,

-1,

9   ]]

?(variable, array): get input from the terminal; interrogate user. If F(x) = ?y; x - y.  F asks the user to enter a value for y, then computes x - y. Fermat halts when it encounters ?y and prompts the user. Nothing will happen until the user enters a value for y, which may be any legal expression.

When used with an array, such as  ?[x]  , Fermat displays the name and coordinates of each entry in the matrix in row-major order and waits for the user to enter a value for each successive coordinate. If you've made a mistake or for any reason want to break out of this array input mode, just enter '@', the cancel symbol.

Interrogation cannot be used with Sparse arrays.
 

Built-in functions
 
 
 

The built-in functions operate on numbers, arrays, or polynomials in arithmetic or algebraic fashion. Initially I intended each function to have a special one-character symbol as its name, but that gets unwieldy. Many have such symbols, and many also have " ordinary" mnemonic names, which always start with a capital letter. These names are reserved and cannot be used by the programmer for any other purpose. With a few exceptions, the name of the function precedes its argument, as in $x = greatest integer in x. Also with very few exceptions, the parentheses around the argument are optional if the symbolic name is used but must be there if the ordinary name is used, unless the argument is an array. Putting the parentheses in when not necessary costs a very tiny additional amount of time to parse them.

Conventions:

In the following, if I make a statement like "x can be a polynomial but not a quolynomial," I mean that x cannot be a quolynomial with denominator <> 1. Similarly, if I say "x can be a number but not a polynomial," I of course mean that it cannot be a polynomial of nonzero degree.

By number I mean a rational or modular number. By scalar I allow in addition a polynomial or quolynomial.

Return

This built-in allows a user's function (see the chapter on "Functions") to terminate and pass back a specified value. Syntax of use is Return(x), where x is any expression.

Basic Arithmetic

+, -, *, / : obvious, except they can be applied to arrays as well as scalars, in which case they often act component-wise. More on this later under " array expressions".

The Increment Command:

A surprisingly large proportion of all commands written in programs are of the form x : = x + y, and a great many of these are of the form x : = x + 1. To obviate the need to look up x twice or read the 1, Fermat allows the programmer to write x :+ to increment x by 1, and x :+(...) to increment x by whatever is between the parentheses. Similarly, x :- to decrement x by 1, and x :-(...) to decrement by (...). However, x must be an integer and less than 2²⁸ in absolute value.

Implicit Multiplication:

If two names are juxtaposed Fermat assumes that they are to be multiplied, as in ordinary mathematical notation. Thus, 5x means 5 times x. As long as you leave a blank between them, the same works for two adjacent variables, x  y. Note: this assumed multiplication does not apply within array expressions or within functions with the Integer option, where the multiplication sign * must always be used. See the later chapters on array expressions and on the "dangerous commands".

More Basic Arithmetic:

\ = integer division, i.e., divide and truncate. In rational mode, in x \y, if x or y is not an integer, the denominators are ignored and the result computed from the numerators alone. This yields an awkward way to extract the numerator of a rational number - the built-in function Numer is more straight-forward. It can also be very confusing, especially when used with divide in the same expression. For example, 4/3\2 = 2.

\ can also be used with arrays, as in [x] \3.

If x and y are polynomials, x \y acts as one would expect in the one variable case. For several variables, sometimes only a "pseudo-quotient" can be computed. See the later chapter on polynomials.

| = modulo. Naively, n|m is the remainder produced by the division of n by m, but there are several complications. Suppose first that n and m are integers. Then the problem is what to do about negatives: should -2 | 3 be -2 or 1? The default in Fermat is to force a non-negative value, but the user may disable this extra step with the interpreter command &| (discussed in the earlier chapter).

In rational mode, if x or y is nonintegral, the denominators are ignored.

| can also be used with arrays, as in [x] | 3.

If x and y are polynomials, x |y acts as one would expect in the one variable case or when y is monic, otherwise only a "pseudo-remainder" can be computed. If x is a rational function ("quolynomial") then x |y is not an error in QFermat.

Beware of sneaky syntax mistakes! (2+y)/3x does not mean (2+y)/(3x). It means divide by 3 and multiply by x.

|...| = absolute value. Note: The argument ... must be a factor, not an expression, i.e., |x+y| is an error; |(x+y)| is okay. Here we are using the following standard grammatical terms: An algebraic expression is a sum of terms. A term is a product or quotient of factors. A factor is either a simple variable, a constant, a function call, or an expression bounded by parentheses.

Numerical Functions

$ = greatest integer function. Can be applied to polynomials, in which case it is done to the coefficients.

 x ^Ùn  means  xⁿ. In rational mode, n has to be a small integer ( < 2²⁸ in absolute value).

÷, or Sqrt(x) = square root.  Computes the (non-negative) square root. In rational arithmetic, this function returns the largest integer less than or equal to the square root. In modular mode, this function is disabled.

n! = n factorial. If n is not an integer, it is truncated first.

Ç = binomial coefficient. Can be invoked in any ground ring. If necessary, n and r are rounded to integers. Ç = option-shift-c.

¿ = random number. This function (which has no argument) returns the next in a sequence of pseudo-random numbers. The numbers are evenly distributed integers between 0 and 2²⁸ - 1. In modular mode, the integers are reduced by the modulus. The precise sequence is always the same. This sameness can be useful in debugging, but is also inconvenient at times. Fermat therefore has a variation, indicated by ¿¿, which factors in the time of day to produce a "truly" random sequence. ¿ is shift-option-/ on the keyboard.

The array form  [x] : = [¿]  or  [x] : = [¿¿]  fills a previously created array with random numbers.  Of course this is not the same as [x] : = ¿.   (Try it and see.)

Additionally, one can set a global variable divisor for random, which is 1 by default. The integers returned by random are divided by this. For example, if you set this constant equal to 2²⁸-1, random will return fractions evenly distributed between 0 and 1. To set this variable, use either the command &¿, which will prompt you for the value, or the imperative form &(¿ = < expression > ).

t = last computed value. Fermat has a hidden " system variable" where all computed scalars are put automatically. This function accesses that variable. Typical use: x := t   to move the value to the variable x. t is option-t [the dagger symbol]. The array form [t] is discussed below under " Array Functions."

S = add up. As in mathematical notation. Here are some examples:

S <  i = 1, n  >   [  1 / i  ] = 1 + 1/2 + 1/3 + ... + 1/n

S < i = 1, n  >   < j = 1, m  >  (  a[i, j]  ) = the sum of the elements in the matrix [a] (assuming that the global initial index variable has been set to 1). Note the set brackets and the square brackets surrounding the expression to be added up. In the second example, round parentheses were used instead of square brackets for clarity; Fermat allows the user to choose either. Any number of indexing assignments (inside the set brackets) listed one after the other, is allowed. The index variables i and j are actual variables in the Fermat session. Modular mode is automatically turned off during the loop control evaluations, i.e., between the angle brackets < and >. S is option-w on the keyboard.

The syntax here resembles that of loops, which are described under "functions" below.

P = multiply out. Standard mathematical notation. Just like S; see above. P is option-shift-p on the keyboard.

Modulus. Returns the numerical value of the modulus now in effect, or last in effect. If not in modular mode, may return a nonsensical value.

Modmode. Boolean function; returns 1 (true) when in modular mode, 0 (false) when not.

Powermod. See Appendix 4.

True. Always returns 1.

False. Always returns 0.

Polynomial and Quolynomial Functions

¶ = Deg. Two distinct uses: degree of a polynomial (or quolynomial), or number of elements in an array. Here we discuss the former. There are two variants: (1) ¶x computes the highest exponent in x (any expression) of the highest precedence polynomial variable. (2) ¶(x, i) computes the highest exponent in x of the i^th polynomial variable, where the highest level variable has the ordinal 1. In modular mode, Deg returns an actual integer, not reduced modulo the modulus. For a quolynomial, it returns the degree of the numerator. ¶ is option-d on the keyboard.

^o = Codeg; "codegree," just like ¶ except computes the lowest exponent. ^o is option-k on the keyboard.

· = polynomial evaluation. x·y replaces the highest precedence variable everywhere in x with y. x·(u = y) allows for replacing other variables (here u) than the highest. x could be a quolynomial but y must be a polynomial only. See the later chapter on "Polynomials".

Fermat also allows evaluation of polynomials at a square matrix. The syntax is x·[y]. The highest precedence polynomial variable in x is replaced with the matrix [y] and the resulting expression simplified. [y] can contain entries that are quolynomials. This command was used in the example in the opening chapter of this manual.

Numb = is the argument a number? If so (as opposed to a polynomial or quolynomial), the result is 1, else it's 0.

Numer = numerator of a quolynomial. Also gives the numerator of a rational number.

Denom = denominator of a quolynomial. Also gives the denominator of a rational number.

Log2 = number of binary digits in the largest numerical coefficient of a quolynomial.

Equal and Equalneg. If-statements can involve a wasteful evaluation of arguments, as in: if x = y[i] then .... when x and y[i] are large polynomials or rational functions. First x is evaluated, which means duplicating its storage, then y[i] is duplicated, etc. Equal and Equalneg do not duplicate existing storage. The syntax is rather obvious: if Equal(x, y) then ... where x and y can be any existing scalar variables, including array references. Equalneg(x,y) is logically equivalent to x = -y. The speedup in time can be profound.

Move and Swap. In the same vein as Equal and Equalneg, Move(x, y) will transfer the data of x into y. y's previous value is discarded and at the end x is 0. x and y must be existing scalar variables. Similarly Swap(x, y) interchanges two such variables' data.

Remquot = remainder and quotient. Remquot(x, d, q) returns the (pseudo)remainder (r, say) of dividing d into x and assigns the (pseudo)quotient to q. Much faster than using x/d because no g.c.d. algorithm is called. c^kx = qd + r, where c is the leading coefficient of d and k = deg(x) - deg(d) + 1 (unless d is a number or c is invertible; then k = 0).

ç = coefficient in a polynomial (or quolynomial), Coef

Suppose first that only one polynomial variable t has been adjoined. Then the syntax of use is either ç(x) or ç(x, n). (ç is option-c on the keyboard.) x can be any expression. n must be a number. In modular mode, modular arithmetic is ignored while n is evaluated. In the first form, without n, the leading coefficient is computed.

When used as an expression, ç(x, n) returns the coefficient of tⁿ in the polynomial x. If x is a quolynomial, the denominator is ignored.

If there are several polynomial variables, the exact coefficient desired is specified by listing the exponents of the variables in precedence order, highest first. For example, if t, u, and v have been adjoined in that order, and

then ç(x, 1, 2) = 7, ç(x, 1, 1, 0) = -8, ç(x, 0, 2, 1) = -5, ç(x, 2) = 3u - 3t - 3, ç(x, 0, 0) = -t³ - 3t - 1, and ç(x, 0, 0, 0) = -1.

£ or Lterm = leading term of a polynomial. £ is option-3 on the keyboard. Follow it with a polynomial expression, whose leading term will be computed.

Lcoef = leading numerical coefficient of a polynomial. Unlike ç, always returns a number.

^¢ = derivative of a polynomial (or quolynomial) with respect to the highest precedence variable (the last attached). This is option-shift-] on the keyboard. Don't confuse it with apostrophe. Precede it with an expression to be differentiated, such as x^¢

GCD = greatest common divisor, as in GCD(x, y), x and y can be numbers or polynomials, but not quolynomials. If numbers, the result is always positive, except that GCD(0, 0) = 0. GCD(0, x) = x if x is not 0. If they are both polynomials, the result always has positive leading coefficient. In rational mode the result is always normalized to have all coefficients integral and be of content 1. In cases where the ground ring is a field, the result has leading coefficient 1.

Content = the content of a polynomial; i.e., the GCD of all its coefficients.

Numcon = numerical content, the GCD of all its numerical coefficients.

¥ = Var. Followed by an expression that evaluates to a positive integer, as in Var(i) or ¥i, returns the i^th polynomial variable, counting the highest (last created) as 1. This is option-y on the keyboard.

Height = the difference between the levels (ordinals) of the polynomial variables in an expression. For example, if three variables have been attached, say t, u, and v in that order, and x = v+t, then Height(x) = 3. If y = u + t, then Height(y) = 2. Height(t) = 1 = Height(u).

Level = the ordinal position of the highest precedence polynomial variable in an expression. For example, if three variables have been attached, say t, u, and v in that order, and x = v+t, then Level(x) = 1. If y = u + t, then Level(y) = 2. Level(t+2) = 3. Level(u) = 2.

Raise = Two forms: Raise(x) and Raise(x, i). In the first, replace each polynomial variable with the variable one level higher. In the situation of Level, above, Raise(y) = v+u. Raise(t+2) = u+2. Raise(x) is an error. The second form allows the user to provide an expression i that evaluates to a positive integer, and raises x that many levels, if possible.

Lower = The inverse of Raise. See above.

Rcoef = change the coefficient of a term within an existing variable. For example, if only one polynomial variable t exists, Rcoef(x, n) : = y will change the coefficient of tⁿ in x to the expression y. y must be a number.

With several polynomial variables, the idea is similar to ç, Coef. In Rcoef(x, n₁, n₂, ...) : = y, y must be suitable to be such a coefficient, else an error occurs. For example, if t, u, and v have been adjoined in that order, and

In Rcoef(x, ...) : = ..., x must be a polynomial, not a quolynomial. But in the latter case, the commands Rcoef(Numer(x), ...) : = ... and Rcoef(Denom(x), ...) : = ... are useful.

Totdeg = total degree. See appendix four.

Divides = Divides(n,m): does n divide evenly into m? See Appendix 4.

Deriv = Deriv(x, t, n) returns the n^th derivative of x with respect to t

Array Functions

Most of the ordinary arithmetic built-in functions can be applied to arrays, as in [y] : = $ [x]. See Appendix 2, last column.

Sparse arrays are implemented in Fermat. This is an alternate mode of storing the data that constitute the array. In an " ordinary" n X m array, nm adjacent spots in memory are allocated to hold the entries in the array. If an array consists of mostly 0's, this is wasteful of space. In a Sparse implementation, the non-zero entries only are stored via list structures. The fact that an array has the Sparse or the " ordinary" storage structure is often transparent to the user; however, some of the functions listed below do not work on Sparse arrays. More on Sparse arrays later, under "Variables and Arrays," " Expressions and Assignment," and " Array Expressions." See also "sparse access loops" in the index.

D, or Det, is used in several ways to compute a scalar from an array argument. (D = option-j.) If used by itself on a square matrix, D is determinant. D#([x] = a) returns the number of entries in [x] that equal a

Similarly D#([x] > a) and D#([x] < a) compute the number of entries of [x] larger or smaller than a. In modular mode, the order is the obvious one on the set of elements of Z_n = { 0,1,2,3, ..., n-1 }. If any entry is a polynomial, an error results. D^Ù[x] returns the index of the largest element of [x] (in column major order if [x] is a matrix). D_[x] returns the index of the smallest element of [x]. D_ + [x] returns the index of the smallest nonzero element of [x], or -1 if there is no such element.  (Typical use:  D_ + |[x]| . [x] here can be replaced by any array expression.)

A few more comments about determinant. Fermat allows a wide range of data types for the entries of a matrix - integers, rationals, floats, modular numbers, polynomials, quolynomials, etc. No single method is most efficient for all cases. Fermat uses three basic methods: expansion by minors, Gaussian elimination, and reducing modulo n for some n's. The last of these is used for matrices of integers or polynomials with integer coefficients. The actual determinant can be reconstructed from its values modulo n (for a "good" set of n's) by the Chinese Remainder Theorem (see Knuth volume 2). Alternatively, it is often possible to work modulo an easily computed "pseudo determinant" known to bound the actual determinant. Gaussian elimination is applicable in all situations - all one needs is the ability to invert any nonzero element in a matrix. If the matrix is small enough, expansion by minors is faster (see the discussion for the interpreter command &D.) Gaussian elimination can be nontrivial and even problematical in modular arithmetic over a nonprime modulus, in polynomial rings, and in polynomial rings modulo a polynomial. Fermat has heuristics to guide its choice of method.

For many matrices of polynomials, especially over the ground ring of integers or rationals, it is faster to figure out the degree of the determinant, evaluate the determinant at a set of values (say, integers), and then interpolate to compute the determinant from these values. A short Fermat program to do this is given in Appendix 3, example 2. This method is built into QFermat, in which the interpolation determinant algorithm is probabalistic, with very high probability of success. It is stunningly fast, especially for two or more variable polynomials.

Nonetheless, if there are many polynomial variables and the matrix is sparse, expansion by minors can be by far the fastest method. Setting the determinant cutoff (with &D) at least as large as the number of rows will force Fermat to do this method. This is true of Sparse matrices as well as " ordinary."

Adjoint = adjoint of a square matrix.

Chpoly = characteristic polynomial of a square matrix. Parentheses mandatory. See Appendix Four.

Sumup = add up the elements of an array.

Trace = trace of a matrix.

Minpoly A sophisticated probabalistic algorithm for computing the minimal polynomial of matrices. See Appendix Four.

Altmult. Multiply two matrices using the algorithm of Knuth volume II, p. 481. A big time saver when multiplication in the ring is much slower than addition. Especially good for Polymods (see that chapter). Syntax is Altmult([x], [y]).

Altpower. Use Altmult to take a matrix [x] to the power n. Syntax is Altpower([x], n).

MPowermod([x], n, m) computes [x]^n mod m, analagously to Powermod. See Appendix Four.

^TM = transpose matrix, as in [y] : = ^TM[x]. This symbol is option-2 on the keyboard.

¨ refers to the diagonal of a matrix, as in ¨[y]: = [x]. [x] is considered a linear array. The diagonal of [y] becomes the entries of [x]. If the name [y] does not yet exist, a new square matrix will be created with off-diagonal entries 0. If square matrix [y] of the right size (i.e., rows equal to the number of entries of [x]) does exist then the off-diagonal elements are not changed.

Dually, ¨ can be used on the right side of an assignment, as in [y] : = ¨[x], which sets [y] equal to a linear array consisting of the diagonal elements of [x]. [x] does not have to be square.

There is a small subtlety in nonsquare arrays. ¨ expects the number of diagonal entries to equal the rows of the matrix. For example, if [e] is a 4 X 3 matrix, ¨[e] : = [(9,9,9,8)] is ok - but only the three 9's will go into [e].

¨ is option-shift-v on the keyboard.

To create a diagonal matrix with all entries equal to a constant, say 1, you can use the easier form   [x] : = [1], if [x] already exists as a square matrix.

¢[x] = Cols[x] = number of columns of array [x]. ¢ is option-4 on the keyboard.

¶ = Deg = degree of a polynomial (or quolynomial), or number of elements in an array. In the first case, follow it with any expression. If that expression is a number, then of course the result is 0. In modular mode, it returns an actual integer, not reduced modulo the modulus. For a quolynomial, it returns the difference in degrees of the numerator and denominator.

When used with arrays the next character must be the square bracket, '['. ¶[x] = total size of array [x] (rows X columns).

[t] = last computed array. Analogous with the preceding use of t (option-t) Fermat has a hidden system array. If you type the command  [x] + [y], arrays [x] and [y] will be added and, since you didn't provide an assignment of the result, the result will go into the system array. You can later access it by typing, for example, [z]: = [z] + [t]. Subarrays cannot be used with [t].

Note that the command [z] + 2 will display 2 plus every element in [z], but typing 2 + [z] will produce an error. In reading from left to right, Fermat encounters the 2 first and cannot later switch to array parsing.

f = concatenate arrays; glue two arrays together to form a larger one, as in [z] : = [x] f [y]. Neither array can be Sparse. See the chapter on array expressions. f = option-f.

Iszero = is the argument (an array) entirely 0? If so, return 1, else return 0. Syntax: Iszero[x].

Switchrow = Interchange two rows in an array. Syntax: Switchrow([x], n, m). The matrix itself will be changed.

Switchcol = Interchange two columns in an array. Syntax: Switchcol([x], n, m). The matrix itself will be changed.

Normalize = Normalize a matrix. The matrix must not be Sparse. Convert it to a diagonal matrix, i.e., all off-diagonal entries will be 0. The matrix itself will be changed. If requested, Fermat will also return the change of basis matrices that it used in normalizing. Possible invocations include Normalize([x]) and Normalize([x], [a], [b], [c], [d]). In the second case, matrices [a], [b], [c], and [d] will be returned that satisfy [a]*[x¢]*[b] = [x], where [x¢] is the original [x], and where [c] = [a]^-1 and [d] = [b]^-1. The value returned by Normalize is the rank of [x].

The inverse change of basis matrices [c] and [d] are provided because it is far faster to compute the inverses of [a] and [b] " along the way" then it is to use the built-in matrix inversion command after Normalize finishes. However, the computation of each of these matrices adds to the total execution time, and your application may not need them, or perhaps may need only [b] and [d]. Therefore, Fermat allows you to omit any one(s) you wish. For example, Normalize([x], ,[b], , [d]) and Normalize([x], [a], , [c]) are possible. Every comma promises that an argument will eventually follow. Therefore, Normalize([x], [a], [b],[c], ) is illegal. See also the commands FFLU and FFLUC.

Colreduce = Column reduce a matrix. The matrix may NOT be Sparse. By column manipulations, the argument is converted to a lower triangular matrix. The matrix itself will be changed. If requested, Fermat will also return the change of basis (or conversion) matrices that it used in normalizing. Possible invocations include Colreduce([x]) and Colreduce([x], [a], [b], [c], [d]). In the second case, matrices [a], [b], [c], and [d] will be returned that satisfy [a]*[x¢]*[b] = [x], where [x¢] is the original [x], and where [c] = [a]^-1 and [d] = [b]^-1. The value returned by Colreduce is the rank of [x].

As in Normalize, one may omit computing some of the conversion matrices, for example, Colreduce([x], , [b], , [d]) or Colreduce([x], [a], , [c]).

Rowreduce = Row reduce a matrix. The matrix must be Sparse. Exactly like Colreduce but for sparse arrays and row reduction.

Smith = Normalize a matrix of integers into Smith normal form. The matrix may be Sparse. This function can only be used in rational mode, and will work only if every entry is an integer. (Any denominator encountered will be ignored, with unpredictable results.) By row and column manipulations, the argument is converted to a diagonal matrix of non-negative integers. Furthermore, each integer on the diagonal divides all the following integers. The set of such integers is an invariant of the matrix.

The matrix itself will be changed. If requested, Fermat will also return the integer change of basis (or conversion) matrices that it used in normalizing. Possible invocations include Smith([x]) and Smith([x], [a], [b], [c], [d]). In the second case, matrices [a], [b], [c], and [d] will be returned that satisfy [a]*[x¢]*[b] = [x], where [x¢] is the original [x], and where [c] = [a]^-1 and [d] = [b]^-1. The value returned by Smith is the rank of [x].

The change of basis matrices [c] and [d] are provided because it is faster to compute the inverses of [a] and [b] " along the way" then it is to use the built-in matrix inversion command after Smith finishes. However, the computation of each of these matrices adds to the total execution time, and your application may not need them, or perhaps may need only [b] and [d]. Therefore, Fermat allows you to omit any one(s) you wish. For example, Smith([x], ,[b], , [d]) and Smith([x], [a], , [c]) are possible. Every comma promises that an argument will eventually follow. Therefore, Smith([x], [a], [b],[c], ) is illegal.

If you do not require any conversion matrices then it is possible to greatly speed up Smith in most cases by working modulo a "pseudo-determinant", a multiple of the gcd of the determinants of all the maximal rank minors (see Kannan and Backem, SIAM Journal of Computing vol 8, no. 4, Nov 1979). Do this in Fermat with the command MSmith. Not to work modulo some number invites a horrendous explosion in the intermediate entries. On the other hand, for relatively small matrices or sparse matrices, it's faster to forgo the modding out. Fermat will compute the pseudo-determinant if the matrix is Sparse. If you already have a pseudo-determinant pd to use, use the syntax MSmith([x], pd). (If the matrix is not Sparse, you must use the latter method. Pseudet may be helpful.)

Hermite = Column reduce a matrix of integers. The matrix may be Sparse. This function can only be used in rational mode, and will work only if every entry is an integer. (Any denominator encountered will be ignored, with unpredictable results.) By column manipulations and row permutations, the argument is converted to a lower triangular matrix of integers. All diagonal entries are non-negative.

The matrix itself will be changed. If requested, Fermat will also return the integer change of basis (or conversion) matrices that it used in normalizing, exactly as in Smith, above.

If the matrix is "large" and "dense" a horrendous explosion is possible in the off diagonal intermediate entries, and in the entries of the conversion matrices.

Redrowech = the reduced row echelon form, for elementary matrix equations of the form AX = B. (Other Fermat commands do column manipulations as well, which could be used to solve AX = B but take an extra step.) Invoke with Redrowech([a]), where all columns but the last in [a] represent the matrix A and the last represents B (i.e., Redrowech never pivots on the last column.) Altnately, Redrowech([a],[u],[v]) will return in [u] the transition matrix used in normalizing [a]. [v] is [u]^-1. As in other similar Fermat commands, you can also do Redrowech([a], ,[v]).

Minors: extract minors from sparse arrays. The syntax is e.g. [y] : = Minors([x],[r],[c]). [x] is an existing sparse array. [r] and [c] are existing ordinary arrays specifying the rows and columns to be extracted. The result is stored in [y], which will be a new sparse array of the right dimensions. [x] is untouched.

FFLU and FFLUC are for fraction-free LU factorization of matrices. See the two articles in the September 1997 SIGSAM Bulletin: "Fraction-free Algorithms for Linear and Polynomial Equations," by Nakos, Turner, and Williams; and "The Turing Factorization of a Rectangular Matrix," by Corless and Jeffrey.
    FFLU is invoked as: FFLU([x], [p], [l], [a], [b]). [x] is the n X m matrix to be factored. [p] is an n X n diagonal matrix consisting of the pivots used, [p] = diag(p_1, p_2, ... , p_(n-1), 1). [l] is the unit lower triangular matrix, the first factor. [a] (optional) is the n X n permutation matrix of row swaps. [b] (optional) is [a]^-1. At the end, [x] is in upper triangular form. Let [z] be a copy of the original [x]. If [f] and [g] are the matrices called f_1 and f_2 in the Corless and Jeffrey article, then at the end one has [f]*[a]*[z] = [l]*[g]*[x]. Note that [f] and [g] are not computed by FFLU; however it is obvious how to get them from [p].
    FFLUC allows column swaps as well as row swaps. In this way, the size of the pivots can be reduced. FFLUC is invoked as: FFLUC([x], [p], [l], [a], [b], [c], [d]). As above, [x] is the n X m matrix to be factored. [p], [l], [a], and [b] are the same as above. At the end, [x] is in upper triangular form. [c] and [d] (optional) are permutation matrices coming from column swaps ([d] is [c]^-1). More information is in Appendix Four.

Several other functions are described in Chapter 15 and Appendix Four.

The user creates names for scalar and array variables, for files, for polynomial variables, and for functions. All but file names must be less than or equal to 10 characters long and consist entirely of lower case letters, upper case letters, the underline "_", and the 10 digits. Spaces and tab marks are ignored. Fermat distinguishes between upper and lower case letters.

The names of variables (scalar, polynomial, or array) must begin with a lower case letter. When referring to an entire array, array names are surrounded by the brackets "[" and "]".

The names of functions must begin with an upper case letter.

The maximum length of 10 may be lowered by using the change name length command,  &l. Upon entering this command, the user is prompted to enter an integer between 1 and 10. The main reason for doing so is that in Fermat, if two names are juxtaposed with no arithmetic operator between, it is assumed that they are to be multiplied, as in mathematical writing. Thus, no matter what the maximum name length, one can write expressions like

Note that if name length is set too small, many built-in functions like Numer can't be recognized.

Changing the namelength is really a somewhat archaic holdover from early versions of Fermat.

Names of files can be just like variable names, or, alternatively, can conform to MPW's file name rules. In the latter case in Fermat, the name must be surrounded by (single) quotes. For example, if you enter the save command &(S = stuff), Fermat will save your stuff to a file called `stuff' in the default directory. To save to a file in another directory, enter the entire name surrounded by quotes, such as `HD:MPW:algebra:stuff'. Any file name that is an illegal Fermat variable name (for example, one containing a colon or the underline _) must be surrounded by quotes. If you wish, you can simply adopt the policy of always putting file names in quotes.

Blanks are not allowed in a name. Nor, for certain technical reasons, can any file name contain W, option-z.
 
 

Variables and Arrays
 
 
 

The name of a variable (see preceding chapter) must begin with a lower case letter. A variable is created by assigning a value to the name.

Fermat allows one or two dimensional arrays. The name must begin with a lower case letter. Before using an array, it must be created. To explicitly create an array called b of 10 elements, use   Array b[10]; to create a 3 X 3 matrix c use  Array c[3,3]. Several arrays can be declared on one line, such as Array x[3,3], y[4,4], z[60,60] Sparse, a[7,7]. In modular mode, the dimensions are evaluated ignoring modular arithmetic. There can be both a scalar variable and an array of the same name.

The maximum array size is 90000. The maximum total size of all arrays is 512000. (This does not apply to Sparse arrays, for which there are no intrinsic limits. However, both rows and cols must be < 2²⁸, otherwise integer overflow will occur within the Fermat interpreter. This limit will probably be removed in future versions.)

When an array is created, its values are undefined.

Sparse arrays are implemented in Fermat. This is an alternate mode of storing the data that constitute the array. In an " ordinary" n X m array, nm adjacent spots in memory are allocated to hold the entries in the array. If an array consists of mostly 0's, this is wasteful of space. Furthermore, multiplying two such matrices [x]* [y] is wasteful of time, since almost all individual multiplications x[i,k] * y[k,j] result in 0. In a Sparse implementation, only the non-zero entries are stored in a linked list structure, in which each node contains a pointer to the actual data item and the row and column of the item. The linked lists are maintained in such a way as to facilitate matrix operations.

A Sparse array is created by following the creation command with the keyword "Sparse," as in   Array x[5,5] Sparse. There is no limitation on the size of the matrix in QFermat. Sparse arrays do not contribute to the total array size limit. An array [x] already created can be converted to Sparse format with the command Sparse [x].

The fact that an array has the Sparse or the " ordinary" storage structure is often transparent to the user. More on Sparse arrays below, under " Expressions and Assignment" and " Array Expressions."

Arrays are accessed, or indexed, with the syntax x[i], where i can be any expression evaluating to a real integer. In modular mode, i is evaluated ignoring modular arithmetic. One has a choice of how to label the first element of an array - usually one thinks of the first element as x[1], but sometimes x[0] is more convenient. The default in Fermat is x[1]. This can be changed by entering the command &a, which switches the initial array index to 0. Entering &a again switches back to 1. Note that this is not a property of any particular array, but of how all arrays are indexed. It is not a property of arrays as such at all. Creation of arrays is not affected - it's still x[8] for an array with 8 elements. For two dimensional arrays, the first element is x[0,0].

Dynamic Allocation of Arrays

Arrays that are no longer needed can be freed to provide space for new arrays. This is done with the cancel command, whose syntax is @[x], or, to free several, @([x], [y], [z]). As arrays are created and destroyed, space is allocated and freed within a linear list of available space in the order that the commands are received. If you have several arrays and free the first one created, the others are moved up to occupy the empty slots. Actually, this moving is not especially time consuming since only pointers need to be changed. Nonetheless, if you are going to do a lot of creating and cancelling of arrays, it is best to follow the last in, first out policy, thereby treating the linear list as a stack.
 
 

Expressions and Assignment
 
 

An expression is any algebraic formula following the usual rules of precedence and involving scalar variables, constants, function calls, or interpreter commands. Example:

The syntax for assignment is

There is a shortcut increment command. Fermat allows the programmer to write x :+ to increment x by 1, and x :+ (...) to increment x by whatever is between the parentheses. Similarly, x :- to decrement x by 1, and x :-(...) to decrement by (...). However, x must be an integer and less than 2²⁸ in absolute value.

An innocuous statement like x := x + y can cause problems if x and y are large polynomials with thousands, or even millions, of terms. The problem is that in evaluating the right side, x's storage is duplicated. That may blow out the RAM. This is silly since x is going to be changed anyway. Therefore there is an alternate syntax using the symbol * to indicate that the value and storage of a variable are disposable, namely x := *x + y. Variants are x := *x + *m[2,3] and x := *x * *y. Should the user interrupt Fermat during the evaluation and inquire what x or y is, he will find it has been set to 1. See also Move and Swap.

When a variable is assigned a value, it is put on an " environment stack" of all active names. Any previous value is lost. The cancel or rubout command @ removes the name from the stack and destroys the value. The command &v displays the active variables.

Similarly, arrays are put on a stack of active array names. With arrays, however, every act of creation, such as Array  a[3,3] puts a new array called a of dimension 3 X 3 on the stack. Previous arrays called a are not lost - they are just pushed down. Any reference to array [a] is to the top most one. To reaccess the lower one(s), cancel the top one or rename it using the "rename command", Rname[c] : =  ¢[d]¢.

Mixing arrays and scalars in an expression is sometimes legal. This is clearly not:

You can mix arrays and scalars in an array assignment statement,

To set [c] equal to [b], the command is [c] : = [b]. In this case, [c] does not have to have been explicitly created before; it will get the same dimensions as [b]. If an array [c] of the same dimensions as [b] already exists and is on the top of the stack of [c] names, its old entries will be destroyed and new ones created equal to those of [b]. Otherwise, a new version of [c] will be created.

Constant and Diagonal Matrices:

 [b] : = 2  will set every component of b to 2.  [b] : = [1]  will set [b] equal to the identity matrix, if [b] has been declared to be a square matrix. (If there is no [b] yet, it is an error. If there is a non-square [b], a new square [b] will be created having the number of rows of the other [b].) Any constant may be substituted for the 1, including polynomials. However, a polynomial inside the brackets must be written using Fermat's conventions of parenthesation and precedence, such as [(5t²+2t+1)u² + (3t-1)u + 7t²-3t+1], assuming that polynomial variables t and u have been created, in that order. For more information, see the later chapter on polynomials, about "polynomial read-in."

Diagonal matrices are Sparse arrays.  [b] : = [1]  is an error if [b] has not been declared Sparse.

Here is a further example. Suppose [a] has been declared to be 4 X 4, but [b] has not been created. Then this will work:  [b] : = [a] + [1]. The interpreter will figure out that the identity matrix [1] should be 4 X 4, because [a] is. But just saying  [b] : = [1]  won't work - the interpreter has no way of knowing how big [1] is supposed to be.

You can't assign an ordinary array to a sparse array. However, you can do it the other way around.
 
 

Array Expressions
 
 
 
 

In Fermat one can write expressions involving matrices and scalars that follow familiar mathematical syntax, such as

Fermat returns the value 0 after an array assignment. It does not automatically display the new array.

In array expressions the multiplication sign * must be used to effect multiplication. In ordinary expressions, if two variables or factors are juxtaposed, multiplication is assumed. That won't work here. The reason is ambiguities like s[x]. Is this s times [x], or is it entry x in array [s]?

Ordinary and Sparse matrices can be mixed in expressions. If any term in a matrix expression is an ordinary matrix or is a scalar, the result will be ordinary (unless it would too big - then it's an error); otherwise it will be Sparse. This provides an inelegant mechanism for converting a Sparse matrix, say [a], to an ordinary one:  [x] : = [a] + 0.

Fermat allows subarray expressions. That is, part of an array [c] can be assigned part of an array [a]. For example,

Subarrays can be used in either the source or target of an assignment statement (right side or left side).

In subarray assignments, a vector declared to be one-dimensional (like a[5]) is treated as a column vector, i.e., a[5,1].

Both  ![x[...]]  and  ?[x[...]]  work with subarrays. ¨ and D work with subarrays.

Subarray cannot be used with Sparse matrices.
 
 

Getting Data Into Arrays

Besides subarray expressions and the interrogation command ?[x], another way to easily get data into an array is with list input, similar to list output, described above. For example,

Yet another way to get data into a matrix is by setting up the data on the screen in rectangular array in the same format as Fermat's short form display of matrices (which has been discussed previously under the `display' built-in function). For example,

> [y] := [[  1,

3,

12,   ,,

0,

24,

-5   ]]

Note the commas, the double square brackets, and the continuation character. Any expression may be used to specify an entry, not just constants. In the MPW versions, highlight both lines with the mouse and then press < enter > . In the stand-alone versions, just put the cursor at the end and hit < return > .

For a Sparse array, one may use as well the long form, as in:

> [x] := [ [ 1, [2, -1],  [3, 19]]  ,,

[ 2, [1, 8],  [2, -2]]  ,,

[ 3, [2, -1],  [3, 9]]  ]

The entries do not have to be in increasing column order within the rows. Furthermore, repeated columns are allowed, in which case the sum of all the given terms ends up in that column.

In the MPW versions, highlight all with the mouse and press < enter > . In the stand-alone versions, just put the cursor at the end and hit return.

Yet another way to easily get data into an array is with "pseudo-loops". For example,

<exp₇> must be an algebraic expression - no loops, ifs, etc. (Of course if you want to create a matrix for which the expression <exp₇> would have to have ifs or loops, use a function to do so.) Each of the indexing expressions is truncated to an integer, if necessary, and must be a small integer ( < 2²⁸). All six of them must be at least the array initial index. <exp₃> and <exp₆> are optional, as in for-loops. This command creates an <exp₂> X <exp₅> matrix if the array initial index is 1, or an (<exp₂> + 1) X (<exp₅> + 1) matrix otherwise. If <exp₃> or <exp₆> is not 1, then a matrix is created which has some undefined elements.
 

Arithmetic of Arrays

Multiplication of arrays [a]*[b] follows this hierarchy: If [a] is n X m and [b] is m X p, an n X p is created, as is usual in matrix multiplication. If [a] and [b] do not match this way but they are of the same total size, then component-wise multiplication is done. Otherwise it's an error.

Similarly for division. If [b] is square and [a] has the same number of columns, [a]  /  [b] means [a] times the inverse matrix of [b]. Otherwise it means componentwise division, if the sizes are the same.

[a]  |  3 takes each entry of [a] modulo 3. If [a] and [b] have the same total size, [a] | [b] returns each entry of [a] modulo the corresponding entry of [b] (otherwise it's an error). Similarly for [a]  \ [b] and [a]  \ 3 .

2*[a], or [a]*2, multiplies every component of [a] by 2. [a] + 3 adds 3 to every component of [a], and so forth. Suppose you want a 4 X 4 square matrix [y] with 7's on the diagonal and 1's everywhere else. Use  [y] : = ¨[(6, 6, 6, 6)] + 1.

You can add or subtract arrays of the same total size. If they aren't of the same declared dimensions, such as adding a 2 X 3 to a 3 X 2, the result may not be what you thought (try it).

Array exponentiation is implemented. The syntax is just like scalars, [x]^Ùn. n must be a real integer. [x] must be a square matrix. If n is negative, [x] must be invertible.
 

Other Miscellaneous Array Operations

All arrays can be accessed via the syntax x[number], even if they were declared to be 2 dimensional. This is occasionally useful. For example, if you have an array x[4,4], x[7] means x[2,3]. (Assuming that the array initial index is 1. See the built-in function &a.)

Matrices can be normalized with the built-in functions Normalize and Smith. Their kernels can be computed with Colreduce and Hermite. See the chapter on built-in functions for other array built-ins.

Arrays can be " adjoined" or "concatenated" with the operator f. (This is option-f on the keyboard; its resemblance to an integral sign is appropriate because the two have been " integrated.") The syntax is  [z] : = [x]  f  [y]. If two arrays have the same number of columns, the result is as if one array were put " under" the other. If not but they have the same number of rows, it is as if they were put next to each other. Otherwise an error results. It is also legal to write [w] : = [x]  f  12, in which case 12 is appended to the end of [x] and a one-dimensional [w] is the result. Similarly, the scalar could be the first argument. This command is mostly of use for manipulating strings (see the next chapter on character strings).

It's very convenient to write expressions like

There are syntactic restrictions on array expressions that do not apply to scalar expressions. For example, array expressions may not contain unlimited nesting of parentheses. An expression like x*(x+x*(x+x*(x+x*(x+y)))) may very well produce an error if x and y are replaced by arrays. Such complex syntax is not necessary. Instead, first set [d] : = [x]+[y], then multiply [x]*[d], etc.

With either syntax  [y] : = 1/[x] or  [y] : = [x]^Ù-1, the inverse of [x] is computed via Gaussian elimination, modular methods, or the Leverrier-Faddeev algorithm (See example 4, Appendix 3). The various versions of Fermat have heuristics for choosing a method.
 
 
 

The Array of Arrays
 
 
 
 

Fermat does not allow general three-dimensional arrays, but there are times when they are very convenient. For example, a group may be represented as a set of matrices, and one would naturally wish to access the ith element of the group as G[i], or something like that. To provide for this, Fermat has a system wide array of arrays. Two thousand pointers are provided, each of which can be set to "point to" or "be an alias for" an array that has already been created in the usual manner. These pointers are accessed by the name f  (option-shift-7).

Suppose that x[3,3] and y[2,2] have been created. To associate the first pointer with [x] use the command f[1] : = [x]. Similarly f[2] : = [y] associates the second with [y]. Then f[1][2,2] is the same as x[2,2], f[2][1,2] is the same as y[1,2], etc. Note Carefully: f[1][2,2] is not a duplicated copy of x[2,2], rather f[1][2,2] is another name for x[2,2]. The assignment f[1][2,2] : = 3 changes x[2,2].

Note that the array of arrays allows a more general data structure than typical three-dimensional arrays, because the arrays being indexed are arbitrary.

The pointer f[n] cannot appear by itself on the right in any assignment statement. Of course, an element of an array, such as f[n][k,m] can appear there. In other words, you can't do [x] : = f[1]. When assigning to a pointer, the right side must be a simple array name, no expressions and no subarrays.

Display and subarray work with array of arrays. Changing the array initial index with &a affects f. Interrogation from the terminal (the ? command) does not work with f.

Beware of dangling pointers! If f[1] is associated with [x], and then [x] is cancelled, further use of f[1] will probably crash the system. Perhaps f  belongs in the chapter on "Dangerous Commands"!

Example one in Appendix 3 would have been cleaner using f.
 
 
 

Functions
 
 
 

All programming languages have the idea of " subroutines" that perform specific, often repeated tasks. In Fermat, these are called "functions."

Every function returns a value, the last expression it computes. (Recall that assignment statements within functions yield the result 0.) One can also use the Return built-in function to exit a function with a certain value, as in Return(x).

Unlimited recursion is allowed.

The syntax of a function definition is

The left hand side must look like <funcname>(x, y, z, ...) or just <funcname> . A <funcname> is a name that starts with a capital letter. The right hand side is explained below under "The Main Body of the Function."

The name of a function must begin with a capital letter. The user can redefine a function F simply by typing a new definition. The function definitions are put on a stack, so any reference to F is to the topmost. @F destroys the topmost F. @ < F > destroys, or purges, all previous definitions of F. The commands  &f, or &F  display the current function definitions. To also see the body of the functions, enter &f*.

It is recommended that most functions be created in a file with a text editor before Fermat is invoked (save the file as "text only"). However, it is possible to edit your function definition from the terminal within an (MPW) Fermat session, have it occupy several lines, and enter the new version by selecting it with the mouse and hitting < enter > . (With the stand-alone version you must copy the old function, paste it after the cursor, make changes there, and then hit < return > .) To facilitate this editing, when Fermat displays a function it adds the continuation character to each line.

The order that the functions are defined (in the input file or the Fermat session) is completely irrelevant. Of course, if you invoke F and F invokes G, G must have been defined.

In F(x, y, z, ...), x, y, z, ... are the parameters. When the function is called, the interpreter evaluates the arguments and puts the parameters on the environment stack with those values. This mechanism of parameter - argument assignment is called call by value. When the function ends, those names (and their values) are popped off the stack. This is the same basic strategy used by APL, Lisp, and other languages, but is unlike Pascal or Fortran. If you have a variable called x whose value is 3, and then you call a function F with parameters x,y, while F is executing x means F's parameter. When F is finished, its parameter x is popped off, allowing your original x with value 3 to become visible again.

Fermat allows another kind of parameter - argument correspondence called call by value-result. Syntactically, a value-result parameter is indicated by putting the exponentiation sign ^ in front of the name in the parameter list of the function, as in F(x,  ^Ùy). The argument passed to y must be a single variable name, not an expression. This provides a mechanism for allowing the changes made to y to survive the termination of F. Suppose you invoke F with F(3, z). Then as the parameters are matched with their arguments, y gets z's value. As the function executes, any change to y, such as y : = y + 1, is done only to y. When the function ends, z gets y's value. (Therefore, you must not have cancelled z, although Fermat should be able to catch this mistake.) For more information, consult any text on the theory of programming languages.

In QFermat, the same syntax in some built-in functions implements call-by-reference. For example, time and compare Terms(x) and Terms(^x) for a large x.

Local Variables

A parameter not matched by an argument when the function is called becomes a local variable with initial value 0. For example, if you define F(x, y, z) and invoke F with F(a, b+c), z is initialized to 0 and cancelled when F ends. In the meantime, z is on the environment stack, suppressing or hiding any earlier z's. Any function that F calls has automatic access to z, as long as it (or some other function) doesn't create another z

If z is a value-result parameter, it must be matched with an argument at function invocation time, and so cannot become a local variable.

The Main Body of the Function

The right hand side of a function (abbreviated <r.h.s.> ) is either an expression, an assignment, an array expression, a for-loop, a while-loop, an if-statement, or a sequence of these separated with semicolons. The function definition ends with a period. The only other places were periods are allowed in a function definition are inside literals and inside comments.

If-Statements

The syntax of an if-statement is

where the first alternative is chosen if the condition is true, and the second (optional) alternative if it is false. Note the reserved word "fi". This if-fi syntax originated in Algol68. If the second is absent and the condition is false, nothing happens - it's as if the statement were not there (except for possible side effects introduced by the evaluation of the condition).

There are two ways to form a <condition> . The first is simply to provide any expression. If the expression evaluates to 1, that's interpreted as true; anything else is false. You can set a variable, say, condition to 1, and write loops like

Secondly, (and more conventionally) define a simple condition as:

While-Loops

The syntax of a while-loop is

Note the " od." The condition is evaluated, and, if true, the loop is entered. At the end of the statement(s) in the loop, the condition is evaluated again, and, if true, the loop is entered again. This pattern repeats until the condition is false.

For-Loops

The syntax of a for-loop is

The first two expressions are the initial and final values for the index variable. The optional third expression is the size of the increment. It can be negative. At the beginning of the loop, these three expressions are evaluated and truncated to integers, if necessary. The resulting integer in all three cases must be less than 2²⁸ in absolute value. After each pass, the index variable is incremented. If it exceeds (or is less than, for a negative increment) the terminating value, the loop is over. After the conclusion of the for-loop, the index variable has value one more than the terminating value (or one less if the increment was negative). It is possible for the " <r.h.s.> " to contain a statement that (apparently) changes the index variable. This confusing practise should be avoided. It may cause a crash.

The words if, then, else, for, while, do, from, by, fi, and od are key words and should not be used for any other purpose inside functions.

Early Termination of Loops

Fermat has no "goto" statement; instead there is a "leave loop" command & > , a "cycle" command &], and an " exit function" command &} .   "Leave loop" and " exit function" are self-explanatory. The cycle command causes Fermat to skip the remaining statements in the loop body and return to the condition or incrementation heading the loop.

Note that the leave loop command & > is independent of function structure. That is, if F calls G and & > appears in G after any loop in G, then upon return to F, the first loop that Fermat enters (or had entered) will be immediately exited. In general, & > forces immediate termination of the next (or present) loop that Fermat enters (or has entered).

Examples

Sparse Access Loops There is a need for a way to work efficiently with sparse arrays. For example, suppose you have a sparse array of 60000 rows and 50000 columns with only 10 or so entries in each row (this is quite realistic). Suppose you wanted to add up all the entries. Naively, one could write something like:

for  i  = 1,60000  do  for  j = 1,50000  do  sum  : =  sum + x[i,j]  od  od

But this will do 3,000,000,000 additions, almost all of which are adding 0! This is a preposterous waste of time. The solution is "sparse column access loops" for sparse arrays. The syntax is, continuing the example above,

for  i  = 1,60000  do  for  j = [x]i  do  sum  : =  sum + x[i,j]  od  od.

"for j = [x]i do" means find the i^th row of [x] and let j run down it - of course encountering only the entries actually there! So j takes on whatever the column indices are in which x[i,j] <> 0. [x] must be an existing sparse array, and i must have a value suitable for [x] at the start of the loop. More generally, one may use the syntax: for j = [x]i,k do ... . Here i and k both refer to rows of the sparse matrix [x]. At the start of the loop, all nonzero column coords in both rows are found. Then as the loop proceeds, j runs through those values in order. Any number of row indices is allowed. There is no analogous procedure for "sparse row loops" due to the way Fermat stores sparse matrices. If necessary, transpose the matrix.

Arrays as parameters and arguments

Comments

Comments within functions are implemented with the set brackets { and } . Any character string is allowed between them, but note that the first } terminates the comment. A comment may extend over more than one line. When editing a function definition on the screen, a multiline comment does not need to be terminated with the continuation character. Indeed, if it is, something different will result - try it. It is possible to have literals (quoted strings) inside comments and visa-versa, but this very confusing practice should be avoided.

The best practice is to devote an entire line to a comment. However, it is possible to use less - for example, a comment may be placed between the end of an expression and the semicolon at the end of the line. But - do not place a comment immediately before the period terminating a function. In particular, one cannot have a function consist only of comments. A comment is not a statement, so do not place a semicolon after a comment.

One can also have comments of a different sort placed anywhere in an input file (between function definitions, for example) for documentation. Start such a line with a semicolon, such as:

; This is the factorial function.

W(n) = if  n < 2  then  ...

Having seen a semicolon, the interpreter simply skips over such a line when reading the input file. Therefore there is no way within the Fermat session to read these comments.

More on Arrays as Parameters

Scalar parameters are evaluated at the time of call and their values put on the environment stack. This is "call by value". But array parameters are not passed that way - it would be too wasteful of both time and space. Instead arrays are passed "by reference". This implies, first of all, that the argument must be simply an array name, not an array expression, and secondly, that any change made by the function to its parameter will survive the termination of the function; i.e., it will really change the argument.

A subtle problem sometimes arises in passing arrays as parameters to functions. If the function is changing an array, sometimes the size of the output array is not known before the function call. For example, a function Add could be written to add two polynomials represented as arrays of coefficients. The size of the answer could be much smaller than that of either of the input arguments because of terms adding to zero. The caller wants to write Add([x], [y], [z]), meaning [z] is to be set to the sum of [x] and [y]. The [z] existing at that moment may be of inappropriate size, yet the calling function must be written assuming the name of the sum is [z]. A solution is to have the function Add create the array [z], and have the caller know this. But then the problem is what to do about repeated calls to Add (in a loop, say), especially when this [z] is later passed as one of the inputs to a different invocation of Add. To provide an efficient way out of this, Fermat has a change of array name feature. The command Rname[c] : = '[z]' will change the name of array [c] to [z]. The solution to the above problem is to have the function Add create an array [c] to store the sum. Then the caller of Add changes the name to [z].

You cannot cancel an array parameter. (There is one arcane exception to this - if you somehow find yourself in the lowest command level with array parameters still on the list of currently active names, you can and should delete them. This situation is barely possible.) If you cancel within a function the argument that an array parameter is matched with, the argument will indeed be cancelled, but in the course of bookkeeping its symbol table, Fermat will notice that the array parameter is now referring to nothing. An error will be generated. If you had not set the command  &e, everything will be fine after the error. But if you had set  &e, then in the new level of the command language you must do a panic stop  &·  immediately, else Fermat may crash.

You cannot change the name of an array parameter. You can change the name of some other array to that of an array parameter. This is a bizarre thing to do, especially since at the end of the function's execution, Fermat pops off all the array parameter names, so access to the genuine arrays's name is lost.

As one can see from the above paragraphs, array name changing and array cancelling must be done carefully, especially inside functions. For these reasons, I do not recommend using the purge-array command inside a function.
 
 

The System Function

Just as there is a system variable (f) and a system array([f]), there is a system function. One frequently wishes to write a loop to compute something, for example,

One could certainly give this a name and make it the body of an ordinary function, but often one would like to not have to bother with that, hence the system function concept, whereby one can simply enter the loop on the terminal. As soon as the line is entered, the loop is executed. Furthermore, the function has been stored and can be executed again by entering the name of the system function, § (this is option-6 on the keyboard), and can be displayed by using &F,§.

The system function must consist of only one loop or if-statement.

No function can call §.

Footnotes: