Linux Downloading Instructions (Intel Hardware 32 bit). Version 3.9.9x, July 5, 2016.

I am no longer updating these old 32 bit versions. Time marches on. I assume that everyone has at least 8 gig on their computers these days. Get the 64 bit version!


You need the files that are in this gzip archive:

fermat.tar.gz. No extensions after 2013, only bug fixes.


Download and expand. To run it, go to the console, cd into the right directory, and type ./ferls (that's period-slash). For some reason, double-clicking on the fermat icon does not work for me, but that is probably a local problem. A file containing the code needed to run one of the examples on the "Fermat Tests" page is included.


This has been compiled with the -static option to gcc, hence the name ferls.


Fermat is freeware. Institutions or those with grant money should contribute $US 70 per machine.

This version of Fermat is written in C and compiled with gcc for Intel machines. There is a Mac OS X version for Intel and the old PPC machines using the identical C code and compiled with gcc.


There is also a 64 bit version.


The manual was updated on July 25, 2011, with a small edit in June 2016 See especially Appendix 6. Revised PDF and HTML Manuals for Linux and OSX.


An important feature: the first line of the file ferstartup should be the number of megabytes of RAM on your machine (with no semicolon). The default is 1000 meaning one gigabyte. Don't worry about the difference between 1000 and 1K = 1024.


Technicality: Often with the Linux version, the backspace key doesn't work. This is very annoying! It often happens with Red Hat. Try this: before you start Fermat, type: stty erase control/V BACKSPACE ENTER. In other words, after typing "stty erase" and a space, type control-V (hold control while typing V), release control, then hit the backspace key (which should display as ^?), then hit enter. I think this could be put in a .cshrc.


Version 3.9.9x, July 5, 2016. Significant very old bug fix. Discovered a rare bug that would manifest by polynomial GCD(u,v) returning too small an answer; a factor would be missing that was part of the GCD of Content(u) and Content(v) relative to one of the polynomial variables (not the one of highest precedence). Looking for such contents is an important speed-up technique in GCD.
This bug was introduced about ten years ago. A rare combination of circumstances has to occur to trip it. No one reported it, and I never encountered it until a week ago when testing the latest 64 bit versions.


Version 3.9.9x, June 7, 2016. Bug fix only. There was a bug in the stashing of gcd results. (Fermat often saves the result of a gcd computation in the hope that an almost identical problem will soon come up.) The stash was not being deleted in a timely manner.


Version 3.9.9x, March 28, 2013. Mac OSX Intel, Linux, Windows:


There was a bug in invoking a speedup technique for multiplying large two variable polynomials. This would manifest as a "Fermat error". Also, refined heuristics for multivariable polynomial gcd.


Version 3.9.9x, November 6, 2012. Mac OSX Intel, Linux, Windows:


There was a bug in Pseudet when the matrix was not of maximal rank and pivot strategy 5 was chosen. It would manifest unpredictably, but inevitably Pseudet would finish too soon with the wrong answer.


Version 3.9.9x, June 12, 2012. Mac OSX Intel, Linux:


There was a bug in a speedup technique for multiplying large two variable polynomials. It could fail if the degrees were large enough. This would manifest as a "Fermat error".


Version 3.9.9x, January 2, 2012. Mac OSX Intel, Linux:


New feature:


- $, which means greatest integer in Fermat, will now similarly truncate a quolynomial. This is most useful in the new float versions.


Bug fixes:


- Polynomial GCD when polymodding over Z had a rare bug.


Version 3.9.9x, November 1, 2011. Mac OSX Intel, Linux.


New feature:


- Some of the determinant commands for sparse matrices did not work if the number of rows was > 5000. That limit is now 50000.
- Sqrt now works over finite fields Z/p.


Bug fixes:


- Multiplication of high degree polynomials over the field of 65536 might produce a Fermat error, as an inappropriate speedup technique was being used. This bug was introduced in August 2010.
- Log2 did work right modulo large primes, such as 2^31 - 19, in that values > 28 were not returned.
- Saving to a file (&S) would sometimes report an error message even though it in fact did the right thing.
- Creating a random sparse array via [m] := [Rand] would fail if the array were very large.
Version 3.9.9x, July 23, 2011. Linux, Mac OSX Intel, 64bit.


Bug fixes:


- In certain rare cases, polynomial gcd when polymodding was very slow. [polymodding means working over a quotient ground field, like Z[x]/(x^2 + 1). ]
- Sigma did not work with Integer in modularmode.
- Sometimes trying to read from a file that did not exist would crash Fermat, instead of just being an error.
- In converting the ground ring by removing a polynomial variable, as in &(J = -x), if that resulted in some denominator becoming 0, Fermat would report an error and stop there, in the middle of the conversion. This is quite inconvenient. Now, that particular data item is set to 1 and conversion continues.
- During an interrupt, displaying the list of variables (&v) would sometimes display hundreds of lines of identical names, if, say, a recursive procedure was interrupted that had called itself hundreds of times. This display of identical names is now counted and suppressed.
- A nil pointer bug would very rarely cause Fermat to crash when testing if one multivariate polynomial divides another.


New features:


- Many speedups to multivariate polynomial gcd heuristics. Most test problems show a speedup of 10 - 30%, some up to 90%.
- A new arithmetic command has been added for when a function is in Integer mode: x :* y to set x := x*y; REPEAT: this only works in Integer.
- New builtin function Reverse: Reverse[a] will reverse the elements in Array a[n]. If [a] has one column, this is obvious. Otherwise, the exact behavior depends on whether [a] is a standard array or a sparse array. For standard, each a[i] is swapped with a[n+1-i], where you think of [a] as in column-major order. For sparse [a], the rows are swapped.
- New builtin function Poly: With x = the highest polynomial variable, Poly[a] takes an array OF NUMBERS and yields Sigma [ a[i] * x^(n+1-i) ]. At least that is what happens on a standard array. For a sparse array, only the first entry in each row is used. So again, if [a] has one column Poly produces what you'd think. If not ...
- New builtin function Toot: Try it.


Version 3.9.9x, October 8, 2010. Mac OSX Intel, Mac OSX G3-G5, Linux.


It has been almost a year since the last formal update, and much has been done.


Bug fixes:


- Memory Leak bug fixed, involving array expressions like [a] + [b].
- Fixed an old bug involving Minpoly. It might fail if alt_form_display was on.
- FIxed a very old bug involving GCD stashing. This is controllable by the user with the &C+, &C- command. On very rare occasions, the GCD was not unstacked correctly.
- Fixed a bug in STrans[a]: if array [a] did not exist, Fermat would crash.


New features:


- New function SDet: "Space-saving determinant." Space is saved when computing over ground ring Z using LaGrange interpolation and the Chinese Remainder Theorem. Fermat has aways used the the CRT algorithm from Knuth volume 2 on page 277 (exercise 7). The advantage is one can do everything "on the fly." The disadvantage is that if one will need, say, 50 primes, then every determinant modulo the 50 primes is stored until the end, when the answer is computed over Z by combining them. That might need too much space. Instead, SDet implements formulas 7-9 on page 270 of Knuth. The disadvantage is it can't be done on the fly: one needs to know in advance how many primes will be needed. The user must (over)estimate this number.
Input: integer and a square matrix of polynomials. Output: determinant. Call: SDet(n, [m]). n = how many primes will be needed.
SDet is not guaranteed to work with the more sophisticated options of Det, i.e. Det([m4], r, d1, d2).
- New function Vars(x) = number of variables that actually occur in x.
- New function Time. It displays the time and date. Visible on startup.
- Sqrt now works in lintmode too (not modularmode). Over a modular ground ring, to compute the sqrt of n, turn off modularmode then take Sqrt(n), such as _Sqrt(n).
- New methods to multilpy one- and two- variable polys in modularmode. Huge speedups, also evident in GCD. In many cases, more than 90% of the previous time is saved on polynomials of degree > 1000. Moduli smaller than 46340 are the fastest, next those < 65535, but all show huge speedups. Computations modulo primes in the range of 45000 are done internally by Fermat even when the user is over Z, so this improvement is significant for all computations but those with many variables.
- New functions Split and Splice. Splice(s,c,m) multiplies c by x^m and "tacks it in front" of s -- actually it adds them, as there could be overlap. c becomes 1, s gets the answer. Split is basically the dual. Invoke with Split(w,n,v) or Split(w,n). w and v are existing scalar variables (including entries in an array). n is an integer. w becomes w mod x^n, where x is the highest variable. v (if present, optional) becomes w \ x^n.
- New command Mono(a,b) to compare monomials; returns true iff a <= b. Numerical coefficients are irrelevant. Individual variables are ranked by order of their creation, latest is largest. Monomials are ranked first by length = #variables, i.e. all univariates < all bivariates < all trivariates, ... etc. Within equal #vars, ranking is by subset of vars. Within subset, ranking is exponent arrays. See "Sort" below. This is the order that is used internally by Fermat for certain algorithms. If you want me to include another ordering, let me know.
- Changed array max to 1000000 for ordinary arrays. (There is "essentially" no size limit on sparse array declarations.)
- New function Sort to sort an (already existing) array (of polynomials, actually monomials). [a] can be either sparse or ordinary. The first column holds the keys. For ordinary arrays, every entry in column 1 must have been assigned a value. 0 is a legal value. For sparse arrays, it is more subtle: every row must have an entry, and the first entry in each row is taken as the key. (Recall that sparse arrays never contain 0). To avoid confusion, the best policy is to have the first column contain the key. As swaps are made, the entire row is swapped. The algorithm is quicksort. Quolynomials are allowed; denominators are ignored.
The order is a monomial order, the one built into Fermat via the Mono command. In comparing a and b, only the leading monomials are compared - the ones you see first when they are displayed. Numerical coefficients are irrelevant. All numbers are considered equal.
To illustrate, create a multivariate polynomial w, do Mons(w, [a], 1), then Sort[a].
Syntax: Sort[a].
- Explanation of elapsed time and CPU time:. When timing is enabled, two numbers are displayed, called "Elapsed CPU time" and "Elapsed real time". CPU time is just the CPU time used by Fermat. This is what has been displayed by Fermat in most previous versions. However, the number is meaningful only up to about an hour. For much longer times, it becomes useless. Elapsed real time is clock time, just as it sounds. If the elapsed real time is more than 5 seconds, then it is also displayed.


Version 3.9.9i, October 19, 2009. Mac OSX Intel, Mac OSX G3-G5, Linux.
- The builtin function Log2(n) now works over Z/p.
- There is a new builtin function Termsf, which counts the total number of terms when polymodding to create a field, counting the field variables.
- As a space-saving aid, one can add the ^ when saving, as in !!(&o, 'q := ', ^q, ';'). Without the ^, q is duplicated in the course of expression evaluation.
- There is a new option for the heuristic that directs pivot choice (see 3.9.8f). &(u=5) takes into account the weight of the column as well.
- Implemented the writing of LaGrange modular determinant coefficients to a file. This can be a big space saving. The command is &(_L=1). In other words,
   if the highest precedence variable is x and lower ones are y, z, ..., and if a determinant c_n x^n + c_(n-1) x^(n-1) + ... is being computed with
   LaGrange interpolation, the coefficients c_0, c_1, ..., c_n (which are polynomials in y, z, ...) will be dumped to the output file to save RAM.
- Fixed a rare bug in matrix inversion introduced in version 3.9.2.
- Fixed a bug. &_P produced an error when encountered during reading a file at the top level. &x should be used instead anyway.
- Fixed a very rare bug in polynomial gcd introduced in version 3.7.0.
- Errors 325 and 326 were sometimes confused.


Version 3.9.8f, January 8, 2009. Mac OSX Intel, Mac OSX G3-G5, Linux.
- The builtin function Isprime(n) now works for values n up to 2^63-1; the limit had been 2^32-1. The algorithm is
   elementary so it is rather slow on large prime n. Isprime(n) = 1 means n is prime, else it returns the smallest
   prime factor.
- It is now possible to adjoin a polynomial variable "at the bottom." So if, say, x and y exist, y later or "above"
   x, one can do &(J>z), which will insert z as the lowest variable (below x) rather than the highest.
- There are two new functions to find the last (trailing) numerical coefficient of a polynomial. Ntcoef(x) returns the
   trailing numerical coefficient of x. That number is always an actual coefficient in x, so can never be 0. Zncoef(x)
   is similar but will return 0 if there is no constant term.
- There are now options for the heuristics that direct the pivot choice in the normalization of matrices. This can
   have a large effect on time and space, though often it does not. The heuristic is set with the command &u or
   &(u = val). val is an integer from 0 - 4. The size or mass of a potential pivot can be measured by just its number
   of terms (called term# below), or by one of two mass heuristics (called mass0 and mass1 below).
   Setting val =
      0 is the default previous heuristic, which selects the least massive entry by the original mass0 heuristic.
      1 selects the 'lightest' entry where weight = term# + sum of term# for the entire row entry is in.
      2 selects the 'lightest' entry where weight = mass0 + sum of term# for the entire row entry is in.
      3 selects the 'lightest' entry where weight = mass1 + sum of term# for the entire row entry is in.
      4 selects the 'lightest' entry where weight = term#.
- Refined the heuristics for multivariate polynomial gcd.
- Fixed a bug. The timing command &T did not work right in OSX Intel.
- Fixed a bug. A space saving command of the form z := x + *y would cause a bug when y was a declared polynomial
   variable. It is now an error (which is reasonable).


Version 3.9.7, May 6, 2008. Mac OSX Intel, Mac OSX G3-G5, Linux.
- Fixed two old bugs. First, the bug fix in 3.7.2 February 18, 2006, was not quite right. The second bug dates to 2001 and occurred with Det([m], p, ...) when quolymodding.
- Refined the heuristics for multivariate polynomial gcd.


Version 3.9.2, February 10, 2008.
- There is a new function STrans to transpose a sparse matrix "in place", without creating any new storage. This is necessary when working with very large arrays.
- Fixed a bug in Rname (rename array) that affected only the Linux version. This dates to June 2005.
- Fixed a bug involving @<[xx]>, purging arrays. This is a very old bug.
- Fixed a slowdown in saving very large sparse arrays to a data file.
- Added a new argument to the Det command, so the user can specify the degree of the poly one level down, as in Det([m], p, deg1, deg2, power). This affects only finding the determinant of a sparse array with LaGrange interpolation. If you don't know deg2, leave it blank, as in Det([m], p, deg1, , power). Here 'power' can be a power of an odd prime, not just an odd prime, as in stated in the documentation.


Version 3.8.8, October 28, 2007.
- This is more a feature than a bug, but computations in which thousands of monomials were added or subtracted one by one to a quolynomial, keeping a running total, ran very slowly. Most people do not write such programs. Such programs now run in a small fraction of the previous time. This is an old bug. (Polynomials were never affected, only quolynomials.)


Version 3.8.7, September 26, 2007.
- Several speed improvements in multivariate polynomial gcd.
- Cosmetic improvement of not listing hundreds of identical names on the terminal after an &v command.


Version 3.8.4, July 4, 2007.
- Time-saving improvement: Typing on the terminal, one can now leave off the terminating fi and od. For example, one can simply type
for i=1,5 do for j=1,4 do if i > j then z := i + j
One does not need to add the fi od od. This is a nice convenience (but ONLY when typing commands on the terminal).
- User interrupt is now more convenient in some situations. Some sensitive interrupts severely restricted what the user could do. In response to some commands, the user would see a message like "not available at this level of interrupt." Most of these are now allowed.
- With the &v command, no more than about 10 identical array names will be displayed; there will follow a message such as "... 32 more of these." This is important because when using array-of-arrays %[i], one typically has created hundreds of identically named arrays for the aliases %[i] to point to. No one wants to see a thousand lines of "Array a[17,2]" dumped to their terminal.
- Bug fix: there was a bug in multivariate polynomial gcd when working over a quotient ground field (called "polymodding" in the manual). This bug was introduced in May 2005 in the Linux, Unix, and OSX versions. It would manifest (rarely) by a message such as: *** Fermat error. r not 0 in num_pseudo poly div.


Version 3.8.1, March 13, 2007.
- Fixed a few minor annoyances: can now do "for i:=1, ... " [note the colon]. Can now do Numer(^x), Denom(^x), and a few other commands with ^.
- The sophisticated determinant command Det([m], divider, degree, power) will now work recursively if more than one variable is present in array [m]. Note, however, that the power field is ignored if [m] is not Sparse.
- Bug fix: running LaGrange interpolation to compute the determinant over ground ring Z of a sparse matrix would fail in very rare cases. This is an old bug.


Version 3.7.9, August 10, 2006.
- Fixed a silly bug in multivariate polynomial gcd, introduced in version 3.7.0. It manifested (rarely) as a "Fermat error."
- Added the ability to assign array-of-array pointers, such as %[i] := %[j]. Note the difference between this and [%[i]] := [%[j]]; the former moves no storage.


Version 3.7.8, June 26, 2006:
- Fixed a typo that caused a small slowdown in some polynomial GCD calculations.
- Fixed a small memory leak in polynomial GCD calculations, introduced in version 3.7.0.
- This is rather technical: added a new command &_G to sort the heap garbage. This can be added to the user's functions periodically during memory intensive polynomial calculations. A noticeable speedup occurs when used between repetitions of an intensive calculation.


Version 3.7.7, June 11, 2006. Several minor bug fixes.
- The bug fix in 3.7.6 below, saving array data, was not quite right for sparse arrays.
- There was a bug in fast dropping into modular ground ring, Z -> Z/p. Sometimes a 0 was introduced into a sparse array (a bad no-no), and sometimes upon return to ground ring Z, some data was not equal to its orginal value. This was introduced in version 3.4, April 2004.


Version 3.7.6, May 26, 2006. Several minor bug fixes.
- If an error occurred while reading a file, subsequent attempts to use &S or &R gave an odd error message.
- If [d] is a sparse array, the (pointless) command [d] := [d] failed.
- Saving arrays to a file was messed up. While the data was there, it was not in a form that could be easily reread. (introduced in 3.6.7, October 2005)


Version 3.7.5, April 13, 2006, fixed a rare bug. If an error happened during the command w#(t = ...), such as for example t does not exist, Fermat would display an appropriate error message (good), but in fact could not recover. This problem was introduced in 3.5.0, June 2005.


Version 3.7.4, March 10, 2006, has further refinements of polynomial gcd for very sparse arguments.


Version 3.7.2, February 18, 2006:
- Patch of a bug in polynomial gcd that was rare, but could cause a big slowdown. It was introduced in version 2.6.4.
- Patch of a memory leak, introduced in version 3.6.0.


Version 3.7.0, February 1, 2006:
- Patch of a bug in polynomial gcd that was very rare, but could cause unpredictable crashes. It was introduced in version 3.6.7.
- Significant speedup in polynomial gcd for very sparse arguments.
- Significant speedup in polynomial evaluation x#(t = q) when q is a rational function and t is deeply nested.


3.6.9:
- Three in polynomial gcd, one producing a slow down only.
- Reading data into a sparse array could fail over Z/p if the first entry was negative and larger > p/2.
- Det([w], divider, degree), with sparse [w], computed with LaGrange interpolation could fail.
- The statement &(p = prime) when read from a file would fail if p was large enough, say > 2^28.


3.6.7 added:
- There is a new command &_s to switch on/off the suppressing of the display of very long polynomials to the terminal window.
- Builtin functions Lterm and Lcoef have been modified to "do the right thing" for multivariate polynomials. Lterm(3t*u^2 + 2u + 3t + 7) is now 3tu^2, no matter how many other poly vars have been attached above u. Similarly Lcoef(3t*u^2 + 2u + 3t + 7) is now 3t; it was 3. If you want just the numerical leading coefficient, use the function Nlcoef.
- There was a small problem in Gauss-Bareiss, which did not affect the computed result.
- There was a bug in Content that occurred with the form Content(^w, n).
- There was a subtle bug in dividing some polys. As a result a "fermat error" message was reported.
- polynomial gcd has been improved working over the field Z/p for small p, say < 200.
- There was a bug in passing builtin functions a pointer to an array element, as in Coef(^x[3]).


3.6.4 fixed a small memory leak in rational function arithmetic over Z. 3.6.3 fixed a small problem with rational function arithmetic; see the second readme. 3.6.1 fixed a bug in rational function arithmetic. 3.6.0 fixed a memory leak. (3.5.6 and 3.5.7 contained bugs; 3.5.8 had a memory leak.) It has faster polynomial gcd, 18% - 85% improvement on various tests. 3.4.9 contained some minor bug fixes and a few new features, now in the manual.
3.4.8 was a minor improvement on 3.4.7:
(1) Two finite fields (other than Z/p) are now efficiently implemented. It has always been possible to work over finite fields in Fermat by setting ground ring Z/p and then modding out by an irreducible polynomial (with the command &P). But now the fields GF(2^8) and GF(2^16) are efficiently represented as bits within 4 bytes; i.e. a 32 bit "longint." GF(2^8) is important in cryptology, and it is important to have a larger field containing it for ease of polynomial interpolation. More information is available at finfield.


(2) Determinant via LaGrange interpolation has been expanded. This feature is implemented because it arises in using the Dixon resultant to solve polynomial systems that exhibit symmetry. (Admitedly, not many people will be interested in this.) The new (optional) syntax is Det([x], div, deg, power). [x] is a matrix whose determinant is desired. Ideally it contains entries that are polynomials over Z in one variable. When symmetry is present one suspects (first case) that the determinant det can be factored as f(x)^n * g(x), and it is only f(x) that is really desired. div = g(x) is a polynomial known to divide the determinant (a "spurious factor"). deg is an estimate (too large is OK) of the degree of the determinant. power = n, also known in advance. Det([x], div, deg, power) returns exactly the desired f(x) very efficiently via interpolation. Technicality: in version 3.4.7 n must be odd. Alternatively (second case), one may suspect that the determinant is f(x^n) * g(x). Then invoke with the command Det([x], div, deg, -n). (In either case, one must first set the flags to select LaGrange interpolation, as explained in the manual.)


Various bugs in 3.4 have been fixed as follows. 3.4.3, present here June 17 - 26, 2004, contained a bug in differentiation. 3.4.4, present here June 26 - July 2, 2004, still contained several small bugs including: Factor did not work over the field of 256 (see the second readme), error message 73 was nonsense, timing with &T did not work (it does now but you often need to put it in parentheses (&T)), and it had been impossible to invoke Rowreduce. A bug remained in 3.4.5, present here 2 - 6 July 2004: cntl-c to interrupt Fermat and bring up a new level of the interpreter could not be done after a panic stop, i.e. the first panic stop disabled the cntl-c feature.

Legal Matters


This Software is provided on an "AS IS" basis, without warranty of any kind, including without limitation the warranties of merchantability, fitness for a particular purpose and non-infringement. The entire risk as to the quality and performance of the Software is borne by you. Should the Software prove defective, you assume the entire cost of any service and repair. This disclaimer of warranty constitutes an essential part of the agreement. Even if parts of the disclaimer violates legal rights of some jurisdiction, only these parts are invalid, but not the entire disclaimer.


Do not use Fermat for any application that may entail the loss of life or property.


THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

since September 25, 2003
(Thanks WebCounter!)