Add tests for gcd, modInverse and modPow that also run on dart2js.

Add tests for gcd, modInverse and modPow that also run on dart2js.

R=regis@google.com, sgjesse@google.com

Committed: https://github.com/dart-lang/sdk/commit/3a0edfba72e27781e98f5debfafc5f01450bd423

[Lasse Reichstein Nielsen, 2015-06-25 12:59:51]

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

[regis, 2015-06-25 17:03:13]

lgtm

Thanks for writing this test.

https://codereview.chromium.org/1205363003/diff/1/runtime/lib/bigint.dart
File runtime/lib/bigint.dart (right):

https://codereview.chromium.org/1205363003/diff/1/runtime/lib/bigint.dart#new...
runtime/lib/bigint.dart:1565: while (x_digits[0].isEven && y_digits[0].isEven) {
Thanks
You could even write ((x_digits[0] & 1) == 0) && ((y_digits[0] & 1) == 0) as
below.

[Søren Gjesse, 2015-06-26 06:19:45]

lgtm

[Lasse Reichstein Nielsen, 2015-06-26 08:40:40]

https://codereview.chromium.org/1205363003/diff/1/runtime/lib/bigint.dart
File runtime/lib/bigint.dart (right):

https://codereview.chromium.org/1205363003/diff/1/runtime/lib/bigint.dart#new...
runtime/lib/bigint.dart:1565: while (x_digits[0].isEven && y_digits[0].isEven) {
Done. 
Would it make sense to count the leading zero-bits and do one rsh, instead of
doing repeated rsh with 1? Or is this as rare a case?

https://codereview.chromium.org/1205363003/diff/20001/runtime/lib/bigint.dart
File runtime/lib/bigint.dart (right):

https://codereview.chromium.org/1205363003/diff/20001/runtime/lib/bigint.dart...
runtime/lib/bigint.dart:1754: // }
Not sure why this doesn't work - maybe it's because _lsh doesn't clear the low
bits, and because m_used below is too low (it should also include the bits of
s).
For 
  (693 * pow(2, 99)),gcd(609 * pow(2, 99))
which should give 21 * pow(2, 99), it gives just 21.
That would match keeping the low bits at 21 and forgetting the high bits.

I tried changing  _lsh(...)  to  m_used = _dlShiftDigits(...) , but the v_digits
array isn't big enough for that (it has an odd length equal to m_used).

So, quick fix that works is to do << after creating a new bigint.

[Lasse Reichstein Nielsen, 2015-06-26 09:05:16]

Committed patchset #3 (id:40001) manually as
3a0edfba72e27781e98f5debfafc5f01450bd423 (presubmit successful).

[regis, 2015-06-26 21:49:46]

https://codereview.chromium.org/1205363003/diff/20001/runtime/lib/bigint.dart
File runtime/lib/bigint.dart (right):

https://codereview.chromium.org/1205363003/diff/20001/runtime/lib/bigint.dart...
runtime/lib/bigint.dart:1754: // }
On 2015/06/26 08:40:40, Lasse Reichstein Nielsen wrote:
> Not sure why this doesn't work - maybe it's because _lsh doesn't clear the low
> bits, and because m_used below is too low (it should also include the bits of
> s).
> For 
>   (693 * pow(2, 99)),gcd(609 * pow(2, 99))
> which should give 21 * pow(2, 99), it gives just 21.
> That would match keeping the low bits at 21 and forgetting the high bits.
> 

That was totally broken. Good that you wrote some gcd tests with even operands.
The problem is that left shift operations need one extra digit (one extra 64-bit
digit on 64-bit platforms), and v_digits does not account for it. Its allocation
length m_len needs adjustment.

Also, the intrinsic _lsh does not clear the low bits, and since we shift in
place, this is not the right one to use.

> I tried changing  _lsh(...)  to  m_used = _dlShiftDigits(...) , but the
v_digits
> array isn't big enough for that (it has an odd length equal to m_used).
> 

That was the right idea, but _dlShiftDigits is the wrong one to use, since it is
a digit shift. We need a bit shift, i.e. _lShiftDigits.

The minimum length calculation in _lShiftDigits and _lShift was too conservative
and can be relaxed.

I'll send a cl to Srdjan (cc'ed) shortly.
 
> So, quick fix that works is to do << after creating a new bigint.

That was the proper workaround. Thanks.