Algorithms

pymbolic.algorithm.integer_power(x, n, one=1)

Compute \(x^n\) using only multiplications.

See also the C2 wiki.

pymbolic.algorithm.extended_euclidean(q, r)

Return a tuple (p, a, b) such that \(p = aq + br\), where p is the greatest common divisor of q and r.

See also the Wikipedia article on the Euclidean algorithm.

pymbolic.algorithm.gcd(q, r)

pymbolic.algorithm.lcm(q, r)

pymbolic.algorithm.fft(x, sign=1, wrap_intermediate=<function <lambda>>, complex_dtype=None)

Computes the Fourier transform of x:

\[F[x]_k = \sum_{j=0}^{n-1} z^{kj} x_j\]

where \(z = \exp(-2i\pi\operatorname{sign}/n)\) and n == len(x). Works for all positive n.

See also Wikipedia.

pymbolic.algorithm.ifft(x, wrap_intermediate=<function <lambda>>, complex_dtype=None)

pymbolic.algorithm.sym_fft(x, sign=1)

Perform a (symbolic) FFT on the numpy object array x.

Remove near-zero floating point constants, insert pymbolic.primitives.CommonSubexpression wrappers at opportune points.