Conference rusure::math

375.0. "On Symbolic Math Programs" by TOOLS::STAN () Fri Nov 08 1985 13:26

Newsgroups: net.math.symbolic
Path: decwrl!decvax!bellcore!petrus!scherzo!allegra!ulysses!burl!clyde!watmath!watnot!watmum!ghgonnet
Subject: Recent article on CACM about SMP
Posted: 27 Oct 85 15:25:07 GMT
Organization: U of Waterloo, Ontario
 
 
	In the April/85 issue of Communications of the ACM, there
appears an article titled "Symbolic Mathematical Computation" by
Stephen Wolfram.  As developers of a symbolic manipulation system,
Maple, we had hoped that such an article would generally promote
interest in computer algebra among our colleagues.  However, we have
perceived by comments from other colleagues and comments coming from
this net itself, that this article has misguided people, and in general
has damaged the credibility of work in the symbolic computation area.
 
	First of all it should be noted that in general, this
article, though not treated editorially as an advertisement,
reads as a sales pitch of a product, in many cases disparaging
other systems that would compete with it.  As such, it is sad to
see that CACM allowed this to happen and hence lose credibility
as a serious technical journal.
 
	On the first page we read: "The most advanced and complete
mathematics system at present available is probably SMP."  This claim,
besides being unethical in a scientific community, is very damaging
given the shortcomings that we found in version 1.5.0 (the latest
as of October/1985) of SMP.  The following examples illustrate some
of these.  Readers may ask:  "If SMP is the 'most advanced ...' and
has this behaviour, then what can we expect from the other systems?"
 
 
_______________________________________________________________________________
 
/* "B" is the function which specifies that exact integers of arbitrary
precision instead of floating point numbers, will be used in the calculation. */
 
#I[1]::  B[ (x+1)^80 ]
		  80
#O[1]:*  (x + (1))
 
 
#I[2]::  Ex[ % ]
	 /* The lengthy result from expanding the above expression,
	 not reproduced here, contains *negative* coefficients */
_______________________________________________________________________________
 
#I[1]::  p : B[ (x+1)^100 ]
		  100
#O[1]:*  (x + (1))
 
#I[2]::  Ex[ p ]
	 /* Appears to be in an infinite loop (exceeded 2000 CPU seconds) */
_______________________________________________________________________________
 
#I[1]::  Pgcd[ (x+1)^2, (x+1)*(x-1), x ]
 
#O[1]:   (1 - x) (1 + x)
	 /* Wrong, the polynomial gcd is obviously  1 + x  */
_______________________________________________________________________________
 
#I[1]::  N[BesJ[0,2.7],40]
 
8878 Bus error
/* This is a Unix system error.  It means that SMP "crashed" . */
/* The N function is used here to compute a 40 Digit floating point approx. */
-------------------------------------------------------------------------------
 
#I[1]::  x/0
 
	 x
#O[1]:   -
	 0
/* Although SMP allows such an expression to exist, this leads to bugs */
 
#I[2]::  Lim[%,x,2]
 
#O[2]:   2
_______________________________________________________________________________
 
#I[1]::  374^3*x - 374*374*374*x
			   3
#O[1]:   -5.23136*^7x + 374  x
 
#I[2]::  B[%]
 
#O[2]:*  x (-52313624) + x (52313624)
	 /* SMP did NOT do the coefficient arithmetic in a sum */
_______________________________________________________________________________
 
#I[1]::  d : x^2-1-(x+1)*(x-1)
 
				  2
#O[1]:   -1 - (-1 + x) (1 + x) + x
 
/* In SMP, little attempt is made to recognize zeroes.  This leads
to wrong or meaningless answers being returned, as well as system failures
as the following examples illustrate.  Other systems make use a normal form
for polynomials and rational functions to recognize zeroes. */
 
#I[2]::  Pgcd[ d, x^2+x+1, x ]
 
#O[2]:   1 + (1 - (1 - x) (1 + x)) (2 - (1 - x) (1 + x))
 
#I[3]::  Ex[ % ]
 
	      2    4
#O[3]:   1 + x  + x
	 /* Note that the degree of both input polynomials is less than 4 */
 
#I[4]::  Lim[ 1/d,x,0 ]
 
	  1
#O[4]:*  ----
	    3
	 0 x
 
#I[5]::  Int[ 1/d,x ]
 
SMP INTERNAL ERROR
Numerical overflow
_______________________________________________________________________________
 
#I[1]::  Coef[ x,(x+y)*(x+z) ]
 
#O[1]:   0
	 /* Mathematically, the coefficient in x is not 0. */
_______________________________________________________________________________
 
#I[1]::  f : (Exp[x]+Sin[x])/(Cos[x]+Log[x]);
 
#I[2]::  <XOpt
	 /* Loading SMP's common subexpression optimizer */
 
#I[3]::  fp : D[f,x];
 
#I[4]::  Optim[fp]
 
#I[5]::  N[#T[4]]
 
#O[5]:   4.63333
	 /* Not bad. Now we try optimizing the second derivative. */
 
#I[6]::  fpp : D[fp,x];
 
#I[7]::  Optim[fpp]
	 /* SMP appears to be in an infinite loop (exceeded 1000 cpu seconds) */
--------------------------------------------------------------------------------
 
#I[1]::  Rand[ 10000000000 ]
 
#O[1]:   0.814888
 
#I[2]::  Rand[ 10000000000 ]
 
#O[2]:   0.309272
	 /* According to the manual, this should produce random numbers in
	 the range  [0..10000000000)  but in fact, no numbers greater than 1
	 are returned */
_______________________________________________________________________________
 
#I[1]::  Hash[ .1 ]
 
#O[1]:   2056
 
#I[2]::  Hash[ .2 ]
 
#O[2]:   2056
 
/* SMP's Hash function is supposed to return "a positive integer less than
2^15 (default) which provides an almost unique 'hash code' for the argument".
However, we note that the hash values for any number in the range [0..1) are
all the same.  Thus Hash[ Rand[] ] always yields the same number ! */
______________________________________________________________________________
 
#I[1]::  Sol[ {x+y=1, 2*x+2*y=2}, {x,y} ]
 
#O[1]:   {{}}
 
	 /* There are, infact, an infinite number of solutions to this */
	 /* system of linear equations which we obtain by doing */
 
#I[2]::  Sol[ {x+y=1}, {x,y} ]
 
#O[2]:   {x -> 1 - y}
______________________________________________________________________________
 
#I[1]::  Int[ -1/x^2, {x,-1,1} ]
 
#O[1]:   2
/* SMP makes the error of assuming continuity over the range of integration */
_______________________________________________________________________________
 
#I[1]::  Simtran[{{3,5,7},{11,13,17},{19,23,29}}]
 
	   0   0   0
#O[1]:   {{-},{-},{-}}
	   0   0   0
	 /* Simtran supposedly computes the similarity transformation matrix. */
	 /* The correct result has three non-zero vector entries. */
_______________________________________________________________________________
 
 
	Of course all systems have their share of shortcomings, bugs,
peculiarities, etc.  The results of all computer programs
must be scrutinzed and checked before being applied.  Yet we feel that
computer users will infer from the CACM article and the above examples
that such untrustworthy results are the norm in all ``computer
mathematics'' systems.  This disappoints us deeply, as it does not
fairly reflect the progress made in the field.
 
	On the third page we read: "They [referring to MACSYMA and
REDUCE] are comparatively slow and able to handle comparatively
small symbolic expressions,...".  We think we cannot allow this line
to appear unchallenged.  Again, we present examples.
 
	Our sample problems were run on a Vax 11/780 running Berkely
Unix 4.1 BSD.  Space figures are given in Kilo-Bytes.  Note that the
space figures include the initial space for the system (1910 Kilo-Bytes
for SMP, 163 Kilo-Bytes for Maple).  Times are given in CPU seconds.
 
	Please note that the problems submited are almost trivial examples.
The other systems in our table are quite capable of handling much larger
problems without running out of space.  We percieve that SMP's problems
arose because firstly, some algorithms are clearly innefficient, particularly
space innefficient.  Secondly, unlike the other systems, no garbage collection
took place during these computations.  Garbage collection only occurred after
the compuation had completed (or had ran out of space).  This apparent
inability to perform garbage collection during some these computations
must severly limit the size of many computations than can be completed
successfully using SMP.
 
 
Problem		SMP 1.5.0	Maple 4.0	Reduce 3.1	Macsyma 3.08
 
1		 16.0, 5,012Kb	  .3, 171Kb	  .7		  .15
1a		>60 (*)		  .6, 195Kb	 1.4		  .3
2		 25.8, 4,309Kb	 1.1, 203Kb	 3.6		 9.0
2a		>73 (*)		 3.3, 283Kb	 9.3		26.0
3		 27.6, 3,501Kb	 4.8, 460Kb	 5.4		 8.8
3a		>122 (*)	11.3, 717Kb	29.8		39.3
3b		>115 (*)	10.1, 438Kb	 6.9		21.9
4		>119 (*)	 3.9, 218Kb	 2.3		 5.7
5		>75 (*)		 4.8, 285Kb	12.4		  .8
5a		>71 (*)		29.6, 554Kb	 2.0		 1.8
6		>71 (*)		  .6, 201Kb	 2.1		  .6
7		>90 (*)		 2.2, 228Kb	 2.2		15.0
 
-----------------------------------------------------------------------------
(*) SMP ran out of space (exceeded the default 7.2 Mega-Byte storage limit)
 
Problem 1:  Integer division:	divide 3^5000 by 3^30
Problem 1a:  			divide 3^10000 by 3^30
Problem 2:  Rational addition:	sum(1/k,k=1..200)
Problem 2a:  			sum(1/k,k=1..400)
Problem 3:  Polynomial multiplication:	s := sum(k*x^k,k=1..64);  expand(s^2);
Problem 3a:				s := sum(k*x^k,k=1..128);  expand(s^2);
Problem 3b:  Let p = 1+x+y+z*y+z.  expand p^5 then expand that squared
Problem 4:  Polynomial division		divide expand(p^6) by expand(p^3)
Problem 5:  Polynomial factorization	factor expand( (x^2+y^3)^3 )
Problem 5a:  				factor  x^6 - y^6
Problem 6:  Polynomial Gcd:	Let f = (107*x+53)^7 and g = (109*x+59)^7 .
				Compute the gcd( expand(f), expand(g) ) .
Problem 7: integrate  x * exp(a*x) * sin(b*x)  with respect to x .
 
 
 
	On the same page we find the comment:  "SMP was probably the
first system designed from the start to be a general computer mathematics
language".  We find this surprising as it contradicts what we remember
from some of Wolfram's own presentations of SMP as a system designed
to satisfy the needs of physicists.  Furthermore, such a statement belittles
the work of others designing general-purpose ``computer mathematics
systems'' which have been available freely or commercially over the past
15 years.
 
Only the author or the people responsible for the SMP system can
attempt to undo the harm caused by the CACM article.  We sincerely hope
they rectify this either by substantially improving the system or by
retracting these claims.
 
				Symbolic Computation Group
				Department of Computer Science
				University of Waterloo
				Waterloo, Ontario, Canada.
				{decvax,inhp4}!watmath!watmum!watmaple

If anyone is interested, I have copies of two UWaterloo reports on MAPLE:
one, comparative performance analysis of MAPLE, SMP and MACSYMA, and; two,
a sample MAPLE session.  Being at the University (managing a joint DEC/ICR
research program), I have access to Keith Geddes and the Symbolic Math folks.

I've seen MAPLE and its pretty impressive, certainly better than SMP (hence
the flame in -.1) and is certainly multiuser unlike MACSYMA (16 users on
780/VMS) altho I believe MACSYMA has more funtionality currently.  MAPLE
has been ported to mV2/VS2; graphics require more work (in progress).

If tech reports/MAPLE tape desired, send MAIL.

Paul.  {In_the_land_of_ice_and_snow_as_of_last_Fri}

The December issue of the Communications of the ACM had two letters
by well-known people in the symbolic math field complaining
about the "SMP article".