多項式の掛け算の結果がおかしくなる

Question

多項式どうしを掛け算した結果を表示するプログラムを作っているのですが、思い通りに出来ません。
例えば、p1 = 3x^2 + 2x + 1、p3 = 3x^2 + 7x + 5、p4 = p1*p3とすると、結果が p4 = 3x^4 + 5x^3 + 18x^2 + 11x +5となります。この結果をよく見てみると、getMultipledメソッドにおける始めのループ処理では、p3の定数項の5とp1の各項との乗算が出来ていることが分かります。しかし、それ以降のループでは全てp3の項の係数を1として計算されているようです（２ループ目では7xの7を係数として計算がなされるはずです）。なぜこのような結果になってしまうのかがよく分かりません。もし分かれば教えてください。よろしくお願いします。ソースコードは以下の通りです。

public class Polynomial {
  int[] co; // 係数(coefficient)の配列
  Polynomial() {
    co = new int[1];
    co[0] = 0;
  }
  Polynomial(int[] co) {
    this.co = co;
  }
  Polynomial(int k2, int k1, int k0) {
    co = new int[3];
    co[0] = k0; // 定数項 (0次の係数)
    co[1] = k1; // 1次の係数
    co[2] = k2; // 2次の係数
  }

  Polynomial getShifted(Polynomial poly, int num) {
    if (num < 1)
      return poly;
    int dim = co.length + num;
    int[] shiftedCo = new int[dim];
    for (int i = 0; i < poly.co.length; i++) {
      shiftedCo[i + num] = co[i];
    }
    for (int i = 0; i < num; i++) {
      shiftedCo[i] = 0;
    }
    return new Polynomial(shiftedCo);
  }

  Polynomial getMultiplied(Polynomial poly , int k){
    int[] mul = new int[poly.co.length];
    for(int i = 0; i < poly.co.length; i++){
      mul[i] = 0;
    }
    for(int i = 0; i < poly.co.length; i++){
      mul[i] = k*poly.co[i];
    }
    return new Polynomial(mul);
  }

  public String toString() {
    StringBuffer sb = new StringBuffer();
    for (int i = co.length - 1; i >= 2; i--) {
      sb.append(co[i]);
      sb.append("x^");
      sb.append(i);
      sb.append(" + ");
    }
    sb.append(co[1] + "x" + " + " + co[0]);
    return new String(sb); // sb.toString() でも OK
  }

  Polynomial getAdded(Polynomial poly) {
    int dim = (this.co.length > poly.co.length) ? this.co.length : poly.co.length;
    int[] addedCo = new int[dim];
    for (int i = 0; i < dim; i++) {
      addedCo[i] = 0;
    }
    for (int i = 0; i < this.co.length; i++) {
      addedCo[i] += this.co[i];
    }
    for (int i = 0; i < poly.co.length; i++) {
      addedCo[i] += poly.co[i];
    }
    return new Polynomial(addedCo);
  }

  static Polynomial plus(Polynomial left, Polynomial right) {
    int dim = (left.co.length > right.co.length) ? left.co.length : right.co.length;
    int[] retPolyCo = new int[dim];
    for (int i = 0; i < dim; i++) {
      retPolyCo[i] = 0;
    }
    for (int i = 0; i < left.co.length; i++) {
      retPolyCo[i] += left.co[i];
    }
    for (int i = 0; i < right.co.length; i++) {
      retPolyCo[i] += right.co[i];
    }
    return new Polynomial(retPolyCo);
  }

  Polynomial getMultiplied(Polynomial poly){
    int dim = (this.co.length - 1)+(poly.co.length -1);
    int[] dimCo = new int[dim];
    Polynomial mul = new Polynomial(dimCo);
    Polynomial addedCo = new Polynomial(dimCo);
    for(int i = 0; i < poly.co.length; i++){
      mul = getMultiplied(this , poly.co[i]);
      mul = getShifted(mul , i);
      addedCo = plus(mul, addedCo);
    }  
    return addedCo;
  }


  public static void main(String[] args){
    Polynomial p1 = new Polynomial(3, 2, 1);
    int[] co = {4, 5};
    Polynomial p2 = new Polynomial(co);
    System.out.println("p1 = " + p1);
    System.out.println("p2 = " + p2);
    System.out.println("p1 + p2 = " + Polynomial.plus(p1, p2));
    Polynomial p3 = p1.getAdded(p2);
    System.out.println("p1 = " + p1);
    System.out.println("p3 = " + p3);
    Polynomial p4 = p1.getMultiplied(p3);
    System.out.println("p4 = " + p4);
    System.out.println("p1 = " + p1);
    System.out.println("p3 = " + p3);
      System.out.println(p3.co[1]);
  }
}

Answer 1

全体的に気になったので書き直してみました。
BigIntegerなどのように不変オブジェクトとし、計算結果はコピーを返す形です。
こうなると、計算のメソッド名もgetAddedなどではなく、「足し算」を明確にするためaddなどにしたいのが本音です。
Javaではint配列を生成した際、すべての要素が0で初期化されるため、手動で0初期化する必要はありません。

public class Polynomial {
  private final int[] co; // 係数(coefficient)の配列
  Polynomial() {
    co = new int[]{0};
  }

  // 次数の高い順に並んでいることを想定し、逆順に並べて入れる
  Polynomial(int... co) {
    int n = co.length;
    this.co = new int[n];
    for (int i = 0; i < n; i++) {
      this.co[i] = co[n - i - 1];
    }
  }

  // 自分自身をシフトし、コピーを返す
  Polynomial getShifted(int num) {
    if (num < 1)
      return this;
    int dim = co.length + num;
    int[] shiftedCo = new int[dim];
    for (int i = 0; i < poly.co.length; i++) {
      shiftedCo[i + num] = co[i];
    }
    return new Polynomial(shiftedCo);
  }

  // 多項式の整数倍　自分自身をk倍してコピーを返却
  Polynomial getMultiplied(int k){
    if (k == 0) return new Polynomial();
    int[] mul = new int[co.length];
    for(int i = 0; i < co.length; i++){
      mul[i] = k*co[i];
    }
    return new Polynomial(mul);
  }

  // 本当はここも自然な多項式の出力になるよういじりたかったが、面倒そうだったので放置
  public String toString() {
    StringBuffer sb = new StringBuffer();
    for (int i = co.length - 1; i >= 2; i--) {
      sb.append(co[i]);
      sb.append("x^");
      sb.append(i);
      sb.append(" + ");
    }
    sb.append(co[1] + "x" + " + " + co[0]);
    return new String(sb); // sb.toString() でも OK
  }

  Polynomial getAdded(Polynomial poly) {
    int dim = Math.max(this.co.length, poly.co.length);
    int[] addedCo = new int[dim];
    for (int i = 0; i < this.co.length; i++) {
      addedCo[i] += this.co[i];
    }
    for (int i = 0; i < poly.co.length; i++) {
      addedCo[i] += poly.co[i];
    }
    return new Polynomial(addedCo);
  }

  // plusメソッドはaddedメソッドでカバー可能のため削除

  // shiftなんぞ使わずとも、2重ループで十分解決可能
  Polynomial getMultiplied(Polynomial poly){
    int dim = (this.co.length - 1)+(poly.co.length -1);
    int[] dimCo = new int[dim];
    for(int i = 0; i < this.co.length; i++){
      for (int j = 0; j < poly.co.length; j++) {
        dimCo[i + j] += this.co[i] * poly.co[j];
      }
    }  
    return new Polynomial(dimCo);
  }
}

Comments

[Ryuuse]

回答ありがとうございます。getShiftedを使わない発想は自分にはありませんでした。他にも色々な書き方がある事を学べました。

[swordone]

書き方というより、ごく自然に分配法則を使っていっただけですけどね。

Answer 2

getShiftedの実装ミスです。

  Polynomial getShifted(Polynomial poly, int num) {
    if (num < 1)
      return poly;
-   int dim = co.length + num;
+   int dim = poly.co.length + num;
    int[] shiftedCo = new int[dim];
    for (int i = 0; i < poly.co.length; i++) {
-     shiftedCo[i + num] = co[i];
+     shiftedCo[i + num] = poly.co[i];
    }
    for (int i = 0; i < num; i++) {
      shiftedCo[i] = 0;
    }
    return new Polynomial(shiftedCo);
  }

今回のケースでは、coはp1.coを、poly.coはp3.coを指しますから、混在していたわけです。
staticメソッドにしておけばこのようなミスは防げます。

追記：
コメントでswordoneさんがご指摘のとおり、
引数polyを受け取らない非staticメソッドの方がJava的には自然かもしれません。

アドバイス

簡単にでもコメントを書きましょう。
第三者（あるいは未来のあなた）にとって読み易くなるだけでなく、思考の整理になります。

例えば次のように。（若干さぼっている部分もあります）

/**
 * 各項の次数を一律に増やし、新しいオブジェクトを作って返す。
 * Polynomial.getShifted(2x^2 + 3x, 2) => 2x^4 + 3x^2
 *
 * @param num シフト幅。正の数もしくは0。
 */
private static Polynomial getShifted(Polynomial poly, int num) {
    if (num < 1) {
        // シフトの必要が無いとき
        return poly;
    }

    // 新しい多項式オブジェクト
    int dim = poly.co.length + num;
    int[] shiftedCo = new int[dim];

    // num分だけずらして係数を代入する
    for (int i = 0; i < poly.co.length; i++) {
       shiftedCo[i + num] = poly.co[i];
    }
    // 余った領域は0で埋める
    for (int i = 0; i < num; i++) {
       shiftedCo[i] = 0;    // なおJavaの場合この処理は不要です。最初から要素の初期値が0なので。
    }

    return new Polynomial(shiftedCo);
}

Comments

[swordone]

staticではなく、インスタンスメソッドとして、引数がシフト数だけのメソッドにしたほうが自然な気はします。

[LouiS0616]

インスタンスに一切の変更が生じない場合はstaticメソッドの方が分かり易いと個人的には思うんですが（引数をいじることは可能だけれども）、BigIntegerあたりのAPIを見る限りswordoneさんの感覚の方がJavaの雰囲気に合っている気がしますね。
回答に追記しました。コメントありがとうございます。

[Ryuuse]

回答ありがとうございます。staticの使い方が良く分からなかったので、今回の質問である程度理解できました。またコメントも所々付けておけば、もっと早くミスに気付いていたと思いました。