## Solving cubic equations – background and timing

For more information on the polynomial functions, including quartic and higher order solvers, see: Solving Quadratic, Cubic, Quartic and higher order equations; examples

Re-reading the Wikipedia article on solving cubic equations, I noticed that the trigonometrical solution for finding 3 real roots seemed a very simple approach, which might be faster than the current code in my current VBA cubic function. (See Cubic Equations). Writing a new CubicT function, I found that this was actually slower than the original function (see more details below), and checking the code I found the original method for finding 3 roots was essentially the same as the Wikipedia method, and the method for 1 real root was simpler. Nonetheless, the code for the new function was better documented than the older code, so I have added the new function and a sheet documenting the method to the download file at:

Polynomial.zip

Times for 100,000 iterations of the new function are shown below, compared with the Cubic function (which returns the same results), CubicC (which also returns complex roots), and the Quartic function:

The VBA version of the CubicT function is more than twice as slow as the original Cubic function, presumably because the routine for finding single real roots is slower.

The code for all four functions was transferred to Python (called from Excel with pyxll), and as is typical with plain (and non-optimised) Python code, the performance was 2-3 times slower.

Modifying the Python code to use the Numba JIT compiler gave a substantial performance improvement, with the Python code now 2-5 times faster than the VBA. The CubicT function with Numba was greatly improved, and was slightly faster than Cubic. The Quartic function had an even greater improvement, and was faster than the CubicC function, and only a little slower than the other two Cubic functions.

Two Python functions also called the Numpy general purpose polynomial routines. These were both very slow, presumably because the solvers are written for polynomials of any degree, and are not optimised for cubic or quartic equations.

Note that the download file includes all the new VBA code, but not the new Python functions. This will be covered in a future post.

This entry was posted in Excel, Link to Python, Maths, Newton, NumPy and SciPy, PyXLL, UDFs, VBA and tagged , , , , , , , , , . Bookmark the permalink.

This site uses Akismet to reduce spam. Learn how your comment data is processed.