Code Generation Optimizations - gxyd/sympy GitHub Wiki

Here are some potential symbolic optimizations for code generation:

• Replace exp with exp2.

• Use horner to evaluate polynomials.

• Use cse. Compilers already do this, but they can be slow, and for large expressions, might even give up. Also, it can apply in cases where the compiler might not be smart enough to do it (like if the constants are passed in as parameters).

• Replace pow(x, n) with x*x*...*x for integer n. See https://github.com/sympy/sympy/pull/7519 for some caveats on this. --ffast-math does this automatically with gcc. It's something that users will want to be able to enable and disable.

• Replace x*y + z with a fused multiply add (may not be faster, but can provide better accuracy).

• Approximate functions by series expansion.

• Common coefficient extraction (2*x - 2*y -> 2*(x - y)). cse should probably be doing this. At least it should work for cse([2*x - 2*y, x - y]) (it currently doesn't). cse does do this, but only with optimizations='basic', which is not enabled by default.

• x**(3/2) -> x*(x)**(1/2). Again, should possibly be part of cse.

• Precomputing constant expressions.

• Reducing the runtime complexity of loops via fast matrix exponentiation. http://kukuruku.co/hub/algorithms/using-the-quick-raise-of-matrices-to-power-to-write-a-very-fast-interpreter-of-a-simple-programming-language describes this (note that that blog post is translated from Russian). The idea is that simple operations on variables, like addition and multiplication, can be represented by matrices. Loops on those variables are then powers of matrices, which can be computed in log(n) time via fast matrix exponentiation. See https://github.com/SkidanovAlex/interpreter for an implementation and https://github.com/borzunov/cpmoptimize for a version that automatically converts Python functions (neither uses SymPy).