diff --git a/lib/assets/libs/long_int.js b/lib/assets/libs/long_int.js new file mode 100644 --- /dev/null +++ b/lib/assets/libs/long_int.js @@ -0,0 +1,639 @@ +/* +Module to manipulate long integers +*/ + +var $module=(function($B){ + +eval($B.InjectBuiltins()) + +var $LongIntDict = {__class__:$B.$type,__name__:'LongInt'} + +function add_pos(v1, v2){ + // Add two positive numbers + // v1, v2 : strings + // Return an instance of LongInt + + var res = '', carry = 0, iself=v1.length, sv=0 + for(var i=v2.length-1;i>=0;i--){ + iself-- + if(iself<0){sv=0}else{sv=parseInt(v1.charAt(iself))} + x = (carry+sv+parseInt(v2.charAt(i))).toString() + if(x.length==2){res=x.charAt(1)+res;carry=parseInt(x.charAt(0))} + else{res=x+res;carry=0} + } + while(iself>0){ + iself-- + x = (carry+parseInt(v1.charAt(iself))).toString() + if(x.length==2){res=x.charAt(1)+res;carry=parseInt(x.charAt(0))} + else{res=x+res;carry=0} + } + if(carry){res=carry+res} + return {__class__:$LongIntDict, value:res, pos:true} +} + +function check_shift(shift){ + // Check the argument of >> and << + if(!isinstance(shift, LongInt)){ + throw TypeError("shift must be LongInt, not '"+ + $B.get_class(shift).__name__+"'") + } + if(!shift.pos){throw ValueError("negative shift count")} +} + +function clone(obj){ + // Used for traces + var obj1 = {} + for(var attr in obj){obj1[attr]=obj[attr]} + return obj1 +} + +function comp_pos(v1, v2){ + // Compare two positive numbers + if(v1.length>v2.length){return 1} + else if(v1.lengthv2){return 1} + else if(v11){ + // If the value in cols[i] has more than one digit, only keep the + // last one and report the others at the right index + // For instance if cols[i] = 123, keep 3 in cols[i], add 2 to + // cols[i-1] and 1 to cols[i-2] + cols[i] = parseInt(col.charAt(col.length-1)) + j = col.length + while(j-->1){ + var report = parseInt(col.charAt(j-1)) + var pos = i-col.length+j + if(cols[pos]===undefined){cols[pos]=report} + else{cols[pos] += report} + } + } + } + + // Find minimum index in cols + // The previous loop may have introduced negative indices + var imin + for(var attr in cols){ + i = parseInt(attr) + if(imin===undefined){imin=i} + else if(i=v2 + + var res = '', carry = 0, i1=v1.length, sv=0 + + // For all digits in v2, starting by the rightmost, substract it from + // the matching digit in v1 + // This is the equivalent of the manual operation : + // 12345678 + // - 98765 + // + // We begin by the rightmost operation : 8-5 (3, no carry), + // then 7-6 (1, no carry) + // then 6-7 (9, carry 1) and so on + for(var i=v2.length-1;i>=0;i--){ + i1-- + sv = parseInt(v1.charAt(i1)) + x = (sv-carry-parseInt(v2.charAt(i))) + if(x<0){res=(10+x)+res;carry=1} + else{res=x+res;carry=0} + } + + // If there are remaining digits in v1, substract the carry, if any + while(i1>0){ + i1-- + x = (parseInt(v1.charAt(i1))-carry) + if(x<0){res=(10+x)+res;carry=1} + else{res=x+res;carry=0} + } + + // Remove leading zeros and return the result + while(res.charAt(0)=='0' && res.length>1){res=res.substr(1)} + return {__class__:$LongIntDict, value:res, pos:true} +} + +// Special methods to implement operations on instances of LongInt + +$LongIntDict.__abs__ = function(self){ + return {__class__:$LongIntDict, value: self.value, pos:true} +} + +$LongIntDict.__add__ = function(self, other){ + if (typeof other == 'number') other=LongInt(_b_.str(other)) + // Addition of "self" and "other" + // If both have the same sign (+ or -) we add their absolute values + // If they have different sign we use the substraction of their + // absolute values + var res + if(self.pos&&other.pos){ // self > 0, other > 0 + return add_pos(self.value, other.value) + }else if(!self.pos&&!other.pos){ // self < 0, other < 0 + res = add_pos(self.value, other.value) + res.pos = false + return res + }else if(self.pos && !other.pos){ // self > 0, other < 0 + switch (comp_pos(self.value, other.value)){ + case 1: + res = sub_pos(self.value, other.value) + break + case 0: + res = {__class__:$LongIntDict, value:0, pos:true} + break + case -1: + res = sub_pos(other.value, self.value) + res.pos = false + break + } + return res + }else{ // self < 0, other > 0 + switch(comp_pos(self.value, other.value)){ + case 1: + res = sub_pos(self.value, other.value) + res.pos = false + break + case 0: + res = {__class__:$LongIntDict, value:0, pos:true} + break + case -1: + res = sub_pos(other.value, self.value) + break + } + return res + } +} + +$LongIntDict.__and__ = function(self, other){ + if (typeof other == 'number') other=LongInt(_b_.str(other)) + // Bitwise "and" : build the binary representation of self and other + var v1 = $LongIntDict.__index__(self) + var v2 = $LongIntDict.__index__(other) + // apply "and" on zeros and ones + if(v1.lengthother.value.length){return true} + else if(self.value.length= other.value} +} + +$LongIntDict.__gt__ = function(self, other){ + return !$LongIntDict.__le__(self, other) +} + +$LongIntDict.__index__ = function(self){ + // Used by bin() + // returns a string with the binary value of self + // The algorithm computes the result of the floor division of self by 2 + + // XXX to do : negative integers + + var res = '', pos=self.value.length, + temp = self.value, d + while(true){ + d = divmod_pos(temp, '2') + res = d[1].value + res + temp = d[0].value + if(temp=='0'){break} + } + return res +} + +$LongIntDict.__invert__ = function(self){ + var bin = $LongIntDict.__index__(self) + var res = '' + for(var i=0;iother.value.length){return false} + else if(self.value.length=0;i--){ + x = (carry+parseInt(res.charAt(i))*2).toString() + if(x.length==2){res1=x.charAt(1)+res1;carry=parseInt(x.charAt(0))} + else{res1=x+res1;carry=0} + } + if(carry){res1=carry+res1} + res=res1 + shift = sub_pos(shift.value, '1') + if(shift.value=='0'){break} + } + return {__class__:$LongIntDict, value:res, pos:self.pos} +} + +$LongIntDict.__mod__ = function(self, other){ + return $LongIntDict.__divmod__(self, other)[1] +} + +$LongIntDict.__mro__ = [$LongIntDict, _b_.object.$dict] + +$LongIntDict.__mul__ = function(self, other){ + if (typeof other == 'number') other=LongInt(_b_.str(other)) + var res = mul_pos(self.value, other.value) + if(self.pos==other.pos){return res} + res.pos = false + return res +} + +$LongIntDict.__neg__ = function(obj){ + return {__class__:$LongIntDict, value:obj.value, pos:!obj.pos} +} + +$LongIntDict.__or__ = function(self, other){ + var v1 = $LongIntDict.__index__(self) + var v2 = $LongIntDict.__index__(other) + if(v1.length0){ + var dm = divmod_pos(v, base.toString()) + res = parseInt(dm[1].value).toString(base)+res + v = dm[0].value + if(v==0){break} + } + return res +} + +function digits(base){ + // Return an object where keys are all the digits valid in specified base + // and value is "true" + // Used to test if the string passed as first argument to LongInt is valid + var is_digits = {} + // Number from 0 to base, or from 0 to 9 if base > 10 + for(var i=0;i10){ + // Additional letters + // For instance in base 16, add "abcdefABCDEF" as keys + for(var i=0;i2){ + throw _b_.TypeError("LongInt takes at most 2 arguments ("+ + arguments.length+" given)") + } + // base defaults to 10 + if(base===undefined){base = 10} + else if(!isinstance(base, int)){ + throw TypeError("'"+$B.get_class(base).__name__+"' object cannot be interpreted as an integer") + } + if(base<0 || base==1 || base>36){ + throw ValueError("LongInt() base must be >= 2 and <= 36") + } + if(isinstance(value, float)){ + if(value>=0){value=Math.round(value.value)} + else{value=Math.ceil(value.value)} + } + if(typeof value=='number'){ + if(isSafeInteger(value)){value = value.toString()} + else{throw ValueError("argument of long_int is not a safe integer")} + }else if(typeof value!='string'){ + throw ValueError("argument of long_int must be a string, not "+ + $B.get_class(value).__name__) + } + var has_prefix = false, pos = true, start = 0 + // Strip leading and trailing whitespaces + while(value.charAt(0)==' ' && value.length){value = value.substr(1)} + while(value.charAt(value.length-1)==' ' && value.length){ + value = value.substr(0, value.length-1) + } + // Check if string starts with + or - + if(value.charAt(0)=='+'){has_prefix=true} + else if(value.charAt(0)=='-'){has_prefix=true;pos=false} + if(has_prefix){ + // Remove prefix + if(value.length==1){ + // "+" or "-" alone are not valid arguments + throw ValueError('LongInt argument is not a valid number: "'+value+'"') + }else{value=value.substr(1)} + } + // Ignore leading zeros + while(start