root / trunk / web / dojo / dojox / math / BigInteger.js @ 12
History | View | Annotate | Download (9.23 KB)
1 |
/*
|
---|---|
2 |
Copyright (c) 2004-2010, The Dojo Foundation All Rights Reserved.
|
3 |
Available via Academic Free License >= 2.1 OR the modified BSD license.
|
4 |
see: http://dojotoolkit.org/license for details
|
5 |
*/
|
6 |
|
7 |
|
8 |
if(!dojo._hasResource["dojox.math.BigInteger"]){ |
9 |
dojo._hasResource["dojox.math.BigInteger"]=true; |
10 |
dojo.provide("dojox.math.BigInteger");
|
11 |
dojo.experimental("dojox.math.BigInteger");
|
12 |
(function(){
|
13 |
var _1;
|
14 |
var _2=244837814094590; |
15 |
var _3=((_2&16777215)==15715070); |
16 |
function _4(a,b,c){ |
17 |
if(a!=null){ |
18 |
if("number"==typeof a){ |
19 |
this._fromNumber(a,b,c);
|
20 |
}else{
|
21 |
if(!b&&"string"!=typeof a){ |
22 |
this._fromString(a,256); |
23 |
}else{
|
24 |
this._fromString(a,b);
|
25 |
} |
26 |
} |
27 |
} |
28 |
}; |
29 |
function _5(){ |
30 |
return new _4(null); |
31 |
}; |
32 |
function _6(i,x,w,j,c,n){ |
33 |
while(--n>=0){ |
34 |
var v=x*this[i++]+w[j]+c; |
35 |
c=Math.floor(v/67108864);
|
36 |
w[j++]=v&67108863;
|
37 |
} |
38 |
return c;
|
39 |
}; |
40 |
function _7(i,x,w,j,c,n){ |
41 |
var xl=x&32767,xh=x>>15; |
42 |
while(--n>=0){ |
43 |
var l=this[i]&32767; |
44 |
var h=this[i++]>>15; |
45 |
var m=xh*l+h*xl;
|
46 |
l=xl*l+((m&32767)<<15)+w[j]+(c&1073741823); |
47 |
c=(l>>>30)+(m>>>15)+xh*h+(c>>>30); |
48 |
w[j++]=l&1073741823;
|
49 |
} |
50 |
return c;
|
51 |
}; |
52 |
function _8(i,x,w,j,c,n){ |
53 |
var xl=x&16383,xh=x>>14; |
54 |
while(--n>=0){ |
55 |
var l=this[i]&16383; |
56 |
var h=this[i++]>>14; |
57 |
var m=xh*l+h*xl;
|
58 |
l=xl*l+((m&16383)<<14)+w[j]+c; |
59 |
c=(l>>28)+(m>>14)+xh*h; |
60 |
w[j++]=l&268435455;
|
61 |
} |
62 |
return c;
|
63 |
}; |
64 |
if(_3&&(navigator.appName=="Microsoft Internet Explorer")){ |
65 |
_4.prototype.am=_7; |
66 |
_1=30;
|
67 |
}else{
|
68 |
if(_3&&(navigator.appName!="Netscape")){ |
69 |
_4.prototype.am=_6; |
70 |
_1=26;
|
71 |
}else{
|
72 |
_4.prototype.am=_8; |
73 |
_1=28;
|
74 |
} |
75 |
} |
76 |
var _9=52; |
77 |
var _a="0123456789abcdefghijklmnopqrstuvwxyz"; |
78 |
var _b=[];
|
79 |
var rr,vv;
|
80 |
rr="0".charCodeAt(0); |
81 |
for(vv=0;vv<=9;++vv){ |
82 |
_b[rr++]=vv; |
83 |
} |
84 |
rr="a".charCodeAt(0); |
85 |
for(vv=10;vv<36;++vv){ |
86 |
_b[rr++]=vv; |
87 |
} |
88 |
rr="A".charCodeAt(0); |
89 |
for(vv=10;vv<36;++vv){ |
90 |
_b[rr++]=vv; |
91 |
} |
92 |
function _c(n){ |
93 |
return _a.charAt(n);
|
94 |
}; |
95 |
function _d(s,i){ |
96 |
var c=_b[s.charCodeAt(i)];
|
97 |
return (c==null)?-1:c; |
98 |
}; |
99 |
function _e(r){ |
100 |
for(var i=this.t-1;i>=0;--i){ |
101 |
r[i]=this[i];
|
102 |
} |
103 |
r.t=this.t;
|
104 |
r.s=this.s;
|
105 |
}; |
106 |
function _f(x){ |
107 |
this.t=1; |
108 |
this.s=(x<0)?-1:0; |
109 |
if(x>0){ |
110 |
this[0]=x; |
111 |
}else{
|
112 |
if(x<-1){ |
113 |
this[0]=x+_DV; |
114 |
}else{
|
115 |
this.t=0; |
116 |
} |
117 |
} |
118 |
}; |
119 |
function nbv(i){ |
120 |
var r=_5();
|
121 |
r._fromInt(i); |
122 |
return r;
|
123 |
}; |
124 |
function _10(s,b){ |
125 |
var k;
|
126 |
if(b==16){ |
127 |
k=4;
|
128 |
}else{
|
129 |
if(b==8){ |
130 |
k=3;
|
131 |
}else{
|
132 |
if(b==256){ |
133 |
k=8;
|
134 |
}else{
|
135 |
if(b==2){ |
136 |
k=1;
|
137 |
}else{
|
138 |
if(b==32){ |
139 |
k=5;
|
140 |
}else{
|
141 |
if(b==4){ |
142 |
k=2;
|
143 |
}else{
|
144 |
this.fromRadix(s,b);
|
145 |
return;
|
146 |
} |
147 |
} |
148 |
} |
149 |
} |
150 |
} |
151 |
} |
152 |
this.t=0; |
153 |
this.s=0; |
154 |
var i=s.length,mi=false,sh=0; |
155 |
while(--i>=0){ |
156 |
var x=(k==8)?s[i]&255:_d(s,i); |
157 |
if(x<0){ |
158 |
if(s.charAt(i)=="-"){ |
159 |
mi=true;
|
160 |
} |
161 |
continue;
|
162 |
} |
163 |
mi=false;
|
164 |
if(sh==0){ |
165 |
this[this.t++]=x; |
166 |
}else{
|
167 |
if(sh+k>this._DB){ |
168 |
this[this.t-1]|=(x&((1<<(this._DB-sh))-1))<<sh; |
169 |
this[this.t++]=(x>>(this._DB-sh)); |
170 |
}else{
|
171 |
this[this.t-1]|=x<<sh; |
172 |
} |
173 |
} |
174 |
sh+=k; |
175 |
if(sh>=this._DB){ |
176 |
sh-=this._DB;
|
177 |
} |
178 |
} |
179 |
if(k==8&&(s[0]&128)!=0){ |
180 |
this.s=-1; |
181 |
if(sh>0){ |
182 |
this[this.t-1]|=((1<<(this._DB-sh))-1)<<sh; |
183 |
} |
184 |
} |
185 |
this._clamp();
|
186 |
if(mi){
|
187 |
_4.ZERO._subTo(this,this); |
188 |
} |
189 |
}; |
190 |
function _11(){ |
191 |
var c=this.s&this._DM; |
192 |
while(this.t>0&&this[this.t-1]==c){ |
193 |
--this.t;
|
194 |
} |
195 |
}; |
196 |
function _12(b){ |
197 |
if(this.s<0){ |
198 |
return "-"+this.negate().toString(b); |
199 |
} |
200 |
var k;
|
201 |
if(b==16){ |
202 |
k=4;
|
203 |
}else{
|
204 |
if(b==8){ |
205 |
k=3;
|
206 |
}else{
|
207 |
if(b==2){ |
208 |
k=1;
|
209 |
}else{
|
210 |
if(b==32){ |
211 |
k=5;
|
212 |
}else{
|
213 |
if(b==4){ |
214 |
k=2;
|
215 |
}else{
|
216 |
return this._toRadix(b); |
217 |
} |
218 |
} |
219 |
} |
220 |
} |
221 |
} |
222 |
var km=(1<<k)-1,d,m=false,r="",i=this.t; |
223 |
var p=this._DB-(i*this._DB)%k; |
224 |
if(i-->0){ |
225 |
if(p<this._DB&&(d=this[i]>>p)>0){ |
226 |
m=true;
|
227 |
r=_c(d); |
228 |
} |
229 |
while(i>=0){ |
230 |
if(p<k){
|
231 |
d=(this[i]&((1<<p)-1))<<(k-p); |
232 |
d|=this[--i]>>(p+=this._DB-k); |
233 |
}else{
|
234 |
d=(this[i]>>(p-=k))&km;
|
235 |
if(p<=0){ |
236 |
p+=this._DB;
|
237 |
--i; |
238 |
} |
239 |
} |
240 |
if(d>0){ |
241 |
m=true;
|
242 |
} |
243 |
if(m){
|
244 |
r+=_c(d); |
245 |
} |
246 |
} |
247 |
} |
248 |
return m?r:"0"; |
249 |
}; |
250 |
function _13(){ |
251 |
var r=_5();
|
252 |
_4.ZERO._subTo(this,r);
|
253 |
return r;
|
254 |
}; |
255 |
function _14(){ |
256 |
return (this.s<0)?this.negate():this; |
257 |
}; |
258 |
function _15(a){ |
259 |
var r=this.s-a.s; |
260 |
if(r){
|
261 |
return r;
|
262 |
} |
263 |
var i=this.t; |
264 |
r=i-a.t; |
265 |
if(r){
|
266 |
return r;
|
267 |
} |
268 |
while(--i>=0){ |
269 |
if((r=this[i]-a[i])){ |
270 |
return r;
|
271 |
} |
272 |
} |
273 |
return 0; |
274 |
}; |
275 |
function _16(x){ |
276 |
var r=1,t; |
277 |
if((t=x>>>16)){ |
278 |
x=t; |
279 |
r+=16;
|
280 |
} |
281 |
if((t=x>>8)){ |
282 |
x=t; |
283 |
r+=8;
|
284 |
} |
285 |
if((t=x>>4)){ |
286 |
x=t; |
287 |
r+=4;
|
288 |
} |
289 |
if((t=x>>2)){ |
290 |
x=t; |
291 |
r+=2;
|
292 |
} |
293 |
if((t=x>>1)){ |
294 |
x=t; |
295 |
r+=1;
|
296 |
} |
297 |
return r;
|
298 |
}; |
299 |
function _17(){ |
300 |
if(this.t<=0){ |
301 |
return 0; |
302 |
} |
303 |
return this._DB*(this.t-1)+_16(this[this.t-1]^(this.s&this._DM)); |
304 |
}; |
305 |
function _18(n,r){ |
306 |
var i;
|
307 |
for(i=this.t-1;i>=0;--i){ |
308 |
r[i+n]=this[i];
|
309 |
} |
310 |
for(i=n-1;i>=0;--i){ |
311 |
r[i]=0;
|
312 |
} |
313 |
r.t=this.t+n;
|
314 |
r.s=this.s;
|
315 |
}; |
316 |
function _19(n,r){ |
317 |
for(var i=n;i<this.t;++i){ |
318 |
r[i-n]=this[i];
|
319 |
} |
320 |
r.t=Math.max(this.t-n,0); |
321 |
r.s=this.s;
|
322 |
}; |
323 |
function _1a(n,r){ |
324 |
var bs=n%this._DB; |
325 |
var cbs=this._DB-bs; |
326 |
var bm=(1<<cbs)-1; |
327 |
var ds=Math.floor(n/this._DB),c=(this.s<<bs)&this._DM,i; |
328 |
for(i=this.t-1;i>=0;--i){ |
329 |
r[i+ds+1]=(this[i]>>cbs)|c; |
330 |
c=(this[i]&bm)<<bs;
|
331 |
} |
332 |
for(i=ds-1;i>=0;--i){ |
333 |
r[i]=0;
|
334 |
} |
335 |
r[ds]=c; |
336 |
r.t=this.t+ds+1; |
337 |
r.s=this.s;
|
338 |
r._clamp(); |
339 |
}; |
340 |
function _1b(n,r){ |
341 |
r.s=this.s;
|
342 |
var ds=Math.floor(n/this._DB); |
343 |
if(ds>=this.t){ |
344 |
r.t=0;
|
345 |
return;
|
346 |
} |
347 |
var bs=n%this._DB; |
348 |
var cbs=this._DB-bs; |
349 |
var bm=(1<<bs)-1; |
350 |
r[0]=this[ds]>>bs; |
351 |
for(var i=ds+1;i<this.t;++i){ |
352 |
r[i-ds-1]|=(this[i]&bm)<<cbs; |
353 |
r[i-ds]=this[i]>>bs;
|
354 |
} |
355 |
if(bs>0){ |
356 |
r[this.t-ds-1]|=(this.s&bm)<<cbs; |
357 |
} |
358 |
r.t=this.t-ds;
|
359 |
r._clamp(); |
360 |
}; |
361 |
function _1c(a,r){ |
362 |
var i=0,c=0,m=Math.min(a.t,this.t); |
363 |
while(i<m){
|
364 |
c+=this[i]-a[i];
|
365 |
r[i++]=c&this._DM;
|
366 |
c>>=this._DB;
|
367 |
} |
368 |
if(a.t<this.t){ |
369 |
c-=a.s; |
370 |
while(i<this.t){ |
371 |
c+=this[i];
|
372 |
r[i++]=c&this._DM;
|
373 |
c>>=this._DB;
|
374 |
} |
375 |
c+=this.s;
|
376 |
}else{
|
377 |
c+=this.s;
|
378 |
while(i<a.t){
|
379 |
c-=a[i]; |
380 |
r[i++]=c&this._DM;
|
381 |
c>>=this._DB;
|
382 |
} |
383 |
c-=a.s; |
384 |
} |
385 |
r.s=(c<0)?-1:0; |
386 |
if(c<-1){ |
387 |
r[i++]=this._DV+c;
|
388 |
}else{
|
389 |
if(c>0){ |
390 |
r[i++]=c; |
391 |
} |
392 |
} |
393 |
r.t=i; |
394 |
r._clamp(); |
395 |
}; |
396 |
function _1d(a,r){ |
397 |
var x=this.abs(),y=a.abs(); |
398 |
var i=x.t;
|
399 |
r.t=i+y.t; |
400 |
while(--i>=0){ |
401 |
r[i]=0;
|
402 |
} |
403 |
for(i=0;i<y.t;++i){ |
404 |
r[i+x.t]=x.am(0,y[i],r,i,0,x.t); |
405 |
} |
406 |
r.s=0;
|
407 |
r._clamp(); |
408 |
if(this.s!=a.s){ |
409 |
_4.ZERO._subTo(r,r); |
410 |
} |
411 |
}; |
412 |
function _1e(r){ |
413 |
var x=this.abs(); |
414 |
var i=r.t=2*x.t; |
415 |
while(--i>=0){ |
416 |
r[i]=0;
|
417 |
} |
418 |
for(i=0;i<x.t-1;++i){ |
419 |
var c=x.am(i,x[i],r,2*i,0,1); |
420 |
if((r[i+x.t]+=x.am(i+1,2*x[i],r,2*i+1,c,x.t-i-1))>=x._DV){ |
421 |
r[i+x.t]-=x._DV; |
422 |
r[i+x.t+1]=1; |
423 |
} |
424 |
} |
425 |
if(r.t>0){ |
426 |
r[r.t-1]+=x.am(i,x[i],r,2*i,0,1); |
427 |
} |
428 |
r.s=0;
|
429 |
r._clamp(); |
430 |
}; |
431 |
function _1f(m,q,r){ |
432 |
var pm=m.abs();
|
433 |
if(pm.t<=0){ |
434 |
return;
|
435 |
} |
436 |
var pt=this.abs(); |
437 |
if(pt.t<pm.t){
|
438 |
if(q!=null){ |
439 |
q._fromInt(0);
|
440 |
} |
441 |
if(r!=null){ |
442 |
this._copyTo(r);
|
443 |
} |
444 |
return;
|
445 |
} |
446 |
if(r==null){ |
447 |
r=_5(); |
448 |
} |
449 |
var y=_5(),ts=this.s,ms=m.s; |
450 |
var nsh=this._DB-_16(pm[pm.t-1]); |
451 |
if(nsh>0){ |
452 |
pm._lShiftTo(nsh,y); |
453 |
pt._lShiftTo(nsh,r); |
454 |
}else{
|
455 |
pm._copyTo(y); |
456 |
pt._copyTo(r); |
457 |
} |
458 |
var ys=y.t;
|
459 |
var y0=y[ys-1]; |
460 |
if(y0==0){ |
461 |
return;
|
462 |
} |
463 |
var yt=y0*(1<<this._F1)+((ys>1)?y[ys-2]>>this._F2:0); |
464 |
var d1=this._FV/yt,d2=(1<<this._F1)/yt,e=1<<this._F2; |
465 |
var i=r.t,j=i-ys,t=(q==null)?_5():q; |
466 |
y._dlShiftTo(j,t); |
467 |
if(r.compareTo(t)>=0){ |
468 |
r[r.t++]=1;
|
469 |
r._subTo(t,r); |
470 |
} |
471 |
_4.ONE._dlShiftTo(ys,t); |
472 |
t._subTo(y,y); |
473 |
while(y.t<ys){
|
474 |
y[y.t++]=0;
|
475 |
} |
476 |
while(--j>=0){ |
477 |
var qd=(r[--i]==y0)?this._DM:Math.floor(r[i]*d1+(r[i-1]+e)*d2); |
478 |
if((r[i]+=y.am(0,qd,r,j,0,ys))<qd){ |
479 |
y._dlShiftTo(j,t); |
480 |
r._subTo(t,r); |
481 |
while(r[i]<--qd){
|
482 |
r._subTo(t,r); |
483 |
} |
484 |
} |
485 |
} |
486 |
if(q!=null){ |
487 |
r._drShiftTo(ys,q); |
488 |
if(ts!=ms){
|
489 |
_4.ZERO._subTo(q,q); |
490 |
} |
491 |
} |
492 |
r.t=ys; |
493 |
r._clamp(); |
494 |
if(nsh>0){ |
495 |
r._rShiftTo(nsh,r); |
496 |
} |
497 |
if(ts<0){ |
498 |
_4.ZERO._subTo(r,r); |
499 |
} |
500 |
}; |
501 |
function _20(a){ |
502 |
var r=_5();
|
503 |
this.abs()._divRemTo(a,null,r); |
504 |
if(this.s<0&&r.compareTo(_4.ZERO)>0){ |
505 |
a._subTo(r,r); |
506 |
} |
507 |
return r;
|
508 |
}; |
509 |
function _21(m){ |
510 |
this.m=m;
|
511 |
}; |
512 |
function _22(x){ |
513 |
if(x.s<0||x.compareTo(this.m)>=0){ |
514 |
return x.mod(this.m); |
515 |
}else{
|
516 |
return x;
|
517 |
} |
518 |
}; |
519 |
function _23(x){ |
520 |
return x;
|
521 |
}; |
522 |
function _24(x){ |
523 |
x._divRemTo(this.m,null,x); |
524 |
}; |
525 |
function _25(x,y,r){ |
526 |
x._multiplyTo(y,r); |
527 |
this.reduce(r);
|
528 |
}; |
529 |
function _26(x,r){ |
530 |
x._squareTo(r); |
531 |
this.reduce(r);
|
532 |
}; |
533 |
dojo.extend(_21,{convert:_22,revert:_23,reduce:_24,mulTo:_25,sqrTo:_26}); |
534 |
function _27(){ |
535 |
if(this.t<1){ |
536 |
return 0; |
537 |
} |
538 |
var x=this[0]; |
539 |
if((x&1)==0){ |
540 |
return 0; |
541 |
} |
542 |
var y=x&3; |
543 |
y=(y*(2-(x&15)*y))&15; |
544 |
y=(y*(2-(x&255)*y))&255; |
545 |
y=(y*(2-(((x&65535)*y)&65535)))&65535; |
546 |
y=(y*(2-x*y%this._DV))%this._DV; |
547 |
return (y>0)?this._DV-y:-y; |
548 |
}; |
549 |
function _28(m){ |
550 |
this.m=m;
|
551 |
this.mp=m._invDigit();
|
552 |
this.mpl=this.mp&32767; |
553 |
this.mph=this.mp>>15; |
554 |
this.um=(1<<(m._DB-15))-1; |
555 |
this.mt2=2*m.t; |
556 |
}; |
557 |
function _29(x){ |
558 |
var r=_5();
|
559 |
x.abs()._dlShiftTo(this.m.t,r);
|
560 |
r._divRemTo(this.m,null,r); |
561 |
if(x.s<0&&r.compareTo(_4.ZERO)>0){ |
562 |
this.m._subTo(r,r);
|
563 |
} |
564 |
return r;
|
565 |
}; |
566 |
function _2a(x){ |
567 |
var r=_5();
|
568 |
x._copyTo(r); |
569 |
this.reduce(r);
|
570 |
return r;
|
571 |
}; |
572 |
function _2b(x){ |
573 |
while(x.t<=this.mt2){ |
574 |
x[x.t++]=0;
|
575 |
} |
576 |
for(var i=0;i<this.m.t;++i){ |
577 |
var j=x[i]&32767; |
578 |
var u0=(j*this.mpl+(((j*this.mph+(x[i]>>15)*this.mpl)&this.um)<<15))&x._DM; |
579 |
j=i+this.m.t;
|
580 |
x[j]+=this.m.am(0,u0,x,i,0,this.m.t); |
581 |
while(x[j]>=x._DV){
|
582 |
x[j]-=x._DV; |
583 |
x[++j]++; |
584 |
} |
585 |
} |
586 |
x._clamp(); |
587 |
x._drShiftTo(this.m.t,x);
|
588 |
if(x.compareTo(this.m)>=0){ |
589 |
x._subTo(this.m,x);
|
590 |
} |
591 |
}; |
592 |
function _2c(x,r){ |
593 |
x._squareTo(r); |
594 |
this.reduce(r);
|
595 |
}; |
596 |
function _2d(x,y,r){ |
597 |
x._multiplyTo(y,r); |
598 |
this.reduce(r);
|
599 |
}; |
600 |
dojo.extend(_28,{convert:_29,revert:_2a,reduce:_2b,mulTo:_2d,sqrTo:_2c}); |
601 |
function _2e(){ |
602 |
return ((this.t>0)?(this[0]&1):this.s)==0; |
603 |
}; |
604 |
function _2f(e,z){ |
605 |
if(e>4294967295||e<1){ |
606 |
return _4.ONE;
|
607 |
} |
608 |
var r=_5(),r2=_5(),g=z.convert(this),i=_16(e)-1; |
609 |
g._copyTo(r); |
610 |
while(--i>=0){ |
611 |
z.sqrTo(r,r2); |
612 |
if((e&(1<<i))>0){ |
613 |
z.mulTo(r2,g,r); |
614 |
}else{
|
615 |
var t=r;
|
616 |
r=r2; |
617 |
r2=t; |
618 |
} |
619 |
} |
620 |
return z.revert(r);
|
621 |
}; |
622 |
function _30(e,m){ |
623 |
var z;
|
624 |
if(e<256||m._isEven()){ |
625 |
z=new _21(m);
|
626 |
}else{
|
627 |
z=new _28(m);
|
628 |
} |
629 |
return this._exp(e,z); |
630 |
}; |
631 |
dojo.extend(_4,{_DB:_1,_DM:(1<<_1)-1,_DV:1<<_1,_FV:Math.pow(2,_9),_F1:_9-_1,_F2:2*_1-_9,_copyTo:_e,_fromInt:_f,_fromString:_10,_clamp:_11,_dlShiftTo:_18,_drShiftTo:_19,_lShiftTo:_1a,_rShiftTo:_1b,_subTo:_1c,_multiplyTo:_1d,_squareTo:_1e,_divRemTo:_1f,_invDigit:_27,_isEven:_2e,_exp:_2f,toString:_12,negate:_13,abs:_14,compareTo:_15,bitLength:_17,mod:_20,modPowInt:_30}); |
632 |
dojo._mixin(_4,{ZERO:nbv(0),ONE:nbv(1),_nbi:_5,_nbv:nbv,_nbits:_16,_Montgomery:_28}); |
633 |
dojox.math.BigInteger=_4; |
634 |
})(); |
635 |
} |