04. Abstraction, Decomposition, and Functions#
Last time#
Exhaustive enumeration
Approximation
The concept of computational complexity
A small function object:
lambdaBisection search
Digression: Floating-point numbers
Newton-Raphson method
Today#
Organization and hiding details#
What we have learned so far…
It will be difficult to maintain or debug once your program becomes bigger and bigger.
We need to learn how to divide problem into sub-problems and hide those unnecessary details for solving each small issues.
The truth is…
Most of the users doesn’t care how it works but the result.
The only thing they do care is how to use it.
Organizing your code#
Divide the problem into sub-problems and solve them separately.
Maintaining small pieces of code is easier.
Reuse them in the rest of parts of the code or in the future.
Keep your code organized, keep your code clean, and keep your code coherent.
Today, we are going to achieve this by creating
function.A few weeks later, we are going to achieve this by using
class.
Create your own functions#
Functions#
It’s a piece of reusable code, which will not be executed until they are called.
Has a name
Has some input parameters (0 or more)
Has a docstring/specification (optional)
Has a body
Returns something (optional)
You can assign the result of a function to an arbitrary variable.
Syntax example#
def hello(params1, params2, default_params1=None, default_params2=1.):
"""
Docstring/specification
"""
# function body
# function body
# function body
return None
# Example of bisection search function
def sqrtBi(target, epsilon=1e-4):
"""
Assume the input is a positive number
Return the approximate square root via bisection search
- - -
Params:
target: float, target number
epsilon: float, minimum acceptable difference
Returns:
g: float, the square root of input number
"""
# Set searching region
lower_bnd = 0.0
upper_bnd = max(1., target)
# Start with a guess
g = (upper_bnd + lower_bnd)/2
numGuesses = 0
# bisection search
while abs(g**2 - target) >= epsilon:
# print("Current search region: [{:.4f}, {:.4f}]".format(lower_bnd, upper_bnd))
numGuesses += 1
if g**2 < target:
lower_bnd = g
else:
upper_bnd = g
# define a new searching region
g = (upper_bnd + lower_bnd)/2
# return the answer
print("# of guesses = {}".format(numGuesses))
return g
ans = sqrtBi(2)
print("The square root of 2 =", ans)
# of guesses = 13
The square root of 2 = 1.4141845703125
# Change the default parameters
ans = sqrtBi(2, epsilon=1e0)
print("The square root of 2 =", ans)
# Change the default parameters
ans = sqrtBi(2, epsilon=1e-6)
print("The square root of 2 =", ans)
# of guesses = 1
The square root of 2 = 1.5
# of guesses = 21
The square root of 2 = 1.4142136573791504
# Call docstring
help(sqrtBi)
print("="*50)
# Module __main__ ???
help(abs)
Help on function sqrtBi in module __main__:
sqrtBi(target, epsilon=0.0001)
Assume the input is a positive number
Return the approximate square root via bisection search
- - -
Params:
target: float, target number
epsilon: float, minimum acceptable difference
Returns:
g: float, the square root of input number
==================================================
Help on built-in function abs in module builtins:
abs(x, /)
Return the absolute value of the argument.
Exercise 4.1#
Please write a function called
fact, which will calculate the result of \(n!\).
def fact(n):
"""
Params:
n: int, n >= 0
Returns:
n_factorial: int
"""
# 自己想
return n_factorial
Test your function with different inputs \(n\), for example,
fact(87).
Understand the concept of scope#
Each function has its own scope, i.e., its own name space.
def sqrtNR(target, epsilon=1e-4):
"""
Assume the input is a positive number
Return the approximate square root via Newton-Raphson method
- - -
Params:
target: float, target number
epsilon: float, minimum acceptable difference
Returns:
ans: float
"""
ans = target/2
numGuesses = 0
# NR method
while abs(ans**2 - target) >= epsilon:
numGuesses += 1
ans = ans - (ans**2 - target) / (2*ans)
# return the answer
print("# of guesses: {}".format(numGuesses))
return ans
target = 87
print("{:f} is close enought to the square root of {}.".format(sqrtNR(target), target))
# of guesses: 6
9.327379 is close enought to the square root of 87.
# A simple example
def f(x):
y = 1
x = x + y
print("x =", x)
return x
x = 3
y = 2
z = f(x)
print("x, y, z = {}, {}, {}".format(x, y, z))
print("f:", f)
x = 4
x, y, z = 3, 2, 4
f: <function f at 0x00000285B2C82340>
What happend?#
After invoking
fby \(𝑧=𝑓(𝑥)\), the scope offwill disappear.
Exercise 4.2#
What will you observe after you running this?
def f(x):
def g():
x = "abc"
print("x =", x)
def h():
z = x
print("z =", z)
x += 1
print("x =", x)
h()
g()
print("x =", x)
return g
x = 3
z = f(x)
print("x =", x)
print("z =", z)
z()
x = 4
z = 4
x = abc
x = 4
x = 3
z = <function f.<locals>.g at 0x00000285B2CB3F60>
x = abc
Details in exercise 2#
Exercise 4.3#
For a given positive number \(x\) and a given positive integer \(n\), please write a function that returns you a real number \(y\) such that \(y^n = x\). If there does not exist such number \(y\), your function should also return the corresponding message.
You can also add a parameter that allows user to choose either bisection search or Newton-Raphson method.
Here is your sample code:
def findRoot(x, n, epsilon=1e-4, method='NR method'):
"""
Using Newton-Raphson method or bisection search method to find root, do not directly calculate it with ** operator.
Params:
x: float, x > 0, input number
n: int, n > 0, exponential power of x
epsilon: float, 1e-4, minimum acceptable difference
method: string, using Newton-Raphson method(NR method) or bisection search method(BS method)
Returns:
answer: float or string, if no such answer, return 'NA' instead
"""
# 自己想
return answer