Implement math.gcd in dart.

Addressing Issue 5991, where functions are requested for:

* greatest common denominator
* modulo inverse
* modulo exponentiation

In addition, I implemented functions for least common multiple and extended gcd, as they are so closely related.

These functions are respectively named gcd(), invert(), modexp(), lcm(), gcdext(), provided in the math package,
and tested in the math package.

When passed arguments larger than 2^53, a javascript implementation of dart will yield unpredictable results,
as is true with all of the dart:int methods.

Some of the function names are arbitrary, as they go by different names in different languages:

* For modular multiplicative inverse, I chose "invert." It goes by "invert" in GMP [1], "modInverse" in Java and Go,
"invmod" in Julia, "PowerMod" in Mathematica, and "pow" in Python.
* For modular exponentiation, I chose "powmod." It goes by "powm" in GMP, "exp" in Go, "modPow" in Java,
"powermod" in Julia and Mathematica, and "pow" in Python (optional arg).
* For extended gcd, I chose "gcdext." It goes by "gcdext" in GMP, "gcd" in Go (optional return args), "gcdx" in Julia,
and "ExtendedGCD" in Mathematica.

BUG= https://code.google.com/p/dart/issues/detail?id=5991

[1] https://gmplib.org/

R=lrn@google.com

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

[srawlins, 2014-08-14 00:57:54]

Hi floitsch@, would this one go to you?

I'd love general input, like: should I split into a separate test? Should I
comment more? Test more? etc.

Then I'd like to implement lcm, inverse modulo, and modulo exponent. Let me
know.

Thanks!

[Lasse Reichstein Nielsen, 2014-08-19 08:31:31]

https://codereview.chromium.org/475463005/diff/20001/sdk/lib/math/math.dart
File sdk/lib/math/math.dart (right):

https://codereview.chromium.org/475463005/diff/20001/sdk/lib/math/math.dart#n...
sdk/lib/math/math.dart:260: int gcd(int a, int b) {
Adding an uncapitalized top-level name to a dart: library is considered a
breaking change.
If someone has a class
  class C {
     int gcd;
     bool isGcd(int x) => x == gcd;
  }
it will break after importing the new math library.

For this reason, I would prefer to put gcd in package:math instead of dart:math.

https://codereview.chromium.org/475463005/diff/20001/sdk/lib/math/math.dart#n...
sdk/lib/math/math.dart:275: b >>= 1;
This may be surprising when it doesn't work for values >2^32 in dart2js.
Use "a ~/= 2" instead of "a >>= 1".
Dittos below.

https://codereview.chromium.org/475463005/diff/20001/sdk/lib/math/math.dart#n...
sdk/lib/math/math.dart:278: while ((a & 1) == 0) a >>= 1;
a.isEven, ditto b below.

https://codereview.chromium.org/475463005/diff/20001/sdk/lib/math/math.dart#n...
sdk/lib/math/math.dart:290: return a << powersOfTwo;
Same problem. You could keep powersOf2 as a factor instead:

int powerOfTwo = 1;
powerOfTwo*=2;  // instead of powersOfTwo++

return a * powerOfTwo;

https://codereview.chromium.org/475463005/diff/20001/tests/lib/math/math_test...
File tests/lib/math/math_test.dart (right):

https://codereview.chromium.org/475463005/diff/20001/tests/lib/math/math_test...
tests/lib/math/math_test.dart:203: Expect.equals(pow(2, 63)*3, gcd(pow(2,
64)*3*5, pow(2,63)*3*7));
This is very quickly reduced by dividing by 2 63 times. 
How about keeping the number big without factors of two:
  gcd(3 * 982451653, 7 * 982451653);

https://codereview.chromium.org/475463005/diff/20001/tests/lib/math/math_test...
tests/lib/math/math_test.dart:204: }
Do these tests succeed on dart2js?

If so, you need more tests :)

[srawlins, 2014-08-19 22:35:23]

Sorry, I was burned by tests/lib/lib.status, which contains "math/math_test:
RuntimeError", which means that testGcd() was never even being run, because
testExp() results in a RunTime error.

I'll rework this making sure my tests are being run with dart2js...

[srawlins, 2014-08-20 01:06:27]

Thanks for all the comments, lrn@. Now that I've got the structure more correct,
I can add perhaps modular exponent.

https://codereview.chromium.org/475463005/diff/20001/sdk/lib/math/math.dart
File sdk/lib/math/math.dart (right):

https://codereview.chromium.org/475463005/diff/20001/sdk/lib/math/math.dart#n...
sdk/lib/math/math.dart:260: int gcd(int a, int b) {
On 2014/08/19 08:31:31, Lasse Reichstein Nielsen wrote:
> Adding an uncapitalized top-level name to a dart: library is considered a
> breaking change.
> If someone has a class
>   class C {
>      int gcd;
>      bool isGcd(int x) => x == gcd;
>   }
> it will break after importing the new math library.
> 
> For this reason, I would prefer to put gcd in package:math instead of
dart:math.

Done and done. Thanks for this recommendation. I've also split the test out.

https://codereview.chromium.org/475463005/diff/20001/sdk/lib/math/math.dart#n...
sdk/lib/math/math.dart:275: b >>= 1;
On 2014/08/19 08:31:31, Lasse Reichstein Nielsen wrote:
> This may be surprising when it doesn't work for values >2^32 in dart2js.
> Use "a ~/= 2" instead of "a >>= 1".
> Dittos below.

Done.

https://codereview.chromium.org/475463005/diff/20001/sdk/lib/math/math.dart#n...
sdk/lib/math/math.dart:278: while ((a & 1) == 0) a >>= 1;
On 2014/08/19 08:31:31, Lasse Reichstein Nielsen wrote:
> a.isEven, ditto b below.

Done.

https://codereview.chromium.org/475463005/diff/20001/sdk/lib/math/math.dart#n...
sdk/lib/math/math.dart:290: return a << powersOfTwo;
On 2014/08/19 08:31:31, Lasse Reichstein Nielsen wrote:
> Same problem. You could keep powersOf2 as a factor instead:
> 
> int powerOfTwo = 1;
> powerOfTwo*=2;  // instead of powersOfTwo++
> 
> return a * powerOfTwo;

Done.

https://codereview.chromium.org/475463005/diff/20001/tests/lib/math/math_test...
File tests/lib/math/math_test.dart (right):

https://codereview.chromium.org/475463005/diff/20001/tests/lib/math/math_test...
tests/lib/math/math_test.dart:203: Expect.equals(pow(2, 63)*3, gcd(pow(2,
64)*3*5, pow(2,63)*3*7));
On 2014/08/19 08:31:31, Lasse Reichstein Nielsen wrote:
> This is very quickly reduced by dividing by 2 63 times. 
> How about keeping the number big without factors of two:
>   gcd(3 * 982451653, 7 * 982451653);

Good idea. Done and split into bigint tests since, eg: 31*595056260442243647 ==
18446744073709552000 in javascript's double :(

https://codereview.chromium.org/475463005/diff/20001/tests/lib/math/math_test...
tests/lib/math/math_test.dart:204: }
On 2014/08/19 08:31:31, Lasse Reichstein Nielsen wrote:
> Do these tests succeed on dart2js?
> 
> If so, you need more tests :)

Sorry, that test file is expected to raise a RuntimeError, so my tests were
_NOT_ running in dart2js. I've fixed this with the separation into a new file.

[Lasse Reichstein Nielsen, 2014-08-20 12:17:03]

Looks good, but move tests to package as well.

https://codereview.chromium.org/475463005/diff/40001/pkg/math/lib/math.dart
File pkg/math/lib/math.dart (right):

https://codereview.chromium.org/475463005/diff/40001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:10: * [a] and [b] must be non-negative integers.
-> Both `a` and `b` must be non-negative integers.


This avoid starting the sentence with a lower-case letter, and there is no need
to make [a]/[b] a link more than once in the same documentation.

https://codereview.chromium.org/475463005/diff/40001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:16: throw new RangeError("a and b must not be negative;
received $a and $b.");
"Both a and b ...

https://codereview.chromium.org/475463005/diff/40001/tests/lib/math/math_pack...
File tests/lib/math/math_package_bigint_test.dart (right):

https://codereview.chromium.org/475463005/diff/40001/tests/lib/math/math_pack...
tests/lib/math/math_package_bigint_test.dart:8: import 'package:math/math.dart';
Test of package functionality should go in the package itself, so put this and
other tests in pkg/math/tests/.

The status file for that is pkg.status.

https://codereview.chromium.org/475463005/diff/40001/tests/lib/math/math_pack...
tests/lib/math/math_package_bigint_test.dart:13: class MathPackageBigintTest {
No need for a class here, or a testMain method, just make the function top-level
and call it directly from main.

Some old tests are using a class, but that's probably because the tests were
written before top-level functions were fully implemented.

https://codereview.chromium.org/475463005/diff/40001/tests/lib/math/math_test...
File tests/lib/math/math_test.dart (right):

https://codereview.chromium.org/475463005/diff/40001/tests/lib/math/math_test...
tests/lib/math/math_test.dart:135: final double EPSILON = 1e-15;
Unnecessary change.

[srawlins, 2014-08-25 05:43:54]

Addressed feedback. Added functions for:

* least common multiple
* extended greatest common denominator
* modulo inverse
* modulo exponentiation

and tests.

https://codereview.chromium.org/475463005/diff/40001/pkg/math/lib/math.dart
File pkg/math/lib/math.dart (right):

https://codereview.chromium.org/475463005/diff/40001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:10: * [a] and [b] must be non-negative integers.
On 2014/08/20 12:17:02, Lasse Reichstein Nielsen wrote:
> -> Both `a` and `b` must be non-negative integers.
> 
> 
> This avoid starting the sentence with a lower-case letter, and there is no
need
> to make [a]/[b] a link more than once in the same documentation.

Done.

https://codereview.chromium.org/475463005/diff/40001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:16: throw new RangeError("a and b must not be negative;
received $a and $b.");
On 2014/08/20 12:17:02, Lasse Reichstein Nielsen wrote:
> "Both a and b ... 

Done.

https://codereview.chromium.org/475463005/diff/40001/tests/lib/math/math_pack...
File tests/lib/math/math_package_bigint_test.dart (right):

https://codereview.chromium.org/475463005/diff/40001/tests/lib/math/math_pack...
tests/lib/math/math_package_bigint_test.dart:8: import 'package:math/math.dart';
On 2014/08/20 12:17:02, Lasse Reichstein Nielsen wrote:
> Test of package functionality should go in the package itself, so put this and
> other tests in pkg/math/tests/.
> 
> The status file for that is pkg.status.
> 

Done.

https://codereview.chromium.org/475463005/diff/40001/tests/lib/math/math_pack...
tests/lib/math/math_package_bigint_test.dart:13: class MathPackageBigintTest {
On 2014/08/20 12:17:02, Lasse Reichstein Nielsen wrote:
> No need for a class here, or a testMain method, just make the function
top-level
> and call it directly from main.
> 
> Some old tests are using a class, but that's probably because the tests were
> written before top-level functions were fully implemented.

Done.

https://codereview.chromium.org/475463005/diff/40001/tests/lib/math/math_test...
File tests/lib/math/math_test.dart (right):

https://codereview.chromium.org/475463005/diff/40001/tests/lib/math/math_test...
tests/lib/math/math_test.dart:135: final double EPSILON = 1e-15;
On 2014/08/20 12:17:03, Lasse Reichstein Nielsen wrote:
> Unnecessary change.

Done.

[Lasse Reichstein Nielsen, 2014-08-26 07:44:27]

Update pubspec.yaml version (to 1.0.0 - might as well get there some day).

LGTM with comments addressed.

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart
File pkg/math/lib/math.dart (right):

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:13: if (a is! int) throw new ArgumentError(a);
Reduce this to just
  if (a == null) ...
the "int" part is checked by the parameters in checked mode and by the analyzer,
and this isn't essential system code, so a wrong argument can't break anything
deep.
Dittos below.

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:34: temp = b;
declare temp here.

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:56: List<int> results = gcdext(-a, b);
result[1] = -result[1];
return result;

No need to create a new result object.
Similar below.

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:64: int g, x, y;
None of g, x, y are used below?

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:71: while (r1 != 0) {
Declare q and tmp inside the while.

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:86: return [r0, x0, y0];
Maybe use:
  new List<int>(3)..[0] = r0 ..[1] = x0 ..[2] = y0;
That makes it a fixed-length list, which has lower resource overhead.

Maybe even make it a class, like: GCDResults { final int gcd, factor1, factor2;
}, but it's probably not worth the effort.

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:92: * Throws an IntegerDivisionByZeroException if `a` has
no inverse modulo `m`:
[IntegerDivisionByZeroException]
(use square brackets the first time you refer to a type in the documentation,
then just use code formatting (backping) if it's mentioned again.

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:115: return a.abs() ~/ gcd(a, b) * b.abs();
Nice touch to avoid overflows :)

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:123: * Throws an IntegerDivisionByZeroException if `exp`
is negative and `base` has
[]-quote the exception type.

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:126: int powmod(int base, int exp, int mod) {
If this method is expected to be used often with a mod that is a power of 2, it
might be worth it to have a specialized version that uses bit-and instead of
modulo. Modulo is a slow operation.

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:143: base = (base * base) % mod;
This is executed one time too many. That's probably ok, if it requires too much
effort to avoid it.

https://codereview.chromium.org/475463005/diff/60001/pkg/math/test/bigint_tes...
File pkg/math/test/bigint_test.dart (right):

https://codereview.chromium.org/475463005/diff/60001/pkg/math/test/bigint_tes...
pkg/math/test/bigint_test.dart:99: new BigintTest().testMain();
I miss tests with negative integers.

[srawlins, 2014-08-29 06:43:25]

Hi lrn@, thanks for the review! I've addressed it all, I believe.

I gained commit access to this project recently, would you mind if I performed
the commit?

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart
File pkg/math/lib/math.dart (right):

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:13: if (a is! int) throw new ArgumentError(a);
On 2014/08/26 07:44:26, Lasse Reichstein Nielsen wrote:
> Reduce this to just
>   if (a == null) ...
> the "int" part is checked by the parameters in checked mode and by the
analyzer,
> and this isn't essential system code, so a wrong argument can't break anything
> deep.
> Dittos below.

Done.

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:34: temp = b;
On 2014/08/26 07:44:26, Lasse Reichstein Nielsen wrote:
> declare temp here.

Done.

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:56: List<int> results = gcdext(-a, b);
On 2014/08/26 07:44:26, Lasse Reichstein Nielsen wrote:
> result[1] = -result[1];
> return result;
> 
> No need to create a new result object.
> Similar below.

:P I should have caught that. Thanks.

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:64: int g, x, y;
On 2014/08/26 07:44:26, Lasse Reichstein Nielsen wrote:
> None of g, x, y are used below?

Done.

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:71: while (r1 != 0) {
On 2014/08/26 07:44:26, Lasse Reichstein Nielsen wrote:
> Declare q and tmp inside the while.

Done.

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:86: return [r0, x0, y0];
On 2014/08/26 07:44:26, Lasse Reichstein Nielsen wrote:
> Maybe use:
>   new List<int>(3)..[0] = r0 ..[1] = x0 ..[2] = y0;
> That makes it a fixed-length list, which has lower resource overhead.
> 
> Maybe even make it a class, like: GCDResults { final int gcd, factor1,
factor2;
> }, but it's probably not worth the effort.
> 
Done, but spread out onto multiple lines. Should I keep them in one line?

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:92: * Throws an IntegerDivisionByZeroException if `a` has
no inverse modulo `m`:
On 2014/08/26 07:44:26, Lasse Reichstein Nielsen wrote:
> [IntegerDivisionByZeroException]
> (use square brackets the first time you refer to a type in the documentation,
> then just use code formatting (backping) if it's mentioned again.

Done.

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:115: return a.abs() ~/ gcd(a, b) * b.abs();
On 2014/08/26 07:44:26, Lasse Reichstein Nielsen wrote:
> Nice touch to avoid overflows :)

Acknowledged.

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:123: * Throws an IntegerDivisionByZeroException if `exp`
is negative and `base` has
On 2014/08/26 07:44:26, Lasse Reichstein Nielsen wrote:
> []-quote the exception type.

Done.

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:126: int powmod(int base, int exp, int mod) {
On 2014/08/26 07:44:26, Lasse Reichstein Nielsen wrote:
> If this method is expected to be used often with a mod that is a power of 2,
it
> might be worth it to have a specialized version that uses bit-and instead of
> modulo. Modulo is a slow operation.

I don't think that is a common use case. One of the primary uses of this
function is in RSA encryption, where the modulus is prime, or at least coprime
with the base.

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:143: base = (base * base) % mod;
On 2014/08/26 07:44:26, Lasse Reichstein Nielsen wrote:
> This is executed one time too many. That's probably ok, if it requires too
much
> effort to avoid it.

Good call. I'd not noticed that before. What about this new forever loop that
returns if exp == 0? Feels a little awkward...

https://codereview.chromium.org/475463005/diff/60001/pkg/math/test/bigint_tes...
File pkg/math/test/bigint_test.dart (right):

https://codereview.chromium.org/475463005/diff/60001/pkg/math/test/bigint_tes...
pkg/math/test/bigint_test.dart:99: new BigintTest().testMain();
On 2014/08/26 07:44:26, Lasse Reichstein Nielsen wrote:
> I miss tests with negative integers.

Eek!!! Good call. I've added them to each test method above.

[Lasse Reichstein Nielsen, 2014-08-29 07:14:43]

LGTM with tiny comments, please do commit after fixing.

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart
File pkg/math/lib/math.dart (right):

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:86: return [r0, x0, y0];
Multiple lines are fine.

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:143: base = (base * base) % mod;
It does. And I'd speed-check it too - having the exit condition obvious in the
loop also helps compilers. 
Either is fine, so just pick the most efficient one :)

This is where I'd love to have composite do+while loops:
 
    do {
      if (exp.isOdd) result = (result * base) % mod;
      exp ~/= 2;
    } while (exp != 0) {
      base = (base * base) % mod;
    }

Alas, not in the language (yet!!!) :)

https://codereview.chromium.org/475463005/diff/80001/pkg/math/lib/math.dart
File pkg/math/lib/math.dart (right):

https://codereview.chromium.org/475463005/diff/80001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:127: * Throws an [IntegerDivisionByZeroException] if
`exp` is negative and `base` has
Long line.

https://codereview.chromium.org/475463005/diff/80001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:142: while (true) {
Maybe add a comment saying that the code also works if exp == 0 at entry. Or add
an "if (exp == 0) return 1;" above.

[srawlins, 2014-09-02 19:49:23]

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart
File pkg/math/lib/math.dart (right):

https://codereview.chromium.org/475463005/diff/60001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:143: base = (base * base) % mod;
On 2014/08/29 07:14:42, Lasse Reichstein Nielsen wrote:
> It does. And I'd speed-check it too - having the exit condition obvious in the
> loop also helps compilers. 
> Either is fine, so just pick the most efficient one :)
> 
> This is where I'd love to have composite do+while loops:
>  
>     do {
>       if (exp.isOdd) result = (result * base) % mod;
>       exp ~/= 2;
>     } while (exp != 0) {
>       base = (base * base) % mod;
>     }
> 
> Alas, not in the language (yet!!!) :)

Good call, I think the short circuit here helped more: benchmarking with
powmod(6714601027348841563, 1000000, 13464639003769154407), I found:
while (exp != 0) yielded 12.69 ops/ms
while (true) yielded 13.24 ops/ms

https://codereview.chromium.org/475463005/diff/80001/pkg/math/lib/math.dart
File pkg/math/lib/math.dart (right):

https://codereview.chromium.org/475463005/diff/80001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:127: * Throws an [IntegerDivisionByZeroException] if
`exp` is negative and `base` has
On 2014/08/29 07:14:42, Lasse Reichstein Nielsen wrote:
> Long line.

Done.

https://codereview.chromium.org/475463005/diff/80001/pkg/math/lib/math.dart#n...
pkg/math/lib/math.dart:142: while (true) {
On 2014/08/29 07:14:42, Lasse Reichstein Nielsen wrote:
> Maybe add a comment saying that the code also works if exp == 0 at entry. Or
add
> an "if (exp == 0) return 1;" above.

Done.

[srawlins, 2014-09-02 19:49:59]

Committed patchset #6 (id:100001) manually as 39769 (presubmit successful).