係数を分数にしよう。
fractionも今までと同じ手法で高速化を行った。
16.7sが、100回で34.3sと、約50倍速くなった。
もうちょっと速くなると思ってたんだが。
ソースは隠しておく。
poly = Array;poly.prototype.copy = poly_copy;
poly.prototype.add = poly_add;
poly.prototype.add_assign = poly_add_assign;
poly.prototype.subtract = poly_subtract;
poly.prototype.subtract_assign = poly_subtract_assign;
poly.prototype.multiply = poly_multiply;
poly.prototype.value = poly_value;
poly.prototype.synthesize = poly_synthesize;
poly.prototype.integral = poly_integral;
poly.prototype.normalize = poly_normalize;
poly.prototype.toString = poly_toString;fraction.prototype.copy = fraction_copy;
fraction.prototype.add = fraction_add;
fraction.prototype.add_assign = fraction_add_assign;
fraction.prototype.subtract = fraction_subtract;
fraction.prototype.subtract_assign = fraction_subtract_assign;
fraction.prototype.multiply = fraction_multiply;
fraction.prototype.multiply_assign = fraction_multiply_assign;
fraction.prototype.divide = fraction_divide;
fraction.prototype.divide_assign = fraction_divide_assign;
fraction.prototype.normalize = fraction_normalize;
fraction.prototype.toString = fraction_toString;var t = (new Date()).getTime();
for(var i = 0; i < 100; i++)
test1();
var dt = (new Date()).getTime() - t;
WScript.Echo(dt + "ms");function test1() {
var f0 = [ new fraction(), new fraction(1) ];
var f1 = [ new fraction(-1), new fraction(1) ];
var n = 10;
var p = [ ];
p[1] = [ ];
p[1][0] = [ new fraction(1) ];
for(var i = 2; i <= n; i++) {
p[i] = [ ];
for(var j = 0; j < i; j++) {
if(j == 0)
p[i][j] = p[i-1][0].integral(0, f0);
else if(j == i - 1)
p[i][j] = p[i-1][i-2].integral(f1, j);
else
{
p[i][j] = p[i-1][j-1].integral(f1, j).add(
p[i-1][j].integral(j, f0));
}
}
}
}function gauss(x) {
if(x < 0 || n <= x)
return 0;
var j = Math.floor(x);
return p[n][j].value(x);
}// コピー
function poly_copy() {
var r = [ ];
var a = this;
for(var i = this.length - 1; i >= 0; i--)
r[i] = a[i].copy();
return r;
}// 加算
function poly_add(p) {
var r = [ ];
var length = this.length;
if(typeof p == "number" || p instanceof fraction) {
if(length > 0)
r[0] = this[0].add(p);
else
r[0] = new fraction(p);
for(var i = 1; i < length; i++)
r[i] = this[i].copy();
}
else if(p instanceof poly) {
var p_length = p.length;
if(length > p_length) {
var i;
for(i = 0; i < p_length; i++)
r[i] = this[i].add(p[i]);
for( ; i < length; i++)
r[i] = this[i].copy();
}
else if(length < p_length) {
var i;
for(i = 0; i < length; i++)
r[i] = this[i].add(p[i]);
for( ; i < p_length; i++)
r[i] = p[i].copy();
}
else {
for(var i = 0; i < p_length; i++)
r[i] = this[i].add(p[i]);
if(r[length-1].a == 0)
r.normalize();
}
}
else
throw("unsupported argument in poly::add");
return r;
}// 減算
function poly_subtract(p) {
var r = [ ];
var length = this.length;
if(typeof p == "number") {
if(length > 0)
r[0] = this[0].subtract(p);
else
r[0] = new fraction(-p);
for(var i = 1; i < length; i++)
r[i] = this[i].copy();
}
else if(p instanceof poly) {
var p_length = p.length;
if(length > p_length) {
var i;
for(i = 0; i < p_length; i++)
r[i] = this[i].subtract(p[i]);
for( ; i < length; i++)
r[i] = this[i].copy();
}
else if(length < p_length) {
var i;
for(i = 0; i < length; i++)
r[i] = this[i].subtract(p[i]);
for( ; i < p_length; i++) {
var tmp = p[i].copy();
tmp.a = -tmp.a;
r[i] = tmp;
}
}
else {
for(var i = 0; i < p_length; i++)
r[i] = this[i].subtract(p[i]);
if(r[length-1] == 0)
r.normalize();
}
}
else
throw("unsupported argument in poly::subtract");
r.normalize();
return r;
}// 加算代入
function poly_add_assign(p) {
var length = this.length;
if(typeof p == "number") {
if(length > 0)
this[0].add_assign(p);
else
this[0] = new fraction(p);
}
else if(p instanceof fraction) {
if(length > 0)
this[0].add_assign(p);
else
this[0] = p.copy();
}
else if(p instanceof poly) {
var p_length = p.length;
if(length > p_length) {
var i;
for(i = 0; i < p_length; i++)
this[i].add_assign(p[i]);
}
else if(length < p_length) {
var i;
for(i = 0; i < length; i++)
this[i].add_assign(p[i]);
for( ; i < p_length; i++)
this[i] = p[i].copy();
}
else {
for(var i = 0; i < p_length; i++)
this[i].add_assign(p[i]);
if(this[length-1].a == 0)
this.normalize();
}
}
else
throw("unsupported argument in poly::add");
return this;
}// 減算算代入
function poly_subtract_assign(p) {
var length = this.length;
if(typeof p == "number") {
if(length > 0)
this[0].subtract_assign(p);
else
this[0] = new fraction(-p);
}
else if(p instanceof fraction) {
if(length > 0)
this[0].subtract_assign(p);
else {
p.a = -p.a;
this[0] = p.copy();
}
}
else if(p instanceof poly) {
var p_length = p.length;
if(length > p_length) {
var i;
for(i = 0; i < p_length; i++)
this[i].subtract_assign(p[i]);
}
else if(length < p_length) {
var i;
for(i = 0; i < length; i++)
this[i].subtract_assign(p[i]);
for( ; i < p_length; i++) {
p[i].a = -p[i].a;
this[i] = p[i].copy();
}
}
else {
for(var i = 0; i < p_length; i++)
this[i].subtract_assign(p[i]);
if(this[length-1].a == 0)
this.normalize();
}
}
else
throw("unsupported argument in poly::add");
return this;
}// 乗算
function poly_multiply(p) {
var r = [ ];
if(typeof p == "number") {
for(var i = this.length - 1; i >= 0; i--)
r[i].a *= p;
}
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;
if(b_length == 0 || c_length == 0) {
return r;
}
var i;
for(i = 0; i < b_length - 1; i++) {
var a = new fraction();
for(var j = 0; j <= i; j++)
a.add_assign(b[j].multiply(c[i-j]));
r[i] = a;
}
for( ; i < c_length; i++) {
var a = new fraction();
for(var j = 0; j < b_length; j++)
a.add_assign(b[j].multiply(c[i-j]));
r[i] = a;
}
for( ; i < b_length + c_length - 1; i++) {
var a = new fraction();
for(var j = i - c_length + 1; j < b_length; j++)
a.add_assign(b[j].multiply(c[i-j]));
r[i] = a;
}
}
else
throw("unsupported argument in poly::multiply");
return r;
}// 関数の値
function poly_value(x) {
if(typeof x == "number" || x instanceof fraction) {
var r = new fraction();
for(var i = this.length - 1; i >= 0; i--) {
r.multiply_assign(x);
r.add_assign(this[i]);
}
}
else
throw("unsupported argument in poly::value");
return r;
}// 合成
function poly_synthesize(p) {
if(!(p instanceof poly))
throw("unsupported argument in poly::synthesize");
var length = this.length;
var r = [ this[length-1] ];
for(var i = length - 2; i >= 0; i--) {
r = r.multiply(p);
r.add_assign(this[i]);
}
return r;
}// 積分
function poly_integral(a1, a2) {
// まず不定積分する
var r = [ new fraction() ];
for(var i = this.length - 1; i >= 0; i--)
r[i+1] = this[i].divide(i + 1);
if(a1 == undefined) { // 不定積分
return r;
}
else if(a2 != undefined) { // 定積分
var r11, r12;
if(a1 instanceof poly) // 多項式なら合成
r11 = r.synthesize(a1);
else
r11 = r.value(a1);
if(a2 instanceof poly) // 多項式なら合成
r12 = r.synthesize(a2);
else
r12 = r.value(a2);
// 種類によって引き算を場合分け
if(r12 instanceof poly) {
return r12.subtract_assign(r11);
}
else {
if(r11 instanceof poly)
return [r12].subtract_assign(r11);
else
return r12.subtract_assign(r11);
}
}
else
throw("wrong number of arguments in poly::integral");
}function poly_normalize() {
// 真の配列の長さを求める
var len = this.length;
for( ; len > 0; len--) {
if(this[len-1] != 0)
break;
}
this.length = len;
}function poly_toString() {
if(this.length == 0) {
return "0";
}
if(this.length == 1) {
return "" + this[0];
}
var str = "";
var first = true;
for(var i = 0; i < this.length; i++) {
var c = this[i];
if(c.a == 0)
continue;
else if(c.a > 0) {
if(!first)
str += "+";
if(!(c.a == 1 && c.b == 1) || i == 0)
str += c;
}
else {
if(c == -1 && i > 0)
str += "-";
else
str += c;
}
if(i == 1)
str += "x";
else if(i > 1)
str += "x^" + i;
first = false;
}
return str;
}function fraction(a, b) {
if(a == undefined) {
this.a = 0;
this.b = 1;
}
else if(b == undefined) {
this.a = a;
this.b = 1;
}
else {
this.a = a; // 分子
this.b = b; // 分母
this.normalize();
}
}function fraction_copy() {
return new fraction(this.a, this.b);
}function fraction_add(f) {
if(typeof f == "number") {
var b = this.b;
return new fraction(this.a + b * f, b);
}
else if(f instanceof fraction) {
var b = this.b;
var f_b = f.b;
return new fraction(this.a * f_b + b * f.a, b * f_b);
}
else
throw("wrong argument in fraction::add");
}function fraction_add_assign(f) {
if(typeof f == "number") {
this.a += f * this.b;
return this;
}
else if(f instanceof fraction) {
var f_b = f.b;
this.a = this.a * f_b + this.b * f.a;
this.b *= f_b;
this.normalize();
return this;
}
else
throw("wrong argument in fraction::add");
}function fraction_subtract(f) {
if(typeof f == "number") {
var b = this.b;
return new fraction(this.a - b * f, b);
}
else if(f instanceof fraction) {
var b = this.b;
var f_b = f.b;
return new fraction(this.a * f_b - b * f.a, b * f_b);
}
else
throw("wrong argument in fraction::add");
}function fraction_subtract_assign(f) {
if(typeof f == "number") {
this.a -= f * this.b;
return this;
}
else if(f instanceof fraction) {
var f_b = f.b;
this.a = this.a * f_b - this.b * f.a;
this.b *= f_b;
this.normalize();
return this;
}
else
throw("wrong argument in fraction::add");
}function fraction_multiply(f) {
if(typeof f == "number")
return new fraction(this.a * f, this.b);
else if(f instanceof fraction) {
return new fraction(this.a * f.a, this.b * f.b);
}
else
throw("wrong argument in fraction::add");
}function fraction_multiply_assign(f) {
if(typeof f == "number") {
this.a *= f;
this.normalize();
return this;
}
else if(f instanceof fraction) {
this.a *= f.a;
this.b *= f.b;
this.normalize();
return this;
}
else
throw("wrong argument in fraction::add");
}function fraction_divide(f) {
if(typeof f == "number")
return new fraction(this.a, this.b * f);
else if(f instanceof fraction)
return new fraction(this.a * f.b, this.b * f.a);
else
throw("wrong argument in fraction::add");
}function fraction_divide_assign(f) {
if(typeof f == "number") {
this.b *= f;
this.normalize();
return this;
}
else if(f instanceof fraction) {
this.a *= f.b;
this.b *= f.a;
this.normalize();
return this;
}
else
throw("wrong argument in fraction::add");
}function fraction_normalize() {
// ユークリッドの互除法
var a = this.a;
var b = this.b;
var a2, f;
while(true) {
if((a2 = a % b) == 0) {
f = b;
break;
}
if((b %= a) == 0) {
f = a;
break;
}
a = a2;
}
this.a /= f;
this.b /= f;
if(this.b < 0) {
this.a = -this.a;
this.b = -this.b;
}
}function fraction_toString() {
if(this.b == 1)
return this.a;
else
return this.a + "/" + this.b;
}
