multiply
1に1+xを9回掛けるを1万回繰り返す。
// 13091ms
this.multiply = function(p) {
var r = new poly();
if(typeof p == "number") {
for(var i = 0; i < this.a.length; i++)
r.a[i] *= p;
}
else if(p instanceof poly) {
for(var i = 0; i < this.a.length; i++) {
for(var j = 0; j < p.a.length; j++) {
if(r.a[i+j] == undefined)
r.a[i+j] = this.a[i] * p.a[j];
else
r.a[i+j] += this.a[i] * p.a[j];
}
}
}
else
throw("unsupported argument in poly::multiply");
r.normalize();
return r;
}
を、Arrayを使って、
なるべくプロパティの参照をしないようにすると、
// 3672ms
function poly_multiply(p) {
var r = new poly();
var length = this.length;
if(typeof p == "number") {
for(var i = 0; i < length; i++)
r[i] *= p;
}
else if(p instanceof poly) {
var p_length = p.length;
for(var i = 0; i < length; i++) {
for(var j = 0; j < p_length; j++) {
if(r[i+j] == undefined)
r[i+j] = this[i] * p[j];
else
r[i+j] += this[i] * p[j];
}
}
}
else
throw("unsupported argument in poly::multiply");
return r;
}
次のようにするとさらにプロパティの参照が減らせる。
// 3588ms
else if(p instanceof poly) {
var length = this.length;
var p_length = p.length;
for(var i = 0; i < length; i++) {
var a = this[i];
for(var j = 0; j < p_length; j++) {
if(r[i+j] == undefined)
r[i+j] = a * p[j];
else
r[i+j] += a * p[j];
}
}
}
(m-1)次の多項式に(n-1)次を掛けると、
プロパティの参照は、4mn回から(3mn+m)回に減らせる。
ここで、n=3だが、n<mであることが多いから、
掛け算を逆にしたほうが回数を減らせる。
そこで、配列の大きさで乗数・被乗数を入れ替えることにする。
// 3256ms
else if(p instanceof poly) {
var length = this.length;
var p_length = p.length;
var b, c, b_length, c_length;
if(length < p_length) {
b = this;
c = p;
}
else {
b = p;
c = this;
}
b_length = b.length;
c_length = c.length;
for(var i = 0; i < b_length; i++) {
var a = b[i];
for(var j = 0; j < c_length; j++) {
if(r[i+j] == undefined)
r[i+j] = a * c[j];
else
r[i+j] += a * c[j];
}
}
}
さらに減らす方法がある。
