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 // TODO(srdjan): fix limitations. | 5 // TODO(srdjan): fix limitations. |
6 // - shift amount must be a Smi. | 6 // - shift amount must be a Smi. |
7 class _IntegerImplementation extends _Num { | 7 class _IntegerImplementation extends _Num { |
8 // The Dart class _Bigint extending _IntegerImplementation requires a | 8 // The Dart class _Bigint extending _IntegerImplementation requires a |
9 // default constructor. | 9 // default constructor. |
10 | 10 |
(...skipping 272 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
283 while (e > 0) { | 283 while (e > 0) { |
284 if (e.isOdd) { | 284 if (e.isOdd) { |
285 r = (r * b) % m; | 285 r = (r * b) % m; |
286 } | 286 } |
287 e >>= 1; | 287 e >>= 1; |
288 b = (b * b) % m; | 288 b = (b * b) % m; |
289 } | 289 } |
290 return r; | 290 return r; |
291 } | 291 } |
292 | 292 |
293 // Returns 1/this % m, with m > 0. | 293 // If inv is false, returns gcd(x, y). |
294 int modInverse(int m) { | 294 // If inv is true and gcd(x, y) = 1, returns d, so that c*x + d*y = 1. |
295 if (m is! int) throw new ArgumentError(m); | 295 // If inv is true and gcd(x, y) != 1, throws RangeError("Not coprime"). |
296 if (m <= 0) throw new RangeError(m); | 296 static int _binaryGcd(int x, int y, bool inv) { |
297 if (m == 1) return 0; | 297 int s = 0; |
298 if (m is _Bigint) { | 298 if (!inv) { |
299 return _toBigint().modInverse(m); | 299 while (x.isEven && y.isEven) { |
| 300 x >>= 1; |
| 301 y >>= 1; |
| 302 s++; |
| 303 } |
| 304 if (y.isOdd) { |
| 305 var t = x; |
| 306 x = y; |
| 307 y = t; |
| 308 } |
300 } | 309 } |
301 int t = this; | 310 final bool ac = x.isEven; |
302 if ((t < 0) || (t >= m)) t %= m; | 311 int u = x; |
303 if (t == 1) return 1; | 312 int v = y; |
304 final bool ac = m.isEven; | |
305 if ((t == 0) || (ac && t.isEven)) throw new RangeError("Not coprime"); | |
306 int u = m; | |
307 int v = t; | |
308 int a = 1, | 313 int a = 1, |
309 b = 0, | 314 b = 0, |
310 c = 0, | 315 c = 0, |
311 d = 1; | 316 d = 1; |
312 do { | 317 do { |
313 while (u.isEven) { | 318 while (u.isEven) { |
314 u >>= 1; | 319 u >>= 1; |
315 if (ac) { | 320 if (ac) { |
316 if (!a.isEven || !b.isEven) { | 321 if (!a.isEven || !b.isEven) { |
317 a += t; | 322 a += y; |
318 b -= m; | 323 b -= x; |
319 } | 324 } |
320 a >>= 1; | 325 a >>= 1; |
321 } else if (!b.isEven) { | 326 } else if (!b.isEven) { |
322 b -= m; | 327 b -= x; |
323 } | 328 } |
324 b >>= 1; | 329 b >>= 1; |
325 } | 330 } |
326 while (v.isEven) { | 331 while (v.isEven) { |
327 v >>= 1; | 332 v >>= 1; |
328 if (ac) { | 333 if (ac) { |
329 if (!c.isEven || !d.isEven) { | 334 if (!c.isEven || !d.isEven) { |
330 c += t; | 335 c += y; |
331 d -= m; | 336 d -= x; |
332 } | 337 } |
333 c >>= 1; | 338 c >>= 1; |
334 } else if (!d.isEven) { | 339 } else if (!d.isEven) { |
335 d -= m; | 340 d -= x; |
336 } | 341 } |
337 d >>= 1; | 342 d >>= 1; |
338 } | 343 } |
339 if (u >= v) { | 344 if (u >= v) { |
340 u -= v; | 345 u -= v; |
341 if (ac) a -= c; | 346 if (ac) a -= c; |
342 b -= d; | 347 b -= d; |
343 } else { | 348 } else { |
344 v -= u; | 349 v -= u; |
345 if (ac) c -= a; | 350 if (ac) c -= a; |
346 d -= b; | 351 d -= b; |
347 } | 352 } |
348 } while (u != 0); | 353 } while (u != 0); |
| 354 if (!inv) return v << s; |
349 if (v != 1) throw new RangeError("Not coprime"); | 355 if (v != 1) throw new RangeError("Not coprime"); |
350 if (d < 0) { | 356 if (d < 0) { |
351 d += m; | 357 d += x; |
352 if (d < 0) d += m; | 358 if (d < 0) d += x; |
353 } else if (d > m) { | 359 } else if (d > x) { |
354 d -= m; | 360 d -= x; |
355 if (d > m) d -= m; | 361 if (d > x) d -= x; |
356 } | 362 } |
357 return d; | 363 return d; |
358 } | 364 } |
| 365 |
| 366 // Returns 1/this % m, with m > 0. |
| 367 int modInverse(int m) { |
| 368 if (m is! int) throw new ArgumentError(m); |
| 369 if (m <= 0) throw new RangeError(m); |
| 370 if (m == 1) return 0; |
| 371 if (m is _Bigint) { |
| 372 return _toBigint().modInverse(m); |
| 373 } |
| 374 int t = this; |
| 375 if ((t < 0) || (t >= m)) t %= m; |
| 376 if (t == 1) return 1; |
| 377 if ((t == 0) || (t.isEven && m.isEven)) throw new RangeError("Not coprime"); |
| 378 return _binaryGcd(m, t, true); |
| 379 } |
| 380 |
| 381 // Returns gcd of abs(this) and abs(other), with this != 0 and other !=0. |
| 382 int gcd(int other) { |
| 383 if (other is! int) throw new ArgumentError(other); |
| 384 if ((this == 0) || (other == 0)) throw new RangeError(0); |
| 385 int x = this.abs(); |
| 386 int y = other.abs(); |
| 387 if ((x == 1) || (y == 1)) return 1; |
| 388 if (other is _Bigint) { |
| 389 return _toBigint().gcd(other); |
| 390 } |
| 391 return _binaryGcd(x, y, false); |
| 392 } |
359 } | 393 } |
360 | 394 |
361 class _Smi extends _IntegerImplementation implements int { | 395 class _Smi extends _IntegerImplementation implements int { |
362 factory _Smi._uninstantiable() { | 396 factory _Smi._uninstantiable() { |
363 throw new UnsupportedError( | 397 throw new UnsupportedError( |
364 "_Smi can only be allocated by the VM"); | 398 "_Smi can only be allocated by the VM"); |
365 } | 399 } |
366 int get _identityHashCode { | 400 int get _identityHashCode { |
367 return this; | 401 return this; |
368 } | 402 } |
(...skipping 201 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
570 // Shift by mint exceeds range that can be handled by the VM. | 604 // Shift by mint exceeds range that can be handled by the VM. |
571 int _shrFromInt(int other) { | 605 int _shrFromInt(int other) { |
572 if (other < 0) { | 606 if (other < 0) { |
573 return -1; | 607 return -1; |
574 } else { | 608 } else { |
575 return 0; | 609 return 0; |
576 } | 610 } |
577 } | 611 } |
578 int _shlFromInt(int other) native "Mint_shlFromInt"; | 612 int _shlFromInt(int other) native "Mint_shlFromInt"; |
579 } | 613 } |
OLD | NEW |