/**
* Copyright uwi ( http://wonderfl.net/user/uwi )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/6tU2
*/
package {
import flash.display.Sprite;
import flash.text.TextField;
// とちゅう
public class Test extends Sprite {
private var _tf : TextField;
public function Test() {
_tf = new TextField();
_tf.width = 465;
_tf.height = 465;
addChild(_tf);
// tr(NX.sqrt([12345678]));
var ret : Array = calc(10, [0,0,0,0,1]);
tr(ret);
}
public function calc(n : uint, base : Array) : Array
{
var a : Array = base.concat();
var b : Array = NX.sqrt(NX.div(NX.mul(base, base), [2])[0]);
tr(b);
var tp : Array = [1];
var den : Array = base.concat();
for(var k : uint = 1;k <= n;k++){
var na : Array = NX.div(NX.add(a.concat(),b), [2])[0];
var nb : Array = NX.sqrt(NX.mul(a,b));
var c : Array;
if(NX.comp(a, b) < 0){
c = NX.sub(b.concat(), a);
}else{
c = NX.sub(a.concat(), b);
}
var bb : int = NX.comp(NX.mul(c,c), base);
if(bb >= 0){
var sq : Array = NX.div(NX.mul(c, c), base)[0];
den = NX.sub(den, NX.mul(sq, tp));
}
a = na; b = nb;
if(bb < 0){
break;
}
tp = NX.mul(tp, [2]);
}
var pi : Array = NX.div(NX.mul(NX.mul(NX.mul(a, a), [4]), base), den)[0];
return pi;
}
private function tr(...o : Array) : void
{
_tf.appendText(o + "\n");
}
}
}
class NX{
public static const N : Number = 1E7;
public static function add(a : Array, b : Array) : Array
{
var i : uint;
var minl : uint = Math.min(a.length, b.length);
for(i = 0;i < minl;i++){
a[i] += b[i];
}
for(i = a.length;i < b.length;i++){
a.push(b[i]);
}
carry(a);
return a;
}
public static function sub(a : Array, b : Array) : Array
{
var i : uint;
for(i = 0;i < b.length;i++){
a[i] -= b[i];
}
minuscarry(a);
shave(a);
return a;
}
public static function minuscarry(a : Array) : Array
{
for(var i : uint = 0;i < a.length;i++){
if(a[i] < 0){
var c : uint = (-a[i] + N - 1) / N;
a[i] += N * c;
a[i+1] -= c;
}
}
return a;
}
public static function mul(a : Array, b : Array) : Array
{
var ret : Array = new Array(a.length + b.length);
var i : uint, j : uint;
for(i = 0;i < ret.length;i++)ret[i] = 0;
for(i = 0;i < a.length;i++){
for(j = 0;j < b.length;j++){
ret[i + j] += a[i] * b[j];
}
}
carry(ret);
shave(ret);
return ret;
}
public static function mulint(a : Array, b : uint) : Array
{
for(var i : uint = 0;i < a.length;i++){
a[i] *= b;
}
carry(a);
return a;
}
public static function comp(a : Array, b : Array) : int
{
if(a.length != b.length)return a.length - b.length;
for(var i : int = a.length - 1;i >= 0;i--){
if(a[i] != b[i]){
return a[i] - b[i];
}
}
return 0;
}
public static function div(ao : Array, bo : Array) : Array
{
var p : Array = ao.concat();
if(ao.length - bo.length < 0){
return [0, p];
}
var b : Array = bo.concat();
p.push(0);
var d : Array = [];
for(var i : int = p.length - b.length - 1;i >= 0;i--){
var q0 : Number = Math.ceil((p[i + b.length] * N + p[i + b.length - 1]) / (b[b.length - 1] + (b[b.length - 2] || 0) / N));
var r : Array = b.concat();
r = mulint(r, q0);
while(true){
var le : Boolean = false;
for(var k : int = r.length;k >= 0;k--){
var pp : Number = p[i+k] || 0;
var rr : Number = r[k] || 0;
if(pp != rr){
le = pp < rr;
break;
}
}
if(le){
q0--;
sub(r, b);
}else{
break;
}
}
d.push(q0);
for(var j : uint = 0;j < r.length;j++){
p[j + i] -= r[j];
}
minuscarry(p);
}
d.reverse();
carry(d);
shave(d);
shave(p);
return [d, p];
}
public static function mod(ao : Array, bo : Array) : Array
{
var p : Array = ao.concat();
if(ao.length - bo.length < 0){
return p;
}
var b : Array = bo.concat();
p.push(0);
var d : Array = [];
for(var i : int = p.length - b.length - 1;i >= 0;i--){
var q0 : Number = Math.ceil((p[i + b.length] * N + p[i + b.length - 1]) / (b[b.length - 1] + (b[b.length - 2] || 0) / N));
var r : Array = b.concat();
r = mulint(r, q0);
while(true){
var le : Boolean = false;
for(var k : int = r.length;k >= 0;k--){
var pp : Number = p[i+k] || 0;
var rr : Number = r[k] || 0;
if(pp != rr){
le = pp < rr;
break;
}
}
if(le){
q0--;
sub(r, b);
}else{
break;
}
}
for(var j : uint = 0;j < r.length;j++){
p[j + i] -= r[j];
}
minuscarry(p);
}
shave(p);
return p;
}
public static function sqrt(a : Array) : Array
{
var x : Array = [1];
for(var i : uint = 0;i < 100;i++){
x = NX.div(NX.add(NX.mul(x, x), a), NX.mul([2], x))[0];
}
return x;
}
public static function carry(a : Array) : Array
{
for(var i : uint = 0;i < a.length;i++){
if(a[i] >= N){
var c : uint = a[i] / N;
if(i == a.length - 1){
a.push(0);
}
a[i + 1] += c;
a[i] %= N;
}
}
return a;
}
private static function gcd(a : Array, b : Array) : Array
{
while(b.length > 1 || b[0] > 0){
var c : Array = a;
a = b;
b = mod(c, b);
}
return a;
}
public static function shave(a : Array) : Array
{
for(var i : uint = a.length - 1;i >= 1;i--){
if(a[i] > 0)break;
a.pop();
}
return a;
}
private static function addFractions(...o : Array) : Array
{
if(o.length == 0)return [[0], [1]];
var ret : Array = o[0].concat();
for(var i : uint = 1;i < o.length;i++){
var num : Array = add(mul(ret[0], o[i][1]), mul(ret[1], o[i][0]));
var den : Array = mul(ret[1], o[i][1]);
var g : Array = gcd(num, den);
ret[0] = div(num, g)[0];
ret[1] = div(den, g)[0];
}
return ret;
}
public static function pow(a : Array, b : uint) : Array
{
var ret : Array = [1];
var m : Array = a.concat();
for(var u : uint = b;u > 0;u >>= 1){
if(u & 1){
ret = mul(ret, m);
}
m = mul(m, m);
}
return ret;
}
}
