Polynomial GCD via Euclid

Formula: repeat polynomial division, gcd(a, b) = gcd(b, a mod b), until the remainder vanishes; the last non-zero remainder, made monic, is the greatest common divisor. Algorithm E of Knuth, TAOCP Vol. 2, sec. 4.6.1, run over the reals with a numerical tolerance in place of exact zero testing.

Usage

EuclP(p, q, tol = 1e-10)

Arguments

p, q

Coefficient vectors in ascending order.

tol

Magnitude at or below which a leading coefficient is zero.

Value

List with estimate, gcd, degree, steps, n, method.

Details

Coefficients are ASCENDING: c(c0, c1, c2) means c0 + c1 x + c2 x^2.

References

Knuth (1997), The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed., sec. 4.6.1, Addison-Wesley.

Examples

V <- c(1, 2, 3, 4, 5, 6, 7, 8)
EuclP(V, V)
#> $estimate
#> [1] 7
#> 
#> $gcd
#> [1] 0.125 0.250 0.375 0.500 0.625 0.750 0.875 1.000
#> 
#> $degree
#> [1] 7
#> 
#> $steps
#> [1] 1
#> 
#> $n
#> [1] 8
#> 
#> $method
#> [1] "Polynomial GCD via Euclid"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"