udiv, urem, urembymul, urembymul_precomp, ugcd

udiv(p1,p2)

urem(p1,p2)

urembymul(p1,p2)

urembymul_precomp(p1,p2,inv)

ugcd(p1,p2)

:: Division and GCD for univariate polynomials.

return

univariate polynomial

p1,p2,inv

univariate polynomial

• For univariate polynomials p1 and p2, there exist polynomials q and r such that p1=q*p2+r and the degree of r is less than that of p2. Then udiv returns q, urem and urembymul return r. ugcd returns the polynomial GCD of p1 and p2. These functions are specially tuned up for dense univariate polynomials. In urembymul the division by p2 is replaced with the inverse computation of p2 as a power series and two polynomial multiplications. It speeds up the computation when the degrees of inputs are large.
• urembymul_precomp is efficient when one repeats divisions by a fixed polynomial. One has to compute the third argument by ureverse_inv_as_power_series().

[177] setmod_ff(2^160-47);
1461501637330902918203684832716283019655932542929
[178] A=randpoly_ff(200,x)$
[179] B=randpoly_ff(101,x)$
[180] cputime(1)$
0sec(1.597e-05sec)
[181] srem(A,B)$
0.15sec + gc : 0.15sec(0.3035sec)
[182] urem(A,B)$
0.11sec + gc : 0.12sec(0.2347sec)
[183] urembymul(A,B)$          
0.08sec + gc : 0.09sec(0.1651sec)
[184] R=ureverse_inv_as_power_series(B,101)$
0.04sec + gc : 0.03sec(0.063sec)
[185] urembymul_precomp(A,B,R)$             
0.03sec(0.02501sec)

References

section uinv_as_power_series, ureverse_inv_as_power_series.

Go to the first, previous, next, last section, table of contents.