--------------------------------------------
Disclaimer and License Agreement
Fermat 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 your use of Fermat.
YOU MAY NOT ATTEMPT TO DECOMPILE FERMAT. Fermat is copyrighted.
You do not own this program and may not sell it or rent it.
Do not use Fermat for any application that may entail the loss of life or property.
----------------------------------------------
REGISTER. Send me your name right away through email.
If there are new versions or bug fixes, I will inform you.
----------------------------------------------
Use Courier or Geneva to view this document.
----------------------------------------------
For All Users:
Read the first chapter of the manual.
Read the index. Yes, I'm serious. It's not that big and will give you a good idea of
what's going on.
Read some of the examples in appendix 3.
THE QUIT COMMAND IS &q.
_______________________________________________________________
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. If s = (t+1)x + t - 1 where t is a field variable, Termsf(s) = 4 while Terms(s) = 2.
- 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. Mac OSX Intel, Mac OSX G3-5, Linux.
- 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. Mac OSX, Mac OS9, Linux, Windows.
- 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 for Linux and OSX, September 26, 2007.
3.8.7 for Mac OS X (G5 or Intel) and Linux:
(1) several speed improvements in multivariate polynomial gcd.
(2) Cosmetic improvement of not listing hundreds of identical names on the terminal after an &v command.
_______________________________________________________________
July 2007: 3.8.4 for Linux and OSX has some user convenience improvements and a bug fix. The bug did not occur in
the Windows version.
_______________________________________________________________
Version 3.8.1 for Linux and OSX, March 13, 2007. 3.6.7 for OS9. 3.6.8 for Windows.
- Fixed a few minor annoyances: can now do "for i:=1, ... ". 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.
Only the bug fix has been done for Windows and OS9.
_______________________________________________________________
Version 3.7.9, August 10, 2006 for Linux and OSX.
- Fixed a rare silly bug in multivariate polynomial gcd, introduced in version 3.7.0. It manifested 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 for Linux and OSX.
- 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.6.7 Windows:
- fixed: If [d] is a sparse array, the (pointless) command [d] := [d] failed.
- fixed: 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.
- One of the speed ups from the OSX version was put into multivariate polynomial gcd.
________________________________________________________________
This is version 3.7.7, June 11, 2006, for OSX and Linux. 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 for OSX and Linux, 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 for Mac OSX and Linux:
- Bug fix. 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 for Mac OSX and Linux; 3.6.6 for Windows:
- Further refinement of polynomial gcd for very sparse polynomials.
- For Windows, also added two small capabilities that have been in OSX and Linux for a long
time: ability to do &(J = -Var(1)) and ability to have a semicolon after the last command
before od and fi.
_______________________________________________________________
Version 3.7.2, February 18, 2006 for Mac OSX and Linux:
- 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 for Mac OSX and Linux:
- 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, for OSX, Unix, and Linux; 3.6.5 for OS9 and Windows:
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.
_______________________________________________________________
Version 3.6.7, October or November, 2005, for OSX, Unix, and Linux:
- 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]).
_______________________________________________________________
Version 3.6.4 for all versions. 27 July 2005.
Fixed a memory leak that could occur in the arithmetic of rational functions over Z. Thanks to Michael
Czakon for finding it.
The C versions (Linux, Unix, and OSX) since 3.6.2 have a new feature: they will not display more than about
200 lines of any polynomial to the terminal window, so that the user is not swamped with verbiage.
The display will end with ... more output suppressed ... Some users protested this, and in a future
version it will be an option for the user. For now, for Linux there is a version with all other
updates but which does not suppress the output:
http://www.bway.net/~lewis/ferls.gz
_______________________________________________________________
Version 3.6.3 for Mac OSX/Linux. 18 July 2005.
Fixed a bug in the speedups below of 3.5.0 - 3.5.8. Thanks to Michael Czakon for finding it.
With &V on (verbose mode) you will be notified if the situtation occurs via a message such as:
Warning. A fast probabilistic test for exact poly division has been turned off (&_t).
You need do nothing; the (very unlikely) problem has been fixed in the most likely situation that
it occurs. However, it is conceivable that the underlying problem (a certain fast test for
polynomial division) will occur in some other situation, in which case you will see "Fermat error."
If you wish to turn off the test once and for all, use the switch &_t. As this is extremely
unlikely to be a problem, I would not routinely turn this off.
_______________________________________________________________
Version 3.5.0 - 3.5.8 for Mac OSX/Linux/Unix. 10 June 2005.
(1) Significant speedups in multivariate polynomial gcd, 14% - 60% in various tests.
(2) Various bug fixes. There was a bug that could crash Fermat when working over Z/p for p
larger than around 2^27, when invoking Gauss-Jordan elimination.
(3) A new feature to enhance the Dixon resultant method on symmetric systems of equations. This is rather
technical and is in the updated manual.
(4) New combined command to add a poly var and mod by it at once. &(J = t, P = ....). This can be a big
time saver.
(5) Updated the manual for these versions, 15 June 2005, html and ps.
_______________________________________________________________
Version 3.4.9 for Mac OS 9 and Windows. 3 January 2005. bug fix involving rational function arithmetic.
_______________________________________________________________
Version 3.4.8 for Linux, Mac OS X and OS 9, and Windows. 3 November and 20 October 2004.
All versions but Unix are now essentially equivalent. (Mac OS 9 has syntactic differences from the other
versions.)
Bug fix in 3.4.8: two small parts of the implementation of GF(2^8) and GF(2^16) [see below] were flawed. A
few small cosmetic improvements were made.
Bug fix in 3.4.7: various aspects of polymodding were fixed: Sqfree, Irred, and Factor would fail on certain
cases when several variables were modded out to create a field in stages.
Significant new features:
(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
http://www.bway.net/~lewis/fermat/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.)
(3) One can now work over Z/p for primes up to 92000099 (Windows) or 2^31-1 (other versions). However, once
the prime exceeds 2^24, arithmetic slows a bit.
(4) The Windows version is converging to the Linux/OS X version. To that end, some of the special symbols
are now plain ASCII, the same as Linux/OS X (so the manual is out of date on these points):
-- continuation character is `
-- first derivative w.r.t highest variable is ", as in w".
-- system function is -l, not -p, as
the manual says. (-p is correct if you use the DOS window instead of the Viewer.)
(2) Implemented a builtin function to return the number of polyvars, Numvars. no argument.
(3) Implemented a builtin function to return the nth prime, Prime(n). 0 < n < 1230
(4) This is a feature not a bug: note that Sqfree's answer may be multiplied by an invertible element
in the ground field.
(5) It is OK now to invoke Coef(^x, ..). The ^ has no effect, as Coef already did not duplicate space.
(6) Content now has a second [optional] parameter, the name or ordinal of a poly var. Content(item, x)
computes the content of item relative to x. Content(item, i) computes the content of item relative to
variable number i (highest = 1). (Content(item) computes it relative to the highest variable present in item.)
The major improvement is yet another large gain in the speed of multivariate GCD. The first benchmark
on the "Fermat Tests" page on the website goes from 105 to 96 seconds, the third goes from 28 to 10 seconds(!)
[These times are on a now obsolete 400mhz G3 computer. On a 1.6 ghz Dell Pentium 4, the time corresponding
to 96 seconds is 47.2.]
---------------------------------------------------------------
Version 3.2, 2 September 2003.
Minor bug fixes:
(1) A few small memory leaks were fixed.
(2) The MPW version could not correctly do arithmetic over Z/pZ with primes near 2^24.
(3) Log2 would fail on very large inputs, when the answer was more than 2^16.
(4) There was a dangling pointer problem that could rarely arise when invoking SDivide or Gauss-Bareiss.
(5) Windows/X86 only: Fermat would sometimes hang after hitting return.
Feature change: changed Terms and Mons so that when polymodding with a field, the elements of the
field are not counted as terms.
The documentation for Minors is wrong. The correct invocation is Minors([x],[r],[c],[y]).
----------------------------------------------------------------
Version 3.3 for Mac and Windows, 3.4 for Linux only, 1 May 2004.
(1) This version provides remarkable speedups in basic one variable polynomial arithmetic and g.c.d.
Since that is used by other parts of Fermat, the speedup propagates throughout the system to some
extent. Problem 3 on the Fermat Tests Page saves
30%. Some computations over Z/p save 60%.
(2) At last, implementation of LaGrange interpolation for determinant of sparse matrices. This
method is often orders of magnitude better than the other Det methods (but sometimes it isn't!).
(3) Linux only, 3.4: One can now work over Z/p for primes up to 2^31 - 1. The largest such prime is
2^31 - 19. However, once the prime exceeds 2^24, arithmetic slows by around 30%. Note however
that Integer mode (not often used apparently) is still restricted to numbers < 2^28.
(4) For Windows, the Viewer does not work for Windows XP Professional. Sorry, you'll have to
double-click on the application QFerX86 and use the DOS window for now.
(5) The MPW version for Mac has not been updated. I will not do so unless someone say they want it.
----------------------------------------------------------------
Version 3.3.2 for Mac and Windows, 3.4.2 for Linux and Unix, 6-9 June 2004.
Bug fixes to all versions.
(1) Differentiation of some rational functions w.r.t. x would hang if the denominator did not
contain x.
(2) Sometimes Gauss-Bareiss and Gaussian elimination methods to compute determinant would fail
to recognize a singular matrix, resulting in a spurious error message about a nil pointer.
Change of feature, all versions:
(3) When converting from ground ring Z/p to Z (modularmode to rational mode), the rule was that a
numerical value > modulus/2 was interpeted as a negative integer, so that e.g. modulo 11 a 9 was
converted to -2. This will no longer be done unless the flag &H has been set, i.e. values
> modulus/2 were being displayed modulo p as negative. Otherwise, in the example above, 9
will be left as 9.
Bug fixes, Linux:
(4) Bin (binomial coefficient) would sometimes fail because the file pow228 was corrupt.
(5) Determinant of an integer-only matrix might fail.
(6) Multiplying sparse_matrices that were integer-only might fail.
New features in Linux/Unix (they were already in the Mac and Windows version):
(7) RRand is now implemented (see manual).
(8) The system function is now implemented via the syntax