exercise: prove that lg(1) equals 0
exercise: prove log(xy) equals log(x) plus log(y)
WC runtime? unknown whether loop terminates
runtime for n a power of 2?
case A: usual assumption?
n fits in one memory location, so each arithmetic op'n takes Theta(1) time
ignore printing
Theta(log n) loop iterations, each iteration takes Theta(1) time, so total runtime Theta(log n)
case B: assume n could be arbitrarily large
each arithmetic op'n takes Theta(log n) time, since n occupies Theta(log n) memory locations
so total runtime Theta(log n) * Theta(log n) = Theta( (log n)*(log n))
correctness?
after some number of steps assume we have this
q say with q*q = n_0
-----
\/ n_0
on the next step we want this
q d (10q + d) * (10q + d) = 100 * n_0 + n_1
-------
\/ n_0 n_1
*** to make things simple, assume r is 0.
-------
m r n_1 we want d*(m+d) = n_1 ... what is m?
(10q + d)^2 = 100q^2 + 20qd + d^2
= 100n_0 + d * (20q + d)
so thats why the multiplier m is 20q+ d
correctness? see also ‘‘why does this work’’ in the following
____________
\/ 13 14 06 25 = ?
***** step 1: largest x such that x*x <= 13 ?
x
____________
\/ 13 14 06 25
x ??
x = 1 ok
x = 2 ok
x = 3 ok
x = 4 TOO BIG
3
____________
\/ 13 14 06 25
3 - 9
-----------
4 14
***** step 2: largest y s.t. (2*10*3 + y)*y <= 414 ?
3 y
____________
\/ 13 14 06 25
3 9
-----------
4 14
6y ? ??
y = 1 ok
...
y = 6 ok
y = 7 too big
3 6
____________
\/ 13 14 06 25
3 - 9
-----------
4 14
66 - 3 96
-----------
18 06
***** step 3: largest z s.t. z*(2*10*36+z) <= 1806 ?
3 6 z
____________
\/ 13 14 06 25
3 -9
-----------
4 14
66 -3 96
-----------
18 06
72z ?? ??
z = 1? ok
z = 2? ok
z = 3? TOO BIG
3 6 2
____________
\/ 13 14 06 25
3 - 9
-----------
4 14
66 - 3 96
-----------
18 06
722 - 14 44
-----------
3 62 25
***** step 4: largest w s.t. w*(2*10*362+w) <= 3 62 25 ?
3 6 2 w
____________
\/ 13 14 06 25
3 -9
-----------
4 14
66 - 3 96
-----------
18 06
722 - 14 44
-----------
3 62 25
724w ? ?? ??
w = 1 ok
...
w = 5 ok
w = 6 TOO BIG
3 6 2 5
____________
\/ 13 14 06 25
3 -9
-----------
4 14
66 - 3 96
-----------
18 06
722 - 14 44
-----------
3 62 25
7245 -3 62 25
-----------
0
____________
\/ 13 14 06 25 = 3 6 2 5
how many steps?
number of steps is number of decimal digits / 2, so ceiling(log-base-10 n)/2
so Theta(log n) steps
how much time per step?
first step: worst case, try x = 1, x = 2, x = 3, x = 4, ... x = 9 so at most 9 multiplications
multiplying a k-digit number times a single digit takes time Theta(k)
step 1, at most 9 multiplications 1-digit number times 1-digit number
step 2, at most 9 mults, 2-digit number times 1-digit number
step j, at most 9 mults, j-digit number times 1-digit number
so total runtime, sum(j runs from 1 to (log-base-10 n)/2) Theta(j)
log-base-10 n in Theta(log n), so (log-base-10 n)/2 in Theta(log n), so total runtime in Theta( (log n)*(log n) )
def fib(n):
if (n<=1):
return n
return fib(n-1) + fib(n-2)
first, we need a definition of n'th fibonacci number f(n)
argue by induction
base cases
fib(n) returns f(n) for n = 0,1 (why?)
inductive case
fix n to be some integer t >= 2
assume fib(n) returns f(n) for all n in {0, 1, ..., t-1}
want to show fib(t) returns f(t)
exercise: finish this proof
n fib(n) s current/prev 30 832040 0.503 1.615 31 1346269 0.815 1.619 32 2178309 1.328 1.628 33 3524578 2.164 1.629 34 5702887 3.517 1.625
within one call, contant number of arith ops, 2 recursive calls
total number T(n) of calls?
T(0) = T(1) = 1
for n >= 2, T(n) = 1 + T(n-1) + T(n-2)
similar to fibonacci
can we estimate asymptotic growth of fibonacci?
so f(n) in Theta( gn ) where g = 1.618... is golden ratio
turns out T(n) also in Theta( gn )
matrix equation
| f(n) | | 1 1 | | f(n-1) |
| | = | | | |
| f(n-1) | | 1 0 | | f(n-2) |
expand equation n-2 times
n-1
| f(n) | | 1 1 | | f(n-1) |
| | = | | | |
| f(n-1) | | 1 0 | | f(n-2) |
solve this equation by diagonalizing the matrix,
the two terms of the Binet equation are the two eigenvalues
def ifib(n):
a,b = 0,1
for _ in range(n):
a, b = b, a+b
return a
loop invariant: after j loop iterations, a = f(j), b = f(j+1)
exercise: prove by induction
n s current/prev 65536 0.096 3.641 131072 0.320 3.333 262144 1.205 3.756 524288 4.645 3.853 1048576 18.215 3.920
when n doubles, expect runtime to increase by factor of 4
def mfib(n): # top-down memoization
if n<2:
return n
L = [-1] * (n+1) # not yet computed? set to -1
L[0], L[1] = 0, 1 # initialize two base values
return rmf(n, L, n+1) # helper function
def rmf(n, M, b): # memoization helper function
# assert(n < b)
if M[n] < 0:
fibn = rmf(n-1, M, b) + rmf(n-2, M, b)
M[n] = fibn
return M[n]
exercise
n s current/prev 128 0.000151 2.174 256 0.000290 1.91522762953 512 0.000679 2.33442622951
much faster than recursive fibonacci (duh !) but still recursive, so not useful for computing fib(n) for large n, e.g. my python exceeds stack limit with fib(1024)