2012-01-03
■[C++][algorithm]cpp_multi_precision::sparse_polyにモニック除算を追加しました
abstract
以下の関数が追加されました。
cpp_multi_precision::sparse_poly::monic_div cpp_multi_precision::sparse_poly::monic_mod
除数がモニック（最大次数の係数が1）の時にオーダーO(M(n))の除算アルゴリズムが実行されます。
M(n)は乗算のオーダーで、現在の所karatsuba法が採用されている為となっています。
モニック以外のケースではオーダーの通常の除法が行われます。
implementation
ある多項式に対し、係数の反転
を定義します。
次に、（但しm = lhsの最大次数a - rhsの最大次数b）を法、rev(rhs)を入力としてNewton法によって
となる
を得ます。
を法として
を計算し、商
と剰余
を得て計算を終了します。
Permalink | コメント(0) | トラックバック(0) | 01:06 
