# 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>>)

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>>)
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.