big-rational
Advanced tools
Comparing version 0.10.7 to 0.10.9
@@ -1,1 +0,1 @@ | ||
var bigInt=function(undefined){"use strict";var BASE=1e7,LOG_BASE=7,MAX_INT=9007199254740992,MAX_INT_ARR=smallToArray(MAX_INT),LOG_MAX_INT=Math.log(MAX_INT);function Integer(v,radix){if(typeof v==="undefined")return Integer[0];if(typeof radix!=="undefined")return+radix===10?parseValue(v):parseBase(v,radix);return parseValue(v)}function BigInteger(value,sign){this.value=value;this.sign=sign;this.isSmall=false}BigInteger.prototype=Object.create(Integer.prototype);function SmallInteger(value){this.value=value;this.sign=value<0;this.isSmall=true}SmallInteger.prototype=Object.create(Integer.prototype);function isPrecise(n){return-MAX_INT<n&&n<MAX_INT}function smallToArray(n){if(n<1e7)return[n];if(n<1e14)return[n%1e7,Math.floor(n/1e7)];return[n%1e7,Math.floor(n/1e7)%1e7,Math.floor(n/1e14)]}function arrayToSmall(arr){trim(arr);var length=arr.length;if(length<4&&compareAbs(arr,MAX_INT_ARR)<0){switch(length){case 0:return 0;case 1:return arr[0];case 2:return arr[0]+arr[1]*BASE;default:return arr[0]+(arr[1]+arr[2]*BASE)*BASE}}return arr}function trim(v){var i=v.length;while(v[--i]===0);v.length=i+1}function createArray(length){var x=new Array(length);var i=-1;while(++i<length){x[i]=0}return x}function truncate(n){if(n>0)return Math.floor(n);return Math.ceil(n)}function add(a,b){var l_a=a.length,l_b=b.length,r=new Array(l_a),carry=0,base=BASE,sum,i;for(i=0;i<l_b;i++){sum=a[i]+b[i]+carry;carry=sum>=base?1:0;r[i]=sum-carry*base}while(i<l_a){sum=a[i]+carry;carry=sum===base?1:0;r[i++]=sum-carry*base}if(carry>0)r.push(carry);return r}function addAny(a,b){if(a.length>=b.length)return add(a,b);return add(b,a)}function addSmall(a,carry){var l=a.length,r=new Array(l),base=BASE,sum,i;for(i=0;i<l;i++){sum=a[i]-base+carry;carry=Math.floor(sum/base);r[i]=sum-carry*base;carry+=1}while(carry>0){r[i++]=carry%base;carry=Math.floor(carry/base)}return r}BigInteger.prototype.add=function(v){var n=parseValue(v);if(this.sign!==n.sign){return this.subtract(n.negate())}var a=this.value,b=n.value;if(n.isSmall){return new BigInteger(addSmall(a,Math.abs(b)),this.sign)}return new BigInteger(addAny(a,b),this.sign)};BigInteger.prototype.plus=BigInteger.prototype.add;SmallInteger.prototype.add=function(v){var n=parseValue(v);var a=this.value;if(a<0!==n.sign){return this.subtract(n.negate())}var b=n.value;if(n.isSmall){if(isPrecise(a+b))return new SmallInteger(a+b);b=smallToArray(Math.abs(b))}return new BigInteger(addSmall(b,Math.abs(a)),a<0)};SmallInteger.prototype.plus=SmallInteger.prototype.add;function subtract(a,b){var a_l=a.length,b_l=b.length,r=new Array(a_l),borrow=0,base=BASE,i,difference;for(i=0;i<b_l;i++){difference=a[i]-borrow-b[i];if(difference<0){difference+=base;borrow=1}else borrow=0;r[i]=difference}for(i=b_l;i<a_l;i++){difference=a[i]-borrow;if(difference<0)difference+=base;else{r[i++]=difference;break}r[i]=difference}for(;i<a_l;i++){r[i]=a[i]}trim(r);return r}function subtractAny(a,b,sign){var value;if(compareAbs(a,b)>=0){value=subtract(a,b)}else{value=subtract(b,a);sign=!sign}value=arrayToSmall(value);if(typeof value==="number"){if(sign)value=-value;return new SmallInteger(value)}return new BigInteger(value,sign)}function subtractSmall(a,b,sign){var l=a.length,r=new Array(l),carry=-b,base=BASE,i,difference;for(i=0;i<l;i++){difference=a[i]+carry;carry=Math.floor(difference/base);difference%=base;r[i]=difference<0?difference+base:difference}r=arrayToSmall(r);if(typeof r==="number"){if(sign)r=-r;return new SmallInteger(r)}return new BigInteger(r,sign)}BigInteger.prototype.subtract=function(v){var n=parseValue(v);if(this.sign!==n.sign){return this.add(n.negate())}var a=this.value,b=n.value;if(n.isSmall)return subtractSmall(a,Math.abs(b),this.sign);return subtractAny(a,b,this.sign)};BigInteger.prototype.minus=BigInteger.prototype.subtract;SmallInteger.prototype.subtract=function(v){var n=parseValue(v);var a=this.value;if(a<0!==n.sign){return this.add(n.negate())}var b=n.value;if(n.isSmall){return new SmallInteger(a-b)}return subtractSmall(b,Math.abs(a),a>=0)};SmallInteger.prototype.minus=SmallInteger.prototype.subtract;BigInteger.prototype.negate=function(){return new BigInteger(this.value,!this.sign)};SmallInteger.prototype.negate=function(){var sign=this.sign;var small=new SmallInteger(-this.value);small.sign=!sign;return small};BigInteger.prototype.abs=function(){return new BigInteger(this.value,false)};SmallInteger.prototype.abs=function(){return new SmallInteger(Math.abs(this.value))};function multiplyLong(a,b){var a_l=a.length,b_l=b.length,l=a_l+b_l,r=createArray(l),base=BASE,product,carry,i,a_i,b_j;for(i=0;i<a_l;++i){a_i=a[i];for(var j=0;j<b_l;++j){b_j=b[j];product=a_i*b_j+r[i+j];carry=Math.floor(product/base);r[i+j]=product-carry*base;r[i+j+1]+=carry}}trim(r);return r}function multiplySmall(a,b){var l=a.length,r=new Array(l),base=BASE,carry=0,product,i;for(i=0;i<l;i++){product=a[i]*b+carry;carry=Math.floor(product/base);r[i]=product-carry*base}while(carry>0){r[i++]=carry%base;carry=Math.floor(carry/base)}return r}function shiftLeft(x,n){var r=[];while(n-- >0)r.push(0);return r.concat(x)}function multiplyKaratsuba(x,y){var n=Math.max(x.length,y.length);if(n<=30)return multiplyLong(x,y);n=Math.ceil(n/2);var b=x.slice(n),a=x.slice(0,n),d=y.slice(n),c=y.slice(0,n);var ac=multiplyKaratsuba(a,c),bd=multiplyKaratsuba(b,d),abcd=multiplyKaratsuba(addAny(a,b),addAny(c,d));var product=addAny(addAny(ac,shiftLeft(subtract(subtract(abcd,ac),bd),n)),shiftLeft(bd,2*n));trim(product);return product}function useKaratsuba(l1,l2){return-.012*l1-.012*l2+15e-6*l1*l2>0}BigInteger.prototype.multiply=function(v){var n=parseValue(v),a=this.value,b=n.value,sign=this.sign!==n.sign,abs;if(n.isSmall){if(b===0)return Integer[0];if(b===1)return this;if(b===-1)return this.negate();abs=Math.abs(b);if(abs<BASE){return new BigInteger(multiplySmall(a,abs),sign)}b=smallToArray(abs)}if(useKaratsuba(a.length,b.length))return new BigInteger(multiplyKaratsuba(a,b),sign);return new BigInteger(multiplyLong(a,b),sign)};BigInteger.prototype.times=BigInteger.prototype.multiply;function multiplySmallAndArray(a,b,sign){if(a<BASE){return new BigInteger(multiplySmall(b,a),sign)}return new BigInteger(multiplyLong(b,smallToArray(a)),sign)}SmallInteger.prototype._multiplyBySmall=function(a){if(isPrecise(a.value*this.value)){return new SmallInteger(a.value*this.value)}return multiplySmallAndArray(Math.abs(a.value),smallToArray(Math.abs(this.value)),this.sign!==a.sign)};BigInteger.prototype._multiplyBySmall=function(a){if(a.value===0)return Integer[0];if(a.value===1)return this;if(a.value===-1)return this.negate();return multiplySmallAndArray(Math.abs(a.value),this.value,this.sign!==a.sign)};SmallInteger.prototype.multiply=function(v){return parseValue(v)._multiplyBySmall(this)};SmallInteger.prototype.times=SmallInteger.prototype.multiply;function square(a){var l=a.length,r=createArray(l+l),base=BASE,product,carry,i,a_i,a_j;for(i=0;i<l;i++){a_i=a[i];for(var j=0;j<l;j++){a_j=a[j];product=a_i*a_j+r[i+j];carry=Math.floor(product/base);r[i+j]=product-carry*base;r[i+j+1]+=carry}}trim(r);return r}BigInteger.prototype.square=function(){return new BigInteger(square(this.value),false)};SmallInteger.prototype.square=function(){var value=this.value*this.value;if(isPrecise(value))return new SmallInteger(value);return new BigInteger(square(smallToArray(Math.abs(this.value))),false)};function divMod1(a,b){var a_l=a.length,b_l=b.length,base=BASE,result=createArray(b.length),divisorMostSignificantDigit=b[b_l-1],lambda=Math.ceil(base/(2*divisorMostSignificantDigit)),remainder=multiplySmall(a,lambda),divisor=multiplySmall(b,lambda),quotientDigit,shift,carry,borrow,i,l,q;if(remainder.length<=a_l)remainder.push(0);divisor.push(0);divisorMostSignificantDigit=divisor[b_l-1];for(shift=a_l-b_l;shift>=0;shift--){quotientDigit=base-1;if(remainder[shift+b_l]!==divisorMostSignificantDigit){quotientDigit=Math.floor((remainder[shift+b_l]*base+remainder[shift+b_l-1])/divisorMostSignificantDigit)}carry=0;borrow=0;l=divisor.length;for(i=0;i<l;i++){carry+=quotientDigit*divisor[i];q=Math.floor(carry/base);borrow+=remainder[shift+i]-(carry-q*base);carry=q;if(borrow<0){remainder[shift+i]=borrow+base;borrow=-1}else{remainder[shift+i]=borrow;borrow=0}}while(borrow!==0){quotientDigit-=1;carry=0;for(i=0;i<l;i++){carry+=remainder[shift+i]-base+divisor[i];if(carry<0){remainder[shift+i]=carry+base;carry=0}else{remainder[shift+i]=carry;carry=1}}borrow+=carry}result[shift]=quotientDigit}remainder=divModSmall(remainder,lambda)[0];return[arrayToSmall(result),arrayToSmall(remainder)]}function divMod2(a,b){var a_l=a.length,b_l=b.length,result=[],part=[],base=BASE,guess,xlen,highx,highy,check;while(a_l){part.unshift(a[--a_l]);trim(part);if(compareAbs(part,b)<0){result.push(0);continue}xlen=part.length;highx=part[xlen-1]*base+part[xlen-2];highy=b[b_l-1]*base+b[b_l-2];if(xlen>b_l){highx=(highx+1)*base}guess=Math.ceil(highx/highy);do{check=multiplySmall(b,guess);if(compareAbs(check,part)<=0)break;guess--}while(guess);result.push(guess);part=subtract(part,check)}result.reverse();return[arrayToSmall(result),arrayToSmall(part)]}function divModSmall(value,lambda){var length=value.length,quotient=createArray(length),base=BASE,i,q,remainder,divisor;remainder=0;for(i=length-1;i>=0;--i){divisor=remainder*base+value[i];q=truncate(divisor/lambda);remainder=divisor-q*lambda;quotient[i]=q|0}return[quotient,remainder|0]}function divModAny(self,v){var value,n=parseValue(v);var a=self.value,b=n.value;var quotient;if(b===0)throw new Error("Cannot divide by zero");if(self.isSmall){if(n.isSmall){return[new SmallInteger(truncate(a/b)),new SmallInteger(a%b)]}return[Integer[0],self]}if(n.isSmall){if(b===1)return[self,Integer[0]];if(b==-1)return[self.negate(),Integer[0]];var abs=Math.abs(b);if(abs<BASE){value=divModSmall(a,abs);quotient=arrayToSmall(value[0]);var remainder=value[1];if(self.sign)remainder=-remainder;if(typeof quotient==="number"){if(self.sign!==n.sign)quotient=-quotient;return[new SmallInteger(quotient),new SmallInteger(remainder)]}return[new BigInteger(quotient,self.sign!==n.sign),new SmallInteger(remainder)]}b=smallToArray(abs)}var comparison=compareAbs(a,b);if(comparison===-1)return[Integer[0],self];if(comparison===0)return[Integer[self.sign===n.sign?1:-1],Integer[0]];if(a.length+b.length<=200)value=divMod1(a,b);else value=divMod2(a,b);quotient=value[0];var qSign=self.sign!==n.sign,mod=value[1],mSign=self.sign;if(typeof quotient==="number"){if(qSign)quotient=-quotient;quotient=new SmallInteger(quotient)}else quotient=new BigInteger(quotient,qSign);if(typeof mod==="number"){if(mSign)mod=-mod;mod=new SmallInteger(mod)}else mod=new BigInteger(mod,mSign);return[quotient,mod]}BigInteger.prototype.divmod=function(v){var result=divModAny(this,v);return{quotient:result[0],remainder:result[1]}};SmallInteger.prototype.divmod=BigInteger.prototype.divmod;BigInteger.prototype.divide=function(v){return divModAny(this,v)[0]};SmallInteger.prototype.over=SmallInteger.prototype.divide=BigInteger.prototype.over=BigInteger.prototype.divide;BigInteger.prototype.mod=function(v){return divModAny(this,v)[1]};SmallInteger.prototype.remainder=SmallInteger.prototype.mod=BigInteger.prototype.remainder=BigInteger.prototype.mod;BigInteger.prototype.pow=function(v){var n=parseValue(v),a=this.value,b=n.value,value,x,y;if(b===0)return Integer[1];if(a===0)return Integer[0];if(a===1)return Integer[1];if(a===-1)return n.isEven()?Integer[1]:Integer[-1];if(n.sign){return Integer[0]}if(!n.isSmall)throw new Error("The exponent "+n.toString()+" is too large.");if(this.isSmall){if(isPrecise(value=Math.pow(a,b)))return new SmallInteger(truncate(value))}x=this;y=Integer[1];while(true){if(b&1===1){y=y.times(x);--b}if(b===0)break;b/=2;x=x.square()}return y};SmallInteger.prototype.pow=BigInteger.prototype.pow;BigInteger.prototype.modPow=function(exp,mod){exp=parseValue(exp);mod=parseValue(mod);if(mod.isZero())throw new Error("Cannot take modPow with modulus 0");var r=Integer[1],base=this.mod(mod);while(exp.isPositive()){if(base.isZero())return Integer[0];if(exp.isOdd())r=r.multiply(base).mod(mod);exp=exp.divide(2);base=base.square().mod(mod)}return r};SmallInteger.prototype.modPow=BigInteger.prototype.modPow;function compareAbs(a,b){if(a.length!==b.length){return a.length>b.length?1:-1}for(var i=a.length-1;i>=0;i--){if(a[i]!==b[i])return a[i]>b[i]?1:-1}return 0}BigInteger.prototype.compareAbs=function(v){var n=parseValue(v),a=this.value,b=n.value;if(n.isSmall)return 1;return compareAbs(a,b)};SmallInteger.prototype.compareAbs=function(v){var n=parseValue(v),a=Math.abs(this.value),b=n.value;if(n.isSmall){b=Math.abs(b);return a===b?0:a>b?1:-1}return-1};BigInteger.prototype.compare=function(v){if(v===Infinity){return-1}if(v===-Infinity){return 1}var n=parseValue(v),a=this.value,b=n.value;if(this.sign!==n.sign){return n.sign?1:-1}if(n.isSmall){return this.sign?-1:1}return compareAbs(a,b)*(this.sign?-1:1)};BigInteger.prototype.compareTo=BigInteger.prototype.compare;SmallInteger.prototype.compare=function(v){if(v===Infinity){return-1}if(v===-Infinity){return 1}var n=parseValue(v),a=this.value,b=n.value;if(n.isSmall){return a==b?0:a>b?1:-1}if(a<0!==n.sign){return a<0?-1:1}return a<0?1:-1};SmallInteger.prototype.compareTo=SmallInteger.prototype.compare;BigInteger.prototype.equals=function(v){return this.compare(v)===0};SmallInteger.prototype.eq=SmallInteger.prototype.equals=BigInteger.prototype.eq=BigInteger.prototype.equals;BigInteger.prototype.notEquals=function(v){return this.compare(v)!==0};SmallInteger.prototype.neq=SmallInteger.prototype.notEquals=BigInteger.prototype.neq=BigInteger.prototype.notEquals;BigInteger.prototype.greater=function(v){return this.compare(v)>0};SmallInteger.prototype.gt=SmallInteger.prototype.greater=BigInteger.prototype.gt=BigInteger.prototype.greater;BigInteger.prototype.lesser=function(v){return this.compare(v)<0};SmallInteger.prototype.lt=SmallInteger.prototype.lesser=BigInteger.prototype.lt=BigInteger.prototype.lesser;BigInteger.prototype.greaterOrEquals=function(v){return this.compare(v)>=0};SmallInteger.prototype.geq=SmallInteger.prototype.greaterOrEquals=BigInteger.prototype.geq=BigInteger.prototype.greaterOrEquals;BigInteger.prototype.lesserOrEquals=function(v){return this.compare(v)<=0};SmallInteger.prototype.leq=SmallInteger.prototype.lesserOrEquals=BigInteger.prototype.leq=BigInteger.prototype.lesserOrEquals;BigInteger.prototype.isEven=function(){return(this.value[0]&1)===0};SmallInteger.prototype.isEven=function(){return(this.value&1)===0};BigInteger.prototype.isOdd=function(){return(this.value[0]&1)===1};SmallInteger.prototype.isOdd=function(){return(this.value&1)===1};BigInteger.prototype.isPositive=function(){return!this.sign};SmallInteger.prototype.isPositive=function(){return this.value>0};BigInteger.prototype.isNegative=function(){return this.sign};SmallInteger.prototype.isNegative=function(){return this.value<0};BigInteger.prototype.isUnit=function(){return false};SmallInteger.prototype.isUnit=function(){return Math.abs(this.value)===1};BigInteger.prototype.isZero=function(){return false};SmallInteger.prototype.isZero=function(){return this.value===0};BigInteger.prototype.isDivisibleBy=function(v){var n=parseValue(v);var value=n.value;if(value===0)return false;if(value===1)return true;if(value===2)return this.isEven();return this.mod(n).equals(Integer[0])};SmallInteger.prototype.isDivisibleBy=BigInteger.prototype.isDivisibleBy;function isBasicPrime(v){var n=v.abs();if(n.isUnit())return false;if(n.equals(2)||n.equals(3)||n.equals(5))return true;if(n.isEven()||n.isDivisibleBy(3)||n.isDivisibleBy(5))return false;if(n.lesser(25))return true}BigInteger.prototype.isPrime=function(){var isPrime=isBasicPrime(this);if(isPrime!==undefined)return isPrime;var n=this.abs(),nPrev=n.prev();var a=[2,3,5,7,11,13,17,19],b=nPrev,d,t,i,x;while(b.isEven())b=b.divide(2);for(i=0;i<a.length;i++){x=bigInt(a[i]).modPow(b,n);if(x.equals(Integer[1])||x.equals(nPrev))continue;for(t=true,d=b;t&&d.lesser(nPrev);d=d.multiply(2)){x=x.square().mod(n);if(x.equals(nPrev))t=false}if(t)return false}return true};SmallInteger.prototype.isPrime=BigInteger.prototype.isPrime;BigInteger.prototype.isProbablePrime=function(iterations){var isPrime=isBasicPrime(this);if(isPrime!==undefined)return isPrime;var n=this.abs();var t=iterations===undefined?5:iterations;for(var i=0;i<t;i++){var a=bigInt.randBetween(2,n.minus(2));if(!a.modPow(n.prev(),n).isUnit())return false}return true};SmallInteger.prototype.isProbablePrime=BigInteger.prototype.isProbablePrime;BigInteger.prototype.modInv=function(n){var t=bigInt.zero,newT=bigInt.one,r=parseValue(n),newR=this.abs(),q,lastT,lastR;while(!newR.equals(bigInt.zero)){q=r.divide(newR);lastT=t;lastR=r;t=newT;r=newR;newT=lastT.subtract(q.multiply(newT));newR=lastR.subtract(q.multiply(newR))}if(!r.equals(1))throw new Error(this.toString()+" and "+n.toString()+" are not co-prime");if(t.compare(0)===-1){t=t.add(n)}if(this.isNegative()){return t.negate()}return t};SmallInteger.prototype.modInv=BigInteger.prototype.modInv;BigInteger.prototype.next=function(){var value=this.value;if(this.sign){return subtractSmall(value,1,this.sign)}return new BigInteger(addSmall(value,1),this.sign)};SmallInteger.prototype.next=function(){var value=this.value;if(value+1<MAX_INT)return new SmallInteger(value+1);return new BigInteger(MAX_INT_ARR,false)};BigInteger.prototype.prev=function(){var value=this.value;if(this.sign){return new BigInteger(addSmall(value,1),true)}return subtractSmall(value,1,this.sign)};SmallInteger.prototype.prev=function(){var value=this.value;if(value-1>-MAX_INT)return new SmallInteger(value-1);return new BigInteger(MAX_INT_ARR,true)};var powersOfTwo=[1];while(powersOfTwo[powersOfTwo.length-1]<=BASE)powersOfTwo.push(2*powersOfTwo[powersOfTwo.length-1]);var powers2Length=powersOfTwo.length,highestPower2=powersOfTwo[powers2Length-1];function shift_isSmall(n){return(typeof n==="number"||typeof n==="string")&&+Math.abs(n)<=BASE||n instanceof BigInteger&&n.value.length<=1}BigInteger.prototype.shiftLeft=function(n){if(!shift_isSmall(n)){throw new Error(String(n)+" is too large for shifting.")}n=+n;if(n<0)return this.shiftRight(-n);var result=this;while(n>=powers2Length){result=result.multiply(highestPower2);n-=powers2Length-1}return result.multiply(powersOfTwo[n])};SmallInteger.prototype.shiftLeft=BigInteger.prototype.shiftLeft;BigInteger.prototype.shiftRight=function(n){var remQuo;if(!shift_isSmall(n)){throw new Error(String(n)+" is too large for shifting.")}n=+n;if(n<0)return this.shiftLeft(-n);var result=this;while(n>=powers2Length){if(result.isZero())return result;remQuo=divModAny(result,highestPower2);result=remQuo[1].isNegative()?remQuo[0].prev():remQuo[0];n-=powers2Length-1}remQuo=divModAny(result,powersOfTwo[n]);return remQuo[1].isNegative()?remQuo[0].prev():remQuo[0]};SmallInteger.prototype.shiftRight=BigInteger.prototype.shiftRight;function bitwise(x,y,fn){y=parseValue(y);var xSign=x.isNegative(),ySign=y.isNegative();var xRem=xSign?x.not():x,yRem=ySign?y.not():y;var xBits=[],yBits=[];var xStop=false,yStop=false;while(!xStop||!yStop){if(xRem.isZero()){xStop=true;xBits.push(xSign?1:0)}else if(xSign)xBits.push(xRem.isEven()?1:0);else xBits.push(xRem.isEven()?0:1);if(yRem.isZero()){yStop=true;yBits.push(ySign?1:0)}else if(ySign)yBits.push(yRem.isEven()?1:0);else yBits.push(yRem.isEven()?0:1);xRem=xRem.over(2);yRem=yRem.over(2)}var result=[];for(var i=0;i<xBits.length;i++)result.push(fn(xBits[i],yBits[i]));var sum=bigInt(result.pop()).negate().times(bigInt(2).pow(result.length));while(result.length){sum=sum.add(bigInt(result.pop()).times(bigInt(2).pow(result.length)))}return sum}BigInteger.prototype.not=function(){return this.negate().prev()};SmallInteger.prototype.not=BigInteger.prototype.not;BigInteger.prototype.and=function(n){return bitwise(this,n,function(a,b){return a&b})};SmallInteger.prototype.and=BigInteger.prototype.and;BigInteger.prototype.or=function(n){return bitwise(this,n,function(a,b){return a|b})};SmallInteger.prototype.or=BigInteger.prototype.or;BigInteger.prototype.xor=function(n){return bitwise(this,n,function(a,b){return a^b})};SmallInteger.prototype.xor=BigInteger.prototype.xor;var LOBMASK_I=1<<30,LOBMASK_BI=(BASE&-BASE)*(BASE&-BASE)|LOBMASK_I;function roughLOB(n){var v=n.value,x=typeof v==="number"?v|LOBMASK_I:v[0]+v[1]*BASE|LOBMASK_BI;return x&-x}function max(a,b){a=parseValue(a);b=parseValue(b);return a.greater(b)?a:b}function min(a,b){a=parseValue(a);b=parseValue(b);return a.lesser(b)?a:b}function gcd(a,b){a=parseValue(a).abs();b=parseValue(b).abs();if(a.equals(b))return a;if(a.isZero())return b;if(b.isZero())return a;var c=Integer[1],d,t;while(a.isEven()&&b.isEven()){d=Math.min(roughLOB(a),roughLOB(b));a=a.divide(d);b=b.divide(d);c=c.multiply(d)}while(a.isEven()){a=a.divide(roughLOB(a))}do{while(b.isEven()){b=b.divide(roughLOB(b))}if(a.greater(b)){t=b;b=a;a=t}b=b.subtract(a)}while(!b.isZero());return c.isUnit()?a:a.multiply(c)}function lcm(a,b){a=parseValue(a).abs();b=parseValue(b).abs();return a.divide(gcd(a,b)).multiply(b)}function randBetween(a,b){a=parseValue(a);b=parseValue(b);var low=min(a,b),high=max(a,b);var range=high.subtract(low);if(range.isSmall)return low.add(Math.round(Math.random()*range));var length=range.value.length-1;var result=[],restricted=true;for(var i=length;i>=0;i--){var top=restricted?range.value[i]:BASE;var digit=truncate(Math.random()*top);result.unshift(digit);if(digit<top)restricted=false}result=arrayToSmall(result);return low.add(typeof result==="number"?new SmallInteger(result):new BigInteger(result,false))}var parseBase=function(text,base){var length=text.length;if(2<=base&&base<=36){if(length<=LOG_MAX_INT/Math.log(base)){return new SmallInteger(parseInt(text,base))}}base=parseValue(base);var digits=[];var i;var isNegative=text[0]==="-";for(i=isNegative?1:0;i<text.length;i++){var c=text[i].toLowerCase(),charCode=c.charCodeAt(0);if(48<=charCode&&charCode<=57)digits.push(parseValue(c));else if(97<=charCode&&charCode<=122)digits.push(parseValue(c.charCodeAt(0)-87));else if(c==="<"){var start=i;do{i++}while(text[i]!==">");digits.push(parseValue(text.slice(start+1,i)))}else throw new Error(c+" is not a valid character")}return parseBaseFromArray(digits,base,isNegative)};function parseBaseFromArray(digits,base,isNegative){var val=Integer[0],pow=Integer[1],i;for(i=digits.length-1;i>=0;i--){val=val.add(digits[i].times(pow));pow=pow.times(base)}return isNegative?val.negate():val}function stringify(digit){var v=digit.value;if(typeof v==="number")v=[v];if(v.length===1&&v[0]<=35){return"0123456789abcdefghijklmnopqrstuvwxyz".charAt(v[0])}return"<"+v+">"}function toBase(n,base){base=bigInt(base);if(base.isZero()){if(n.isZero())return"0";throw new Error("Cannot convert nonzero numbers to base 0.")}if(base.equals(-1)){if(n.isZero())return"0";if(n.isNegative())return new Array(1-n).join("10");return"1"+new Array(+n).join("01")}var minusSign="";if(n.isNegative()&&base.isPositive()){minusSign="-";n=n.abs()}if(base.equals(1)){if(n.isZero())return"0";return minusSign+new Array(+n+1).join(1)}var out=[];var left=n,divmod;while(left.isNegative()||left.compareAbs(base)>=0){divmod=left.divmod(base);left=divmod.quotient;var digit=divmod.remainder;if(digit.isNegative()){digit=base.minus(digit).abs();left=left.next()}out.push(stringify(digit))}out.push(stringify(left));return minusSign+out.reverse().join("")}BigInteger.prototype.toString=function(radix){if(radix===undefined)radix=10;if(radix!==10)return toBase(this,radix);var v=this.value,l=v.length,str=String(v[--l]),zeros="0000000",digit;while(--l>=0){digit=String(v[l]);str+=zeros.slice(digit.length)+digit}var sign=this.sign?"-":"";return sign+str};SmallInteger.prototype.toString=function(radix){if(radix===undefined)radix=10;if(radix!=10)return toBase(this,radix);return String(this.value)};BigInteger.prototype.valueOf=function(){return+this.toString()};BigInteger.prototype.toJSNumber=BigInteger.prototype.valueOf;SmallInteger.prototype.valueOf=function(){return this.value};SmallInteger.prototype.toJSNumber=SmallInteger.prototype.valueOf;function parseStringValue(v){if(isPrecise(+v)){var x=+v;if(x===truncate(x))return new SmallInteger(x);throw"Invalid integer: "+v}var sign=v[0]==="-";if(sign)v=v.slice(1);var split=v.split(/e/i);if(split.length>2)throw new Error("Invalid integer: "+split.join("e"));if(split.length===2){var exp=split[1];if(exp[0]==="+")exp=exp.slice(1);exp=+exp;if(exp!==truncate(exp)||!isPrecise(exp))throw new Error("Invalid integer: "+exp+" is not a valid exponent.");var text=split[0];var decimalPlace=text.indexOf(".");if(decimalPlace>=0){exp-=text.length-decimalPlace-1;text=text.slice(0,decimalPlace)+text.slice(decimalPlace+1)}if(exp<0)throw new Error("Cannot include negative exponent part for integers");text+=new Array(exp+1).join("0");v=text}var isValid=/^([0-9][0-9]*)$/.test(v);if(!isValid)throw new Error("Invalid integer: "+v);var r=[],max=v.length,l=LOG_BASE,min=max-l;while(max>0){r.push(+v.slice(min,max));min-=l;if(min<0)min=0;max-=l}trim(r);return new BigInteger(r,sign)}function parseNumberValue(v){if(isPrecise(v)){if(v!==truncate(v))throw new Error(v+" is not an integer.");return new SmallInteger(v)}return parseStringValue(v.toString())}function parseValue(v){if(typeof v==="number"){return parseNumberValue(v)}if(typeof v==="string"){return parseStringValue(v)}return v}for(var i=0;i<1e3;i++){Integer[i]=new SmallInteger(i);if(i>0)Integer[-i]=new SmallInteger(-i)}Integer.one=Integer[1];Integer.zero=Integer[0];Integer.minusOne=Integer[-1];Integer.max=max;Integer.min=min;Integer.gcd=gcd;Integer.lcm=lcm;Integer.isInstance=function(x){return x instanceof BigInteger||x instanceof SmallInteger};Integer.randBetween=randBetween;Integer.fromArray=function(digits,base,isNegative){return parseBaseFromArray(digits.map(parseValue),parseValue(base||10),isNegative)};return Integer}();if(typeof module!=="undefined"&&module.hasOwnProperty("exports")){module.exports=bigInt}if(typeof define==="function"&&define.amd){define("big-integer",[],function(){return bigInt})}var bigRat=function(bigInt){"use strict";function BigRational(num,denom){if(denom.isZero())throw"Denominator cannot be 0.";this.numerator=this.num=num;this.denominator=this.denom=denom}var gcd=bigInt.gcd,lcm=bigInt.lcm;function reduce(n,d){var divisor=gcd(n,d),num=n.over(divisor),denom=d.over(divisor);if(denom.isNegative()){return new BigRational(num.negate(),denom.negate())}return new BigRational(num,denom)}BigRational.prototype.add=function(n,d){var v=interpret(n,d),multiple=lcm(this.denom,v.denom),a=multiple.divide(this.denom),b=multiple.divide(v.denom);a=this.num.times(a);b=v.num.times(b);return reduce(a.add(b),multiple)};BigRational.prototype.plus=BigRational.prototype.add;BigRational.prototype.subtract=function(n,d){var v=interpret(n,d);return this.add(v.negate())};BigRational.prototype.minus=BigRational.prototype.subtract;BigRational.prototype.multiply=function(n,d){var v=interpret(n,d);return reduce(this.num.times(v.num),this.denom.times(v.denom))};BigRational.prototype.times=BigRational.prototype.multiply;BigRational.prototype.divide=function(n,d){var v=interpret(n,d);return reduce(this.num.times(v.denom),this.denom.times(v.num))};BigRational.prototype.over=BigRational.prototype.divide;BigRational.prototype.reciprocate=function(){return new BigRational(this.denom,this.num)};BigRational.prototype.mod=function(n,d){var v=interpret(n,d);return this.minus(v.times(this.over(v).floor()))};BigRational.prototype.pow=function(n){var v=bigInt(n);var num=this.num.pow(v),denom=this.denom.pow(v);return reduce(num,denom)};BigRational.prototype.floor=function(toBigInt){var divmod=this.num.divmod(this.denom),floor;if(divmod.remainder.isZero()||!divmod.quotient.sign){floor=divmod.quotient}else floor=divmod.quotient.prev();if(toBigInt)return floor;return new BigRational(floor,bigInt[1])};BigRational.prototype.ceil=function(toBigInt){var divmod=this.num.divmod(this.denom),ceil;if(divmod.remainder.isZero()||divmod.quotient.sign){ceil=divmod.quotient}else ceil=divmod.quotient.next();if(toBigInt)return ceil;return new BigRational(ceil,bigInt[1])};BigRational.prototype.round=function(toBigInt){return this.add(1,2).floor(toBigInt)};BigRational.prototype.compareAbs=function(n,d){var v=interpret(n,d);if(this.denom.equals(v.denom)){return this.num.compareAbs(v.num)}return this.num.times(v.denom).compareAbs(v.num.times(this.denom))};BigRational.prototype.compare=function(n,d){var v=interpret(n,d);if(this.denom.equals(v.denom)){return this.num.compare(v.num)}var comparison=this.denom.sign===v.denom.sign?1:-1;return comparison*this.num.times(v.denom).compare(v.num.times(this.denom))};BigRational.prototype.compareTo=BigRational.prototype.compare;BigRational.prototype.equals=function(n,d){return this.compare(n,d)===0};BigRational.prototype.eq=BigRational.prototype.equals;BigRational.prototype.notEquals=function(n,d){return this.compare(n,d)!==0};BigRational.prototype.neq=BigRational.prototype.notEquals;BigRational.prototype.lesser=function(n,d){return this.compare(n,d)<0};BigRational.prototype.lt=BigRational.prototype.lesser;BigRational.prototype.lesserOrEquals=function(n,d){return this.compare(n,d)<=0};BigRational.prototype.leq=BigRational.prototype.lesserOrEquals;BigRational.prototype.greater=function(n,d){return this.compare(n,d)>0};BigRational.prototype.gt=BigRational.prototype.greater;BigRational.prototype.greaterOrEquals=function(n,d){return this.compare(n,d)>=0};BigRational.prototype.geq=BigRational.prototype.greaterOrEquals;BigRational.prototype.abs=function(){if(this.isPositive())return this;return this.negate()};BigRational.prototype.negate=function(){if(this.denom.sign){return new BigRational(this.num,this.denom.negate())}return new BigRational(this.num.negate(),this.denom)};BigRational.prototype.isNegative=function(){return this.num.sign!==this.denom.sign&&!this.num.isZero()};BigRational.prototype.isPositive=function(){return this.num.sign===this.denom.sign&&!this.num.isZero()};BigRational.prototype.isZero=function(){return this.num.isZero()};BigRational.prototype.toDecimal=function(digits){digits=typeof digits==="number"?digits:10;var n=this.num.divmod(this.denom);var intPart=n.quotient.abs().toString();var remainder=parse(n.remainder.abs(),this.denom);var shiftedRemainder=remainder.times(bigInt("1e"+digits));var decPart=shiftedRemainder.num.over(shiftedRemainder.denom).toString();if(decPart.length<digits){decPart=new Array(digits-decPart.length+1).join("0")+decPart}if(shiftedRemainder.num.mod(shiftedRemainder.denom).isZero()){while(decPart.slice(-1)==="0"){decPart=decPart.slice(0,-1)}}if(digits<1)decPart="";if(this.isNegative()){intPart="-"+intPart}if(decPart===""){return intPart}return intPart+"."+decPart};BigRational.prototype.toString=function(){return String(this.num)+"/"+String(this.denom)};BigRational.prototype.valueOf=function(){return this.num/this.denom};function interpret(n,d){return parse(n,d)}function parseDecimal(n){var parts=n.split(/e/i);if(parts.length>2){throw new Error("Invalid input: too many 'e' tokens")}if(parts.length>1){var isPositive=true;if(parts[1][0]==="-"){parts[1]=parts[1].slice(1);isPositive=false}if(parts[1][0]==="+"){parts[1]=parts[1].slice(1)}var significand=parseDecimal(parts[0]);var exponent=new BigRational(bigInt(10).pow(parts[1]),bigInt[1]);if(isPositive){return significand.times(exponent)}else{return significand.over(exponent)}}parts=n.trim().split(".");if(parts.length>2){throw new Error("Invalid input: too many '.' tokens")}if(parts.length>1){var isNegative=parts[0][0]==="-";if(isNegative)parts[0]=parts[0].slice(1);var intPart=new BigRational(bigInt(parts[0]),bigInt[1]);var length=parts[1].length;while(parts[1][0]==="0"){parts[1]=parts[1].slice(1)}var exp="1"+Array(length+1).join("0");var decPart=reduce(bigInt(parts[1]),bigInt(exp));intPart=intPart.add(decPart);if(isNegative)intPart=intPart.negate();return intPart}return new BigRational(bigInt(n),bigInt[1])}function parse(a,b){if(!a){return new BigRational(bigInt(0),bigInt[1])}if(b){return reduce(bigInt(a),bigInt(b))}if(bigInt.isInstance(a)){return new BigRational(a,bigInt[1])}if(a instanceof BigRational)return a;var num;var denom;var text=String(a);var texts=text.split("/");if(texts.length>2){throw new Error("Invalid input: too many '/' tokens")}if(texts.length>1){var parts=texts[0].split("_");if(parts.length>2){throw new Error("Invalid input: too many '_' tokens")}if(parts.length>1){var isPositive=parts[0][0]!=="-";num=bigInt(parts[0]).times(texts[1]);if(isPositive){num=num.add(parts[1])}else{num=num.subtract(parts[1])}denom=bigInt(texts[1]);return reduce(num,denom)}return reduce(bigInt(texts[0]),bigInt(texts[1]))}return parseDecimal(text)}parse.zero=parse(0);parse.one=parse(1);parse.minusOne=parse(-1);return parse}(typeof bigInt!=="undefined"?bigInt:require("big-integer"));if(typeof module!=="undefined"){if(module.hasOwnProperty("exports")){module.exports=bigRat}} | ||
var bigInt=function(undefined){"use strict";var BASE=1e7,LOG_BASE=7,MAX_INT=9007199254740992,MAX_INT_ARR=smallToArray(MAX_INT),DEFAULT_ALPHABET="0123456789abcdefghijklmnopqrstuvwxyz";var supportsNativeBigInt=typeof BigInt==="function";function Integer(v,radix,alphabet,caseSensitive){if(typeof v==="undefined")return Integer[0];if(typeof radix!=="undefined")return+radix===10&&!alphabet?parseValue(v):parseBase(v,radix,alphabet,caseSensitive);return parseValue(v)}function BigInteger(value,sign){this.value=value;this.sign=sign;this.isSmall=false}BigInteger.prototype=Object.create(Integer.prototype);function SmallInteger(value){this.value=value;this.sign=value<0;this.isSmall=true}SmallInteger.prototype=Object.create(Integer.prototype);function NativeBigInt(value){this.value=value}NativeBigInt.prototype=Object.create(Integer.prototype);function isPrecise(n){return-MAX_INT<n&&n<MAX_INT}function smallToArray(n){if(n<1e7)return[n];if(n<1e14)return[n%1e7,Math.floor(n/1e7)];return[n%1e7,Math.floor(n/1e7)%1e7,Math.floor(n/1e14)]}function arrayToSmall(arr){trim(arr);var length=arr.length;if(length<4&&compareAbs(arr,MAX_INT_ARR)<0){switch(length){case 0:return 0;case 1:return arr[0];case 2:return arr[0]+arr[1]*BASE;default:return arr[0]+(arr[1]+arr[2]*BASE)*BASE}}return arr}function trim(v){var i=v.length;while(v[--i]===0);v.length=i+1}function createArray(length){var x=new Array(length);var i=-1;while(++i<length){x[i]=0}return x}function truncate(n){if(n>0)return Math.floor(n);return Math.ceil(n)}function add(a,b){var l_a=a.length,l_b=b.length,r=new Array(l_a),carry=0,base=BASE,sum,i;for(i=0;i<l_b;i++){sum=a[i]+b[i]+carry;carry=sum>=base?1:0;r[i]=sum-carry*base}while(i<l_a){sum=a[i]+carry;carry=sum===base?1:0;r[i++]=sum-carry*base}if(carry>0)r.push(carry);return r}function addAny(a,b){if(a.length>=b.length)return add(a,b);return add(b,a)}function addSmall(a,carry){var l=a.length,r=new Array(l),base=BASE,sum,i;for(i=0;i<l;i++){sum=a[i]-base+carry;carry=Math.floor(sum/base);r[i]=sum-carry*base;carry+=1}while(carry>0){r[i++]=carry%base;carry=Math.floor(carry/base)}return r}BigInteger.prototype.add=function(v){var n=parseValue(v);if(this.sign!==n.sign){return this.subtract(n.negate())}var a=this.value,b=n.value;if(n.isSmall){return new BigInteger(addSmall(a,Math.abs(b)),this.sign)}return new BigInteger(addAny(a,b),this.sign)};BigInteger.prototype.plus=BigInteger.prototype.add;SmallInteger.prototype.add=function(v){var n=parseValue(v);var a=this.value;if(a<0!==n.sign){return this.subtract(n.negate())}var b=n.value;if(n.isSmall){if(isPrecise(a+b))return new SmallInteger(a+b);b=smallToArray(Math.abs(b))}return new BigInteger(addSmall(b,Math.abs(a)),a<0)};SmallInteger.prototype.plus=SmallInteger.prototype.add;NativeBigInt.prototype.add=function(v){return new NativeBigInt(this.value+parseValue(v).value)};NativeBigInt.prototype.plus=NativeBigInt.prototype.add;function subtract(a,b){var a_l=a.length,b_l=b.length,r=new Array(a_l),borrow=0,base=BASE,i,difference;for(i=0;i<b_l;i++){difference=a[i]-borrow-b[i];if(difference<0){difference+=base;borrow=1}else borrow=0;r[i]=difference}for(i=b_l;i<a_l;i++){difference=a[i]-borrow;if(difference<0)difference+=base;else{r[i++]=difference;break}r[i]=difference}for(;i<a_l;i++){r[i]=a[i]}trim(r);return r}function subtractAny(a,b,sign){var value;if(compareAbs(a,b)>=0){value=subtract(a,b)}else{value=subtract(b,a);sign=!sign}value=arrayToSmall(value);if(typeof value==="number"){if(sign)value=-value;return new SmallInteger(value)}return new BigInteger(value,sign)}function subtractSmall(a,b,sign){var l=a.length,r=new Array(l),carry=-b,base=BASE,i,difference;for(i=0;i<l;i++){difference=a[i]+carry;carry=Math.floor(difference/base);difference%=base;r[i]=difference<0?difference+base:difference}r=arrayToSmall(r);if(typeof r==="number"){if(sign)r=-r;return new SmallInteger(r)}return new BigInteger(r,sign)}BigInteger.prototype.subtract=function(v){var n=parseValue(v);if(this.sign!==n.sign){return this.add(n.negate())}var a=this.value,b=n.value;if(n.isSmall)return subtractSmall(a,Math.abs(b),this.sign);return subtractAny(a,b,this.sign)};BigInteger.prototype.minus=BigInteger.prototype.subtract;SmallInteger.prototype.subtract=function(v){var n=parseValue(v);var a=this.value;if(a<0!==n.sign){return this.add(n.negate())}var b=n.value;if(n.isSmall){return new SmallInteger(a-b)}return subtractSmall(b,Math.abs(a),a>=0)};SmallInteger.prototype.minus=SmallInteger.prototype.subtract;NativeBigInt.prototype.subtract=function(v){return new NativeBigInt(this.value-parseValue(v).value)};NativeBigInt.prototype.minus=NativeBigInt.prototype.subtract;BigInteger.prototype.negate=function(){return new BigInteger(this.value,!this.sign)};SmallInteger.prototype.negate=function(){var sign=this.sign;var small=new SmallInteger(-this.value);small.sign=!sign;return small};NativeBigInt.prototype.negate=function(){return new NativeBigInt(-this.value)};BigInteger.prototype.abs=function(){return new BigInteger(this.value,false)};SmallInteger.prototype.abs=function(){return new SmallInteger(Math.abs(this.value))};NativeBigInt.prototype.abs=function(){return new NativeBigInt(this.value>=0?this.value:-this.value)};function multiplyLong(a,b){var a_l=a.length,b_l=b.length,l=a_l+b_l,r=createArray(l),base=BASE,product,carry,i,a_i,b_j;for(i=0;i<a_l;++i){a_i=a[i];for(var j=0;j<b_l;++j){b_j=b[j];product=a_i*b_j+r[i+j];carry=Math.floor(product/base);r[i+j]=product-carry*base;r[i+j+1]+=carry}}trim(r);return r}function multiplySmall(a,b){var l=a.length,r=new Array(l),base=BASE,carry=0,product,i;for(i=0;i<l;i++){product=a[i]*b+carry;carry=Math.floor(product/base);r[i]=product-carry*base}while(carry>0){r[i++]=carry%base;carry=Math.floor(carry/base)}return r}function shiftLeft(x,n){var r=[];while(n-- >0)r.push(0);return r.concat(x)}function multiplyKaratsuba(x,y){var n=Math.max(x.length,y.length);if(n<=30)return multiplyLong(x,y);n=Math.ceil(n/2);var b=x.slice(n),a=x.slice(0,n),d=y.slice(n),c=y.slice(0,n);var ac=multiplyKaratsuba(a,c),bd=multiplyKaratsuba(b,d),abcd=multiplyKaratsuba(addAny(a,b),addAny(c,d));var product=addAny(addAny(ac,shiftLeft(subtract(subtract(abcd,ac),bd),n)),shiftLeft(bd,2*n));trim(product);return product}function useKaratsuba(l1,l2){return-.012*l1-.012*l2+15e-6*l1*l2>0}BigInteger.prototype.multiply=function(v){var n=parseValue(v),a=this.value,b=n.value,sign=this.sign!==n.sign,abs;if(n.isSmall){if(b===0)return Integer[0];if(b===1)return this;if(b===-1)return this.negate();abs=Math.abs(b);if(abs<BASE){return new BigInteger(multiplySmall(a,abs),sign)}b=smallToArray(abs)}if(useKaratsuba(a.length,b.length))return new BigInteger(multiplyKaratsuba(a,b),sign);return new BigInteger(multiplyLong(a,b),sign)};BigInteger.prototype.times=BigInteger.prototype.multiply;function multiplySmallAndArray(a,b,sign){if(a<BASE){return new BigInteger(multiplySmall(b,a),sign)}return new BigInteger(multiplyLong(b,smallToArray(a)),sign)}SmallInteger.prototype._multiplyBySmall=function(a){if(isPrecise(a.value*this.value)){return new SmallInteger(a.value*this.value)}return multiplySmallAndArray(Math.abs(a.value),smallToArray(Math.abs(this.value)),this.sign!==a.sign)};BigInteger.prototype._multiplyBySmall=function(a){if(a.value===0)return Integer[0];if(a.value===1)return this;if(a.value===-1)return this.negate();return multiplySmallAndArray(Math.abs(a.value),this.value,this.sign!==a.sign)};SmallInteger.prototype.multiply=function(v){return parseValue(v)._multiplyBySmall(this)};SmallInteger.prototype.times=SmallInteger.prototype.multiply;NativeBigInt.prototype.multiply=function(v){return new NativeBigInt(this.value*parseValue(v).value)};NativeBigInt.prototype.times=NativeBigInt.prototype.multiply;function square(a){var l=a.length,r=createArray(l+l),base=BASE,product,carry,i,a_i,a_j;for(i=0;i<l;i++){a_i=a[i];carry=0-a_i*a_i;for(var j=i;j<l;j++){a_j=a[j];product=2*(a_i*a_j)+r[i+j]+carry;carry=Math.floor(product/base);r[i+j]=product-carry*base}r[i+l]=carry}trim(r);return r}BigInteger.prototype.square=function(){return new BigInteger(square(this.value),false)};SmallInteger.prototype.square=function(){var value=this.value*this.value;if(isPrecise(value))return new SmallInteger(value);return new BigInteger(square(smallToArray(Math.abs(this.value))),false)};NativeBigInt.prototype.square=function(v){return new NativeBigInt(this.value*this.value)};function divMod1(a,b){var a_l=a.length,b_l=b.length,base=BASE,result=createArray(b.length),divisorMostSignificantDigit=b[b_l-1],lambda=Math.ceil(base/(2*divisorMostSignificantDigit)),remainder=multiplySmall(a,lambda),divisor=multiplySmall(b,lambda),quotientDigit,shift,carry,borrow,i,l,q;if(remainder.length<=a_l)remainder.push(0);divisor.push(0);divisorMostSignificantDigit=divisor[b_l-1];for(shift=a_l-b_l;shift>=0;shift--){quotientDigit=base-1;if(remainder[shift+b_l]!==divisorMostSignificantDigit){quotientDigit=Math.floor((remainder[shift+b_l]*base+remainder[shift+b_l-1])/divisorMostSignificantDigit)}carry=0;borrow=0;l=divisor.length;for(i=0;i<l;i++){carry+=quotientDigit*divisor[i];q=Math.floor(carry/base);borrow+=remainder[shift+i]-(carry-q*base);carry=q;if(borrow<0){remainder[shift+i]=borrow+base;borrow=-1}else{remainder[shift+i]=borrow;borrow=0}}while(borrow!==0){quotientDigit-=1;carry=0;for(i=0;i<l;i++){carry+=remainder[shift+i]-base+divisor[i];if(carry<0){remainder[shift+i]=carry+base;carry=0}else{remainder[shift+i]=carry;carry=1}}borrow+=carry}result[shift]=quotientDigit}remainder=divModSmall(remainder,lambda)[0];return[arrayToSmall(result),arrayToSmall(remainder)]}function divMod2(a,b){var a_l=a.length,b_l=b.length,result=[],part=[],base=BASE,guess,xlen,highx,highy,check;while(a_l){part.unshift(a[--a_l]);trim(part);if(compareAbs(part,b)<0){result.push(0);continue}xlen=part.length;highx=part[xlen-1]*base+part[xlen-2];highy=b[b_l-1]*base+b[b_l-2];if(xlen>b_l){highx=(highx+1)*base}guess=Math.ceil(highx/highy);do{check=multiplySmall(b,guess);if(compareAbs(check,part)<=0)break;guess--}while(guess);result.push(guess);part=subtract(part,check)}result.reverse();return[arrayToSmall(result),arrayToSmall(part)]}function divModSmall(value,lambda){var length=value.length,quotient=createArray(length),base=BASE,i,q,remainder,divisor;remainder=0;for(i=length-1;i>=0;--i){divisor=remainder*base+value[i];q=truncate(divisor/lambda);remainder=divisor-q*lambda;quotient[i]=q|0}return[quotient,remainder|0]}function divModAny(self,v){var value,n=parseValue(v);if(supportsNativeBigInt){return[new NativeBigInt(self.value/n.value),new NativeBigInt(self.value%n.value)]}var a=self.value,b=n.value;var quotient;if(b===0)throw new Error("Cannot divide by zero");if(self.isSmall){if(n.isSmall){return[new SmallInteger(truncate(a/b)),new SmallInteger(a%b)]}return[Integer[0],self]}if(n.isSmall){if(b===1)return[self,Integer[0]];if(b==-1)return[self.negate(),Integer[0]];var abs=Math.abs(b);if(abs<BASE){value=divModSmall(a,abs);quotient=arrayToSmall(value[0]);var remainder=value[1];if(self.sign)remainder=-remainder;if(typeof quotient==="number"){if(self.sign!==n.sign)quotient=-quotient;return[new SmallInteger(quotient),new SmallInteger(remainder)]}return[new BigInteger(quotient,self.sign!==n.sign),new SmallInteger(remainder)]}b=smallToArray(abs)}var comparison=compareAbs(a,b);if(comparison===-1)return[Integer[0],self];if(comparison===0)return[Integer[self.sign===n.sign?1:-1],Integer[0]];if(a.length+b.length<=200)value=divMod1(a,b);else value=divMod2(a,b);quotient=value[0];var qSign=self.sign!==n.sign,mod=value[1],mSign=self.sign;if(typeof quotient==="number"){if(qSign)quotient=-quotient;quotient=new SmallInteger(quotient)}else quotient=new BigInteger(quotient,qSign);if(typeof mod==="number"){if(mSign)mod=-mod;mod=new SmallInteger(mod)}else mod=new BigInteger(mod,mSign);return[quotient,mod]}BigInteger.prototype.divmod=function(v){var result=divModAny(this,v);return{quotient:result[0],remainder:result[1]}};NativeBigInt.prototype.divmod=SmallInteger.prototype.divmod=BigInteger.prototype.divmod;BigInteger.prototype.divide=function(v){return divModAny(this,v)[0]};NativeBigInt.prototype.over=NativeBigInt.prototype.divide=SmallInteger.prototype.over=SmallInteger.prototype.divide=BigInteger.prototype.over=BigInteger.prototype.divide;BigInteger.prototype.mod=function(v){return divModAny(this,v)[1]};NativeBigInt.prototype.mod=NativeBigInt.prototype.remainder=SmallInteger.prototype.remainder=SmallInteger.prototype.mod=BigInteger.prototype.remainder=BigInteger.prototype.mod;BigInteger.prototype.pow=function(v){var n=parseValue(v),a=this.value,b=n.value,value,x,y;if(b===0)return Integer[1];if(a===0)return Integer[0];if(a===1)return Integer[1];if(a===-1)return n.isEven()?Integer[1]:Integer[-1];if(n.sign){return Integer[0]}if(!n.isSmall)throw new Error("The exponent "+n.toString()+" is too large.");if(this.isSmall){if(isPrecise(value=Math.pow(a,b)))return new SmallInteger(truncate(value))}x=this;y=Integer[1];while(true){if(b&1===1){y=y.times(x);--b}if(b===0)break;b/=2;x=x.square()}return y};SmallInteger.prototype.pow=BigInteger.prototype.pow;var pow;if(supportsNativeBigInt){pow=eval("(a,b)=>a**b")}NativeBigInt.prototype.pow=function(v){var n=parseValue(v);var a=this.value,b=n.value;if(b===BigInt(0))return Integer[1];if(a===BigInt(0))return Integer[0];if(a===BigInt(1))return Integer[1];if(a===BigInt(-1))return n.isEven()?Integer[1]:Integer[-1];if(n.isNegative())return new NativeBigInt(BigInt(0));return new NativeBigInt(pow(a,b))};BigInteger.prototype.modPow=function(exp,mod){exp=parseValue(exp);mod=parseValue(mod);if(mod.isZero())throw new Error("Cannot take modPow with modulus 0");var r=Integer[1],base=this.mod(mod);while(exp.isPositive()){if(base.isZero())return Integer[0];if(exp.isOdd())r=r.multiply(base).mod(mod);exp=exp.divide(2);base=base.square().mod(mod)}return r};NativeBigInt.prototype.modPow=SmallInteger.prototype.modPow=BigInteger.prototype.modPow;function compareAbs(a,b){if(a.length!==b.length){return a.length>b.length?1:-1}for(var i=a.length-1;i>=0;i--){if(a[i]!==b[i])return a[i]>b[i]?1:-1}return 0}BigInteger.prototype.compareAbs=function(v){var n=parseValue(v),a=this.value,b=n.value;if(n.isSmall)return 1;return compareAbs(a,b)};SmallInteger.prototype.compareAbs=function(v){var n=parseValue(v),a=Math.abs(this.value),b=n.value;if(n.isSmall){b=Math.abs(b);return a===b?0:a>b?1:-1}return-1};NativeBigInt.prototype.compareAbs=function(v){var a=this.value;var b=parseValue(v).value;a=a>=0?a:-a;b=b>=0?b:-b;return a===b?0:a>b?1:-1};BigInteger.prototype.compare=function(v){if(v===Infinity){return-1}if(v===-Infinity){return 1}var n=parseValue(v),a=this.value,b=n.value;if(this.sign!==n.sign){return n.sign?1:-1}if(n.isSmall){return this.sign?-1:1}return compareAbs(a,b)*(this.sign?-1:1)};BigInteger.prototype.compareTo=BigInteger.prototype.compare;SmallInteger.prototype.compare=function(v){if(v===Infinity){return-1}if(v===-Infinity){return 1}var n=parseValue(v),a=this.value,b=n.value;if(n.isSmall){return a==b?0:a>b?1:-1}if(a<0!==n.sign){return a<0?-1:1}return a<0?1:-1};SmallInteger.prototype.compareTo=SmallInteger.prototype.compare;NativeBigInt.prototype.compare=function(v){if(v===Infinity){return-1}if(v===-Infinity){return 1}var a=this.value;var b=parseValue(v).value;return a===b?0:a>b?1:-1};NativeBigInt.prototype.compareTo=NativeBigInt.prototype.compare;BigInteger.prototype.equals=function(v){return this.compare(v)===0};NativeBigInt.prototype.eq=NativeBigInt.prototype.equals=SmallInteger.prototype.eq=SmallInteger.prototype.equals=BigInteger.prototype.eq=BigInteger.prototype.equals;BigInteger.prototype.notEquals=function(v){return this.compare(v)!==0};NativeBigInt.prototype.neq=NativeBigInt.prototype.notEquals=SmallInteger.prototype.neq=SmallInteger.prototype.notEquals=BigInteger.prototype.neq=BigInteger.prototype.notEquals;BigInteger.prototype.greater=function(v){return this.compare(v)>0};NativeBigInt.prototype.gt=NativeBigInt.prototype.greater=SmallInteger.prototype.gt=SmallInteger.prototype.greater=BigInteger.prototype.gt=BigInteger.prototype.greater;BigInteger.prototype.lesser=function(v){return this.compare(v)<0};NativeBigInt.prototype.lt=NativeBigInt.prototype.lesser=SmallInteger.prototype.lt=SmallInteger.prototype.lesser=BigInteger.prototype.lt=BigInteger.prototype.lesser;BigInteger.prototype.greaterOrEquals=function(v){return this.compare(v)>=0};NativeBigInt.prototype.geq=NativeBigInt.prototype.greaterOrEquals=SmallInteger.prototype.geq=SmallInteger.prototype.greaterOrEquals=BigInteger.prototype.geq=BigInteger.prototype.greaterOrEquals;BigInteger.prototype.lesserOrEquals=function(v){return this.compare(v)<=0};NativeBigInt.prototype.leq=NativeBigInt.prototype.lesserOrEquals=SmallInteger.prototype.leq=SmallInteger.prototype.lesserOrEquals=BigInteger.prototype.leq=BigInteger.prototype.lesserOrEquals;BigInteger.prototype.isEven=function(){return(this.value[0]&1)===0};SmallInteger.prototype.isEven=function(){return(this.value&1)===0};NativeBigInt.prototype.isEven=function(){return(this.value&BigInt(1))===BigInt(0)};BigInteger.prototype.isOdd=function(){return(this.value[0]&1)===1};SmallInteger.prototype.isOdd=function(){return(this.value&1)===1};NativeBigInt.prototype.isOdd=function(){return(this.value&BigInt(1))===BigInt(1)};BigInteger.prototype.isPositive=function(){return!this.sign};SmallInteger.prototype.isPositive=function(){return this.value>0};NativeBigInt.prototype.isPositive=SmallInteger.prototype.isPositive;BigInteger.prototype.isNegative=function(){return this.sign};SmallInteger.prototype.isNegative=function(){return this.value<0};NativeBigInt.prototype.isNegative=SmallInteger.prototype.isNegative;BigInteger.prototype.isUnit=function(){return false};SmallInteger.prototype.isUnit=function(){return Math.abs(this.value)===1};NativeBigInt.prototype.isUnit=function(){return this.abs().value===BigInt(1)};BigInteger.prototype.isZero=function(){return false};SmallInteger.prototype.isZero=function(){return this.value===0};NativeBigInt.prototype.isZero=function(){return this.value===BigInt(0)};BigInteger.prototype.isDivisibleBy=function(v){var n=parseValue(v);if(n.isZero())return false;if(n.isUnit())return true;if(n.compareAbs(2)===0)return this.isEven();return this.mod(n).isZero()};NativeBigInt.prototype.isDivisibleBy=SmallInteger.prototype.isDivisibleBy=BigInteger.prototype.isDivisibleBy;function isBasicPrime(v){var n=v.abs();if(n.isUnit())return false;if(n.equals(2)||n.equals(3)||n.equals(5))return true;if(n.isEven()||n.isDivisibleBy(3)||n.isDivisibleBy(5))return false;if(n.lesser(49))return true}function millerRabinTest(n,a){var nPrev=n.prev(),b=nPrev,r=0,d,t,i,x;while(b.isEven())b=b.divide(2),r++;next:for(i=0;i<a.length;i++){if(n.lesser(a[i]))continue;x=bigInt(a[i]).modPow(b,n);if(x.isUnit()||x.equals(nPrev))continue;for(d=r-1;d!=0;d--){x=x.square().mod(n);if(x.isUnit())return false;if(x.equals(nPrev))continue next}return false}return true}BigInteger.prototype.isPrime=function(strict){var isPrime=isBasicPrime(this);if(isPrime!==undefined)return isPrime;var n=this.abs();var bits=n.bitLength();if(bits<=64)return millerRabinTest(n,[2,325,9375,28178,450775,9780504,1795265022]);var logN=Math.log(2)*bits.toJSNumber();var t=Math.ceil(strict===true?2*Math.pow(logN,2):logN);for(var a=[],i=0;i<t;i++){a.push(bigInt(i+2))}return millerRabinTest(n,a)};NativeBigInt.prototype.isPrime=SmallInteger.prototype.isPrime=BigInteger.prototype.isPrime;BigInteger.prototype.isProbablePrime=function(iterations){var isPrime=isBasicPrime(this);if(isPrime!==undefined)return isPrime;var n=this.abs();var t=iterations===undefined?5:iterations;for(var a=[],i=0;i<t;i++){a.push(bigInt.randBetween(2,n.minus(2)))}return millerRabinTest(n,a)};NativeBigInt.prototype.isProbablePrime=SmallInteger.prototype.isProbablePrime=BigInteger.prototype.isProbablePrime;BigInteger.prototype.modInv=function(n){var t=bigInt.zero,newT=bigInt.one,r=parseValue(n),newR=this.abs(),q,lastT,lastR;while(!newR.isZero()){q=r.divide(newR);lastT=t;lastR=r;t=newT;r=newR;newT=lastT.subtract(q.multiply(newT));newR=lastR.subtract(q.multiply(newR))}if(!r.isUnit())throw new Error(this.toString()+" and "+n.toString()+" are not co-prime");if(t.compare(0)===-1){t=t.add(n)}if(this.isNegative()){return t.negate()}return t};NativeBigInt.prototype.modInv=SmallInteger.prototype.modInv=BigInteger.prototype.modInv;BigInteger.prototype.next=function(){var value=this.value;if(this.sign){return subtractSmall(value,1,this.sign)}return new BigInteger(addSmall(value,1),this.sign)};SmallInteger.prototype.next=function(){var value=this.value;if(value+1<MAX_INT)return new SmallInteger(value+1);return new BigInteger(MAX_INT_ARR,false)};NativeBigInt.prototype.next=function(){return new NativeBigInt(this.value+BigInt(1))};BigInteger.prototype.prev=function(){var value=this.value;if(this.sign){return new BigInteger(addSmall(value,1),true)}return subtractSmall(value,1,this.sign)};SmallInteger.prototype.prev=function(){var value=this.value;if(value-1>-MAX_INT)return new SmallInteger(value-1);return new BigInteger(MAX_INT_ARR,true)};NativeBigInt.prototype.prev=function(){return new NativeBigInt(this.value-BigInt(1))};var powersOfTwo=[1];while(2*powersOfTwo[powersOfTwo.length-1]<=BASE)powersOfTwo.push(2*powersOfTwo[powersOfTwo.length-1]);var powers2Length=powersOfTwo.length,highestPower2=powersOfTwo[powers2Length-1];function shift_isSmall(n){return Math.abs(n)<=BASE}BigInteger.prototype.shiftLeft=function(v){var n=parseValue(v).toJSNumber();if(!shift_isSmall(n)){throw new Error(String(n)+" is too large for shifting.")}if(n<0)return this.shiftRight(-n);var result=this;if(result.isZero())return result;while(n>=powers2Length){result=result.multiply(highestPower2);n-=powers2Length-1}return result.multiply(powersOfTwo[n])};NativeBigInt.prototype.shiftLeft=SmallInteger.prototype.shiftLeft=BigInteger.prototype.shiftLeft;BigInteger.prototype.shiftRight=function(v){var remQuo;var n=parseValue(v).toJSNumber();if(!shift_isSmall(n)){throw new Error(String(n)+" is too large for shifting.")}if(n<0)return this.shiftLeft(-n);var result=this;while(n>=powers2Length){if(result.isZero()||result.isNegative()&&result.isUnit())return result;remQuo=divModAny(result,highestPower2);result=remQuo[1].isNegative()?remQuo[0].prev():remQuo[0];n-=powers2Length-1}remQuo=divModAny(result,powersOfTwo[n]);return remQuo[1].isNegative()?remQuo[0].prev():remQuo[0]};NativeBigInt.prototype.shiftRight=SmallInteger.prototype.shiftRight=BigInteger.prototype.shiftRight;function bitwise(x,y,fn){y=parseValue(y);var xSign=x.isNegative(),ySign=y.isNegative();var xRem=xSign?x.not():x,yRem=ySign?y.not():y;var xDigit=0,yDigit=0;var xDivMod=null,yDivMod=null;var result=[];while(!xRem.isZero()||!yRem.isZero()){xDivMod=divModAny(xRem,highestPower2);xDigit=xDivMod[1].toJSNumber();if(xSign){xDigit=highestPower2-1-xDigit}yDivMod=divModAny(yRem,highestPower2);yDigit=yDivMod[1].toJSNumber();if(ySign){yDigit=highestPower2-1-yDigit}xRem=xDivMod[0];yRem=yDivMod[0];result.push(fn(xDigit,yDigit))}var sum=fn(xSign?1:0,ySign?1:0)!==0?bigInt(-1):bigInt(0);for(var i=result.length-1;i>=0;i-=1){sum=sum.multiply(highestPower2).add(bigInt(result[i]))}return sum}BigInteger.prototype.not=function(){return this.negate().prev()};NativeBigInt.prototype.not=SmallInteger.prototype.not=BigInteger.prototype.not;BigInteger.prototype.and=function(n){return bitwise(this,n,function(a,b){return a&b})};NativeBigInt.prototype.and=SmallInteger.prototype.and=BigInteger.prototype.and;BigInteger.prototype.or=function(n){return bitwise(this,n,function(a,b){return a|b})};NativeBigInt.prototype.or=SmallInteger.prototype.or=BigInteger.prototype.or;BigInteger.prototype.xor=function(n){return bitwise(this,n,function(a,b){return a^b})};NativeBigInt.prototype.xor=SmallInteger.prototype.xor=BigInteger.prototype.xor;var LOBMASK_I=1<<30,LOBMASK_BI=(BASE&-BASE)*(BASE&-BASE)|LOBMASK_I;function roughLOB(n){var v=n.value,x=typeof v==="number"?v|LOBMASK_I:typeof v==="bigint"?v|BigInt(LOBMASK_I):v[0]+v[1]*BASE|LOBMASK_BI;return x&-x}function integerLogarithm(value,base){if(base.compareTo(value)<=0){var tmp=integerLogarithm(value,base.square(base));var p=tmp.p;var e=tmp.e;var t=p.multiply(base);return t.compareTo(value)<=0?{p:t,e:e*2+1}:{p:p,e:e*2}}return{p:bigInt(1),e:0}}BigInteger.prototype.bitLength=function(){var n=this;if(n.compareTo(bigInt(0))<0){n=n.negate().subtract(bigInt(1))}if(n.compareTo(bigInt(0))===0){return bigInt(0)}return bigInt(integerLogarithm(n,bigInt(2)).e).add(bigInt(1))};NativeBigInt.prototype.bitLength=SmallInteger.prototype.bitLength=BigInteger.prototype.bitLength;function max(a,b){a=parseValue(a);b=parseValue(b);return a.greater(b)?a:b}function min(a,b){a=parseValue(a);b=parseValue(b);return a.lesser(b)?a:b}function gcd(a,b){a=parseValue(a).abs();b=parseValue(b).abs();if(a.equals(b))return a;if(a.isZero())return b;if(b.isZero())return a;var c=Integer[1],d,t;while(a.isEven()&&b.isEven()){d=min(roughLOB(a),roughLOB(b));a=a.divide(d);b=b.divide(d);c=c.multiply(d)}while(a.isEven()){a=a.divide(roughLOB(a))}do{while(b.isEven()){b=b.divide(roughLOB(b))}if(a.greater(b)){t=b;b=a;a=t}b=b.subtract(a)}while(!b.isZero());return c.isUnit()?a:a.multiply(c)}function lcm(a,b){a=parseValue(a).abs();b=parseValue(b).abs();return a.divide(gcd(a,b)).multiply(b)}function randBetween(a,b){a=parseValue(a);b=parseValue(b);var low=min(a,b),high=max(a,b);var range=high.subtract(low).add(1);if(range.isSmall)return low.add(Math.floor(Math.random()*range));var digits=toBase(range,BASE).value;var result=[],restricted=true;for(var i=0;i<digits.length;i++){var top=restricted?digits[i]:BASE;var digit=truncate(Math.random()*top);result.push(digit);if(digit<top)restricted=false}return low.add(Integer.fromArray(result,BASE,false))}var parseBase=function(text,base,alphabet,caseSensitive){alphabet=alphabet||DEFAULT_ALPHABET;text=String(text);if(!caseSensitive){text=text.toLowerCase();alphabet=alphabet.toLowerCase()}var length=text.length;var i;var absBase=Math.abs(base);var alphabetValues={};for(i=0;i<alphabet.length;i++){alphabetValues[alphabet[i]]=i}for(i=0;i<length;i++){var c=text[i];if(c==="-")continue;if(c in alphabetValues){if(alphabetValues[c]>=absBase){if(c==="1"&&absBase===1)continue;throw new Error(c+" is not a valid digit in base "+base+".")}}}base=parseValue(base);var digits=[];var isNegative=text[0]==="-";for(i=isNegative?1:0;i<text.length;i++){var c=text[i];if(c in alphabetValues)digits.push(parseValue(alphabetValues[c]));else if(c==="<"){var start=i;do{i++}while(text[i]!==">"&&i<text.length);digits.push(parseValue(text.slice(start+1,i)))}else throw new Error(c+" is not a valid character")}return parseBaseFromArray(digits,base,isNegative)};function parseBaseFromArray(digits,base,isNegative){var val=Integer[0],pow=Integer[1],i;for(i=digits.length-1;i>=0;i--){val=val.add(digits[i].times(pow));pow=pow.times(base)}return isNegative?val.negate():val}function stringify(digit,alphabet){alphabet=alphabet||DEFAULT_ALPHABET;if(digit<alphabet.length){return alphabet[digit]}return"<"+digit+">"}function toBase(n,base){base=bigInt(base);if(base.isZero()){if(n.isZero())return{value:[0],isNegative:false};throw new Error("Cannot convert nonzero numbers to base 0.")}if(base.equals(-1)){if(n.isZero())return{value:[0],isNegative:false};if(n.isNegative())return{value:[].concat.apply([],Array.apply(null,Array(-n.toJSNumber())).map(Array.prototype.valueOf,[1,0])),isNegative:false};var arr=Array.apply(null,Array(n.toJSNumber()-1)).map(Array.prototype.valueOf,[0,1]);arr.unshift([1]);return{value:[].concat.apply([],arr),isNegative:false}}var neg=false;if(n.isNegative()&&base.isPositive()){neg=true;n=n.abs()}if(base.isUnit()){if(n.isZero())return{value:[0],isNegative:false};return{value:Array.apply(null,Array(n.toJSNumber())).map(Number.prototype.valueOf,1),isNegative:neg}}var out=[];var left=n,divmod;while(left.isNegative()||left.compareAbs(base)>=0){divmod=left.divmod(base);left=divmod.quotient;var digit=divmod.remainder;if(digit.isNegative()){digit=base.minus(digit).abs();left=left.next()}out.push(digit.toJSNumber())}out.push(left.toJSNumber());return{value:out.reverse(),isNegative:neg}}function toBaseString(n,base,alphabet){var arr=toBase(n,base);return(arr.isNegative?"-":"")+arr.value.map(function(x){return stringify(x,alphabet)}).join("")}BigInteger.prototype.toArray=function(radix){return toBase(this,radix)};SmallInteger.prototype.toArray=function(radix){return toBase(this,radix)};NativeBigInt.prototype.toArray=function(radix){return toBase(this,radix)};BigInteger.prototype.toString=function(radix,alphabet){if(radix===undefined)radix=10;if(radix!==10)return toBaseString(this,radix,alphabet);var v=this.value,l=v.length,str=String(v[--l]),zeros="0000000",digit;while(--l>=0){digit=String(v[l]);str+=zeros.slice(digit.length)+digit}var sign=this.sign?"-":"";return sign+str};SmallInteger.prototype.toString=function(radix,alphabet){if(radix===undefined)radix=10;if(radix!=10)return toBaseString(this,radix,alphabet);return String(this.value)};NativeBigInt.prototype.toString=SmallInteger.prototype.toString;NativeBigInt.prototype.toJSON=BigInteger.prototype.toJSON=SmallInteger.prototype.toJSON=function(){return this.toString()};BigInteger.prototype.valueOf=function(){return parseInt(this.toString(),10)};BigInteger.prototype.toJSNumber=BigInteger.prototype.valueOf;SmallInteger.prototype.valueOf=function(){return this.value};SmallInteger.prototype.toJSNumber=SmallInteger.prototype.valueOf;NativeBigInt.prototype.valueOf=NativeBigInt.prototype.toJSNumber=function(){return parseInt(this.toString(),10)};function parseStringValue(v){if(isPrecise(+v)){var x=+v;if(x===truncate(x))return supportsNativeBigInt?new NativeBigInt(BigInt(x)):new SmallInteger(x);throw new Error("Invalid integer: "+v)}var sign=v[0]==="-";if(sign)v=v.slice(1);var split=v.split(/e/i);if(split.length>2)throw new Error("Invalid integer: "+split.join("e"));if(split.length===2){var exp=split[1];if(exp[0]==="+")exp=exp.slice(1);exp=+exp;if(exp!==truncate(exp)||!isPrecise(exp))throw new Error("Invalid integer: "+exp+" is not a valid exponent.");var text=split[0];var decimalPlace=text.indexOf(".");if(decimalPlace>=0){exp-=text.length-decimalPlace-1;text=text.slice(0,decimalPlace)+text.slice(decimalPlace+1)}if(exp<0)throw new Error("Cannot include negative exponent part for integers");text+=new Array(exp+1).join("0");v=text}var isValid=/^([0-9][0-9]*)$/.test(v);if(!isValid)throw new Error("Invalid integer: "+v);if(supportsNativeBigInt){return new NativeBigInt(BigInt(sign?"-"+v:v))}var r=[],max=v.length,l=LOG_BASE,min=max-l;while(max>0){r.push(+v.slice(min,max));min-=l;if(min<0)min=0;max-=l}trim(r);return new BigInteger(r,sign)}function parseNumberValue(v){if(supportsNativeBigInt){return new NativeBigInt(BigInt(v))}if(isPrecise(v)){if(v!==truncate(v))throw new Error(v+" is not an integer.");return new SmallInteger(v)}return parseStringValue(v.toString())}function parseValue(v){if(typeof v==="number"){return parseNumberValue(v)}if(typeof v==="string"){return parseStringValue(v)}if(typeof v==="bigint"){return new NativeBigInt(v)}return v}for(var i=0;i<1e3;i++){Integer[i]=parseValue(i);if(i>0)Integer[-i]=parseValue(-i)}Integer.one=Integer[1];Integer.zero=Integer[0];Integer.minusOne=Integer[-1];Integer.max=max;Integer.min=min;Integer.gcd=gcd;Integer.lcm=lcm;Integer.isInstance=function(x){return x instanceof BigInteger||x instanceof SmallInteger||x instanceof NativeBigInt};Integer.randBetween=randBetween;Integer.fromArray=function(digits,base,isNegative){return parseBaseFromArray(digits.map(parseValue),parseValue(base||10),isNegative)};return Integer}();if(typeof module!=="undefined"&&module.hasOwnProperty("exports")){module.exports=bigInt}if(typeof define==="function"&&define.amd){define("big-integer",[],function(){return bigInt})}var bigRat=function(bigInt){"use strict";function BigRational(num,denom){if(denom.isZero())throw"Denominator cannot be 0.";this.numerator=this.num=num;this.denominator=this.denom=denom}var gcd=bigInt.gcd,lcm=bigInt.lcm;function reduce(n,d){var divisor=gcd(n,d),num=n.over(divisor),denom=d.over(divisor);if(denom.isNegative()){return new BigRational(num.negate(),denom.negate())}return new BigRational(num,denom)}BigRational.prototype.add=function(n,d){var v=interpret(n,d),multiple=lcm(this.denom,v.denom),a=multiple.divide(this.denom),b=multiple.divide(v.denom);a=this.num.times(a);b=v.num.times(b);return reduce(a.add(b),multiple)};BigRational.prototype.plus=BigRational.prototype.add;BigRational.prototype.subtract=function(n,d){var v=interpret(n,d);return this.add(v.negate())};BigRational.prototype.minus=BigRational.prototype.subtract;BigRational.prototype.multiply=function(n,d){var v=interpret(n,d);return reduce(this.num.times(v.num),this.denom.times(v.denom))};BigRational.prototype.times=BigRational.prototype.multiply;BigRational.prototype.divide=function(n,d){var v=interpret(n,d);return reduce(this.num.times(v.denom),this.denom.times(v.num))};BigRational.prototype.over=BigRational.prototype.divide;BigRational.prototype.reciprocate=function(){return new BigRational(this.denom,this.num)};BigRational.prototype.mod=function(n,d){var v=interpret(n,d);return this.minus(v.times(this.over(v).floor()))};BigRational.prototype.pow=function(n){var v=bigInt(n);var num=this.num.pow(v),denom=this.denom.pow(v);return reduce(num,denom)};BigRational.prototype.floor=function(toBigInt){var divmod=this.num.divmod(this.denom),floor;if(divmod.remainder.isZero()||!divmod.quotient.isNegative()){floor=divmod.quotient}else floor=divmod.quotient.prev();if(toBigInt)return floor;return new BigRational(floor,bigInt[1])};BigRational.prototype.ceil=function(toBigInt){var divmod=this.num.divmod(this.denom),ceil;if(divmod.remainder.isZero()||divmod.quotient.isNegative()){ceil=divmod.quotient}else ceil=divmod.quotient.next();if(toBigInt)return ceil;return new BigRational(ceil,bigInt[1])};BigRational.prototype.round=function(toBigInt){return this.add(1,2).floor(toBigInt)};BigRational.prototype.compareAbs=function(n,d){var v=interpret(n,d);if(this.denom.equals(v.denom)){return this.num.compareAbs(v.num)}return this.num.times(v.denom).compareAbs(v.num.times(this.denom))};BigRational.prototype.compare=function(n,d){var v=interpret(n,d);if(this.denom.equals(v.denom)){return this.num.compare(v.num)}var comparison=this.denom.isNegative()===v.denom.isNegative()?1:-1;return comparison*this.num.times(v.denom).compare(v.num.times(this.denom))};BigRational.prototype.compareTo=BigRational.prototype.compare;BigRational.prototype.equals=function(n,d){return this.compare(n,d)===0};BigRational.prototype.eq=BigRational.prototype.equals;BigRational.prototype.notEquals=function(n,d){return this.compare(n,d)!==0};BigRational.prototype.neq=BigRational.prototype.notEquals;BigRational.prototype.lesser=function(n,d){return this.compare(n,d)<0};BigRational.prototype.lt=BigRational.prototype.lesser;BigRational.prototype.lesserOrEquals=function(n,d){return this.compare(n,d)<=0};BigRational.prototype.leq=BigRational.prototype.lesserOrEquals;BigRational.prototype.greater=function(n,d){return this.compare(n,d)>0};BigRational.prototype.gt=BigRational.prototype.greater;BigRational.prototype.greaterOrEquals=function(n,d){return this.compare(n,d)>=0};BigRational.prototype.geq=BigRational.prototype.greaterOrEquals;BigRational.prototype.abs=function(){if(this.isPositive())return this;return this.negate()};BigRational.prototype.negate=function(){if(this.denom.isNegative()){return new BigRational(this.num,this.denom.negate())}return new BigRational(this.num.negate(),this.denom)};BigRational.prototype.isNegative=function(){return this.num.isNegative()!==this.denom.isNegative()&&!this.num.isZero()};BigRational.prototype.isPositive=function(){return this.num.isNegative()===this.denom.isNegative()&&!this.num.isZero()};BigRational.prototype.isZero=function(){return this.num.isZero()};BigRational.prototype.toDecimal=function(digits){digits=typeof digits==="number"?digits:10;var n=this.num.divmod(this.denom);var intPart=n.quotient.abs().toString();var remainder=parse(n.remainder.abs(),this.denom);var shiftedRemainder=remainder.times(bigInt("1e"+digits));var decPart=shiftedRemainder.num.over(shiftedRemainder.denom).toString();if(decPart.length<digits){decPart=new Array(digits-decPart.length+1).join("0")+decPart}if(shiftedRemainder.num.mod(shiftedRemainder.denom).isZero()){while(decPart.slice(-1)==="0"){decPart=decPart.slice(0,-1)}}if(digits<1)decPart="";if(this.isNegative()){intPart="-"+intPart}if(decPart===""){return intPart}return intPart+"."+decPart};BigRational.prototype.toString=function(){return String(this.num)+"/"+String(this.denom)};BigRational.prototype.valueOf=function(){if(!isFinite(+this.num)||!isFinite(+this.denom)){return+this.toDecimal(64)}return this.num/this.denom};function interpret(n,d){return parse(n,d)}function parseDecimal(n){var parts=n.split(/e/i);if(parts.length>2){throw new Error("Invalid input: too many 'e' tokens")}if(parts.length>1){var isPositive=true;if(parts[1][0]==="-"){parts[1]=parts[1].slice(1);isPositive=false}if(parts[1][0]==="+"){parts[1]=parts[1].slice(1)}var significand=parseDecimal(parts[0]);var exponent=new BigRational(bigInt(10).pow(parts[1]),bigInt[1]);if(isPositive){return significand.times(exponent)}else{return significand.over(exponent)}}parts=n.trim().split(".");if(parts.length>2){throw new Error("Invalid input: too many '.' tokens")}if(parts.length>1){var isNegative=parts[0][0]==="-";if(isNegative)parts[0]=parts[0].slice(1);var intPart=new BigRational(bigInt(parts[0]),bigInt[1]);var length=parts[1].length;while(parts[1][0]==="0"){parts[1]=parts[1].slice(1)}var exp="1"+Array(length+1).join("0");var decPart=reduce(bigInt(parts[1]),bigInt(exp));intPart=intPart.add(decPart);if(isNegative)intPart=intPart.negate();return intPart}return new BigRational(bigInt(n),bigInt[1])}function parse(a,b){if(!a){return new BigRational(bigInt(0),bigInt[1])}if(b){return reduce(bigInt(a),bigInt(b))}if(bigInt.isInstance(a)){return new BigRational(a,bigInt[1])}if(a instanceof BigRational)return a;var num;var denom;var text=String(a);var texts=text.split("/");if(texts.length>2){throw new Error("Invalid input: too many '/' tokens")}if(texts.length>1){var parts=texts[0].split("_");if(parts.length>2){throw new Error("Invalid input: too many '_' tokens")}if(parts.length>1){var isPositive=parts[0][0]!=="-";num=bigInt(parts[0]).times(texts[1]);if(isPositive){num=num.add(parts[1])}else{num=num.subtract(parts[1])}denom=bigInt(texts[1]);return reduce(num,denom)}return reduce(bigInt(texts[0]),bigInt(texts[1]))}return parseDecimal(text)}parse.zero=parse(0);parse.one=parse(1);parse.minusOne=parse(-1);return parse}(typeof bigInt!=="undefined"?bigInt:require("big-integer"));if(typeof module!=="undefined"){if(module.hasOwnProperty("exports")){module.exports=bigRat}} |
@@ -1,2 +0,2 @@ | ||
;var bigRat = (function (bigInt) { | ||
; var bigRat = (function (bigInt) { | ||
"use strict"; | ||
@@ -71,3 +71,3 @@ | ||
floor; | ||
if (divmod.remainder.isZero() || !divmod.quotient.sign) { | ||
if (divmod.remainder.isZero() || !divmod.quotient.isNegative()) { | ||
floor = divmod.quotient; | ||
@@ -82,3 +82,3 @@ } | ||
ceil; | ||
if (divmod.remainder.isZero() || divmod.quotient.sign) { | ||
if (divmod.remainder.isZero() || divmod.quotient.isNegative()) { | ||
ceil = divmod.quotient; | ||
@@ -106,3 +106,3 @@ } | ||
} | ||
var comparison = this.denom.sign === v.denom.sign ? 1 : -1; | ||
var comparison = this.denom.isNegative() === v.denom.isNegative() ? 1 : -1; | ||
return comparison * this.num.times(v.denom).compare(v.num.times(this.denom)); | ||
@@ -147,3 +147,3 @@ }; | ||
BigRational.prototype.negate = function () { | ||
if (this.denom.sign) { | ||
if (this.denom.isNegative()) { | ||
return new BigRational(this.num, this.denom.negate()); | ||
@@ -154,6 +154,6 @@ } | ||
BigRational.prototype.isNegative = function () { | ||
return this.num.sign !== this.denom.sign && !this.num.isZero(); | ||
return this.num.isNegative() !== this.denom.isNegative() && !this.num.isZero(); | ||
}; | ||
BigRational.prototype.isPositive = function () { | ||
return this.num.sign === this.denom.sign && !this.num.isZero(); | ||
return this.num.isNegative() === this.denom.isNegative() && !this.num.isZero(); | ||
}; | ||
@@ -179,5 +179,5 @@ BigRational.prototype.isZero = function () { | ||
} | ||
if(digits < 1) decPart = ""; | ||
if (digits < 1) decPart = ""; | ||
if (this.isNegative()) { | ||
intPart = "-"+intPart; | ||
intPart = "-" + intPart; | ||
} | ||
@@ -195,2 +195,5 @@ if (decPart === "") { | ||
BigRational.prototype.valueOf = function () { | ||
if (!isFinite(+this.num) || !isFinite(+this.denom)) { | ||
return +this.toDecimal(64); | ||
} | ||
return this.num / this.denom; | ||
@@ -204,12 +207,12 @@ }; | ||
var parts = n.split(/e/i); | ||
if(parts.length > 2) { | ||
if (parts.length > 2) { | ||
throw new Error("Invalid input: too many 'e' tokens"); | ||
} | ||
if(parts.length > 1) { | ||
if (parts.length > 1) { | ||
var isPositive = true; | ||
if(parts[1][0] === "-") { | ||
if (parts[1][0] === "-") { | ||
parts[1] = parts[1].slice(1); | ||
isPositive = false; | ||
} | ||
if(parts[1][0] === "+") { | ||
if (parts[1][0] === "+") { | ||
parts[1] = parts[1].slice(1); | ||
@@ -219,3 +222,3 @@ } | ||
var exponent = new BigRational(bigInt(10).pow(parts[1]), bigInt[1]); | ||
if(isPositive) { | ||
if (isPositive) { | ||
return significand.times(exponent); | ||
@@ -227,6 +230,6 @@ } else { | ||
parts = n.trim().split("."); | ||
if(parts.length > 2) { | ||
if (parts.length > 2) { | ||
throw new Error("Invalid input: too many '.' tokens"); | ||
} | ||
if(parts.length > 1) { | ||
if (parts.length > 1) { | ||
var isNegative = parts[0][0] === '-'; | ||
@@ -236,3 +239,3 @@ if (isNegative) parts[0] = parts[0].slice(1); | ||
var length = parts[1].length; | ||
while(parts[1][0] === "0") { | ||
while (parts[1][0] === "0") { | ||
parts[1] = parts[1].slice(1); | ||
@@ -249,6 +252,6 @@ } | ||
function parse(a, b) { | ||
if(!a) { | ||
if (!a) { | ||
return new BigRational(bigInt(0), bigInt[1]); | ||
} | ||
if(b) { | ||
if (b) { | ||
return reduce(bigInt(a), bigInt(b)); | ||
@@ -266,14 +269,14 @@ } | ||
var texts = text.split("/"); | ||
if(texts.length > 2) { | ||
if (texts.length > 2) { | ||
throw new Error("Invalid input: too many '/' tokens"); | ||
} | ||
if(texts.length > 1) { | ||
if (texts.length > 1) { | ||
var parts = texts[0].split("_"); | ||
if(parts.length > 2) { | ||
if (parts.length > 2) { | ||
throw new Error("Invalid input: too many '_' tokens"); | ||
} | ||
if(parts.length > 1) { | ||
if (parts.length > 1) { | ||
var isPositive = parts[0][0] !== "-"; | ||
num = bigInt(parts[0]).times(texts[1]); | ||
if(isPositive) { | ||
if (isPositive) { | ||
num = num.add(parts[1]); | ||
@@ -280,0 +283,0 @@ } else { |
@@ -1,1 +0,1 @@ | ||
var bigRat=function(bigInt){"use strict";function BigRational(num,denom){if(denom.isZero())throw"Denominator cannot be 0.";this.numerator=this.num=num;this.denominator=this.denom=denom}var gcd=bigInt.gcd,lcm=bigInt.lcm;function reduce(n,d){var divisor=gcd(n,d),num=n.over(divisor),denom=d.over(divisor);if(denom.isNegative()){return new BigRational(num.negate(),denom.negate())}return new BigRational(num,denom)}BigRational.prototype.add=function(n,d){var v=interpret(n,d),multiple=lcm(this.denom,v.denom),a=multiple.divide(this.denom),b=multiple.divide(v.denom);a=this.num.times(a);b=v.num.times(b);return reduce(a.add(b),multiple)};BigRational.prototype.plus=BigRational.prototype.add;BigRational.prototype.subtract=function(n,d){var v=interpret(n,d);return this.add(v.negate())};BigRational.prototype.minus=BigRational.prototype.subtract;BigRational.prototype.multiply=function(n,d){var v=interpret(n,d);return reduce(this.num.times(v.num),this.denom.times(v.denom))};BigRational.prototype.times=BigRational.prototype.multiply;BigRational.prototype.divide=function(n,d){var v=interpret(n,d);return reduce(this.num.times(v.denom),this.denom.times(v.num))};BigRational.prototype.over=BigRational.prototype.divide;BigRational.prototype.reciprocate=function(){return new BigRational(this.denom,this.num)};BigRational.prototype.mod=function(n,d){var v=interpret(n,d);return this.minus(v.times(this.over(v).floor()))};BigRational.prototype.pow=function(n){var v=bigInt(n);var num=this.num.pow(v),denom=this.denom.pow(v);return reduce(num,denom)};BigRational.prototype.floor=function(toBigInt){var divmod=this.num.divmod(this.denom),floor;if(divmod.remainder.isZero()||!divmod.quotient.sign){floor=divmod.quotient}else floor=divmod.quotient.prev();if(toBigInt)return floor;return new BigRational(floor,bigInt[1])};BigRational.prototype.ceil=function(toBigInt){var divmod=this.num.divmod(this.denom),ceil;if(divmod.remainder.isZero()||divmod.quotient.sign){ceil=divmod.quotient}else ceil=divmod.quotient.next();if(toBigInt)return ceil;return new BigRational(ceil,bigInt[1])};BigRational.prototype.round=function(toBigInt){return this.add(1,2).floor(toBigInt)};BigRational.prototype.compareAbs=function(n,d){var v=interpret(n,d);if(this.denom.equals(v.denom)){return this.num.compareAbs(v.num)}return this.num.times(v.denom).compareAbs(v.num.times(this.denom))};BigRational.prototype.compare=function(n,d){var v=interpret(n,d);if(this.denom.equals(v.denom)){return this.num.compare(v.num)}var comparison=this.denom.sign===v.denom.sign?1:-1;return comparison*this.num.times(v.denom).compare(v.num.times(this.denom))};BigRational.prototype.compareTo=BigRational.prototype.compare;BigRational.prototype.equals=function(n,d){return this.compare(n,d)===0};BigRational.prototype.eq=BigRational.prototype.equals;BigRational.prototype.notEquals=function(n,d){return this.compare(n,d)!==0};BigRational.prototype.neq=BigRational.prototype.notEquals;BigRational.prototype.lesser=function(n,d){return this.compare(n,d)<0};BigRational.prototype.lt=BigRational.prototype.lesser;BigRational.prototype.lesserOrEquals=function(n,d){return this.compare(n,d)<=0};BigRational.prototype.leq=BigRational.prototype.lesserOrEquals;BigRational.prototype.greater=function(n,d){return this.compare(n,d)>0};BigRational.prototype.gt=BigRational.prototype.greater;BigRational.prototype.greaterOrEquals=function(n,d){return this.compare(n,d)>=0};BigRational.prototype.geq=BigRational.prototype.greaterOrEquals;BigRational.prototype.abs=function(){if(this.isPositive())return this;return this.negate()};BigRational.prototype.negate=function(){if(this.denom.sign){return new BigRational(this.num,this.denom.negate())}return new BigRational(this.num.negate(),this.denom)};BigRational.prototype.isNegative=function(){return this.num.sign!==this.denom.sign&&!this.num.isZero()};BigRational.prototype.isPositive=function(){return this.num.sign===this.denom.sign&&!this.num.isZero()};BigRational.prototype.isZero=function(){return this.num.isZero()};BigRational.prototype.toDecimal=function(digits){digits=typeof digits==="number"?digits:10;var n=this.num.divmod(this.denom);var intPart=n.quotient.abs().toString();var remainder=parse(n.remainder.abs(),this.denom);var shiftedRemainder=remainder.times(bigInt("1e"+digits));var decPart=shiftedRemainder.num.over(shiftedRemainder.denom).toString();if(decPart.length<digits){decPart=new Array(digits-decPart.length+1).join("0")+decPart}if(shiftedRemainder.num.mod(shiftedRemainder.denom).isZero()){while(decPart.slice(-1)==="0"){decPart=decPart.slice(0,-1)}}if(digits<1)decPart="";if(this.isNegative()){intPart="-"+intPart}if(decPart===""){return intPart}return intPart+"."+decPart};BigRational.prototype.toString=function(){return String(this.num)+"/"+String(this.denom)};BigRational.prototype.valueOf=function(){return this.num/this.denom};function interpret(n,d){return parse(n,d)}function parseDecimal(n){var parts=n.split(/e/i);if(parts.length>2){throw new Error("Invalid input: too many 'e' tokens")}if(parts.length>1){var isPositive=true;if(parts[1][0]==="-"){parts[1]=parts[1].slice(1);isPositive=false}if(parts[1][0]==="+"){parts[1]=parts[1].slice(1)}var significand=parseDecimal(parts[0]);var exponent=new BigRational(bigInt(10).pow(parts[1]),bigInt[1]);if(isPositive){return significand.times(exponent)}else{return significand.over(exponent)}}parts=n.trim().split(".");if(parts.length>2){throw new Error("Invalid input: too many '.' tokens")}if(parts.length>1){var isNegative=parts[0][0]==="-";if(isNegative)parts[0]=parts[0].slice(1);var intPart=new BigRational(bigInt(parts[0]),bigInt[1]);var length=parts[1].length;while(parts[1][0]==="0"){parts[1]=parts[1].slice(1)}var exp="1"+Array(length+1).join("0");var decPart=reduce(bigInt(parts[1]),bigInt(exp));intPart=intPart.add(decPart);if(isNegative)intPart=intPart.negate();return intPart}return new BigRational(bigInt(n),bigInt[1])}function parse(a,b){if(!a){return new BigRational(bigInt(0),bigInt[1])}if(b){return reduce(bigInt(a),bigInt(b))}if(bigInt.isInstance(a)){return new BigRational(a,bigInt[1])}if(a instanceof BigRational)return a;var num;var denom;var text=String(a);var texts=text.split("/");if(texts.length>2){throw new Error("Invalid input: too many '/' tokens")}if(texts.length>1){var parts=texts[0].split("_");if(parts.length>2){throw new Error("Invalid input: too many '_' tokens")}if(parts.length>1){var isPositive=parts[0][0]!=="-";num=bigInt(parts[0]).times(texts[1]);if(isPositive){num=num.add(parts[1])}else{num=num.subtract(parts[1])}denom=bigInt(texts[1]);return reduce(num,denom)}return reduce(bigInt(texts[0]),bigInt(texts[1]))}return parseDecimal(text)}parse.zero=parse(0);parse.one=parse(1);parse.minusOne=parse(-1);return parse}(typeof bigInt!=="undefined"?bigInt:require("big-integer"));if(typeof module!=="undefined"){if(module.hasOwnProperty("exports")){module.exports=bigRat}} | ||
var bigRat=function(bigInt){"use strict";function BigRational(num,denom){if(denom.isZero())throw"Denominator cannot be 0.";this.numerator=this.num=num;this.denominator=this.denom=denom}var gcd=bigInt.gcd,lcm=bigInt.lcm;function reduce(n,d){var divisor=gcd(n,d),num=n.over(divisor),denom=d.over(divisor);if(denom.isNegative()){return new BigRational(num.negate(),denom.negate())}return new BigRational(num,denom)}BigRational.prototype.add=function(n,d){var v=interpret(n,d),multiple=lcm(this.denom,v.denom),a=multiple.divide(this.denom),b=multiple.divide(v.denom);a=this.num.times(a);b=v.num.times(b);return reduce(a.add(b),multiple)};BigRational.prototype.plus=BigRational.prototype.add;BigRational.prototype.subtract=function(n,d){var v=interpret(n,d);return this.add(v.negate())};BigRational.prototype.minus=BigRational.prototype.subtract;BigRational.prototype.multiply=function(n,d){var v=interpret(n,d);return reduce(this.num.times(v.num),this.denom.times(v.denom))};BigRational.prototype.times=BigRational.prototype.multiply;BigRational.prototype.divide=function(n,d){var v=interpret(n,d);return reduce(this.num.times(v.denom),this.denom.times(v.num))};BigRational.prototype.over=BigRational.prototype.divide;BigRational.prototype.reciprocate=function(){return new BigRational(this.denom,this.num)};BigRational.prototype.mod=function(n,d){var v=interpret(n,d);return this.minus(v.times(this.over(v).floor()))};BigRational.prototype.pow=function(n){var v=bigInt(n);var num=this.num.pow(v),denom=this.denom.pow(v);return reduce(num,denom)};BigRational.prototype.floor=function(toBigInt){var divmod=this.num.divmod(this.denom),floor;if(divmod.remainder.isZero()||!divmod.quotient.isNegative()){floor=divmod.quotient}else floor=divmod.quotient.prev();if(toBigInt)return floor;return new BigRational(floor,bigInt[1])};BigRational.prototype.ceil=function(toBigInt){var divmod=this.num.divmod(this.denom),ceil;if(divmod.remainder.isZero()||divmod.quotient.isNegative()){ceil=divmod.quotient}else ceil=divmod.quotient.next();if(toBigInt)return ceil;return new BigRational(ceil,bigInt[1])};BigRational.prototype.round=function(toBigInt){return this.add(1,2).floor(toBigInt)};BigRational.prototype.compareAbs=function(n,d){var v=interpret(n,d);if(this.denom.equals(v.denom)){return this.num.compareAbs(v.num)}return this.num.times(v.denom).compareAbs(v.num.times(this.denom))};BigRational.prototype.compare=function(n,d){var v=interpret(n,d);if(this.denom.equals(v.denom)){return this.num.compare(v.num)}var comparison=this.denom.isNegative()===v.denom.isNegative()?1:-1;return comparison*this.num.times(v.denom).compare(v.num.times(this.denom))};BigRational.prototype.compareTo=BigRational.prototype.compare;BigRational.prototype.equals=function(n,d){return this.compare(n,d)===0};BigRational.prototype.eq=BigRational.prototype.equals;BigRational.prototype.notEquals=function(n,d){return this.compare(n,d)!==0};BigRational.prototype.neq=BigRational.prototype.notEquals;BigRational.prototype.lesser=function(n,d){return this.compare(n,d)<0};BigRational.prototype.lt=BigRational.prototype.lesser;BigRational.prototype.lesserOrEquals=function(n,d){return this.compare(n,d)<=0};BigRational.prototype.leq=BigRational.prototype.lesserOrEquals;BigRational.prototype.greater=function(n,d){return this.compare(n,d)>0};BigRational.prototype.gt=BigRational.prototype.greater;BigRational.prototype.greaterOrEquals=function(n,d){return this.compare(n,d)>=0};BigRational.prototype.geq=BigRational.prototype.greaterOrEquals;BigRational.prototype.abs=function(){if(this.isPositive())return this;return this.negate()};BigRational.prototype.negate=function(){if(this.denom.isNegative()){return new BigRational(this.num,this.denom.negate())}return new BigRational(this.num.negate(),this.denom)};BigRational.prototype.isNegative=function(){return this.num.isNegative()!==this.denom.isNegative()&&!this.num.isZero()};BigRational.prototype.isPositive=function(){return this.num.isNegative()===this.denom.isNegative()&&!this.num.isZero()};BigRational.prototype.isZero=function(){return this.num.isZero()};BigRational.prototype.toDecimal=function(digits){digits=typeof digits==="number"?digits:10;var n=this.num.divmod(this.denom);var intPart=n.quotient.abs().toString();var remainder=parse(n.remainder.abs(),this.denom);var shiftedRemainder=remainder.times(bigInt("1e"+digits));var decPart=shiftedRemainder.num.over(shiftedRemainder.denom).toString();if(decPart.length<digits){decPart=new Array(digits-decPart.length+1).join("0")+decPart}if(shiftedRemainder.num.mod(shiftedRemainder.denom).isZero()){while(decPart.slice(-1)==="0"){decPart=decPart.slice(0,-1)}}if(digits<1)decPart="";if(this.isNegative()){intPart="-"+intPart}if(decPart===""){return intPart}return intPart+"."+decPart};BigRational.prototype.toString=function(){return String(this.num)+"/"+String(this.denom)};BigRational.prototype.valueOf=function(){if(!isFinite(+this.num)||!isFinite(+this.denom)){return+this.toDecimal(64)}return this.num/this.denom};function interpret(n,d){return parse(n,d)}function parseDecimal(n){var parts=n.split(/e/i);if(parts.length>2){throw new Error("Invalid input: too many 'e' tokens")}if(parts.length>1){var isPositive=true;if(parts[1][0]==="-"){parts[1]=parts[1].slice(1);isPositive=false}if(parts[1][0]==="+"){parts[1]=parts[1].slice(1)}var significand=parseDecimal(parts[0]);var exponent=new BigRational(bigInt(10).pow(parts[1]),bigInt[1]);if(isPositive){return significand.times(exponent)}else{return significand.over(exponent)}}parts=n.trim().split(".");if(parts.length>2){throw new Error("Invalid input: too many '.' tokens")}if(parts.length>1){var isNegative=parts[0][0]==="-";if(isNegative)parts[0]=parts[0].slice(1);var intPart=new BigRational(bigInt(parts[0]),bigInt[1]);var length=parts[1].length;while(parts[1][0]==="0"){parts[1]=parts[1].slice(1)}var exp="1"+Array(length+1).join("0");var decPart=reduce(bigInt(parts[1]),bigInt(exp));intPart=intPart.add(decPart);if(isNegative)intPart=intPart.negate();return intPart}return new BigRational(bigInt(n),bigInt[1])}function parse(a,b){if(!a){return new BigRational(bigInt(0),bigInt[1])}if(b){return reduce(bigInt(a),bigInt(b))}if(bigInt.isInstance(a)){return new BigRational(a,bigInt[1])}if(a instanceof BigRational)return a;var num;var denom;var text=String(a);var texts=text.split("/");if(texts.length>2){throw new Error("Invalid input: too many '/' tokens")}if(texts.length>1){var parts=texts[0].split("_");if(parts.length>2){throw new Error("Invalid input: too many '_' tokens")}if(parts.length>1){var isPositive=parts[0][0]!=="-";num=bigInt(parts[0]).times(texts[1]);if(isPositive){num=num.add(parts[1])}else{num=num.subtract(parts[1])}denom=bigInt(texts[1]);return reduce(num,denom)}return reduce(bigInt(texts[0]),bigInt(texts[1]))}return parseDecimal(text)}parse.zero=parse(0);parse.one=parse(1);parse.minusOne=parse(-1);return parse}(typeof bigInt!=="undefined"?bigInt:require("big-integer"));if(typeof module!=="undefined"){if(module.hasOwnProperty("exports")){module.exports=bigRat}} |
{ | ||
"name": "big-rational", | ||
"version": "0.10.7", | ||
"version": "0.10.9", | ||
"author": "Peter Olson <peter.e.c.olson+npm@gmail.com>", | ||
@@ -8,3 +8,6 @@ "description": "An arbitrary length rational number library for Javascript", | ||
"bin": {}, | ||
"scripts": {}, | ||
"scripts": { | ||
"minify": "uglifyjs BigRational.js -o BigRational.min.js", | ||
"combine": "copy \"..\\BigInteger.js\\BigInteger.min.js\" + BigRational.min.js BigInt_BigRat.min.js" | ||
}, | ||
"main": "./BigRational", | ||
@@ -26,4 +29,4 @@ "repository": { | ||
], | ||
"dependencies" : { | ||
"big-integer" : "^1.6.23" | ||
"dependencies": { | ||
"big-integer": "^1.6.40" | ||
}, | ||
@@ -30,0 +33,0 @@ "license": "WTFPL", |
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Major refactor
Supply chain riskPackage has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.
Found 1 instance in 1 package
Uses eval
Supply chain riskPackage uses eval() which is a dangerous function. This prevents the code from running in certain environments and increases the risk that the code may contain exploits or malicious behavior.
Found 1 instance in 1 package
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Major refactor
Supply chain riskPackage has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.
Found 1 instance in 1 package
Minified code
QualityThis package contains minified code. This may be harmless in some cases where minified code is included in packaged libraries, however packages on npm should not minify code.
Found 1 instance in 1 package
66009
265
3
2
Updatedbig-integer@^1.6.40