Closed adam-singer closed 11 years ago
diff --git a/lib/src/BigInteger_v8/big_integer.dart b/lib/src/BigInteger_v8/big_integer.dart index 10cbea2..a0c1c45 100644 --- a/lib/src/BigInteger_v8/big_integer.dart +++ b/lib/src/BigInteger_v8/big_integer.dart @@ -111,7 +111,7 @@ class Montgomery { var u0 = (j*this.mpl+(((j*this.mph+(x_array[i]>>15)*this.mpl)&this.um)<<15))&BigInteger.BI_DM; // use am to combine the multiply-shift-add into one call j = i+this.m.t; - x_array[j] += this.m.am(0,u0,x,i,0,this.m.t); + x_array[j] += (this.m.am)(0,u0,x,i,0,this.m.t); // propagate carry while(x_array[j] >= BigInteger.BI_DV) { x_array[j] -= BigInteger.BI_DV; @@ -227,6 +227,26 @@ class NullExp { // typedef AmplitudeModulation + +/** + * This class wraps a Dart List and provides a JS-like behaviour. + * i.e. Storing an out-of-bounds element grows the list automatically. + */ +class JSArray<T> { + operator [](var index) { + return data[index]; + } + + operator []=(var index, var value) { + if (index > data.length - 1) { + data.length = index + 1; + } + return data[index] = value; + } + + List<T> data = new List<T>(); +} + /** * Basic dart [BigInteger] class. Implementation works across * dart and dart2js. @@ -272,7 +292,7 @@ class BigInteger { * support a rapid implementation. This will be replaced at a later * time for a [List] data structure. */ - Map array; // TODO: create an array implementation that can handle out of bounds issues. + var array; Function am; @@ -322,8 +342,11 @@ class BigInteger { // Setup all the global scope js code here _setupDigitConversions(); _lplim = (1<<26)~/_lowprimes[_lowprimes.length-1]; + // am3 works better on x64, while am3 is faster on 32-bit platforms. + //_setupEngine(_am4, 26); _setupEngine(_am3, 28); - this.array = new Map(); + + this.array = new JSArray<int>(); if (a != null) { if (a is int) { @@ -358,7 +381,23 @@ class BigInteger { } return c; } + + _am4(i,x,w,j,c,n) { + var this_array = this.array; + var w_array = w.array; + var xl = x.toInt()&0x1fff, xh = x.toInt()>>13; + while(--n >= 0) { + var l = this_array[i]&0x1fff; + var h = this_array[i++]>>13; + var m = xh*l+h*xl; + l = xl*l+((m&0x1fff)<<13)+w_array[j]+c; + c = (l>>26)+(m>>13)+xh*h; + w_array[j++] = l&0x3ffffff; + } + return c; + } + /** * am3/28 is best for SM, Rhino, but am4/26 is best for v8. * Kestrel (Opera 9.5) gets its best result with am4/26. @@ -697,7 +736,7 @@ class BigInteger { var i = x.t; r.t = i+y.t; while(--i >= 0) r_array[i] = 0; - for(i = 0; i < y.t; ++i) r_array[i+x.t] = x.am(0,y_array[i],r,i,0,x.t); + for(i = 0; i < y.t; ++i) r_array[i+x.t] = (x.am)(0,y_array[i],r,i,0,x.t); r.s = 0; r.clamp(); @@ -716,13 +755,13 @@ class BigInteger { var i = r.t = 2*x.t; while(--i >= 0) r_array[i] = 0; for(i = 0; i < x.t-1; ++i) { - var c = x.am(i,x_array[i],r,2*i,0,1); - if((r_array[i+x.t]+=x.am(i+1,2*x_array[i],r,2*i+1,c,x.t-i-1)) >= BI_DV) { + var c = (x.am)(i,x_array[i],r,2*i,0,1); + if((r_array[i+x.t]+=(x.am)(i+1,2*x_array[i],r,2*i+1,c,x.t-i-1)) >= BI_DV) { r_array[i+x.t] -= BI_DV; r_array[i+x.t+1] = 1; } } - if(r.t > 0) r_array[r.t-1] += x.am(i,x_array[i],r,2*i,0,1); + if(r.t > 0) r_array[r.t-1] += (x.am)(i,x_array[i],r,2*i,0,1); r.s = 0; r.clamp(); } @@ -770,7 +809,7 @@ class BigInteger { while(--j >= 0) { // Estimate quotient digit var qd = (r_array[--i]==y0)?BI_DM:(r_array[i]*d1+(r_array[i-1]+e)*d2).floor(); - if((r_array[i]+=y.am(0,qd,r,j,0,ys)) < qd) { // Try it out + if((r_array[i]+=(y.am)(0,qd,r,j,0,ys)) < qd) { // Try it out y.dlShiftTo(j,t); r.subTo(t,r); while(r_array[i] < --qd) r.subTo(t,r); @@ -1290,7 +1329,7 @@ class BigInteger { /** this *= n, this >= 0, 1 < n < [BI_DV] */ dMultiply(n) { var this_array = this.array; - this_array[this.t] = this.am(0,n-1,this,0,0,this.t); + this_array[this.t] = (this.am)(0,n-1,this,0,0,this.t); ++this.t; this.clamp(); } @@ -1325,8 +1364,8 @@ class BigInteger { r.t = i; while(i > 0) r_array[--i] = 0; var j; - for(j = r.t-this.t; i < j; ++i) r_array[i+this.t] = this.am(0,a_array[i],r,i,0,this.t); - for(j = Mathx.min(a.t,n); i < j; ++i) this.am(0,a_array[i],r,i,0,n-i); + for(j = r.t-this.t; i < j; ++i) r_array[i+this.t] = (this.am)(0,a_array[i],r,i,0,this.t); + for(j = Mathx.min(a.t,n); i < j; ++i) (this.am)(0,a_array[i],r,i,0,n-i); r.clamp(); } @@ -1342,7 +1381,7 @@ class BigInteger { r.s = 0; // assumes a,this >= 0 while(--i >= 0) r_array[i] = 0; for(i = Mathx.max(n-this.t,0); i < a.t; ++i) - r_array[this.t+i-n] = this.am(n-i,a_array[i],r,0,0,this.t+i-n); + r_array[this.t+i-n] = (this.am)(n-i,a_array[i],r,0,0,this.t+i-n); r.clamp(); r.drShiftTo(1,r); }