Skip to content

Instantly share code, notes, and snippets.

@cympfh
Created April 3, 2016 03:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save cympfh/cb59bd7412601166ee6d8e5eb23f4a02 to your computer and use it in GitHub Desktop.
Save cympfh/cb59bd7412601166ee6d8e5eb23f4a02 to your computer and use it in GitHub Desktop.
多倍長ライブラリ
/*
* 多倍長ライブラリ
*
* 整数の、加減積乗だけ
* メソッドチェーンして使う
*
new Integer(n) :: Int -> Integer , () -> Integer(0)
n.add(m) :: Integer.Integer -> Integer
n.mul(m) :: Integer.Integer -> Integer, Integer.Int -> Integer
n.pow(m) :: Integer.Int -> Integer
n.show() :: Integer -> "String"
*
> print = console.log;
> n = new Integer(2)
> print(n.pow(58).show())
288230376151711744
*
* 普通にやると丸められる
> Math.pow(2,58)
288230376151711740
*
* 掛け算とか筆算法なので特に速くもないことに注意
*/
function Integer(n) {
n = n || 0;
this.sign = n>0 ? 1 : n<0 ? -1 : 0;
this.number = [0];
if (n<0) n = -n;
this.th = 1e10;
for (var i=0; n>0; ++i) {
this.number[i] = n % this.th;
n = (n/this.th) | 0;
}
}
var intp = Integer.prototype;
intp.normalize = function () {
var n = this;
var num = n.number;
if (num.every(function(x){return x==0})) return new Integer(0);
for (var i=0; i<num.length; ++i) {
if (num[i] < 0) {
if (!((i+1) in num)) break;
var k = Math.ceil(-num[i]/n.th);
num[i+1] -= k;
num[i] += n.th * k;
}
if (num[i] > n.th) {
if (!((i+1) in num)) num[i+1] = 0;
num[i+1] += (num[i]/n.th) | 0;
num[i] %= n.th;
}
}
for (var i=num.length-1; i>=0; --i) {
if (num[i] == 0) {
num.length--;
continue;
}
if (num[i] < 0) {
num[i] *= -1;
n.sign = -1;
break;
} else {
n.sign = 1;
break;
}
}
return n;
};
intp.add = function(m) {
var n = this;
var r = new Integer(0);
var num1 = n.number, num2 = m.number;
for (var i=0, l=Math.max(num1.length, num2.length); i<l; ++i) {
r.number[i] =
(i in num1 ? num1[i] * n.sign : 0)
+ (i in num2 ? num2[i] * m.sign : 0)
}
return r.normalize();
};
intp.copy = function() {
var r = new Integer();
r.sign = this.sign;
r.number = [];
for (var i=0; i<this.number.length; ++i) r.number[i] = this.number[i];
return r;
};
intp.neg = function() {
var r = this.copy();
r.sign *= -1;
return r;
};
intp.sub = function(m) {
return this.add(m.neg());
};
intp.mul = function(m) {
var n = this;
if (!(m instanceof Integer)) m = new Integer(m);
var r = new Integer();
r.sign = n.sign * m.sign;
for (var i=0; i<n.number.length; ++i) {
for (var j=0; j<m.number.length; ++j) {
var k = i+j;
if (!(k in r.number)) r.number[k] = 0;
r.number[k] += n.number[i] * m.number[j];
}
}
return r.normalize();
};
intp.pow = function(r) {
function pows(n, r) {
if (r == 0) return new Integer(1);
else if (r == 1) return n;
else if (r == 2) return n.mul(n);
var s = (r/2) | 0;
var x = pows(n,s);
var y = pows(n, r-s-s)
return x.mul(x.mul(y))
}
return pows(this,r);
};
intp.show = function() {
if (this.sign == 0) return "0";
var s = this.sign<0 ? "-" : "";
for (var i=this.number.length-1; i>=0; --i) s += this.number[i];
return s;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment