/usr/share/axiom-20170501/src/algebra/BOUNDZRO.spad is in axiom-source 20170501-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 | )abbrev package BOUNDZRO BoundIntegerRoots
++ Author: Manuel Bronstein
++ Date Created: 11 March 1991
++ Date Last Updated: 18 November 1991
++ Description:
++ \spadtype{BoundIntegerRoots} provides functions to
++ find lower bounds on the integer roots of a polynomial.
BoundIntegerRoots(F, UP) : SIG == CODE where
F : Join(Field, RetractableTo Fraction Integer)
UP : UnivariatePolynomialCategory F
Z ==> Integer
Q ==> Fraction Z
K ==> Kernel F
UPQ ==> SparseUnivariatePolynomial Q
ALGOP ==> "%alg"
SIG ==> with
integerBound : UP -> Z
++ integerBound(p) returns a lower bound on the negative integer
++ roots of p, and 0 if p has no negative integer roots.
CODE ==> add
import RationalFactorize(UPQ)
import UnivariatePolynomialCategoryFunctions2(F, UP, Q, UPQ)
qbound : (UP, UPQ) -> Z
zroot1 : UP -> Z
qzroot1: UPQ -> Z
negint : Q -> Z
-- returns 0 if p has no integer root < 0,
-- its negative integer root otherwise
qzroot1 p == negint(- leadingCoefficient(reductum p)/leadingCoefficient p)
-- returns 0 if p has no integer root < 0,
-- its negative integer root otherwise
zroot1 p ==
z := - leadingCoefficient(reductum p) / leadingCoefficient p
(r := retractIfCan(z)@Union(Q, "failed")) case Q => negint(r::Q)
0
-- returns 0 if r is not a negative integer, r otherwise
negint r ==
((u := retractIfCan(r)@Union(Z, "failed")) case Z) and (u::Z < 0) => u::Z
0
if F has ExpressionSpace then
bringDown: F -> Q
-- the random substitution used by bringDown is NOT always a ring-homorphism
-- (because of potential algebraic kernels), but is ALWAYS a Z-linear map.
-- this guarantees that bringing down the coefficients of (x + n) q(x) for an
-- integer n yields a polynomial h(x) which is divisible by x + n
-- the only problem is that evaluating with random numbers can cause a
-- division by 0. We should really be able to trap this error later and
-- reevaluate with a new set of random numbers MB 11/91
bringDown f ==
t := tower f
retract eval(f, t, [random()$Q :: F for k in t])
integerBound p ==
(degree p) = 1 => zroot1 p
q1 := map(bringDown, p)
q2 := map(bringDown, p)
qbound(p, gcd(q1, q2))
else
integerBound p ==
(degree p) = 1 => zroot1 p
qbound(p, map((z1:F):Q +-> retract(z1)@Q, p))
-- we can probably do better here (without factoring)
qbound(p, q) ==
bound:Z := 0
for rec in factors factor q repeat
if ((degree(rec.factor)) = 1) and ((r := qzroot1(rec.factor)) < bound)
and zero? p(r::Q::F) then bound := r
bound
|