portfolio

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
<WRAP round info>
====== cs12ps23as12: Generator Functions and Infinite Sequences ======

===== Goals =====

  * Practice with generator functions in Python.
  * Consider some notable mathematical sequences and their relationships to some special numbers.
</WRAP>

-----

<WRAP round help>
====== Prerequisites ======

This assignment requires familiarity with the [[:lecture materials/]] presented in class through [[:lecture materials/week 12]].
</WRAP>

-----

====== Background ======

===== Fibonacci Numbers and the Golden Ratio =====

<WRAP right>
{{fibonacci_spiral_320.png?nolink|The Fibonacci spiral: an approximation of the golden spiral created by drawing circular arcs connecting the opposite corners of squares in the Fibonacci tiling}}
</WRAP>

We know that the [[https://en.wikipedia.org/wiki/Fibonacci_number|Fibonacci sequence]] is defined as a sequence in which each number is the sum of the two preceding numbers, i.e.:

$$
\begin{aligned}
F_{0} &= 0 \\
F_{1} &= 1 \\
F_{n} &= F_{n-1} + F_{n-2} \text{ for n > 1}
\end{aligned}
$$

The beginning of the Fibonacci sequence is then: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

The Fibonacci sequence is closely related to the [[https://en.wikipedia.org/wiki/Golden_ratio|golden ratio (φ)]] in various ways. One relationship is that the ratio of consecutive Fibonacci numbers gets closer and closer to (i.e., //converges to//) φ as //n// increases. That is,

$$
\begin{aligned}
φ &\approx \frac{F_{n+1}}{F_{n}} & \text{more precise as n increases}\\
  &= \lim_{n\to\infty}\frac{F_{n+1}}{F_n} & \text{formally via limit notation}
\end{aligned}
$$

The golden ratio is an **irrational number** and therefore can't be expressed as the ratio of two integers. However, it can be expressed in the following forms and approximations:

$$
\begin{aligned}
φ &= \frac{1 + \sqrt{5}}{2} & \text{as a closed-form solution} \\
  &= \sqrt{1 + \sqrt{1 + \sqrt{1 + \cdots}}} & \text{as a nested radical} \\
  &\approx 1.618033988749895 & \text{as an approximate decimal value} \\
\end{aligned}
$$

===== Padovan and Perrin Numbers and the Plastic Number =====

<WRAP right>
{{padovan_triangles_320.png?nolink|Spiral of equilateral triangles with side lengths which follow the Padovan sequence.}}

{{perrin_triangles_320.png?nolink|Spiral of equilateral triangles with side lengths which follow the Perrin sequence.}}
</WRAP>

Two other sequences, very similar to the Fibonacci sequence, exhibit some similar characteristics. The  [[https://en.wikipedia.org/wiki/Padovan_sequence|Padovan sequence]] and the [[https://en.wikipedia.org/wiki/Perrin_number|Perrin sequence]] are identical except for their starting points:

$$
\begin{aligned}
Padovan_{0} &= 1 \\
Padovan_{1} &= 1 \\
Padovan_{2} &= 1 \\
Padovan_{n} &= Padovan_{n-2} + Padovan_{n-3} \text{ for n > 2}
\end{aligned}
$$

The beginning of the Padovan sequence is then: 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, ...

$$
\begin{aligned}
Perrin_{0} &= 3 \\
Perrin_{1} &= 0 \\
Perrin_{2} &= 2 \\
Perrin_{n} &= Perrin_{n-2} + Perrin_{n-3} \text{ for n > 2}
\end{aligned}
$$

The beginning of the Perrin sequence is then: 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, ...

These sequences are related to the [[https://en.wikipedia.org/wiki/Plastic_number|plastic number (ρ)]] much like the Fibonacci sequence is related to the golden ratio. One relationship is that the ratio of consecutive Padovan or Perrin numbers gets closer and closer to (i.e., //converges to//) ρ as //n// increases. That is,

$$
\begin{aligned}
ρ &\approx \frac{Padovan_{n+1}}{Padovan_{n}} & \text{more precise as n increases} \\
  &= \lim_{n\to\infty}\frac{Padovan_{n+1}}{Padovan_n} & \text{formally via limit notation} \\
  &\approx \frac{Perrin_{n+1}}{Perrin_{n}} & \text{more precise as n increases} \\
  &= \lim_{n\to\infty}\frac{Perrin_{n+1}}{Perrin_n} & \text{formally via limit notation}
\end{aligned}
$$

The plastic number is an **irrational number** and therefore can't be expressed as the ratio of two integers. However, it can be expressed in the following forms and approximations:

$$
\begin{aligned}
ρ &= \sqrt[3]{\frac{9+\sqrt{69}}{18}}+\sqrt[3]{\frac{9-\sqrt{69}}{18}} & \text{as a closed-form solution} \\
  &= \sqrt[3]{1 + \sqrt[3]{1 + \sqrt[3]{1 + \cdots}}} & \text{as a nested radical} \\
  &\approx 1.324717957244746 & \text{as an approximate decimal value} \\
\end{aligned}
$$

-----

<WRAP round todo>
====== Assignment ======

You shall implement the functions described in module ''recurrence.py'' [[#Starter Code|below]]. Pay close attention to the function docstrings as well as the [[https://docs.python.org/3/library/doctest.html|doctests]] within the docstrings that illustrate the expected behavior.

  * Use **exponentiation** to calculate square and cube roots. As of Python 3.11 there is a ''math.cbrt()'' function in addition to ''math.sqrt()'', but since we don't have 3.11 on the server just yet, stick with exponentiation: <code python>2**(1 / 2)  # square root of 2
2**(1 / 3)  # cube root of 2</code>
  * Take advantage of the embedded doctests to test your work. You can run them by telling the interpreter to use the ''doctest'' module as the main module and giving it ''recurrence.py'' to test: <code bash>python -m doctest recurrence.py     # output only failed tests
python -m doctest -v recurrence.py  # verbose output
</code>
</WRAP>

===== Starter Code =====

<file python recurrence.py>
"""
This module implements several functions in order to practice with generators.

Function docstrings also have extended info on parameters and return values, as well as doctests,
which are a way of embedding runnable tests in docstrings.
https://docs.python.org/3/library/doctest.html

python -m doctest recurrence.py     # output only failed tests
python -m doctest -v recurrence.py  # verbose output
"""

from typing import Generator, Callable


def fibonacci() -> Generator[str, None, None]:
  """
  Yields an infinite sequence of Fibonacci numbers.
  See: https://en.wikipedia.org/wiki/Fibonacci_number

  >>> [fib for (idx, fib) in zip(range(10), fibonacci())]
  [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
  """
  # We did this in class, so it's good to go:
  previous, current = 0, 1
  yield previous
  yield current
  while True:
    previous, current = current, previous + current
    yield current


def padovan() -> Generator[str, None, None]:
  """
  Yields an infinite sequence of Padovan numbers.
  See: https://en.wikipedia.org/wiki/Padovan_sequence

  >>> [pad for (idx, pad) in zip(range(10), padovan())]
  [1, 1, 1, 2, 2, 3, 4, 5, 7, 9]
  """
  pass  # TODO


def perrin() -> Generator[str, None, None]:
  """
  Yields an infinite sequence of Perrin numbers.
  See: https://en.wikipedia.org/wiki/Perrin_number

  >>> [per for (idx, per) in zip(range(10), perrin())]
  [3, 0, 2, 3, 2, 5, 5, 7, 10, 12]
  """
  pass  # TODO


def phi(terms: int) -> float:
  """
  Recursively calculates the golden ratio (often denoted as the Greek letter ϕ, i.e. "phi")
  via its nested radical representation.
  See: https://en.wikipedia.org/wiki/Golden_ratio

  :param terms: the number of formula terms to calculate, assumed to be positive
  :return: phi calculated to the requested number of terms

  >>> phi(1) == 1**(1 / 2)
  True
  >>> phi(2) == (1 + 1**(1 / 2))**(1 / 2)
  True
  >>> phi(3) == (1 + (1 + 1**(1 / 2))**(1 / 2))**(1 / 2)
  True
  >>> phi(4) == (1 + (1 + (1 + 1**(1 / 2))**(1 / 2))**(1 / 2))**(1 / 2)
  True
  """
  pass  # TODO


def rho(terms: int) -> float:
  """
  Calculates the plastic number (often denoted as the Greek letter ρ, i.e. "rho")
  via its nested radical representation.

  :param terms: the number of formula terms to calculate, assumed to be positive
  :return: rho calculated to the requested number of terms

  >>> rho(1) == 1**(1 / 3)
  True
  >>> rho(2) == (1 + 1**(1 / 3))**(1 / 3)
  True
  >>> rho(3) == (1 + (1 + 1**(1 / 3))**(1 / 3))**(1 / 3)
  True
  >>> rho(4) == (1 + (1 + (1 + 1**(1 / 3))**(1 / 3))**(1 / 3))**(1 / 3)
  True
  """
  pass  # TODO


def most_precise(function: Callable):
  """
  Calls a function with successively larger positive integer arguments (starting from 1)
  until the function returns the same value twice in succession. Meant to work with
  functions like rho and phi in this module, e.g. most_precise(rho) will repeatedly call rho
  requesting more terms in the calculationuntil two successive calls return the same value.

  :param function: the function to call with successively larger arguments
  :return: the first repeated return value

  >>> most_precise_phi = most_precise(phi)
  >>> most_precise_phi == phi(32)  # nested-radical phi should hit peak precision at 32 terms
  True
  >>> most_precise_phi == (1 + 5**(1 / 2)) / 2  # closed-form solution should be equal
  True
  >>> # verify the relationship between Fibonacci sequence and phi (30 terms, within a billionth)
  >>> fib_30 = [fib for (idx, fib) in zip(range(30), fibonacci())]
  >>> abs(fib_30[-1] / fib_30[-2] - most_precise_phi) < 1e-9
  True
  >>>
  >>> most_precise_rho = most_precise(rho)
  >>> most_precise_rho == rho(24)  # nested-radical rho should hit peak precision at 24 terms
  True
  >>> most_precise_rho == ((9 - 69**(1 / 2)) / 18)**(1 / 3) + (
  ...       (9 + 69**(1 / 2)) / 18)**(1 / 3)  # closed-form solution should be equal
  True
  >>> # verify the relationship between the Padovan/Perrin sequences and rho
  >>> padovan_60 = [pad for (idx, pad) in zip(range(60), padovan())]
  >>> abs(padovan_60[-1] / padovan_60[-2] - most_precise_rho) < 1e-9
  True
  >>> perrin_60 = [per for (idx, per) in zip(range(60), perrin())]
  >>> abs(perrin_60[-1] / perrin_60[-2] - most_precise_rho) < 1e-9
  True
  """
  pass  # TODO
</file>

-----

====== Submission ======

Submit ''recurrence.py'' via [[info:turnin]].

<WRAP round box>
{{https://jeff.cis.cabrillo.edu/images/feedback-robot.png?nolink }} //**Feedback Robot**//

This project has a feedback robot that will run some tests on your submission and provide you with a feedback report via email within roughly one minute.

<wrap em>Please read the feedback carefully.</wrap>
</WRAP>

====== Due Date and Point Value ======

<WRAP round important>
Due at 23:59:59 on the date listed on the [[:syllabus|syllabus]].

''Assignment 12'' is worth 60 points.

<code>
Possible point values per category:
---------------------------------------
phi()                                12
rho()                                12
padovan()                            12
perrin()                             12
most_precise()                       12
Possible deductions:
  Style and practices            10–20%
---------------------------------------
</code>
</WRAP>