*** This page and these versions of Fermat are no longer being updated. ***
November 2016
There are three versions, Linux, for Intel hardware; and Mac, for Intel hardware and OS 10.6, Snow Leopard, and one for Mac OS 10.4.11 - 10.5. (The former also works on
10.7 - 10.**)
These versions use virtually identical C code, which I produced from the 32 bit code in 2010 with the strong assistance of Fordham University student Alexander Golec. Thanks Alex!.
If you do not have at least, say, 6 gig of RAM, there may be no point in using a 64 bit version. However, at least on the Mac, on some platforms the
64bit version runs faster than the 32bit version. It tends to use 50% more RAM. Also, the older 32 bit versions are no longer in active development.
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.
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.
NO ONE MAY USE THIS SOFTWARE AS PART OF ANY BUSINESS OR FOR-PROFIT ENDEAVOR WITHOUT THE
EXPRESS WRITTEN PERMISSION OF ROBERT H. LEWIS. ROBERT H. LEWIS RETAINS THE COPYRIGHT TO
ANY PROGRAM THAT INCLUDES THIS SOFTWARE.
See also the Fermat FAQ page.
64 bit Mac version 5.25. This was compiled with 10.6.8. It will not work on 10.5 and earlier.
It works on 10.7 and later. Expand the tar bundle. Put ferm64 in the right place so that the application Terminal sees it. Start up Terminal, then cd into ferm64.
Type ./fer64. Don't just open the folder
and double-click on fer64. For me, at least, that doesn't work well.
OLD 64 bit Mac version. NOT version 5.*. This was compiled with 10.4.11. It may not work right under 10.6. The new
polynomial multiply method does not compile on Xcode for 10.4.11.
See also the Mac download page (32 bit versions).
64 bit Linux version 5.25. This is compiled with the static option. See also
the Linux download page.
Fermat is freeware. Institutions or those with grant money should contribute $US 70 per machine.
July 5, 2016: 5.25. 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 version 5.24.
June 16, 2016: 5.24. Further upgrades after 5.23 (see below). Improvements in speed of multivariate polynomial gcd, very noticeable in some applications with more
than four variables.
June 7, 2016: 5.23. Many updates.
- Fixed the manual description of the command Minors (it was wrong). The revised manual can be downloaded.
- Can now do subarray of sparse arrays. The command is the same as for ordinary arrays.
- New command Rows, as in Rows[m], number of rows in array [m].
- A lot of work was done improving Redrowech, reduced row echelon, for sparse matrices. A function has been created called Zcol, a kind of preprocessor
for Redrowech. Zcol ("zero the column") searches for rows that have only one entry, in column c, say. It then deletes the row and sets the entire column c to 0.
If desired, a record is kept of which columns were zeroed out. The syntax is Zcol([m]) or Zcol([m], [q]). [q] has the list of zeroed columns. This can greatly
speed up Redrowech on large very sparse matrices.
- Command Sort now works with integers, not just polynomials.
- Command Minpoly now works on matrices up to 65536 rows.
- Added a new function What that returns info about the version and platform.
- 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.
- Fixed an old omission: In Linux, unlike other versions, the command Rname required the new name to have only one character. Other small bugs were fixed.
November 25, 2015: 5.21. Significant revision of some heuristics for multivariate polynomial GCD. Noticeable improvements in many benchmarks, up to 70%.
New interface feature: One can now do the linux command echo "2+2" | ./fer64. Previously, this would spawn an infinite loop. Also try ./fer64 < test. Here test
is a plain text file simulating keyboard input. It must therefore have things like the continuation character at the end of lines carrying commands over, same as
standard input. If you include &N and &(M = ''), you will see no extraneous output as Fermat executes.
For example, try ./fer64 < tst5 with this file: tst5. Note the continuation characters. There can be no comments in this file.
October 20, 2014: 5.17. Bug fix in both Mac and Linux 64 bit versions. There was another small bug in monomial multiply involving constants. Also, the imperative
command &(_o = ...) now works.
June 24, 2014: 5.15 or 5.16. Bug fix in both Mac and Linux 64 bit versions. A small bug introduced last August when monomial multiply was implemented could crash Fermat.
March 28, 2013 versions 4.29:
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.
November 6, 2012 versions 4.28:
Bug fix in 4.28:
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.
Bug fix in 4.27:
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".
New feature in 4.25:
- $, which means greatest integer in Fermat, will now similarly truncate a quolynomial. This is most useful in the new float versions.
Bug fix:
- Polynomial GCD when polymodding over Z had a rare bug.
New feature in 4.23:
- Some of the determinant commands for sparse matrices did not work if the number of rows was > 5000. That limit is now 50000.
Bug fixes 4.23:
- 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.
September 29, 2011 versions 4.22:
- Sqrt now works over finite fields Z/p.
Bug fixes in 4.22:
- 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.
- There was a subtle error involving 64 bit/32 bit arithmetic. This would manifest as a crash, or as "fermat error: bad x in mod_num_poly_mult."
It would occur only after several days of CPU time running Fermat on multivariate polynomial arithmetic.
July 23, 2011 versions 4.19:
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). ]
- Some internal system variables were still 32 bit instead of 64 bit.
- 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 in 4.19:
- 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.
October 6, 2010 versions 4.08:
There are quite a few bug fixes (relative to older 32 bit versions) and new features.
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 builtin 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 builtin function Vars(x) = number of variables that actually occur in x.
- New builtin 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 builtin 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 builtin 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.
(Thanks WebCounter!)