Initial population.

1 files changed, 392 insertions, 0 deletions

diff --git a/src/algebra/sign.spad.pamphlet b/src/algebra/sign.spad.pamphlet
new file mode 100644
index 00000000..a9c3a5c3
--- /dev/null
+++ b/src/algebra/sign.spad.pamphlet
@@ -0,0 +1,392 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra sign.spad}
+\author{Manuel Bronstein}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\section{package TOOLSIGN ToolsForSign}
+<<package TOOLSIGN ToolsForSign>>=
+)abbrev package TOOLSIGN ToolsForSign
+++ Tools for the sign finding utilities
+++ Author: Manuel Bronstein
+++ Date Created: 25 August 1989
+++ Date Last Updated: 26 November 1991
+++ Description: Tools for the sign finding utilities.
+ToolsForSign(R:Ring): with
+    sign     : R      -> Union(Integer, "failed")
+	++ sign(r) \undocumented
+    nonQsign : R      -> Union(Integer, "failed")
+	++ nonQsign(r) \undocumented
+    direction: String -> Integer
+	++ direction(s) \undocumented
+ == add
+ 
+    if R is AlgebraicNumber then
+      nonQsign r ==
+        sign((r pretend AlgebraicNumber)::Expression(
+                  Integer))$ElementaryFunctionSign(Integer, Expression Integer)
+    else
+      nonQsign r == "failed"
+ 
+    if R has RetractableTo Fraction Integer then
+      sign r ==
+        (u := retractIfCan(r)@Union(Fraction Integer, "failed"))
+          case Fraction(Integer) => sign(u::Fraction Integer)
+        nonQsign r
+ 
+    else
+      if R has RetractableTo Integer then
+        sign r ==
+          (u := retractIfCan(r)@Union(Integer, "failed"))
+            case "failed" => "failed"
+          sign(u::Integer)
+ 
+      else
+        sign r ==
+          zero? r => 0
+--          one? r => 1
+          r = 1 => 1
+          r = -1 => -1
+          "failed"
+ 
+    direction st ==
+      st = "right" => 1
+      st = "left" => -1
+      error "Unknown option"
+
+@
+\section{package INPSIGN InnerPolySign}
+<<package INPSIGN InnerPolySign>>=
+)abbrev package INPSIGN InnerPolySign
+--%% InnerPolySign
+++ Author: Manuel Bronstein
+++ Date Created: 23 Aug 1989
+++ Date Last Updated: 19 Feb 1990
+++ Description:
+++ Find the sign of a polynomial around a point or infinity.
+InnerPolySign(R, UP): Exports == Implementation where
+  R : Ring
+  UP: UnivariatePolynomialCategory R
+ 
+  U ==> Union(Integer, "failed")
+ 
+  Exports ==> with
+    signAround: (UP,    Integer, R -> U) -> U
+	++ signAround(u,i,f) \undocumented
+    signAround: (UP, R, Integer, R -> U) -> U
+	++ signAround(u,r,i,f) \undocumented
+    signAround: (UP, R,          R -> U) -> U
+	++ signAround(u,r,f) \undocumented
+ 
+  Implementation ==> add
+    signAround(p:UP, x:R, rsign:R -> U) ==
+      (ur := signAround(p, x,  1, rsign)) case "failed" => "failed"
+      (ul := signAround(p, x, -1, rsign)) case "failed" => "failed"
+      (ur::Integer) = (ul::Integer) => ur
+      "failed"
+ 
+    signAround(p, x, dir, rsign) ==
+      zero? p => 0
+      zero?(r := p x) =>
+        (u := signAround(differentiate p, x, dir, rsign)) case "failed"
+          => "failed"
+        dir * u::Integer
+      rsign r
+ 
+    signAround(p:UP, dir:Integer, rsign:R -> U) ==
+      zero? p => 0
+      (u := rsign leadingCoefficient p) case "failed" => "failed"
+      (dir > 0) or (even? degree p) => u::Integer
+      - (u::Integer)
+
+@
+\section{package SIGNRF RationalFunctionSign}
+<<package SIGNRF RationalFunctionSign>>=
+)abbrev package SIGNRF RationalFunctionSign
+--%% RationalFunctionSign
+++ Author: Manuel Bronstein
+++ Date Created: 23 August 1989
+++ Date Last Updated: 26 November 1991
+++ Description:
+++ Find the sign of a rational function around a point or infinity.
+RationalFunctionSign(R:GcdDomain): Exports == Implementation where
+  SE  ==> Symbol
+  P   ==> Polynomial R
+  RF  ==> Fraction P
+  ORF ==> OrderedCompletion RF
+  UP  ==> SparseUnivariatePolynomial RF
+  U   ==> Union(Integer, "failed")
+  SGN ==> ToolsForSign(R)
+ 
+  Exports ==> with
+    sign: RF -> U
+      ++ sign f returns the sign of f if it is constant everywhere.
+    sign: (RF, SE, ORF) -> U
+      ++ sign(f, x, a) returns the sign of f as x approaches \spad{a},
+      ++ from both sides if \spad{a} is finite.
+    sign: (RF, SE, RF, String) -> U
+      ++ sign(f, x, a, s) returns the sign of f as x nears \spad{a} from
+      ++ the left (below) if s is the string \spad{"left"},
+      ++ or from the right (above) if s is the string \spad{"right"}.
+ 
+  Implementation ==> add
+    import SGN
+    import InnerPolySign(RF, UP)
+    import PolynomialCategoryQuotientFunctions(IndexedExponents SE,
+                                                      SE, R, P, RF)
+ 
+    psign     : P -> U
+    sqfrSign  : P -> U
+    termSign  : P -> U
+    listSign  : (List P, Integer) -> U
+    finiteSign: (Fraction UP, RF) -> U
+ 
+    sign f ==
+      (un := psign numer f) case "failed" => "failed"
+      (ud := psign denom f) case "failed" => "failed"
+      (un::Integer) * (ud::Integer)
+ 
+    finiteSign(g, a) ==
+      (ud := signAround(denom g, a, sign$%)) case "failed" => "failed"
+      (un := signAround(numer g, a, sign$%)) case "failed" => "failed"
+      (un::Integer) * (ud::Integer)
+ 
+    sign(f, x, a) ==
+      g := univariate(f, x)
+      zero?(n := whatInfinity a) => finiteSign(g, retract a)
+      (ud := signAround(denom g, n, sign$%)) case "failed" => "failed"
+      (un := signAround(numer g, n, sign$%)) case "failed" => "failed"
+      (un::Integer) * (ud::Integer)
+ 
+    sign(f, x, a, st) ==
+      (ud := signAround(denom(g := univariate(f, x)), a,
+                    d := direction st, sign$%)) case "failed" => "failed"
+      (un := signAround(numer g, a, d, sign$%)) case "failed" => "failed"
+      (un::Integer) * (ud::Integer)
+ 
+    psign p ==
+      (r := retractIfCan(p)@Union(R, "failed")) case R => sign(r::R)$SGN
+      (u := sign(retract(unit(s := squareFree p))@R)$SGN) case "failed" =>
+        "failed"
+      ans := u::Integer
+      for term in factors s | odd?(term.exponent) repeat
+        (u := sqfrSign(term.factor)) case "failed" => return "failed"
+        ans := ans * (u::Integer)
+      ans
+ 
+    sqfrSign p ==
+      (u := termSign first(l := monomials p)) case "failed" => "failed"
+      listSign(rest l, u::Integer)
+ 
+    listSign(l, s) ==
+      for term in l repeat
+        (u := termSign term) case "failed" => return "failed"
+        u::Integer ^= s => return "failed"
+      s
+ 
+    termSign term ==
+      for var in variables term repeat
+        odd? degree(term, var) => return "failed"
+      sign(leadingCoefficient term)$SGN
+
+@
+\section{package LIMITRF RationalFunctionLimitPackage}
+<<package LIMITRF RationalFunctionLimitPackage>>=
+)abbrev package LIMITRF RationalFunctionLimitPackage
+++ Computation of limits for rational functions
+++ Author: Manuel Bronstein
+++ Date Created: 4 October 1989
+++ Date Last Updated: 26 November 1991
+++ Description: Computation of limits for rational functions.
+++ Keywords: limit, rational function.
+RationalFunctionLimitPackage(R:GcdDomain):Exports==Implementation where
+  Z       ==> Integer
+  P       ==> Polynomial R
+  RF      ==> Fraction P
+  EQ      ==> Equation
+  ORF     ==> OrderedCompletion RF
+  OPF     ==> OnePointCompletion RF
+  UP      ==> SparseUnivariatePolynomial RF
+  SE      ==> Symbol
+  QF      ==> Fraction SparseUnivariatePolynomial RF
+  Result  ==> Union(ORF, "failed")
+  TwoSide ==> Record(leftHandLimit:Result, rightHandLimit:Result)
+  U       ==> Union(ORF, TwoSide, "failed")
+  RFSGN   ==> RationalFunctionSign(R)
+ 
+  Exports ==> with
+-- The following are the one we really want, but the interpreter cannot
+-- handle them...
+--  limit: (RF,EQ ORF) -> U
+--  ++ limit(f(x),x,a) computes the real two-sided limit lim(x -> a,f(x))
+ 
+--  complexLimit: (RF,EQ OPF) -> OPF
+--  ++ complexLimit(f(x),x,a) computes the complex limit lim(x -> a,f(x))
+ 
+-- ... so we replace them by the following 4:
+    limit: (RF,EQ OrderedCompletion P) -> U
+      ++ limit(f(x),x = a) computes the real two-sided limit
+      ++ of f as its argument x approaches \spad{a}.
+    limit: (RF,EQ RF) -> U
+      ++ limit(f(x),x = a) computes the real two-sided limit
+      ++ of f as its argument x approaches \spad{a}.
+    complexLimit: (RF,EQ OnePointCompletion P) -> OPF
+      ++ \spad{complexLimit(f(x),x = a)} computes the complex limit
+      ++ of \spad{f} as its argument x approaches \spad{a}.
+    complexLimit: (RF,EQ RF) -> OPF
+      ++ complexLimit(f(x),x = a) computes the complex limit
+      ++ of f as its argument x approaches \spad{a}.
+    limit: (RF,EQ RF,String) -> Result
+      ++ limit(f(x),x,a,"left") computes the real limit
+      ++ of f as its argument x approaches \spad{a} from the left;
+      ++ limit(f(x),x,a,"right") computes the corresponding limit as x
+      ++ approaches \spad{a} from the right.
+ 
+  Implementation ==> add
+    import ToolsForSign R
+    import InnerPolySign(RF, UP)
+    import RFSGN
+    import PolynomialCategoryQuotientFunctions(IndexedExponents SE,
+                                                      SE, R, P, RF)
+ 
+    finiteComplexLimit: (QF, RF) -> OPF
+    finiteLimit       : (QF, RF) -> U
+    fLimit            : (Z, UP, RF, Z) -> Result
+ 
+-- These 2 should be exported, see comment above
+    locallimit       : (RF, SE, ORF) -> U
+    locallimitcomplex: (RF, SE, OPF) -> OPF
+ 
+    limit(f:RF,eq:EQ RF) ==
+      (xx := retractIfCan(lhs eq)@Union(SE,"failed")) case "failed" =>
+        error "limit: left hand side must be a variable"
+      x := xx :: SE; a := rhs eq
+      locallimit(f,x,a::ORF)
+ 
+    complexLimit(f:RF,eq:EQ RF) ==
+      (xx := retractIfCan(lhs eq)@Union(SE,"failed")) case "failed" =>
+        error "limit: left hand side must be a variable"
+      x := xx :: SE; a := rhs eq
+      locallimitcomplex(f,x,a::OPF)
+ 
+    limit(f:RF,eq:EQ OrderedCompletion P) ==
+      (p := retractIfCan(lhs eq)@Union(P,"failed")) case "failed" =>
+        error "limit: left hand side must be a variable"
+      (xx := retractIfCan(p)@Union(SE,"failed")) case "failed" =>
+        error "limit: left hand side must be a variable"
+      x := xx :: SE
+      a := map(#1::RF,rhs eq)$OrderedCompletionFunctions2(P,RF)
+      locallimit(f,x,a)
+ 
+    complexLimit(f:RF,eq:EQ OnePointCompletion P) ==
+      (p := retractIfCan(lhs eq)@Union(P,"failed")) case "failed" =>
+        error "limit: left hand side must be a variable"
+      (xx := retractIfCan(p)@Union(SE,"failed")) case "failed" =>
+        error "limit: left hand side must be a variable"
+      x := xx :: SE
+      a := map(#1::RF,rhs eq)$OnePointCompletionFunctions2(P,RF)
+      locallimitcomplex(f,x,a)
+ 
+    fLimit(n, d, a, dir) ==
+      (s := signAround(d, a, dir, sign$RFSGN)) case "failed" => "failed"
+      n * (s::Z) * plusInfinity()
+ 
+    finiteComplexLimit(f, a) ==
+      zero?(n := (numer f) a) => 0
+      zero?(d := (denom f) a) => infinity()
+      (n / d)::OPF
+ 
+    finiteLimit(f, a) ==
+      zero?(n := (numer f) a) => 0
+      zero?(d := (denom f) a) =>
+        (s := sign(n)$RFSGN) case "failed" => "failed"
+        rhsl := fLimit(s::Z, denom f, a, 1)
+        lhsl := fLimit(s::Z, denom f, a, -1)
+        rhsl case "failed" =>
+          lhsl case "failed" => "failed"
+          [lhsl, rhsl]
+        lhsl case "failed" => [lhsl, rhsl]
+        rhsl::ORF = lhsl::ORF => lhsl::ORF
+        [lhsl, rhsl]
+      (n / d)::ORF
+ 
+    locallimit(f,x,a) ==
+      g := univariate(f, x)
+      zero?(n := whatInfinity a) => finiteLimit(g, retract a)
+      (dn := degree numer g) > (dd := degree denom g) =>
+        (sn := signAround(numer g, n, sign$RFSGN)) case "failed" => "failed"
+        (sd := signAround(denom g, n, sign$RFSGN)) case "failed" => "failed"
+        (sn::Z) * (sd::Z) * plusInfinity()
+      dn < dd => 0
+      ((leadingCoefficient numer g) / (leadingCoefficient denom g))::ORF
+ 
+    limit(f,eq,st) ==
+      (xx := retractIfCan(lhs eq)@Union(SE,"failed")) case "failed" =>
+        error "limit: left hand side must be a variable"
+      x := xx :: SE; a := rhs eq
+      zero?(n := (numer(g := univariate(f, x))) a) => 0
+      zero?(d := (denom g) a) =>
+        (s := sign(n)$RFSGN) case "failed" => "failed"
+        fLimit(s::Z, denom g, a, direction st)
+      (n / d)::ORF
+ 
+    locallimitcomplex(f,x,a) ==
+      g := univariate(f, x)
+      (r := retractIfCan(a)@Union(RF, "failed")) case RF =>
+        finiteComplexLimit(g, r::RF)
+      (dn := degree numer g) > (dd := degree denom g) => infinity()
+      dn < dd => 0
+      ((leadingCoefficient numer g) / (leadingCoefficient denom g))::OPF
+
+@
+\section{License}
+<<license>>=
+--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
+--All rights reserved.
+--
+--Redistribution and use in source and binary forms, with or without
+--modification, are permitted provided that the following conditions are
+--met:
+--
+--    - Redistributions of source code must retain the above copyright
+--      notice, this list of conditions and the following disclaimer.
+--
+--    - Redistributions in binary form must reproduce the above copyright
+--      notice, this list of conditions and the following disclaimer in
+--      the documentation and/or other materials provided with the
+--      distribution.
+--
+--    - Neither the name of The Numerical ALgorithms Group Ltd. nor the
+--      names of its contributors may be used to endorse or promote products
+--      derived from this software without specific prior written permission.
+--
+--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 OWNER
+--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.
+@
+<<*>>=
+<<license>>
+ 
+<<package TOOLSIGN ToolsForSign>>
+<<package INPSIGN InnerPolySign>>
+<<package SIGNRF RationalFunctionSign>>
+<<package LIMITRF RationalFunctionLimitPackage>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}