Project

General

Profile

Statistics
| Revision:

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
}