S.l.e!ep.¢%

像打了激速一样,以四倍的速度运转,开心的工作
简单、开放、平等的公司文化;尊重个性、自由与个人价值;
posts - 1098, comments - 335, trackbacks - 0, articles - 1
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Flash AS3 封装的 BigInt

Posted on 2009-12-14 15:03 S.l.e!ep.¢% 阅读(1053) 评论(0)  编辑 收藏 引用 所属分类: Flash
/* *
 * BigInt
 * An ActionScript 3 implementation of Big Integer (light version)
 * Copyright (c) 2009 Alex.li
 * 
 * Derived from: 
 *         BigInt.js - Arbitrary size integer math package for JavaScript
 *         Copyright (C) 2000 Masanao Izumo <iz@onicos.co.jp>
 * 
 * Interfaces:
 * var x:BigInt = new BigInt("1234567890123456789012345678901234567890");
 * var y:BigInt = new BigInt("0x123456789abcdef0123456789abcdef0");
 * var z:BigInt = x.clone();
 * z = x.negative();
 * z = BigInt.plus(x, y);
 * z = BigInt.minus(x, y);
 * z = BigInt.multiply(x, y);
 * z = BigInt.divide(x, y);
 * z = BigInt.mod(x, y);    
 * var compare:int = BigInt.compare(x, y); //return -1, 0, or 1
 * var num:Number = x.toNumber(); //convert to normal number 
 
*/

package
{    
    
public   class  BigInt
    {
        
// sign of BigInt, negative or not
         private  var _sign:Boolean;
        
// length of BigInt
         private  var _len: int ;
        
// digits of BigInt
         private  var _digits:Array;
        
        
public  function BigInt(arg)
        {
            var i:
* , x: * , need_init:Boolean;

            
if  (arg.length  ==   0
            {
                _sign 
=   true ;
                _len 
=   1 ;
                _digits 
=   new  Array( 1 );
                need_init 
=   true ;            
            } 
else   if  (arg.length  ==   1
            {
                x 
=  getBigIntFromAny(arg[ 0 ]);
                
if  (x  ==  arg[ 0 ]) x  =  x.clone();                
                _sign 
=  x._sign;
                _len 
=  x._len;
                _digits 
=  x._digits;
                need_init 
=   false ;            
            } 
else  
            {
                _sign 
=  (arg[ 1 ?   true  :  false );
                _len 
=  arg[ 0 ];
                _digits 
=   new  Array(_len);
                need_init 
=   true ;
            }

            
if  (need_init) 
            {
                
for (i  =   0 ; i  <  _len; i ++ )
                _digits[i] 
=   0 ;
            }
        }
        
        
public  function toString():String
        {
            
return   this .toStringBase( 10 );
        }
        
        
public  function toStringBase( base : int ):String
        {
            var i:
* , j: * , hbase: * ;
            var t:
* ;
            var ds:
* ;
            var c:
* ;

            i 
=   this ._len;
            
if  (i  ==   0 return   " 0 " ;
            
if  (i  ==   1   &&   ! this ._digits[ 0 ])  return   " 0 " ;

            
switch ( base ) {
              
default :
              
case   10 :
              j 
=  Math.floor(( 2 * 8 * i * 241 ) / 800 ) + 2 ;
              hbase 
=   10000 ;
              
break ;

              
case   16 :
              j 
=  Math.floor(( 2 * 8 * i) / 4 ) + 2 ;
              hbase 
=   0x10000 ;
              
break ;

              
case   8 :
              j 
=  ( 2 * 8 * i) + 2 ;
              hbase 
=   010000 ;
              
break ;

              
case   2 :
              j 
=  ( 2 * 8 * i) + 2 ;
              hbase 
=   020 ;
              
break ;
            }

            t 
=   this .clone();
            ds 
=  t._digits;
            var s:String 
=   "" ;

            
while  (i  &&  j) 
            {
                var k:
*   =  i;
                var num:
*   =   0 ;

                
while  (k --
                {
                    num 
=  (num << 16 +  ds[k];
                    
if (num  <   0 ) num  +=   4294967296 ;
                    ds[k] 
=  Math.floor(num  /  hbase);
                    num 
%=  hbase;
                }

                
if  (ds[i - 1 ==   0 )
                i
-- ;
                k 
=   4 ;
                
while  (k --
                {
                    c 
=  (num  %   base );
                    s 
=   " 0123456789abcdef " .charAt(c)  +  s;
                    
-- j;
                    num 
=  Math.floor(num  /   base );
                    
if  (i  ==   0   &&  num  ==   0
                    {
                        
break ;
                    }
                }
            }

            i 
=   0 ;
            
while (i  <  s.length  &&  s.charAt(i)  ==   " 0 " )
            i
++ ;
            
if (i)
            s 
=  s.substring(i, s.length);
            
if ( ! this ._sign)
            s 
=   " - "   +  s;            
            
return  s;
        }
        
        
public  function clone():BigInt
        {
            var x:BigInt, i:
int ;

            x 
=   new  BigInt( this ._len,  this ._sign);
            
for  (i  =   0 ; i  <   this ._len; i ++ )
            {
                x._digits[i] 
=   this ._digits[i]; 
            }            
            
return  x;
        }        
        
        
/* *
         * become a negative BigInt
         * @return
         
*/
        
public  function negative():BigInt
        {
          var n:BigInt 
=   this .clone();
          n._sign 
=   ! n._sign;
          
return  normalize(n);
        }        
        
        
public  function toNumber():Number
        {
            var d:
*   =   0.0 ;
            var i:
*   =  _len;
            var ds:
*   =  _digits;

            
while  (i --
            {
                d 
=  ds[i]  +   65536.0   *  d;
            }
            
if  ( ! _sign) d  =   - d;
            
return  d;
        }
        
        
public  function  get  sign():Boolean 
        { 
            
return  _sign; 
        }
        
        
public  function  get  length(): int  
        { 
            
return  _len; 
        }
        
        
public  function  get  digits():Array 
        { 
            
return  _digits; 
        }    
        
        
        
/* ************  public static methods  ************* */
        
        
        
public   static  function plus(x: * , y: * ):BigInt
        {
            x 
=  getBigIntFromAny(x);
            y 
=  getBigIntFromAny(y);
            
return  add(x, y,  1 );
        }
        
        
public   static  function minus(x: * , y: * ):BigInt
        {
            x 
=  getBigIntFromAny(x);
            y 
=  getBigIntFromAny(y);
            
return  add(x, y,  0 );
        }        
        
        
public   static  function multiply(x: * , y: * ):BigInt
        {
            var i:
* , j: * ;
            var n:
*   =   0 ;
            var z:
* ;
            var zds:
* , xds: * , yds: * ;
            var dd:
* , ee: * ;
            var ylen:
* ;

            x 
=  getBigIntFromAny(x);
            y 
=  getBigIntFromAny(y);

            j 
=  x._len  +  y._len  +   1 ;
            z 
=   new  BigInt(j, x._sign  ==  y._sign);

            xds 
=  x._digits;
            yds 
=  y._digits;
            zds 
=  z._digits;
            ylen 
=  y._len;
            
            
while  (j -- ) zds[j]  =   0 ;
            
for  (i  =   0 ; i  <  x._len; i ++
            {
                dd 
=  xds[i]; 
                
if  (dd  ==   0 continue ;
                n 
=   0 ;
                
for  (j  =   0 ; j  <  ylen; j ++
                {
                    ee 
=  n  +  dd  *  yds[j];
                    n 
=  zds[i  +  j]  +  ee;
                    
if  (ee) zds[i  +  j]  =  (n  &   0xffff );
                    n 
>>>=   16 ;
                }
                
if  (n) 
                {
                    zds[i 
+  j]  =  n;
                }
            }
            
return  normalize(z);
        }        
        
        
public   static  function divide(x: * , y: * ):BigInt
        {
            x 
=  getBigIntFromAny(x);
            y 
=  getBigIntFromAny(y);
            
return  divideAndMod(x, y,  0 );
        }
        
        
public   static  function mod(x: * , y: * ):BigInt
        {
            x 
=  getBigIntFromAny(x);
            y 
=  getBigIntFromAny(y);
            
return  divideAndMod(x, y,  1 );
        }
        
        
/* *
         * compare two BigInts, if  x=y return 0, if x>y return 1, if x<y return -1.
         * @param    x
         * @param    y
         * @return
         
*/
        
public   static  function compare(x: * , y: * ): int
        {
            var xlen:
* ;

            
if  (x  ==  y)  return   0 ;

            x 
=  getBigIntFromAny(x);
            y 
=  getBigIntFromAny(y);
            xlen 
=  x._len;

            
if  (x._sign  !=  y._sign) 
            {
                
if  (x._sign)  return   1 ;
                
return   - 1 ;
            }

            
if  (xlen  <  y._len)  return  (x._sign)  ?   - 1  :  1 ;
            
if  (xlen  >  y._len)  return  (x._sign)  ?   1  :  - 1 ;

            
while  (xlen --   &&  (x._digits[xlen]  ==  y._digits[xlen]));
            
if  (  - 1   ==  xlen)  return   0 ;
            
            
return  (x._digits[xlen]  >  y._digits[xlen])  ?
            (x._sign 
?   1  :  - 1 ) :
            (x._sign 
?   - 1  :  1 );
        }
        
        
        
/* ************  private static methods  ************* */
        
        
        
private   static  function getBigIntFromAny(x: * ):BigInt
        {            
            
if  ( typeof (x)  ==   " object "
            {
                
if  (x  is  BigInt)  return  x;
                
return   new  BigInt( 1 1 );
            }
            
            
if  ( typeof (x)  ==   " string "
            {
                
                
return  getBigIntFromString(x);
            }
            
            
if  ( typeof (x)  ==   " number "
            {                
                var i:
* , x1: * , x2: * , fpt: * , np: * ;
                
                
if  (  - 2147483647   <=  x  &&  x  <=   2147483647
                {
                    
return  getBigIntFromInt(x);
                }
                x 
=  x  +   "" ;
                i 
=  x.indexOf( " e " 0 );
                
if  (i  ==   - 1 return  getBigIntFromString(x);
                x1 
=  x.substr( 0 , i);
                x2 
=  x.substr(i  +   2 , x.length  -  (i  +   2 ));

                fpt 
=  x1.indexOf( " . " 0 );
                
if  (fpt  !=   - 1
                {
                    np 
=  x1.length  -  (fpt  +   1 );
                    x1 
=  x1.substr( 0 , fpt)  +  x1.substr(fpt  +   1 , np);
                    x2 
=  parseInt(x2)  -  np;
                } 
else  
                {
                    x2 
=  parseInt(x2);
                }
                
while  (x2 --   >   0
                {
                    x1 
+=   " 0 " ;
                }
                
return  getBigIntFromString(x1);
            }
            
return   new  BigInt( 1 1 );
        }    
        
        
private   static  function getBigIntFromInt(n:Number):BigInt
        {
            var sign:
* , big:BigInt, i: * ;
            
            
if  (n  <   0
            {
                n 
=   - n;
                sign 
=   false ;
            } 
else
            {                
                sign 
=   true ;                
            }
            n 
&=   0x7FFFFFFF ;
            
            
if  (n  <=   0xFFFF
            {
                big 
=   new  BigInt( 1 1 );
                big._digits[
0 =  n;
            } 
else
            {                
                big 
=   new  BigInt( 2 1 );                
                big._digits[
0 =  (n  &   0xffff );
                big._digits[
1 =  ((n  >>   16 &   0xffff );
            }
            
return  big;
        }
        
        
private   static  function getBigIntFromString(str:String,  base : *   =   null ):BigInt
        {
            var str_i:
* ;
            var sign:Boolean 
=   true ;
            var c:
* ;
            var len:
* ;
            var z:
* ;
            var zds:
* ;
            var num:
* ;
            var i:
* ;
            var blen:
*   =   1 ;

            str 
+=   " @ " ;
            str_i 
=   0 ;

            
if  (str.charAt(str_i)  ==   " + "
            {
                str_i
++ ;
            }
else   if  (str.charAt(str_i)  ==   " - "
            {
                str_i
++ ;
                sign 
=   false ;
            }

            
if  (str.charAt(str_i)  ==   " @ " )
                
return   null ;

            
if  ( ! base
            {
                
if  (str.charAt(str_i)  ==   " 0 " )
                {
                    c 
=  str.charAt(str_i  +   1 );
                    
if  (c  ==   " x "   ||  c  ==   " X "
                    {
                        
base   =   16 ;
                    }
else   if  (c ==   " b "   ||  c  ==   " B "
                    {
                        
base   =   2 ;
                    }
else  
                    {
                        
base   =   8 ;
                    }
                }
else  
                {
                    
base   =   10 ;
                }
            }

            
if  ( base   ==   8
            {
                
while  (str.charAt(str_i)  ==   " 0 " )
                str_i
++ ;
                len 
=   3   *  (str.length  -  str_i);
            }
else  
            {
                
if  ( base   ==   16   &&  str.charAt(str_i)  ==   ' 0 '   &&  (str.charAt(str_i  +   1 ==   " x "   ||  str.charAt(str_i  +   1 ==   " X " )) 
                {
                    str_i 
+=   2 ;
                }
                
if  ( base   ==   2   &&  str.charAt(str_i)  ==   ' 0 '   &&  (str.charAt(str_i  +   1 ==   " b "   ||  str.charAt(str_i  +   1 ==   " B " )) 
                {
                    str_i 
+=   2 ;
                }
                
while  (str.charAt(str_i)  ==   " 0 " )
                str_i
++ ;
                
if  (str.charAt(str_i)  ==   " @ " ) str_i -- ;
                len 
=   4   *  (str.length  -  str_i);
            }

            len 
=  (len  >>   4 +   1 ;
            z 
=   new  BigInt(len, sign);
            zds 
=  z._digits;

            
while  ( true
            {
                c 
=  str.charAt(str_i ++ );
                
if (c  ==   " @ " )
                
break ;
                
switch  (c) 
                {
                    
case   ' 0 ' : c  =   0 break ;
                    
case   ' 1 ' : c  =   1 break ;
                    
case   ' 2 ' : c  =   2 break ;
                    
case   ' 3 ' : c  =   3 break ;
                    
case   ' 4 ' : c  =   4 break ;
                    
case   ' 5 ' : c  =   5 break ;
                    
case   ' 6 ' : c  =   6 break ;
                    
case   ' 7 ' : c  =   7 break ;
                    
case   ' 8 ' : c  =   8 break ;
                    
case   ' 9 ' : c  =   9 break ;
                    
case   ' a ' case   ' A ' : c  =   10 break ;
                    
case   ' b ' case   ' B ' : c  =   11 break ;
                    
case   ' c ' case   ' C ' : c  =   12 break ;
                    
case   ' d ' case   ' D ' : c  =   13 break ;
                    
case   ' e ' case   ' E ' : c  =   14 break ;
                    
case   ' f ' case   ' F ' : c  =   15 break ;
                    
default :
                    c 
=   base ;
                    
break ;
                }
                
if  (c  >=   base break ;

                i 
=   0 ;
                num 
=  c;
                
while  ( true
                {
                    
while  (i  <  blen) 
                    {
                        num 
+=  zds[i] * base ;
                        zds[i
++ =  (num  &   0xffff );
                        num 
>>>=   16 ;
                    }
                    
if  (num) 
                    {
                        blen
++ ;
                        
continue ;
                    }
                    
break ;
                }
            }
            
return  normalize(z);
        }            
        
        
private   static  function add(x:BigInt, y:BigInt, sign: * ):BigInt
        {
            var z:
* ;
            var num:
* ;
            var i:
* , len: * ;

            sign 
=  (sign  ==  y._sign);
            
if  (x._sign  !=  sign) 
            {
                
if  (sign)  return  subtract(y, x);
                
return  subtract(x, y);
            }

            
if  (x._len  >  y._len) 
            {
                len 
=  x._len  +   1 ;
                z 
=  x; x  =  y; y  =  z;
            } 
else  
            {
                len 
=  y._len  +   1 ;
            }
            z 
=   new  BigInt(len, sign);

            len 
=  x._len;
            
for  (i  =   0 , num  =   0 ; i  <  len; i ++
            {
                num 
+=  x._digits[i]  +  y._digits[i];
                z._digits[i] 
=  (num  &   0xffff );
                num 
>>>=   16 ;
            }
            len 
=  y._len;
            
while  (num  &&  i  <  len) 
            {
                num 
+=  y._digits[i];
                z._digits[i
++ =  (num  &   0xffff );
                num 
>>>=   16 ;
            }
            
while  (i  <  len) 
            {
                z._digits[i] 
=  y._digits[i];
                i
++ ;
            }
            z._digits[i] 
=  (num  &   0xffff );
            
return  normalize(z);
        }
        
        
private   static  function subtract(x:BigInt, y:BigInt):BigInt
        {
            var z:
*   =   0 ;
            var zds:
* ;
            var num:
* ;
            var i:
* ;

            i 
=  x._len;
            
if  (x._len  <  y._len) 
            {
                z 
=  x; x  =  y; y  =  z;
            }
else   if  (x._len  ==  y._len) 
            {
                
while  (i  >   0
                {
                    i
-- ;
                    
if  (x._digits[i]  >  y._digits[i]) 
                    {
                        
break ;
                    }
                    
if  (x._digits[i]  <  y._digits[i]) 
                    {
                        z 
=  x; x  =  y; y  =  z;
                        
break ;
                    }
                }
            }

            z 
=   new  BigInt(x._len, (z  ==   0 ?   1  :  0 );
            zds 
=  z._digits;

            
for  (i  =   0 , num  =   0 ; i  <  y._len; i ++
            { 
                num 
+=  x._digits[i]  -  y._digits[i];
                zds[i] 
=  (num  &   0xffff );
                num 
>>>=   16 ;
            } 
            
while  (num  &&  i  <  x._len) 
            {
                num 
+=  x._digits[i];
                zds[i
++ =  (num  &   0xffff );
                num 
>>>=   16 ;
            }
            
while  (i  <  x._len) 
            {
                zds[i] 
=  x._digits[i];
                i
++ ;
            }            
            
return  normalize(z);
        }
        
        
private   static  function divideAndMod(x:BigInt, y:BigInt, modulo: * ):BigInt
        {
            var nx:
*   =  x._len;
            var ny:
*   =  y._len;
            var i:
* , j: * ;
            var yy:
* , z: * ;
            var xds:
* , yds: * , zds: * , tds: * ;
            var t2:
* ;
            var num:
* ;
            var dd:
* , q: * ;
            var ee:
* ;
            var mod:
* , div: * ;

            yds 
=  y._digits;
            
if  (ny  ==   0   &&  yds[ 0 ==   0 return   null ;

            
if  (nx  <  ny  ||  nx  ==  ny  &&  x._digits[nx  -   1 <  y._digits[ny  -   1 ]) 
            {
                
if  (modulo)  return  normalize(x);
                
return   new  BigIt( 1 1 );
            }

            xds 
=  x._digits;
            
if  (ny  ==   1
            {
                dd 
=  yds[ 0 ];
                z 
=  x.clone();
                zds 
=  z._digits;
                t2 
=   0 ;
                i 
=  nx;
                
while  (i --
                {
                    t2 
=  t2  *   65536   +  zds[i];
                    zds[i] 
=  (t2  /  dd)  &   0xffff ;
                    t2 
%=  dd;
                }
                z._sign 
=  (x._sign  ==  y._sign);
                
if  (modulo)
                {
                    
if  ( ! x._sign) t2  =   - t2;
                    
if  (x._sign  !=  y._sign)
                    {
                        t2 
=  t2  +  yds[ 0 *  (y._sign  ?   1  :  - 1 );
                    }
                    
return  getBigIntFromInt(t2);
                }
                
return  normalize(z);
            }

            z 
=   new  BigInt(nx  ==  ny  ?  nx  +   2  : nx  +   1 , x._sign  ==  y._sign);
            zds 
=  z._digits;
            
if  (nx  ==  ny) zds[nx  +   1 =   0 ;
            
while  ( ! yds[ny  -   1 ]) ny -- ;
            
if  ((dd  =  (( 65536   /  (yds[ny  -   1 +   1 ))  &   0xffff ))  !=   1
            {
                yy 
=  y.clone();
                tds 
=  yy._digits;
                j 
=   0 ;
                num 
=   0 ;
                
while  (j  <  ny) 
                {
                    num 
+=  yds[j]  *  dd;
                    tds[j
++ =  num  &   0xffff ;
                    num 
>>=   16 ;
                }
                yds 
=  tds;
                j 
=   0 ;
                num 
=   0 ;
                
while  (j  <  nx) 
                {
                    num 
+=  xds[j]  *  dd;
                    zds[j
++ =  num  &   0xffff ;
                    num 
>>=   16 ;
                }
                zds[j] 
=  num  &   0xffff ;
            }
else  
            {
                zds[nx] 
=   0 ;
                j 
=  nx;
                
while  (j -- ) zds[j]  =  xds[j];
            }
            j 
=  nx  ==  ny  ?  nx  +   1  : nx;
            
            
do  
            {
                
if  (zds[j]  ==   yds[ny  -   1 ]) q  =   65535 ;
                
else  q  =  ((zds[j]  *   65536   +  zds[j  -   1 ])  /  yds[ny  -   1 ])  &   0xffff ;
                
if  (q) 
                {
                    i 
=   0 ; num  =   0 ; t2  =   0 ;
                    
do  
                    {
                        t2 
+=  yds[i]  *  q;
                        ee 
=  num  -  (t2  &   0xffff );
                        num 
=  zds[j  -  ny  +  i]  +  ee;
                        
if  (ee) zds[j  -  ny  +  i]  =  num  &   0xffff ;
                        num 
>>=   16 ;
                        t2 
>>>=   16 ;
                    } 
while  ( ++ <  ny);
                    
                    num 
+=  zds[j  -  ny  +  i]  -  t2;
                    
while  (num) 
                    {
                        i 
=   0 ; num  =   0 ; q -- ;
                        
do  
                        {
                            ee 
=  num  +  yds[i];
                            num 
=  zds[j  -  ny  +  i]  +  ee;
                            
if  (ee) zds[j  -  ny  +  i]  =  num  &   0xffff ;
                            num 
>>=   16 ;
                        } 
while  ( ++ <  ny);
                        num
-- ;
                    }
                }
                zds[j] 
=  q;
            } 
while  ( -- >=  ny);

            
if  (modulo) 
            {
                mod 
=  z.clone();
                
if  (dd) 
                {
                    zds 
=  mod._digits;
                    t2 
=   0 ; i  =  ny;
                    
while  (i --
                    {
                        t2 
=  (t2 * 65536 +  zds[i];
                        zds[i] 
=  (t2  /  dd)  &   0xffff ;
                        t2 
%=  dd;
                    }
                }
                mod._len 
=  ny;
                mod._sign 
=  x._sign;
                
if  (x._sign  !=  y._sign) 
                {
                    
return  add(mod, y,  1 );
                }
                
return  normalize(mod);
            }

            div 
=  z.clone();
            zds 
=  div._digits;
            j 
=  (nx  ==  ny  ?  nx  +   2  : nx  +   1 -  ny;
            
for  (i  =   0 ; i  <  j; i ++ ) zds[i]  =  zds[i  +  ny];
            div._len 
=  i;
            
return  normalize(div);
        }        
        
        
private   static  function normalize(x:BigInt):BigInt
        {
            var len:
*   =  x._len;
            var ds:
*   =  x._digits;

            
while  (len --   &&   ! ds[len]);
            x._len 
=   ++ len;
            
return  x;
        }
    }    
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理