What is a generator?

%load_ext itikz

A generator is a function that uses the yield keyword to return an item. When a generator function is called, it returns a generator object, which is a type of iterator. Here is a simple generator, that produces a sequence of numbers:

def number_generator(n):
    for i in range(n):
        yield i

gen = number_generator(1_000_000)

print(next(gen))
print(next(gen))
print(next(gen))

0
1
2

The state of the generator is saved between yield calls. The state of generator is the state of the local variables when the generator is suspended. This allows it to resume where it left off.

The main use of generators is to save memory - instead of having a very large list of elements in memory, holding everything at once, we have an object that knows how to produce each particular element, one at a time. This enables lazy computations of heavy objects in memory.

Example: Flattening a list of lists

A common task is to flatten a list of lists into a single list.

Imagine you have a list of trades, where each trade has a list of associated cashflows. You want to process all cashflows from all trades.

# Ref: bwrob.github.io/posts/python-academy-iteration 
trades_cashflows = [
    [10, 20, 30],   # Cashflows for trade 1
    [15, 25],       # Cashflows for trade 2
    [100, -10, 5],  # Cashflows for trade 3
    110             # Simple payment doesn't need to be in a list
]

def flatten(list_of_lists):
    for item in list_of_lists:
        if isinstance(item, list):
            for subitem in item:
                yield subitem
        else:
            yield item

# The generator does not hold all cashflows in memory
all_cashflows_generator = flatten(trades_cashflows)

for cf in all_cashflows_generator:
    print(cf, end=" ")

10 20 30 15 25 100 -10 5 110

This flatten generator is memory-efficient. It only needs to store one cashflow at a time, regardless of the total number of cashflows.

Example: Generating the fibonacci sequence

The Fibonacci sequence is defined by the recurrence relation: \(F_n = F_{n-1} + F_{n-2}\) with seed values \(F_0 = 0\) and \(F_1 = 1\). A naive implementation of this in Python is a direct translation of the mathematical formula:

def fibonacci_recursive(n: int):
    """Calculate the nth Fibonacci number using a recursive approach."""
    if n < 0:
        raise ValueError("Fibonacci is not defined for negative numbers")
    
    if n < 2:
        return n

    return fibonacci_recursive(n) + fibonacci_recursive(n-1)

For n=40, this already takes a long amount of time. We are doing lot of rework. Another way to solve this problem is to use an iterative approach.

def fibonacci_iterative(n: int):
    """Calculate the nth Fibonacci number using an iterative approach."""
    if n < 0:
        raise ValueError("Fibonacci is not defined for negative numbers")

    if n < 2:
        return n

    a, b = 0, 1
    for _ in range(n-1):
        a, b = b, a + b
    
    return b

We can also code up a generator to produce the fibonacci sequence.

def fibonacci_generator():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

gen = fibonacci_generator()

for i in range(10):
    print(f"F_{i} = {next(gen)}")

F_0 = 0
F_1 = 1
F_2 = 1
F_3 = 2
F_4 = 3
F_5 = 5
F_6 = 8
F_7 = 13
F_8 = 21
F_9 = 34

Generator expressions

List comprehensions are widely used in Python. However, many of the use-cases do not need to have the full list created in-memory. Instead, they only need to iterate over the elements one at a time.

For example, the following summation code will build a full list of squares in memory, iterate over those values, and when the reference is no longer needed, delete the list.

sum([x**2 for x in range(10)])

Memory is conserved by using a generator expression instead.

sum(x**2 for x in range(10))

Consider taking the inner product of the vectors x_vector and y_vector:

x_vector = [1,2,3,4,5]
y_vector = [6,7,8,9,10]

sum(x * y for x, y in zip(x_vector, y_vector))

Iterators

An iterator is an object that represents a stream of data. It produces one item at a time, only when requested. This lazy evaluation is incredibly memory-efficient. The iterator protocol in Pythoon consists of two methods:

__iter__(): Returns the iterator object itself
__next__(): Returns the next item from the stream. When there are no more items, it raise a StopIteration exception.

Having these protocols in Python has an advantage: everyone know that Python will be familiar with this interface already, so there a sort of standard contract.

Example : Finding the implied volatility of European vanilla options using an iterative root-solver

For the purposes of this example, I will use the bisection method to solve for the implied volatility of a European call option.

The bisection method makes use of the intermediate value theorem(IVT) from Real Analysis. The intermediate value theorem states that the image of a continuous function \(f\) over an interval \((a,b)\) is an interval. If \(f\) is a continuous function, it preserves intervals. If we take an interval and apply a continous function \(f\) to it, the image is also an interval. It captures the intuitive notion, there are no gaps or jumps in a continuous curve. If \(f\) is continuous and \(f(a) < k <f(b)\), then there exists an element \(c\in(a,b)\), such that \(f(c)=k\).

Iteration process

We start with an initial interval \([a,b]\), such that the function values \(f(a)\) and \(f(b)\) are of opposite sign.

Step 1. We calculate the midpoint \(m = (a + b)/2\).

Step 2. Case I. If \(f(a)\) and \(f(m)\) have the same signs, the root must be in the right half \([m,b]\). So, we set \(a=m\).

Case II. If \(f(m)\) and \(f(b)\) have the same signs, the root must be in the left half \([a,m]\). So, we set \(b=m\).

We iteratively perform steps (1) and (2) until the absolute or relative error is within a certain tolerance \(\epsilon\).

Show the code

%%itikz --temp-dir --tex-packages=tikz --tikz-libraries=backgrounds --implicit-standalone

% Scenario 1: Root in left half
\begin{tikzpicture}[scale=1.2, background rectangle/.style={fill=white}, show background rectangle]
    % Axes
    \draw[->] (-0.5,0) -- (5,0) node[right] {$x$};
    \draw[->] (0,-2.5) -- (0,2.5) node[above] {$y$};
    
    % Points
    \coordinate (a) at (0.5,0);
    \coordinate (b) at (4.5,0);
    \coordinate (m) at (2.5,0);
    
    % Function curve (convex)
    \draw[thick, blue, domain=0.5:4.5, samples=100] 
        plot (\x, {0.3*(\x-1.5)*(\x-1.5) - 1.2});
    
    % Vertical lines and points
    \draw[dashed] (0.5,0) -- (0.5,{0.3*(0.5-1.5)*(0.5-1.5) - 1.2});
    \draw[dashed] (2.5,0) -- (2.5,{0.3*(2.5-1.5)*(2.5-1.5) - 1.2});
    \draw[dashed] (4.5,0) -- (4.5,{0.3*(4.5-1.5)*(4.5-1.5) - 1.2});
    
    % Function values
    \fill[red] (0.5,{0.3*(0.5-1.5)*(0.5-1.5) - 1.2}) circle (2pt) 
        node[below left] {$f(a) < 0$};
    \fill[red] (2.5,{0.3*(2.5-1.5)*(2.5-1.5) - 1.2}) circle (2pt) 
        node[below right] {$f(m) < 0$};
    \fill[red] (4.5,{0.3*(4.5-1.5)*(4.5-1.5) - 1.2}) circle (2pt) 
        node[above right] {$f(b) > 0$};
    
    % x-axis labels
    \fill (0.5,0) circle (1.5pt) node[below] {$a$};
    \fill (2.5,0) circle (1.5pt) node[below] {$m$};
    \fill (4.5,0) circle (1.5pt) node[below] {$b$};
    
    % Root indicator
    \draw[thick, red] (0.5,-0.3) -- (2.5,-0.3);
    \node[red] at (1.5,-0.6) {Root in $[a, m]$};
    
    % Title
    \node[align=center] at (2.5,3) {\textbf{Scenario 1:} $f(m)$ and $f(b)$ have same sign};
    \node[align=center] at (2.5,2.5) {New interval: $[a, m]$};
\end{tikzpicture}

Show the code

%%itikz --temp-dir --tex-packages=tikz --tikz-libraries=backgrounds --implicit-standalone
\begin{tikzpicture}[scale=1.2, background rectangle/.style={fill=white}, show background rectangle]
    % Axes
    \draw[->] (-0.5,0) -- (5,0) node[right] {$x$};
    \draw[->] (0,-2.5) -- (0,2.5) node[above] {$y$};
    
    % Points
    \coordinate (a) at (0.5,0);
    \coordinate (b) at (4.5,0);
    \coordinate (m) at (2.5,0);
    
    % Function curve (convex)
    \draw[thick, blue, domain=0.5:4.5, samples=100] 
        plot (\x, {0.3*(\x-3.5)*(\x-3.5) - 1.2});
    
    % Vertical lines and points
    \draw[dashed] (0.5,0) -- (0.5,{0.3*(0.5-3.5)*(0.5-3.5) - 1.2});
    \draw[dashed] (2.5,0) -- (2.5,{0.3*(2.5-3.5)*(2.5-3.5) - 1.2});
    \draw[dashed] (4.5,0) -- (4.5,{0.3*(4.5-3.5)*(4.5-3.5) - 1.2});
    
    % Function values
    \fill[red] (0.5,{0.3*(0.5-3.5)*(0.5-3.5) - 1.2}) circle (2pt) 
        node[above left] {$f(a) > 0$};
    \fill[red] (2.5,{0.3*(2.5-3.5)*(2.5-3.5) - 1.2}) circle (2pt) 
        node[above right] {$f(m) > 0$};
    \fill[red] (4.5,{0.3*(4.5-3.5)*(4.5-3.5) - 1.2}) circle (2pt) 
        node[below right] {$f(b) < 0$};
    
    % x-axis labels
    \fill (0.5,0) circle (1.5pt) node[below] {$a$};
    \fill (2.5,0) circle (1.5pt) node[below] {$m$};
    \fill (4.5,0) circle (1.5pt) node[below] {$b$};
    
    % Root indicator
    \draw[thick, red] (2.5,-0.3) -- (4.5,-0.3);
    \node[red] at (3.5,-0.6) {Root in $[m, b]$};
    
    % Title
    \node[align=center] at (2.5,3) {\textbf{Scenario 2:} $f(a)$ and $f(m)$ have same sign};
    \node[align=center] at (2.5,2.5) {New interval: $[m, b]$};
\end{tikzpicture}

A call option is the right to buy an asset at a future time \(T\), at a pre-determined price \(K\). A put option is the right to sell an asset at a future time \(T\), at a pre-determined price \(K\).

Vanilla options have two quote conventions - they can be quoted in terms of a price (in dollar terms) or in terms of the implied volatility. The Black-Scholes analytic formula used as a converter to convert an implied-vol quote to a price.

Let \(\sigma\) be the market-implied volatility of the option. Then, the option price is given by:

\[ C_{BS}(\sigma) = S_t \Phi(d_{+}) - K e^{-r(T-t)}\Phi(d_{-}) \]

where

\[ d_{\pm} = \frac{\log(S_t/K) + (r \pm \sigma^2/2)(T-t)}{\sigma \sqrt{T-t}} \]

Conversely, if we have the option price \(C_{BS}\), we can backout the implied volatility \(\sigma\), by solving for the root of the above equation.

Thus, we can define