path: root/src/hyper/pages/RECLOS.ht

% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
\newcommand{\RealClosureXmpTitle}{RealClosure}
\newcommand{\RealClosureXmpNumber}{9.66}
%
% =====================================================================
\begin{page}{RealClosureXmpPage}{9.66 RealClosure}
% =====================================================================
\beginscroll


The Real Closure 1.0 package provided by Renaud Rioboo (Renaud.Rioboo@lip6.fr) consists of different
packages, categories and domains :

\begin{items}
\item The package \axiomType{RealPolynomialUtilitiesPackage} which needs a \axiomType{Field} {\em F} and a
\axiomType{UnivariatePolynomialCategory} domain with coefficients in {\em F}. It computes some
simple functions such as Sturm and Sylvester sequences 
(\axiomOpFrom{sturmSequence}{RealPolynomialUtilitiesPackage}, 
\axiomOpFrom{sylvesterSequence}{RealPolynomialUtilitiesPackage}).

\item The category \axiomType{RealRootCharacterizationCategory} provides abstract
functions to work with "real roots" of univariate polynomials. These
resemble variables with some functionality needed to compute important
operations.

\item The category \axiomType{RealClosedField} provides common operations available over
real closed fiels. These include finding all the roots of a univariate
polynomial, taking square (and higher) roots, ...

\item The domain \axiomType{RightOpenIntervalRootCharacterization} is the main code that
provides the functionality of \axiomType{RealRootCharacterizationCategory} for the case
of archimedean fields. Abstract roots are encoded with a left closed right
open interval containing the root together with a defining polynomial for the
root.

\item  The \axiomType{RealClosure} domain is the end-user code. It provides usual arithmetic
with real algebraic numbers, along with the functionality of a real closed
field. It also provides functions to approximate a real algebraic number by an
element of the base field. This approximation may either be absolute
(\axiomOpFrom{approximate}{RealClosure}) or relative (\axiomOpFrom{relativeApprox}{RealClosure}).


\end{items}

\centerline{CAVEATS}

Since real algebraic expressions are stored as depending on "real roots" which
are managed like variables, there is an ordering on these. This ordering is
dynamical in the sense that any new algebraic takes precedence over older
ones. In particular every creation function raises a new "real root". This has
the effect that when you type something like \spad{sqrt(2) + sqrt(2)} you have two
new variables which happen to be equal. To avoid this name the expression such
as in \spad{s2 := sqrt(2) ; s2 + s2}

Also note that computing times depend strongly on the ordering you implicitly
provide. Please provide algebraics in the order which seems most natural to you.

\centerline{LIMITATIONS}

This packages uses
algorithms which are published in [1] and [2] which are based on field
arithmetics, in particular for polynomial gcd related algorithms. This can be
quite slow for high degree polynomials and subresultants methods usually work
best. Beta versions of the package try to use these techniques in a better
way and work significantly faster. These are mostly based on unpublished
algorithms and cannot be distributed. Please contact the author if you have a
particular problem to solve or want to use these versions.

Be aware that approximations behave as post-processing and that all
computations are done excatly. They can thus be quite time consuming when
depending on several "real roots".

\centerline{REFERENCES}


[1]  R. Rioboo : Real Algebraic Closure of an ordered Field : Implementation 
     in Axiom. 
     In proceedings of the ISSAC'92 Conference, Berkeley 1992 pp. 206-215.

[2]  Z. Ligatsikas, R. Rioboo, M. F. Roy : Generic computation of the real
     closure of an ordered field.
     In Mathematics and Computers in Simulation Volume 42, Issue 4-6,
     November 1996.

\centerline{EXAMPLES}
\xtc{
We shall work with the real closure of the ordered field of 
rational numbers.
}{
\spadpaste{Ran := RECLOS(FRAC INT) \bound{Ran}}
}
\xtc{
Some simple signs for square roots, these correspond to an extension
of degree 16 of the rational numbers. Examples provided by J. Abbot.
}{
\spadpaste{fourSquares(a:Ran,b:Ran,c:Ran,d:Ran):Ran == sqrt(a)+sqrt(b) - sqrt(c)-sqrt(d) \free{Ran} \bound{fs}}
}
\xtc{
These produce values very close to zero.
}{
\spadpaste{squareDiff1 := fourSquares(73,548,60,586) \free{fs}\bound{sd1}}
}
\xtc{
}{
\spadpaste{recip(squareDiff1)\free{sd1}}
}
\xtc{
}{
\spadpaste{sign(squareDiff1)\free{sd1}}
}
\xtc{
}{
\spadpaste{squareDiff2 := fourSquares(165,778,86,990) \free{fs}\bound{sd2}}
}
\xtc{
}{
\spadpaste{recip(squareDiff2)\free{sd2}}
}
\xtc{
}{
\spadpaste{sign(squareDiff2)\free{sd2}}
}
\xtc{
}{
\spadpaste{squareDiff3 := fourSquares(217,708,226,692) \free{fs}\bound{sd3}}
}
\xtc{
}{
\spadpaste{recip(squareDiff3)\free{sd3}}
}
\xtc{
}{
\spadpaste{sign(squareDiff3)\free{sd3}}
}
\xtc{
}{
\spadpaste{squareDiff4 := fourSquares(155,836,162,820)  \free{fs}\bound{sd4}}
}
\xtc{
}{
\spadpaste{recip(squareDiff4)\free{sd4}}
}
\xtc{
}{
\spadpaste{sign(squareDiff4)\free{sd4}}
}
\xtc{
}{
\spadpaste{squareDiff5 := fourSquares(591,772,552,818) \free{fs}\bound{sd5}}
}
\xtc{
}{
\spadpaste{recip(squareDiff5)\free{sd5}}
}
\xtc{
}{
\spadpaste{sign(squareDiff5)\free{sd5}}
}
\xtc{
}{
\spadpaste{squareDiff6 := fourSquares(434,1053,412,1088) \free{fs}\bound{sd6}}
}
\xtc{
}{
\spadpaste{recip(squareDiff6)\free{sd6}}
}
\xtc{
}{
\spadpaste{sign(squareDiff6)\free{sd6}}
}
\xtc{
}{
\spadpaste{squareDiff7 := fourSquares(514,1049,446,1152) \free{fs}\bound{sd7}}
}
\xtc{
}{
\spadpaste{recip(squareDiff7)\free{sd7}}
}
\xtc{
}{
\spadpaste{sign(squareDiff7)\free{sd7}}
}
\xtc{
}{
\spadpaste{squareDiff8 := fourSquares(190,1751,208,1698) \free{fs}\bound{sd8}}
}
\xtc{
}{
\spadpaste{recip(squareDiff8)\free{sd8}}
}
\xtc{
}{
\spadpaste{sign(squareDiff8)\free{sd8}}
}
\xtc{
This should give three digits of precision
}{
\spadpaste{relativeApprox(squareDiff8,10**(-3))::Float \free{sd8}}
}
\xtc{
The sum of these 4 roots is 0
}{
\spadpaste{l := allRootsOf((x**2-2)**2-2)$Ran \free{Ran} \bound{l}}
}
\xtc{
Check that they are all roots of the same polynomial
}{
\spadpaste{removeDuplicates map(mainDefiningPolynomial,l) \free{l}}
}
\xtc{
We can see at a glance that they are separate roots
}{
\spadpaste{map(mainCharacterization,l) \free{l}}
}
\xtc{
Check the sum and product
}{
\spadpaste{[reduce(+,l),reduce(*,l)-2] \free{l}}
}
\xtc{
A more complicated test that involve an extension of degree 256.
This is a way of checking nested radical identities.
}{
\spadpaste{(s2, s5, s10) := (sqrt(2)$Ran, sqrt(5)$Ran, sqrt(10)$Ran) \free{Ran}\bound{s2}\bound{s5}\bound{s10}}
}
\xtc{
}{
\spadpaste{eq1:=sqrt(s10+3)*sqrt(s5+2) - sqrt(s10-3)*sqrt(s5-2) = sqrt(10*s2+10) \free{s2}\free{s5}\free{s10}\bound{eq1}}
}
\xtc{
}{
\spadpaste{eq1::Boolean \free{eq1}}
}
\xtc{
}{
\spadpaste{eq2:=sqrt(s5+2)*sqrt(s2+1) - sqrt(s5-2)*sqrt(s2-1) = sqrt(2*s10+2)\free{s2}\free{s5}\free{s10}\bound{eq2}}
}
\xtc{
}{
\spadpaste{eq2::Boolean \free{eq2}}
}
\xtc{
Some more examples from J. M. Arnaudies
}{
\spadpaste{s3 := sqrt(3)$Ran \free{Ran}\bound{s3}}
}
\xtc{
}{
\spadpaste{s7:= sqrt(7)$Ran \free{Ran}\bound{s7}}
}
\xtc{
}{
\spadpaste{e1 := sqrt(2*s7-3*s3,3) \free{s7} \free{s3} \bound{e1}}
}
\xtc{
}{
\spadpaste{e2 := sqrt(2*s7+3*s3,3) \free{s7} \free{s3} \bound{e2}}
}
\xtc{
This should be null
}{
\spadpaste{e2-e1-s3 \free{e2} \free{e1} \free{s3}}
}
\xtc{
A quartic polynomial
}{
\spadpaste{pol : UP(x,Ran) := x**4+(7/3)*x**2+30*x-(100/3) \free{Ran} \bound{pol}}
}
\xtc{
Add some cubic roots
}{
\spadpaste{r1 := sqrt(7633)$Ran \free{Ran}\bound{r1}}
}
\xtc{
}{
\spadpaste{alpha := sqrt(5*r1-436,3)/3 \free{r1} \bound{alpha}}
}
\xtc{
}{
\spadpaste{beta := -sqrt(5*r1+436,3)/3 \free{r1} \bound{beta}}
}
\xtc{
this should be null
}{
\spadpaste{pol.(alpha+beta-1/3) \free{pol} \free{alpha} \free{beta}}
}
\xtc{
A quintic polynomial
}{
\spadpaste{qol : UP(x,Ran) := x**5+10*x**3+20*x+22 \free{Ran}\bound{qol}}
}
\xtc{
Add some cubic roots
}{
\spadpaste{r2 := sqrt(153)$Ran \free{Ran}\bound{r2}}
}
\xtc{
}{
\spadpaste{alpha2 := sqrt(r2-11,5) \free{r2}\bound{alpha2}}
}
\xtc{
}{
\spadpaste{beta2 := -sqrt(r2+11,5) \free{r2}\bound{beta2}}
}
\xtc{
this should be null
}{
\spadpaste{qol(alpha2+beta2) \free{qol}\free{alpha2}\free{beta2}}
}
\xtc{
Finally, some examples from the book Computer Algebra by 
Davenport, Siret and Tournier (page 77).
The last one is due to Ramanujan.
}{
\spadpaste{dst1:=sqrt(9+4*s2)=1+2*s2 \free{s2}\bound{dst1}}
}
\xtc{
}{
\spadpaste{dst1::Boolean \free{dst1}}
}
\xtc{
}{
\spadpaste{s6:Ran:=sqrt 6 \free{Ran}\bound{s6}}
}
\xtc{
}{
\spadpaste{dst2:=sqrt(5+2*s6)+sqrt(5-2*s6) = 2*s3 \free{s6}\free{s3}\bound{dst2}}
}
\xtc{
}{
\spadpaste{dst2::Boolean \free{dst2}}
}
\xtc{
}{
\spadpaste{s29:Ran:=sqrt 29 \free{Ran}\bound{s29}}
}
\xtc{
}{
\spadpaste{dst4:=sqrt(16-2*s29+2*sqrt(55-10*s29)) = sqrt(22+2*s5)-sqrt(11+2*s29)+s5 \free{s29}\free{s5}\bound{dst4}}
}
\xtc{
}{
\spadpaste{dst4::Boolean \free{dst4}}
}
\xtc{
}{
\spadpaste{dst6:=sqrt((112+70*s2)+(46+34*s2)*s5) = (5+4*s2)+(3+s2)*s5 \free{s2}\free{s5}\bound{dst6}}
}
\xtc{
}{
\spadpaste{dst6::Boolean \free{dst6}}
}
\xtc{
}{
\spadpaste{f3:Ran:=sqrt(3,5) \free{Ran}\bound{f3}}
}
\xtc{
}{
\spadpaste{f25:Ran:=sqrt(1/25,5) \free{Ran}\bound{f25}}
}
\xtc{
}{
\spadpaste{f32:Ran:=sqrt(32/5,5) \free{Ran}\bound{f32}}
}
\xtc{
}{
\spadpaste{f27:Ran:=sqrt(27/5,5) \free{Ran}\bound{f27}}
}
\xtc{
}{
\spadpaste{dst5:=sqrt((f32-f27,3)) = f25*(1+f3-f3**2)\free{f32}\free{f27}\free{f25}\free{f3}\bound{dst5}}
}
\xtc{
}{
\spadpaste{dst5::Boolean \free{dst5}}
}

\endscroll
\autobuttons
\end{page}
%