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

非負整数

• 一変数多項式の乗算を, 次数に応じて決まるアルゴリズムを用いて 高速に行う.
• umul(), usquare(), utmul() は 係数を整数と見なして, 整数係数の多項式として積を求める. 係数が有限体 GF(p) の元の場合には, 係数は 0 以上 p 未満の整数と見なされる.
• umul_ff(), usquare_ff(), utmul_ff() は, 係数を有限体の元と見なして, 有限体上の多項式として 積を求める. ただし, 引数の係数が整数の場合, 整数係数の多項式を返す場合もあるので, これらを呼び出した結果 が有限体係数であることを保証するためには あらかじめ simp_ff() で係数を有限体の元に変換しておくとよい.
• umul_ff(), usquare_ff(), utmul_ff() は, GF(2^n) 係数の多項式を引数に取れない.
• umul(), umul_ff() の結果は p1, p2 の積, usquare(), usquare_ff() の結果は p1 の 2 乗, utmul(), utmul_ff() の結果は p1, p2 の積 の, d 次以下の部分となる.
• いずれも, set_upkara() (utmul, utmul_ff については set_uptkara()) で返される値以下の次数に対しては通常の筆算 形式の方法, set_upfft() で返される値以下の次数に対しては Karatsuba 法, それ以上では FFTおよび中国剰余定理が用いられる. すなわち, 整数に対する FFT ではなく, 十分多くの 1 ワード以内の法 mi を用意し, p1, p2 の係数を mi で割った余りとしたものの積を, FFT で計算し, 最後に中国剰余定理で合成する. その際, 有限体版の関数に おいては, 最後に基礎体を表す法で各係数の剰余を計算するが, ここでは Shoup によるトリック [Shoup] を用いて高速化してある.

[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

非負整数

• 一変数多項式の乗算を Karatsuba 法で行う.
• 基本的には umul と同様だが, 次数が大きくなっても FFT を用いた高速化は行わない.
• GF(2^n) 係数の多項式にも用いることができる.

[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

非負整数

• いずれも, 一変数多項式の積の計算における, アルゴリズム切替えの閾値を 設定する.
• 一変数多項式の積は, 次数 N が小さい範囲では通常の N^2 アルゴリズム, 中程度 の場合 Karatsuba アルゴリズム, 大きい場合には FFT アルゴリズムで計算 される. この切替えの次数を設定する.
• 詳細は, それぞれの積関数の項を参照のこと.

参照

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

非負整数

• p の変数を x とする. このとき p = p1+x^(d+1)p2 (p1 の次数は d 以下) と分解できる. utrunc() は p1 を返し, udecomp() は [p1,p2] を返す.
• p の次数を e とし, i 次の係数を p[i] とすれば, ureverse() は p[e]+p[e-1]x+... を返す.

[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

非負整数

• uinv_as_power_series(p,d) は, 定数項が 0 でない 多項式 p に対し, pr-1 の最低次数が d+1 以上になるような 高々 d 次の多項式 r を求める.
• ureverse_inv_as_power_series(p,d) は p の次数を e とするとき, p1=ureverse(p,e) に対して uinv_as_power_series(p1,d) を計算する.
• rembymul_precomp() の引数として用いる場合, ureverse_inv_as_power_series() の結果をそのまま用いることができる.

[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

一変数多項式

• 一変数多項式 p1, p2 に対し, udiv は商, urem, urembymul は剰余, ugcd は GCD を返す. これらは, 密な一変数多項式に対する高速化を図ったものである. urembymul は, p2 による剰余計算を, p2 の 冪級数としての逆元計算および, 乗算 2 回に置き換えたもので, 次数が大きい場合に有効である.
• urembymul_precomp は, 固定された多項式による剰余 計算を多数行う場合などに効果を発揮する. 第 3 引数は, あらかじめ 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)

参照

uinv_as_power_series, ureverse_inv_as_power_series.

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