[ << ] [ < ] [] [ > ] [ >> ]         [冒頭] [目次] [見出し] [ ? ]

6.4 一変数多項式の演算


[ << ] [ < ] [] [ > ] [ >> ]         [冒頭] [目次] [見出し] [ ? ]

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

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

:: 一変数多項式の高速乗算

usquare(p1)
usquare_ff(p1)

:: 一変数多項式の高速 2 乗算

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

:: 一変数多項式の高速乗算 (打ち切り次数指定)

return

一変数多項式

p1 p2

一変数多項式

d

非負整数

[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
参照

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


[ << ] [ < ] [] [ > ] [ >> ]         [冒頭] [目次] [見出し] [ ? ]

6.4.2 kmul, ksquare, ktmul

kmul(p1,p2)

:: 一変数多項式の高速乗算

ksquare(p1)

:: 一変数多項式の高速 2 乗算

ktmul(p1,p2,d)

:: 一変数多項式の高速乗算 (打ち切り次数指定)

return

一変数多項式

p1 p2

一変数多項式

d

非負整数

[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)$

[ << ] [ < ] [] [ > ] [ >> ]         [冒頭] [目次] [見出し] [ ? ]

6.4.3 set_upkara, set_uptkara, set_upfft

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

:: 1 変数多項式の積演算における N^2 , Karatsuba, FFT アルゴリズムの切替えの閾値

return

設定されている値

threshold

非負整数

参照

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


[ << ] [ < ] [] [ > ] [ >> ]         [冒頭] [目次] [見出し] [ ? ]

6.4.4 utrunc, udecomp, ureverse

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

:: 多項式に対する操作

return

一変数多項式あるいは一変数多項式のリスト

p

一変数多項式

d

非負整数

[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
参照

udiv, urem, urembymul, urembymul_precomp, ugcd.


[ << ] [ < ] [] [ > ] [ >> ]         [冒頭] [目次] [見出し] [ ? ]

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)

:: 多項式を冪級数とみて, 逆元計算

return

一変数多項式

p

一変数多項式

d

非負整数

[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
参照

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


[ << ] [ < ] [] [ > ] [ >> ]         [冒頭] [目次] [見出し] [ ? ]

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)

:: 一変数多項式の除算, GCD

return

一変数多項式

p1 p2 inv

一変数多項式

[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)
参照

uinv_as_power_series, ureverse_inv_as_power_series.


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

この文書は3月 29, 2024texi2html 5.0を用いて生成されました。