Divide a 2n-bit nonnegative integer a by an n-bit positive integer b, using a recursive divide-and-conquer algorithm. Inputs: n is a positive integer b is a positive integer with exactly n bits a is a nonnegative integer such that a < 2**n * b Output: (q, r) suc
(a, b, n)
| 420 | |
| 421 | |
| 422 | def _div2n1n(a, b, n): |
| 423 | """Divide a 2n-bit nonnegative integer a by an n-bit positive integer |
| 424 | b, using a recursive divide-and-conquer algorithm. |
| 425 | |
| 426 | Inputs: |
| 427 | n is a positive integer |
| 428 | b is a positive integer with exactly n bits |
| 429 | a is a nonnegative integer such that a < 2**n * b |
| 430 | |
| 431 | Output: |
| 432 | (q, r) such that a = b*q+r and 0 <= r < b. |
| 433 | |
| 434 | """ |
| 435 | if a.bit_length() - n <= _DIV_LIMIT: |
| 436 | return divmod(a, b) |
| 437 | pad = n & 1 |
| 438 | if pad: |
| 439 | a <<= 1 |
| 440 | b <<= 1 |
| 441 | n += 1 |
| 442 | half_n = n >> 1 |
| 443 | mask = (1 << half_n) - 1 |
| 444 | b1, b2 = b >> half_n, b & mask |
| 445 | q1, r = _div3n2n(a >> n, (a >> half_n) & mask, b, b1, b2, half_n) |
| 446 | q2, r = _div3n2n(r, a & mask, b, b1, b2, half_n) |
| 447 | if pad: |
| 448 | r >>= 1 |
| 449 | return q1 << half_n | q2, r |
| 450 | |
| 451 | |
| 452 | def _div3n2n(a12, a3, b, b1, b2, n): |
no test coverage detected
searching dependent graphs…