Add modPow(int exponent, int modulus) method to int abstract class.

Add modPow(int exponent, int modulus) method to int abstract class.
Provide a dart2js implementation.

R=floitsch@google.com, lrn@google.com

Committed: https://code.google.com/p/dart/source/detail?r=43572

[regis, 2015-02-05 20:14:44]

regis@google.com changed reviewers:
+ lrn@google.com

[regis, 2015-02-06 18:47:36]

regis@google.com changed reviewers:
+ floitsch@google.com

[regis, 2015-02-06 18:47:36]

ping

[Lasse Reichstein Nielsen, 2015-02-06 19:57:04]

lgtm

https://codereview.chromium.org/896393004/diff/1/sdk/lib/_internal/compiler/j...
File sdk/lib/_internal/compiler/js_lib/js_number.dart (right):

https://codereview.chromium.org/896393004/diff/1/sdk/lib/_internal/compiler/j...
sdk/lib/_internal/compiler/js_lib/js_number.dart:372: if (m is! int || m <= 0)
throw new ArgumentError(m);
Maybe not worth it, but you can use RangeError for the e<0 and m<=0 cases.

https://codereview.chromium.org/896393004/diff/1/sdk/lib/_internal/compiler/j...
sdk/lib/_internal/compiler/js_lib/js_number.dart:373: if (e < 1) return 1;
Why not 
  if (e == 0) ...

https://codereview.chromium.org/896393004/diff/1/sdk/lib/_internal/compiler/j...
sdk/lib/_internal/compiler/js_lib/js_number.dart:383: e >>= 1;
Using bit-operations restricts e to 2^32. Maybe use  
  if (e & 1 != 0) {
    ...
    e -= 1; 
  }
  e ~/ 2;
?

https://codereview.chromium.org/896393004/diff/1/sdk/lib/_internal/compiler/j...
sdk/lib/_internal/compiler/js_lib/js_number.dart:384: b = (b * b) % m;
I guess %m is expensive. Would it be worth it to do:
  b *= b;
  if (b > m) b %= m;
to avoid unnecessary modulos?

https://codereview.chromium.org/896393004/diff/1/sdk/lib/core/int.dart
File sdk/lib/core/int.dart (right):

https://codereview.chromium.org/896393004/diff/1/sdk/lib/core/int.dart#newcod...
sdk/lib/core/int.dart:110: * negative or zero.
I think we have migrated to writing this as:

  The [exponent] must be non-negative and [modulus] must be positive.

[Lasse Reichstein Nielsen, 2015-02-06 19:57:45]

but wait for Florian too.

[floitsch, 2015-02-06 20:05:19]

LGTM.

https://codereview.chromium.org/896393004/diff/1/sdk/lib/_internal/compiler/j...
File sdk/lib/_internal/compiler/js_lib/js_number.dart (right):

https://codereview.chromium.org/896393004/diff/1/sdk/lib/_internal/compiler/j...
sdk/lib/_internal/compiler/js_lib/js_number.dart:369: // Return pow(this, e) %
m.
Returns

https://codereview.chromium.org/896393004/diff/1/sdk/lib/_internal/compiler/j...
sdk/lib/_internal/compiler/js_lib/js_number.dart:383: e >>= 1;
On 2015/02/06 19:57:03, Lasse Reichstein Nielsen wrote:
> Using bit-operations restricts e to 2^32. Maybe use  
>   if (e & 1 != 0) {
>     ...
>     e -= 1; 
>   }
>   e ~/ 2;
> ?

I'm not sure it's worth it. But it would allow the exponent to go up to 53 bits.

https://codereview.chromium.org/896393004/diff/1/sdk/lib/_internal/compiler/j...
sdk/lib/_internal/compiler/js_lib/js_number.dart:384: b = (b * b) % m;
On 2015/02/06 19:57:03, Lasse Reichstein Nielsen wrote:
> I guess %m is expensive. Would it be worth it to do:
>   b *= b;
>   if (b > m) b %= m;
> to avoid unnecessary modulos?

I would hope that % is optimized for that case anyway.

[regis, 2015-02-06 21:46:02]

New patchsets have been uploaded after l-g-t-m from
lrn@google.com,floitsch@google.com

[regis, 2015-02-06 21:46:38]

Committed patchset #2 (id:20001) manually as r43572 (presubmit successful).

[regis, 2015-02-06 21:46:54]

Thanks!

https://codereview.chromium.org/896393004/diff/1/sdk/lib/_internal/compiler/j...
File sdk/lib/_internal/compiler/js_lib/js_number.dart (right):

https://codereview.chromium.org/896393004/diff/1/sdk/lib/_internal/compiler/j...
sdk/lib/_internal/compiler/js_lib/js_number.dart:369: // Return pow(this, e) %
m.
On 2015/02/06 20:05:19, floitsch wrote:
> Returns

Done.

https://codereview.chromium.org/896393004/diff/1/sdk/lib/_internal/compiler/j...
sdk/lib/_internal/compiler/js_lib/js_number.dart:372: if (m is! int || m <= 0)
throw new ArgumentError(m);
On 2015/02/06 19:57:03, Lasse Reichstein Nielsen wrote:
> Maybe not worth it, but you can use RangeError for the e<0 and m<=0 cases.

Done.

https://codereview.chromium.org/896393004/diff/1/sdk/lib/_internal/compiler/j...
sdk/lib/_internal/compiler/js_lib/js_number.dart:373: if (e < 1) return 1;
On 2015/02/06 19:57:03, Lasse Reichstein Nielsen wrote:
> Why not 
>   if (e == 0) ...

Done.

https://codereview.chromium.org/896393004/diff/1/sdk/lib/_internal/compiler/j...
sdk/lib/_internal/compiler/js_lib/js_number.dart:383: e >>= 1;
On 2015/02/06 19:57:03, Lasse Reichstein Nielsen wrote:
> Using bit-operations restricts e to 2^32. Maybe use  
>   if (e & 1 != 0) {
>     ...
>     e -= 1; 
>   }
>   e ~/ 2;
> ?

I replaced e & 1 != 0 by e.isOdd, since & is a bit operation. I am not sure if
using isOdd makes a difference in dart2js. Decrementing e is actually not
necessary.
I also replaced >>= 1 by ~/= 2.

https://codereview.chromium.org/896393004/diff/1/sdk/lib/_internal/compiler/j...
sdk/lib/_internal/compiler/js_lib/js_number.dart:384: b = (b * b) % m;
On 2015/02/06 19:57:03, Lasse Reichstein Nielsen wrote:
> I guess %m is expensive. Would it be worth it to do:
>   b *= b;
>   if (b > m) b %= m;
> to avoid unnecessary modulos?

The vm is optimizing this case. I do not know if dart2js does it too. I left the
code as is (but fixed the bad indentation).

https://codereview.chromium.org/896393004/diff/1/sdk/lib/core/int.dart
File sdk/lib/core/int.dart (right):

https://codereview.chromium.org/896393004/diff/1/sdk/lib/core/int.dart#newcod...
sdk/lib/core/int.dart:110: * negative or zero.
On 2015/02/06 19:57:04, Lasse Reichstein Nielsen wrote:
> I think we have migrated to writing this as:
> 
>   The [exponent] must be non-negative and [modulus] must be positive.

Done.