Advanced Python Programming

Example 2 – inherently sequential tasks

Let us consider a quick example:

Computing f¹⁰⁰⁰(3), with f(x) = x² - x + 1, and f^{n + 1}(x) = f(fⁿ(x)).

With complicated functions like f (where it is relatively difficult to find a general form of fⁿ(x)), the only obviously reasonable way to compute f¹⁰⁰⁰(3) or similar values is to iteratively compute f²(3) = f( f(3)), f³(3) = f( f²(3)), ... , f⁹⁹⁹(3) = f( f⁹⁹⁸(3)), and, finally, f¹⁰⁰⁰(3) = f( f⁹⁹⁹(3)).

Since it will take significant time to actually compute f¹⁰⁰⁰(3), even when using a computer, we will only consider f²⁰(3) in our code (my laptop actually started heating up after f²⁵(3)):

# Chapter08/example2.pydef f(x):    return x * x - x + 1# sequentialdef f(x):    return x * x - x + 1start = timer()