numpy
2.0.0
|
Go to the source code of this file.
Data Structures | |
struct | diophantine_term_t |
Defines | |
#define | NPY_MAY_SHARE_BOUNDS 0 |
#define | NPY_MAY_SHARE_EXACT -1 |
Enumerations | |
enum | mem_overlap_t { MEM_OVERLAP_NO = 0, MEM_OVERLAP_YES = 1, MEM_OVERLAP_TOO_HARD = -1, MEM_OVERLAP_OVERFLOW = -2, MEM_OVERLAP_ERROR = -3 } |
Functions | |
NPY_VISIBILITY_HIDDEN mem_overlap_t | solve_diophantine (unsigned int n, diophantine_term_t *E, npy_int64 b, Py_ssize_t max_work, int require_nontrivial, npy_int64 *x) |
NPY_VISIBILITY_HIDDEN int | diophantine_simplify (unsigned int *n, diophantine_term_t *E, npy_int64 b) |
NPY_VISIBILITY_HIDDEN mem_overlap_t | solve_may_share_memory (PyArrayObject *a, PyArrayObject *b, Py_ssize_t max_work) |
NPY_VISIBILITY_HIDDEN mem_overlap_t | solve_may_have_internal_overlap (PyArrayObject *a, Py_ssize_t max_work) |
NPY_VISIBILITY_HIDDEN void | offset_bounds_from_strides (const int itemsize, const int nd, const npy_intp *dims, const npy_intp *strides, npy_intp *lower_offset, npy_intp *upper_offset) |
#define NPY_MAY_SHARE_BOUNDS 0 |
#define NPY_MAY_SHARE_EXACT -1 |
enum mem_overlap_t |
NPY_VISIBILITY_HIDDEN int diophantine_simplify | ( | unsigned int * | n, |
diophantine_term_t * | E, | ||
npy_int64 | b | ||
) |
NPY_VISIBILITY_HIDDEN void offset_bounds_from_strides | ( | const int | itemsize, |
const int | nd, | ||
const npy_intp * | dims, | ||
const npy_intp * | strides, | ||
npy_intp * | lower_offset, | ||
npy_intp * | upper_offset | ||
) |
NPY_VISIBILITY_HIDDEN mem_overlap_t solve_diophantine | ( | unsigned int | n, |
diophantine_term_t * | E, | ||
npy_int64 | b, | ||
Py_ssize_t | max_work, | ||
int | require_ub_nontrivial, | ||
npy_int64 * | x | ||
) |
A[0] x[0] + A[1] x[1] + ... + A[n-1] x[n-1] == b 0 <= x[i] <= U[i] A[i] > 0
References diophantine_dfs(), diophantine_precompute(), MEM_OVERLAP_ERROR, and MEM_OVERLAP_OVERFLOW.
NPY_VISIBILITY_HIDDEN mem_overlap_t solve_may_have_internal_overlap | ( | PyArrayObject * | a, |
Py_ssize_t | max_work | ||
) |
solutions to <blockquote> sum(a*x) = b, 0 <= x[i] <= ub[i]</blockquote>
for any b. Equivalently, <blockquote> sum(a*x0) - sum(a*x1) = 0</blockquote>
Mapping the coefficients on the left by x0'[i] = x0[i] if a[i] > 0 else ub[i]-x0[i] and opposite for x1, we have <blockquote> sum(abs(a)*(x0' + x1')) = sum(abs(a)*ub)</blockquote>
Now, x0!=x1 if for some i we have x0'[i] + x1'[i] != ub[i]. We can now change variables to z[i] = x0'[i] + x1'[i] so the problem becomes <blockquote> sum(abs(a)*z) = sum(abs(a)*ub), 0 <= z[i] <= 2*ub[i], z != ub</blockquote>
This can be solved with solve_diophantine.
NPY_VISIBILITY_HIDDEN mem_overlap_t solve_may_share_memory | ( | PyArrayObject * | a, |
PyArrayObject * | b, | ||
Py_ssize_t | max_work | ||
) |
The bounds computed by offset_bounds_from_strides correspond to all-positive strides.
start1 + sum(abs(stride1)*x1) == start2 + sum(abs(stride2)*x2) == end1 - 1 - sum(abs(stride1)*x1') == end2 - 1 - sum(abs(stride2)*x2')
<=>
sum(abs(stride1)*x1) + sum(abs(stride2)*x2') == end2 - 1 - start1
OR
sum(abs(stride1)*x1') + sum(abs(stride2)*x2) == end1 - 1 - start2
We pick the problem with the smaller RHS (they are non-negative due to the extent check above.)
References MEM_OVERLAP_NO.
Referenced by raw_array_is_aligned().