* Solve bounded Diophantine equation * * The problem considered is:: * * A[0] x[0] + A[1] x[1] + ... + A[n-1] x[n-1] == b * 0 <= x[i] <= U[i] * A[i] > 0 * * Solve via depth-first Euclid's algorithm, as explained in [1]. * * If require_ub_nontrivial!=0, look for solutions to the problem * where b = A[0]*(U[0]/2) + ... + A[n]*(U[n-1]/2) but ignoring * the trivial solution x[i
| 480 | * The value given for `b` is ignored in this case. |
| 481 | */ |
| 482 | NPY_VISIBILITY_HIDDEN mem_overlap_t |
| 483 | solve_diophantine(unsigned int n, diophantine_term_t *E, npy_int64 b, |
| 484 | Py_ssize_t max_work, int require_ub_nontrivial, npy_int64 *x) |
| 485 | { |
| 486 | mem_overlap_t res; |
| 487 | unsigned int j; |
| 488 | |
| 489 | for (j = 0; j < n; ++j) { |
| 490 | if (E[j].a <= 0) { |
| 491 | return MEM_OVERLAP_ERROR; |
| 492 | } |
| 493 | else if (E[j].ub < 0) { |
| 494 | return MEM_OVERLAP_NO; |
| 495 | } |
| 496 | } |
| 497 | |
| 498 | if (require_ub_nontrivial) { |
| 499 | npy_int64 ub_sum = 0; |
| 500 | char overflow = 0; |
| 501 | for (j = 0; j < n; ++j) { |
| 502 | if (E[j].ub % 2 != 0) { |
| 503 | return MEM_OVERLAP_ERROR; |
| 504 | } |
| 505 | ub_sum = safe_add(ub_sum, |
| 506 | safe_mul(E[j].a, E[j].ub/2, &overflow), |
| 507 | &overflow); |
| 508 | } |
| 509 | if (overflow) { |
| 510 | return MEM_OVERLAP_ERROR; |
| 511 | } |
| 512 | b = ub_sum; |
| 513 | } |
| 514 | |
| 515 | if (b < 0) { |
| 516 | return MEM_OVERLAP_NO; |
| 517 | } |
| 518 | |
| 519 | if (n == 0) { |
| 520 | if (require_ub_nontrivial) { |
| 521 | /* Only trivial solution for 0-variable problem */ |
| 522 | return MEM_OVERLAP_NO; |
| 523 | } |
| 524 | if (b == 0) { |
| 525 | return MEM_OVERLAP_YES; |
| 526 | } |
| 527 | return MEM_OVERLAP_NO; |
| 528 | } |
| 529 | else if (n == 1) { |
| 530 | if (require_ub_nontrivial) { |
| 531 | /* Only trivial solution for 1-variable problem */ |
| 532 | return MEM_OVERLAP_NO; |
| 533 | } |
| 534 | if (b % E[0].a == 0) { |
| 535 | x[0] = b / E[0].a; |
| 536 | if (x[0] >= 0 && x[0] <= E[0].ub) { |
| 537 | return MEM_OVERLAP_YES; |
| 538 | } |
| 539 | } |