OS X, 32 bit Intel Version 3.9.9x, July 5, 2016
OS X G3-G5 Version 3.9.9x, October 8, 2010
OS 9 (Classic) Version 3.7.0, October 29, 2007
Fermat is freeware. Institutions or those with grant money should contribute $US 60 per machine.
Download Intel version: ifermat.tar.gz. This was compiled under 10.6.8.
Download G3, G4, G5 version: fermatG.tar.gz.
Expand. Put Fermat in the right folder so that the application Terminal sees it. Start up Terminal, then cd into fermat. Type ./fermat. Don't just open the folder and double-click on fermat. For me, at least, that doesn't work.
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.
The manual was updated on July 25, 2011, with a small edit in June 2016. See especially Appendix Six. Revised PDF and HTML Manuals for Linux and OSX.
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. Mac OSX Intel, Linux:
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:
- $, which means greatest integer in Fermat, will now similarly truncate a quolynomial. This is most useful in the new float versions.
- Polynomial GCD when polymodding over Z had a rare bug.
Version 3.9.9x, November 1, 2011. Mac OSX Intel, Linux:
- 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.
- 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. Mac OSX Intel, Linux:
- 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.
- 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.
See also the new 64 bit versions.
- 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 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].
- 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.
G3-G5 machines are obsolete. This version will no longer be updated.
- 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
- 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 25, 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.
Version 3.6.9, December 15, 2005:
This patches several small bugs:
- 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 > 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 prime was large enough, say > 2^28.
- 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.6.4, July 27, 2005, 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 had some bug fixes and is 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.8 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.)
A note on timing: the OS X version times CPU time, not elapsed real time. They can be quite different, especially if you are running Classic. (Classic is obsolete.)
Suggested donation $60. Please indicate platform on the "payment for" field.
Any Mac purchased since around 1996 is a PowerPC (PPC) machine (until the Intel Macs came out, in February 2006). The even older Macs are
called 68K machines.
This is an OS 9 (Classic) application. It will not run at all on the new (February 2006) Intel Macs. There is no reason to use this version unless you are still using an
old Mac that boots up on OS 9. Are there any such people left in the world?
The programs are in a number of self-extracting archives which
have been binhexed (converting them into ascii or text files).
To download the rational version, you'll need
Assuming you are doing some serious computations, select the QFermat icon, do command-i, and bring up "memory". Give Fermat most of your RAM. If you have, say, 500 meg of RAM, allocate 400 meg to Fermat.
After an update is announced on the main web page, it is usually necessary to download only the first of these files, as the second is rarely changed.
A file of examples (from appendix three of the manual) suitable for direct input to QFermat is
To download the float (graphics) version, you'll need
FferPPC.sit.Hqx. This is an OS 9 (Classic) application. It will not run on the new (February 2006) Intel Macs.
There are no stand-alone 68K versions.
Use Apple's MPW to run these MPW tools on a 68K Mac with FPU. I use MPW3.3. This can also be done
on a PPC via emulation. (You don't need a
SoftwareFPU anymore, as of version 2.6.4, January 20, 2002.) You may actually prefer this to the
stand-alone versions, because the environment
provided by MPW is extremely nice. (Of course the stand-alone version will run much faster on a PPC.) MPW is also included in many releases of Metrowerks Codewarrior.
Any version since around 1998 is OK.
Note: This is version 3.3, May 1, 2004. I am no longer updating the MPW version.
(The object files that were in objectfiles.sit.Hqx have been removed. Email me if you need them.)
After an update is announced on the main web page, it is usually necessary to download only the second of these files, as the first is rarely changed.
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.
Please note that although the author plans to release enhanced versions of this software,
the author cannot guarantee indefinite software support.
since February 5, 1999