組立除法

代数学において、組立除法（くみたてじょほう、）は、を手計算で行う方法の一つであり、よりも記述量と計算量を少なくできる。

主に一次のモニック多項式で割る場合、すなわちとして教えられることが多いが、この方法は任意の多項式による除法へ一般化できる。

組立除法の利点は、変数を書かずに計算できること、計算回数が少ないこと、筆算除法よりも紙面を大幅に節約できることである。また、筆算除法に現れる減法は、最初に符号を変えることで加法に変換されるため、符号の誤りを防ぎやすい。

通常の組立除法最初の例は、一次のモニックな分母による組立除法である。

分子はと書ける。

分母の零点はである。

の係数を次のように並べ、左側にの零点を書く。

線の右側にあるを最下段に「下ろす」。

に、線の左にあるを掛け、その結果をに置く。

次の列でを行う。

前の二つの手順を繰り返すと、次が得られる。

ここで、最後の項 −123 が余りであり、それ以外は商の係数に対応する。

余りと商の両方について、右から左へ次数が大きくなるように、定数項を次数 0 として項を書く。

したがって、商と余りは次のようになる。

よって次を得る。

剰余の定理による多項式の評価

上の形の組立除法は、剰余の定理を用いて一変数多項式を評価する文脈で有用である。要約すると、におけるの値は、をで割ったときの余りに等しい。

この方法で値を計算する利点は、素朴な代入計算よりも乗法の回数が半分強で済むことである。別の評価方法としてホーナー法がある。

拡張組立除法

この方法は、少し修正するだけで任意のモニック多項式による除法へ一般化できる。なお、次の例では表示されない場合があるが、除数も係数を省略せずに書く必要がある。例えばのようにする。前と同じ手順を用いて、次の除法を行う。

ここでは係数だけを考える。割られる多項式の係数を上段に書く。

除数の係数の符号を反転する。

先頭を除くすべての係数を、左側に右上がりの対角線上に書く（次の図を参照）。

ここで、1 が −1 に、−3 が 3 に符号変化していることに注意する。線の右側にある最初の係数を最下段に下ろす。

下ろした数に、線の左にある対角線上の数を掛け、得られた値を、下ろした数から見て右上がりの対角方向に置く。

次の列で加法を行う。

次の対角方向の記入が上段の項を越える直前まで、前の二つの手順を繰り返す。

残りの列を足し合わせる。

線の左側の項の数を数える。この場合は二つなので、余りは次数 1 であり、線の下にある右側の二つの項が余りである。区切りとしてバーティカルバーを入れる。

余りと結果の両方について、右から左へ次数が大きくなるように、定数項を次数 0 として項を書く。

この除法の結果は次のようになる。

モニックでない除数の場合

少し工夫すれば、拡張した手法はモニックだけでなく、任意の多項式に対してさらに一般化できる。通常の方法は、除数をその最高次係数（ここでは a とする）で割ることである。

その後、を除数として組立除法を行い、得られた商を a で割ると、元の除法の商が得られる（余りは同じままである）。しかし、この方法では途中で扱いにくい分数が現れ、後で消えることが多いため、誤りが起きやすい。の係数を先に正規化しなくても計算することは可能である。

このようなモニックでない除数に対して最初に筆算除法を行うと分かるように、の係数は「下ろした」後、掛け算の前にの最高次係数で割られる。

次の除法を例に説明する。

少し修正した表を用いる。

下に一行余分にあることに注意する。この行は、「下ろした」値をの最高次係数で割って得た値を書くために使われる（この場合は /3 で示されている。なお、の他の係数とは異なり、この数の符号は変えない）。

次に、通常どおりの最初の係数を下ろす。

そして、下ろした値を 3 で割り、その下の行に置く。

次に、この新しい割った後の値を用いて、拡張手法と同様に 2 と 1 の倍数を上の行に記入する。

次に 5 を下ろし、その下の 4 を加え、結果をもう一度割る。

そして 3 を用いて上の行を埋める。

この時点で、第三の和を得た後にそれを用いて上の行を埋めようとすると、右端を越えてしまう。したがって、第三の和は、通常の組立除法と同様に余りの最初の係数である。ただし、余りの値は除数の最高次係数で割らない。

これで答えの係数を読み取ることができる。拡張組立除法と同様に、最後の二つの値（2 は除数の次数である）が余りの係数であり、それ以外が商の係数である。

したがって結果は次のようになる。

コンパクトな拡張組立除法

しかし、上の対角線形式は、除数の次数が被除数の次数の半分を超える場合、空間効率が悪くなる。次の除法を考える。

各積は正しい列に入っていれば任意の行に書いてよいため、次の除法で示すように、貪欲法によって算法をコンパクト化できる。

以下に、この算法の実行方法を示す。この算法には、モニックでない除数による除法の手順も含まれる。

Pythonによる実装

次のコード片は、任意の一変数多項式に対する拡張組立除法をPythonで実装したものである。

def expanded_synthetic_division(dividend, divisor): """Fast polynomial division by using Expanded Synthetic Division. Also works with non-monic polynomials.

Dividend and divisor are both polynomials, which are here simply lists of coefficients. E.g.: x**2 + 3*x + 5 will be represented as [1, 3, 5] """ out = list(dividend) # Copy the dividend normalizer = divisor for i in range(len(dividend) - len(divisor) + 1): # For general polynomial division (when polynomials are non-monic), # we need to normalize by dividing the coefficient with the divisor's first coefficient out[i] /= normalizer

coef = out[i] if coef != 0: # Useless to multiply if coef is 0 # In synthetic division, we always skip the first coefficient of the divisor, # because it is only used to normalize the dividend coefficients for j in range(1, len(divisor)): out[i + j] += -divisor[j] * coef

# The resulting out contains both the quotient and the remainder, # the remainder being the size of the divisor (the remainder # has necessarily the same degree as the divisor since it is # what we couldn't divide from the dividend), so we compute the index # where this separation is, and return the quotient and remainder. separator = 1 - len(divisor) return out[:separator], out[separator:] # Return quotient, remainder.

Źródło i licencja