Approximating factorials with Cython

The last example is about approximating factorials with Cython. We will use two approximation methods. First, we will use the Stirling approximation method (see http://en.wikipedia.org/wiki/Stirling%27s_approximation for more information). The formula for the Stirling approximation is:

Approximating factorials with Cython

Secondly, we will be using the approximation due to Ramanujan, with the following formula:

Approximating factorials with Cython

How to do it...

This section describes how to approximate factorials using Cython. In this recipe, we will be using types, which as you may remember, is optional in Cython. In theory, declaring static types should speed things up. Static typing offers interesting challenges that you may not encounter when writing Python code, but don't worry, we will try to keep it simple.

  1. Write the Cython code.

    The Cython code that we will write looks like regular Python code, except that we declare function parameters and a local variable to be an ndarray array. In order to get the static types to work, we need to import NumPy using the cimport statement. Also we have to use the cdef keyword to declare the type of the local variable.

    import numpy
cimport numpy

def ramanujan_factorial(numpy.ndarray n):
   sqrt_pi = numpy.sqrt(numpy.pi, dtype=numpy.float64)
   cdef numpy.ndarray root = (8 * n + 4) * n + 1 
   root = root * n + 1/30.
   root = root ** (1/6.)
   return sqrt_pi * calc_eton(n) * root

def stirling_factorial(numpy.ndarray n):
    return numpy.sqrt(2 * numpy.pi * n) * calc_eton(n)

def calc_eton(numpy.ndarray n):
    return (n/numpy.e) ** n
  2. Build the code.

    Building requires us to create a setup.py file, as in the previous tutorials, but we now need to include NumPy-related directories by calling the get_include function. With this amendment, the setup.py file will have the following content:

    from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext
import numpy

ext_modules = [Extension("factorial", ["factorial.pyx"], include_dirs = [numpy.get_include()])] 

setup(
        name = 'Factorial app',
        cmdclass = {'build_ext': build_ext},
        ext_modules = ext_modules
     )
  3. Plot the relative error.

    Let's plot the relative error for both approximation methods. We will calculate the error relative to the factorial values that we will compute with the NumPy cumprod function, as we have done throughout the book.

    from factorial import ramanujan_factorial
from factorial import stirling_factorial
import numpy
import matplotlib.pyplot

N = 50
numbers = numpy.arange(1, N)
factorials = numpy.cumprod(numbers, dtype=float)

def error(approximations):
   return (factorials - approximations)/factorials

matplotlib.pyplot.plot(error(ramanujan_factorial(numbers)), 'b-')
matplotlib.pyplot.plot(error(stirling_factorial(numbers)), 'ro')
matplotlib.pyplot.show()

    The following plot shows the relative error for the Ramanujan approximation (dots) and the Stirling approximation (line). As you can see, the Ramanujan method is more accurate:

    How to do it...

How it works...

In this example, we saw a demonstration of Cython's static types. The main ingredients of this recipe were:

  • cimport, which imports C declarations
  • Including directories with the get_include() function
  • The cdef keyword to define the type of local variables
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset