OLD | NEW |
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 part of _interceptors; | 5 part of _interceptors; |
6 | 6 |
7 /** | 7 /** |
8 * The super interceptor class for [JSInt] and [JSDouble]. The compiler | 8 * The super interceptor class for [JSInt] and [JSDouble]. The compiler |
9 * recognizes this class as an interceptor, and changes references to | 9 * recognizes this class as an interceptor, and changes references to |
10 * [:this:] to actually use the receiver of the method, which is | 10 * [:this:] to actually use the receiver of the method, which is |
(...skipping 392 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
403 while (e > 0) { | 403 while (e > 0) { |
404 if (e.isOdd) { | 404 if (e.isOdd) { |
405 r = (r * b) % m; | 405 r = (r * b) % m; |
406 } | 406 } |
407 e ~/= 2; | 407 e ~/= 2; |
408 b = (b * b) % m; | 408 b = (b * b) % m; |
409 } | 409 } |
410 return r; | 410 return r; |
411 } | 411 } |
412 | 412 |
413 // Returns 1/this % m, with m > 0. | 413 // If inv is false, returns gcd(x, y). |
414 int modInverse(int m) { | 414 // If inv is true and gcd(x, y) = 1, returns d, so that c*x + d*y = 1. |
415 if (m is! int) throw argumentErrorValue(m); | 415 // If inv is true and gcd(x, y) != 1, throws RangeError("Not coprime"). |
416 if (m <= 0) throw new RangeError(m); | 416 static int _binaryGcd(int x, int y, bool inv) { |
417 if (m == 1) return 0; | 417 int s = 1; |
418 int t = this; | 418 if (!inv) { |
419 if ((t < 0) || (t >= m)) t %= m; | 419 while (x.isEven && y.isEven) { |
420 if (t == 1) return 1; | 420 x ~/= 2; |
421 final bool ac = m.isEven; | 421 y ~/= 2; |
422 if ((t == 0) || (ac && t.isEven)) throw new RangeError("Not coprime"); | 422 s *= 2; |
423 int u = m; | 423 } |
424 int v = t; | 424 if (y.isOdd) { |
| 425 var t = x; |
| 426 x = y; |
| 427 y = t; |
| 428 } |
| 429 } |
| 430 final bool ac = x.isEven; |
| 431 int u = x; |
| 432 int v = y; |
425 int a = 1, | 433 int a = 1, |
426 b = 0, | 434 b = 0, |
427 c = 0, | 435 c = 0, |
428 d = 1; | 436 d = 1; |
429 do { | 437 do { |
430 while (u.isEven) { | 438 while (u.isEven) { |
431 u ~/= 2; | 439 u ~/= 2; |
432 if (ac) { | 440 if (ac) { |
433 if (!a.isEven || !b.isEven) { | 441 if (!a.isEven || !b.isEven) { |
434 a += t; | 442 a += y; |
435 b -= m; | 443 b -= x; |
436 } | 444 } |
437 a ~/= 2; | 445 a ~/= 2; |
438 } else if (!b.isEven) { | 446 } else if (!b.isEven) { |
439 b -= m; | 447 b -= x; |
440 } | 448 } |
441 b ~/= 2; | 449 b ~/= 2; |
442 } | 450 } |
443 while (v.isEven) { | 451 while (v.isEven) { |
444 v ~/= 2; | 452 v ~/= 2; |
445 if (ac) { | 453 if (ac) { |
446 if (!c.isEven || !d.isEven) { | 454 if (!c.isEven || !d.isEven) { |
447 c += t; | 455 c += y; |
448 d -= m; | 456 d -= x; |
449 } | 457 } |
450 c ~/= 2; | 458 c ~/= 2; |
451 } else if (!d.isEven) { | 459 } else if (!d.isEven) { |
452 d -= m; | 460 d -= x; |
453 } | 461 } |
454 d ~/= 2; | 462 d ~/= 2; |
455 } | 463 } |
456 if (u >= v) { | 464 if (u >= v) { |
457 u -= v; | 465 u -= v; |
458 if (ac) a -= c; | 466 if (ac) a -= c; |
459 b -= d; | 467 b -= d; |
460 } else { | 468 } else { |
461 v -= u; | 469 v -= u; |
462 if (ac) c -= a; | 470 if (ac) c -= a; |
463 d -= b; | 471 d -= b; |
464 } | 472 } |
465 } while (u != 0); | 473 } while (u != 0); |
| 474 if (!inv) return s*v; |
466 if (v != 1) throw new RangeError("Not coprime"); | 475 if (v != 1) throw new RangeError("Not coprime"); |
467 if (d < 0) { | 476 if (d < 0) { |
468 d += m; | 477 d += x; |
469 if (d < 0) d += m; | 478 if (d < 0) d += x; |
470 } else if (d > m) { | 479 } else if (d > x) { |
471 d -= m; | 480 d -= x; |
472 if (d > m) d -= m; | 481 if (d > x) d -= x; |
473 } | 482 } |
474 return d; | 483 return d; |
475 } | 484 } |
476 | 485 |
| 486 // Returns 1/this % m, with m > 0. |
| 487 int modInverse(int m) { |
| 488 if (m is! int) throw new ArgumentError(m); |
| 489 if (m <= 0) throw new RangeError(m); |
| 490 if (m == 1) return 0; |
| 491 int t = this; |
| 492 if ((t < 0) || (t >= m)) t %= m; |
| 493 if (t == 1) return 1; |
| 494 if ((t == 0) || (t.isEven && m.isEven)) throw new RangeError("Not coprime"); |
| 495 return _binaryGcd(m, t, true); |
| 496 } |
| 497 |
| 498 // Returns gcd of abs(this) and abs(other), with this != 0 and other !=0. |
| 499 int gcd(int other) { |
| 500 if (other is! int) throw new ArgumentError(other); |
| 501 if ((this == 0) || (other == 0)) throw new RangeError(0); |
| 502 int x = this.abs(); |
| 503 int y = other.abs(); |
| 504 if ((x == 1) || (y == 1)) return 1; |
| 505 return _binaryGcd(x, y, false); |
| 506 } |
| 507 |
477 // Assumes i is <= 32-bit and unsigned. | 508 // Assumes i is <= 32-bit and unsigned. |
478 static int _bitCount(int i) { | 509 static int _bitCount(int i) { |
479 // See "Hacker's Delight", section 5-1, "Counting 1-Bits". | 510 // See "Hacker's Delight", section 5-1, "Counting 1-Bits". |
480 | 511 |
481 // The basic strategy is to use "divide and conquer" to | 512 // The basic strategy is to use "divide and conquer" to |
482 // add pairs (then quads, etc.) of bits together to obtain | 513 // add pairs (then quads, etc.) of bits together to obtain |
483 // sub-counts. | 514 // sub-counts. |
484 // | 515 // |
485 // A straightforward approach would look like: | 516 // A straightforward approach would look like: |
486 // | 517 // |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
521 } | 552 } |
522 | 553 |
523 class JSDouble extends JSNumber implements double { | 554 class JSDouble extends JSNumber implements double { |
524 const JSDouble(); | 555 const JSDouble(); |
525 Type get runtimeType => double; | 556 Type get runtimeType => double; |
526 } | 557 } |
527 | 558 |
528 class JSPositiveInt extends JSInt {} | 559 class JSPositiveInt extends JSInt {} |
529 class JSUInt32 extends JSPositiveInt {} | 560 class JSUInt32 extends JSPositiveInt {} |
530 class JSUInt31 extends JSUInt32 {} | 561 class JSUInt31 extends JSUInt32 {} |
OLD | NEW |