sicmutils.polynomial.gcd — sicmutils 0.21.1

*clock* clj/s

*poly-gcd-cache-enable* clj/s

When true, multivariate GCD will cache each recursive step in the Euclidean GCD algorithm, and attempt to shortcut out on a successful cache hit. True by default.

*poly-gcd-debug* clj/s

When true, multivariate GCD will log each u and v input and the result of each step, along with the recursive level of the logged GCD computation. False by default.

*poly-gcd-time-limit* clj/s

Pair of the form [number Keyword], where keyword is one of the supported units from sicmutils.util.stopwatch. If Euclidean GCD takes longer than this time limit, the system will bail out by throwing an exception.

->content+primitive clj/s

(->content+primitive p gcd)

Given some polynomial p, and a multi-arity gcd function for its coefficients, returns a pair of the polynomial's content and primitive.

The 'content' of a polynomial is the greatest common divisor of its coefficients. The 'primitive part' of a polynomial is the quotient of the polynomial by its content.

See Wikipedia's 'Primitive Part and Content' page for more details.

classical-gcd clj/s

(classical-gcd u v)

Higher-level wrapper around full-gcd that:

• optimizes the case where u and v share no variables
• sorts the variables in u and v in order of increasing degree

before attempting full-gcd. See full-gcd for a full description.

full-gcd clj/s

(full-gcd u v)

(full-gcd level u v)

Given two polynomials u and v (potentially multivariate) with non-polynomial coefficients, returns the greatest common divisor of u and v calculated using a multivariate extension of Knuth's algorithm 4.6.1E.

Optionally takes a debugging level. To see the debugging logs generated over the course of the run, set *poly-gcd-debug* to true.

NOTE: full-gcd Internally checks that it hasn't run out a stopwatch set with with-limited-time; you can wrap a call to full-gcd in this function to limit its execution time.

For example, this form will throw a TimeoutException after 1 second:

(with-limited-time [1 :seconds]
  (fn [] (full-gcd u v)))

gcd clj/s

(gcd)

(gcd u)

(gcd u v)

(gcd u v & more)

Returns the greatest common divisor of u and v, calculated by a multivariate extension to the Euclidean algorithm for multivariate polynomials.

u and v can be polynomials or non-polynomials coefficients.

gcd-Dp clj/s

(gcd-Dp p)

Returns the greatest common divisor of all partial derivatives of the polynomial p using binary applications of the gcd algorithm between each partial derivative.

This algorithm assumes that all coefficients are integral, and halts when it encounters a result that responds true to [[sicmutils.value/one?]].

If a non-[[p/Polynomial]] is supplied, returns 1.

gcd-stats clj/s

(gcd-stats)

When called, logs statistics about the GCD memoization cache, and the number of times the system has encountered monomial or other trivial GCDs.

lcm clj/s

(lcm u v)

Returns the least common multiple of (possibly polynomial) arguments u and v, using gcd to calculate the gcd portion of

(/ (g/abs (* u v))
   (gcd u v))

time-expired? clj/s

(time-expired?)

Returns true if the *clock* dynamic variable contains a Stopwatch with an elapsed time that's passed the limit allowed by the dynamic *poly-gcd-time-limit*, false otherwise.

trivial-gcd clj/s

(trivial-gcd u v)

Given two polynomials u and v, attempts to return the greatest common divisor of u and v by testing for trivial cases. If no trivial case applies, returns nil.

univariate-gcd clj/s

(univariate-gcd u v)

Given two univariate polynomials u and v, returns the greatest common divisor of u and v calculated using Knuth's algorithm 4.6.1E.

with-limited-time clj/s

(with-limited-time timeout thunk)

Given an explicit timeout and a no-argument function thunk, calls thunk in a context where *poly-gcd-time-limit* is dynamically bound to timeout. Calling time-expired? or [[maybe-bail-out!]] inside thunk will signal failure appropriately if thunk has taken longer than timeout.