[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

6.4 Univariate polynomials


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

6.4.1 umul, umul_ff, usquare, usquare_ff, utmul, utmul_ff

umul(p1,p2)
umul_ff(p1,p2)

:: Fast multiplication of univariate polynomials

usquare(p1)
usquare_ff(p1)

:: Fast squaring of a univariate polynomial

utmul(p1,p2,d)
utmul_ff(p1,p2,d)

:: Fast multiplication of univariate polynomials with truncation

return

univariate polynomial

p1 p2

univariate polynomial

d

non-negative integer

[176] load("fff")$
[177] cputime(1)$
0sec(1.407e-05sec)
[178] setmod_ff(2^160-47);
1461501637330902918203684832716283019655932542929
0sec(0.00028sec)
[179] A=randpoly_ff(100,x)$
0sec(0.001422sec)
[180] B=randpoly_ff(100,x)$
0sec(0.00107sec)
[181] for(I=0;I<100;I++)A*B;
7.77sec + gc : 8.38sec(16.15sec)
[182] for(I=0;I<100;I++)umul(A,B);
2.24sec + gc : 1.52sec(3.767sec)
[183] for(I=0;I<100;I++)umul_ff(A,B);
1.42sec + gc : 0.24sec(1.653sec)
[184] for(I=0;I<100;I++)usquare_ff(A);  
1.08sec + gc : 0.21sec(1.297sec)
[185] for(I=0;I<100;I++)utmul_ff(A,B,100);
1.2sec + gc : 0.17sec(1.366sec)
[186] deg(utmul_ff(A,B,100),x);
100
References

set_upkara, set_uptkara, set_upfft, kmul, ksquare, ktmul.


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

6.4.2 kmul, ksquare, ktmul

kmul(p1,p2)

:: Fast multiplication of univariate polynomials

ksquare(p1)

:: Fast squaring of a univariate polynomial

ktmul(p1,p2,d)

:: Fast multiplication of univariate polynomials with truncation

return

univariate polynomial

p1 p2

univariate polynomial

d

non-negative integer

[0] load("code/fff");
1
[34] setmod_ff(defpoly_mod2(160));
x^160+x^5+x^3+x^2+1
[35] A=randpoly_ff(100,x)$
[36] B=randpoly_ff(100,x)$
[37] umul(A,B)$
umul : invalid argument
return to toplevel
[37] kmul(A,B)$

[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

6.4.3 set_upkara, set_uptkara, set_upfft

set_upkara([threshold])
set_uptkara([threshold])
set_upfft([threshold])

:: Set thresholds in the selection of an algorithm from N^2, Karatsuba, FFT algorithms for univariate polynomial multiplication.

return

value currently set

threshold

non-negative integer

References

kmul, ksquare, ktmul, umul, umul_ff, usquare, usquare_ff, utmul, utmul_ff.


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

6.4.4 utrunc, udecomp, ureverse

utrunc(p,d)
udecomp(p,d)
ureverse(p)

:: Operations on polynomials

return

univariate polynomial or list of univariate polynomials

p

univariate polynomial

d

non-negative integer

[132] utrunc((x+1)^10,5);
252*x^5+210*x^4+120*x^3+45*x^2+10*x+1
[133] udecomp((x+1)^10,5);
[252*x^5+210*x^4+120*x^3+45*x^2+10*x+1,x^4+10*x^3+45*x^2+120*x+210]
[134] ureverse(3*x^3+x^2+2*x);
2*x^2+x+3
References

udiv, urem, urembymul, urembymul_precomp, ugcd.


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

6.4.5 uinv_as_power_series, ureverse_inv_as_power_series

uinv_as_power_series(p,d)
ureverse_inv_as_power_series(p,d)

:: Computes the truncated inverse as a power series.

return

univariate polynomial

p

univariate polynomial

d

non-negative integer

[123] A=(x+1)^5;                 
x^5+5*x^4+10*x^3+10*x^2+5*x+1
[124] uinv_as_power_series(A,5); 
-126*x^5+70*x^4-35*x^3+15*x^2-5*x+1
[126] A*R;
-126*x^10-560*x^9-945*x^8-720*x^7-210*x^6+1
[127] A=x^10+x^9;
x^10+x^9
[128] R=ureverse_inv_as_power_series(A,5);
-x^5+x^4-x^3+x^2-x+1
[129] ureverse(A)*R;
-x^6+1
References

utrunc, udecomp, ureverse, udiv, urem, urembymul, urembymul_precomp, ugcd.


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

6.4.6 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

[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

uinv_as_power_series, ureverse_inv_as_power_series.


[ << ] [ < ] [ Up ] [ > ] [ >> ]

This document was generated on December 18, 2017 using texi2html 5.0.