|
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
(
++
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; } } }
|