|
|
Posted on 2009-12-14 15:03 S.l.e!ep.￠% 阅读(1034) 评论(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
(
++
i
<
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
(
++
i
<
ny);
num
--
;
}
}
zds[j]
=
q;
}
while
(
--
j
>=
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;
}
}
}
|